From 20552d0e08865d69047f9c794f9ff763434e06b3 Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Sat, 2 May 2015 06:09:52 +0200 Subject: [PATCH] Optimize DataTreeCandidate.applyToModification() Both implementations use recursive calls to themselves. Instead of recursion, we can use a simplistic single-linked stack of operations and iterate over them. While this results in object allocation, these objects are short-lived and never leak from current thread, which means they are easily collected. Since the call is not recursive, JIT should be able to more easily inline and optimize the operations. Change-Id: I7d82a58c6be3e853ea5bcf9069876370804cb199 Signed-off-by: Robert Varga --- .../schema/tree/DataTreeCandidateNodes.java | 65 +++++++++++++++ .../api/schema/tree/DataTreeCandidates.java | 79 ++++++++++++------- 2 files changed, 117 insertions(+), 27 deletions(-) diff --git a/yang/yang-data-api/src/main/java/org/opendaylight/yangtools/yang/data/api/schema/tree/DataTreeCandidateNodes.java b/yang/yang-data-api/src/main/java/org/opendaylight/yangtools/yang/data/api/schema/tree/DataTreeCandidateNodes.java index 44f24c2a70..e1636ae77e 100644 --- a/yang/yang-data-api/src/main/java/org/opendaylight/yangtools/yang/data/api/schema/tree/DataTreeCandidateNodes.java +++ b/yang/yang-data-api/src/main/java/org/opendaylight/yangtools/yang/data/api/schema/tree/DataTreeCandidateNodes.java @@ -8,6 +8,9 @@ package org.opendaylight.yangtools.yang.data.api.schema.tree; import com.google.common.annotations.Beta; +import com.google.common.base.Preconditions; +import java.util.Collection; +import java.util.Iterator; import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode; @Beta @@ -19,4 +22,66 @@ public final class DataTreeCandidateNodes { public static DataTreeCandidateNode fromNormalizedNode(final NormalizedNode node) { return new NormalizedNodeDataTreeCandidateNode(node); } + + public static void applyToCursor(final DataTreeModificationCursor cursor, final DataTreeCandidateNode node) { + switch (node.getModificationType()) { + case DELETE: + cursor.delete(node.getIdentifier()); + break; + case SUBTREE_MODIFIED: + cursor.enter(node.getIdentifier()); + NodeIterator iterator = new NodeIterator(null, node.getChildNodes().iterator()); + do { + iterator = iterator.next(cursor); + } while (iterator != null); + break; + case UNMODIFIED: + // No-op + break; + case WRITE: + cursor.write(node.getIdentifier(), node.getDataAfter().get()); + break; + default: + throw new IllegalArgumentException("Unsupported modification " + node.getModificationType()); + } + } + + private static final class NodeIterator { + private final Iterator iterator; + private final NodeIterator parent; + + NodeIterator(final NodeIterator parent, final Iterator iterator) { + this.parent = Preconditions.checkNotNull(parent); + this.iterator = Preconditions.checkNotNull(iterator); + } + + NodeIterator next(final DataTreeModificationCursor cursor) { + while (iterator.hasNext()) { + final DataTreeCandidateNode node = iterator.next(); + switch (node.getModificationType()) { + case DELETE: + cursor.delete(node.getIdentifier()); + break; + case SUBTREE_MODIFIED: + final Collection children = node.getChildNodes(); + if (!children.isEmpty()) { + cursor.enter(node.getIdentifier()); + return new NodeIterator(this, children.iterator()); + } + break; + case UNMODIFIED: + // No-op + break; + case WRITE: + cursor.write(node.getIdentifier(), node.getDataAfter().get()); + break; + default: + throw new IllegalArgumentException("Unsupported modification " + node.getModificationType()); + } + } + + cursor.exit(); + return parent; + } + } } diff --git a/yang/yang-data-api/src/main/java/org/opendaylight/yangtools/yang/data/api/schema/tree/DataTreeCandidates.java b/yang/yang-data-api/src/main/java/org/opendaylight/yangtools/yang/data/api/schema/tree/DataTreeCandidates.java index 99256397b0..1b242918dd 100644 --- a/yang/yang-data-api/src/main/java/org/opendaylight/yangtools/yang/data/api/schema/tree/DataTreeCandidates.java +++ b/yang/yang-data-api/src/main/java/org/opendaylight/yangtools/yang/data/api/schema/tree/DataTreeCandidates.java @@ -8,6 +8,8 @@ package org.opendaylight.yangtools.yang.data.api.schema.tree; import com.google.common.annotations.Beta; +import com.google.common.base.Preconditions; +import java.util.Iterator; import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier; import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode; import org.slf4j.Logger; @@ -31,17 +33,20 @@ public final class DataTreeCandidates { return new DefaultDataTreeCandidate(rootPath, new NormalizedNodeDataTreeCandidateNode(node)); } + public static void applyToCursor(final DataTreeModificationCursor cursor, final DataTreeCandidate candidate) { + DataTreeCandidateNodes.applyToCursor(cursor, candidate.getRootNode()); + } + public static void applyToModification(final DataTreeModification modification, final DataTreeCandidate candidate) { if (modification instanceof CursorAwareDataTreeModification) { try (DataTreeModificationCursor cursor = ((CursorAwareDataTreeModification) modification).createCursor(candidate.getRootPath())) { - applyNode(cursor, candidate.getRootNode()); + applyToCursor(cursor, candidate); } - } else { - applyNode(modification, candidate.getRootPath(), candidate.getRootNode()); + return; } - } - private static void applyNode(final DataTreeModification modification, final YangInstanceIdentifier path, final DataTreeCandidateNode node) { + final DataTreeCandidateNode node = candidate.getRootNode(); + final YangInstanceIdentifier path = candidate.getRootPath(); switch (node.getModificationType()) { case DELETE: modification.delete(path); @@ -49,9 +54,11 @@ public final class DataTreeCandidates { break; case SUBTREE_MODIFIED: LOG.debug("Modification {} modified path {}", modification, path); - for (DataTreeCandidateNode child : node.getChildNodes()) { - applyNode(modification, path.node(child.getIdentifier()), child); - } + + NodeIterator iterator = new NodeIterator(null, path, node.getChildNodes().iterator()); + do { + iterator = iterator.next(modification); + } while (iterator != null); break; case UNMODIFIED: LOG.debug("Modification {} unmodified path {}", modification, path); @@ -66,26 +73,44 @@ public final class DataTreeCandidates { } } - private static void applyNode(final DataTreeModificationCursor cursor, final DataTreeCandidateNode node) { - switch (node.getModificationType()) { - case DELETE: - cursor.delete(node.getIdentifier()); - break; - case SUBTREE_MODIFIED: - cursor.enter(node.getIdentifier()); - for (DataTreeCandidateNode child : node.getChildNodes()) { - applyNode(cursor, child); + private static final class NodeIterator { + private final Iterator iterator; + private final YangInstanceIdentifier path; + private final NodeIterator parent; + + public NodeIterator(final NodeIterator parent, final YangInstanceIdentifier path, final Iterator iterator) { + this.iterator = Preconditions.checkNotNull(iterator); + this.parent = Preconditions.checkNotNull(parent); + this.path = Preconditions.checkNotNull(path); + } + + NodeIterator next(final DataTreeModification modification) { + while (iterator.hasNext()) { + final DataTreeCandidateNode node = iterator.next(); + final YangInstanceIdentifier child = path.node(node.getIdentifier()); + + switch (node.getModificationType()) { + case DELETE: + modification.delete(child); + LOG.debug("Modification {} deleted path {}", modification, child); + break; + case SUBTREE_MODIFIED: + LOG.debug("Modification {} modified path {}", modification, child); + return new NodeIterator(this, child, node.getChildNodes().iterator()); + case UNMODIFIED: + LOG.debug("Modification {} unmodified path {}", modification, child); + // No-op + break; + case WRITE: + modification.write(child, node.getDataAfter().get()); + LOG.debug("Modification {} written path {}", modification, child); + break; + default: + throw new IllegalArgumentException("Unsupported modification " + node.getModificationType()); + } } - cursor.exit(); - break; - case UNMODIFIED: - // No-op - break; - case WRITE: - cursor.write(node.getIdentifier(), node.getDataAfter().get()); - break; - default: - throw new IllegalArgumentException("Unsupported modification " + node.getModificationType()); + + return parent; } } } -- 2.36.6