Greatly simplified ImmutablePath and MutablePath.retract() algorithms. Got a 3x speedup on a big ol fat match() query I'm benchmarking with. Simplified LP_XXXX_Traverser implementations around retract(). Small fix to NativeNeo4jCypherCheck -- had an extra ( in an Ignored Test.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/a8bcd7dc Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/a8bcd7dc Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/a8bcd7dc Branch: refs/heads/TINKERPOP-1278 Commit: a8bcd7dc1262b2eea93472a4f8e04d5ffb84fc0a Parents: b900de2 Author: Marko A. Rodriguez <okramma...@gmail.com> Authored: Mon Jul 11 13:09:31 2016 -0600 Committer: Marko A. Rodriguez <okramma...@gmail.com> Committed: Mon Jul 11 13:09:31 2016 -0600 ---------------------------------------------------------------------- .../traversal/step/util/ImmutablePath.java | 132 +++---------------- .../traversal/step/util/MutablePath.java | 22 +--- .../traverser/B_LP_O_S_SE_SL_Traverser.java | 46 ++++--- .../traverser/LP_O_OB_P_S_SE_SL_Traverser.java | 22 ++-- .../neo4j/process/NativeNeo4jCypherCheck.java | 2 +- 5 files changed, 61 insertions(+), 163 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a8bcd7dc/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePath.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePath.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePath.java index b71c56e..fb3155f 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePath.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePath.java @@ -24,7 +24,6 @@ import org.apache.tinkerpop.gremlin.process.traversal.Pop; import java.io.Serializable; import java.util.ArrayList; import java.util.Collections; -import java.util.HashSet; import java.util.LinkedHashSet; import java.util.List; import java.util.Set; @@ -78,121 +77,28 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo @Override public Path retract(final Set<String> labels) { - if (labels == null || labels.isEmpty()) { + if (labels.isEmpty()) return this; - } - // first see if the labels in the set are even present in this path - boolean found = false; - for (final Set<String> labelSet : labels()) { - if (!Collections.disjoint(labelSet, labels)) { - found = true; + // get all the immutable path sections + final List<ImmutablePath> immutablePaths = new ArrayList<>(); + ImmutablePath currentPathSection = this; + while (true) { + immutablePaths.add(0, currentPathSection); + if (currentPathSection.previousPath instanceof TailPath) break; - } - } - - if (!found) { - return this; - } - - if (this.previousPath instanceof TailPath) { - ImmutablePath clone = cloneImmutablePath(this); - clone.currentLabels.removeAll(labels); - clone.previousPath = TailPath.instance(); - if (clone.currentLabels.isEmpty()) { - // return the previous tail path because this path segment can be dropped - return clone.previousPath; - } - return clone; + else + currentPathSection = (ImmutablePath) currentPathSection.previousPath; } - - ImmutablePath parent; - ImmutablePath child; - if (this.previousPath != null) { - parent = this; - child = (ImmutablePath)this.previousPath; - } else { - parent = (ImmutablePath)this.previousPath; - child = this; + // build a new immutable path using the respective path sections that are not to be retracted + Path newPath = TailPath.instance(); + for (final ImmutablePath immutablePath : immutablePaths) { + final Set<String> temp = new LinkedHashSet<>(immutablePath.currentLabels); + temp.removeAll(labels); + if (!temp.isEmpty()) + newPath = newPath.extend(immutablePath.currentObject, temp); } - - if (!Collections.disjoint(parent.currentLabels, labels)) { - ImmutablePath clonedParent = cloneImmutablePath(parent); - clonedParent.currentLabels.removeAll(labels); - if (clonedParent.currentLabels.isEmpty()) { - parent = (ImmutablePath) parent.previousPath; - } else { - parent = clonedParent; - } - } - - // store the head and return it at the end of this - ImmutablePath head = parent; - - // parents can be a mixture of ImmutablePaths and collapsed - // cloned ImmutablePaths that are a result of branching - List<Object> parents = new ArrayList<>(); - parents.add(parent); - - while(true) { - if (Collections.disjoint(child.currentLabels, labels)) { - parents.add(child); - if (child.previousPath instanceof TailPath) { - break; - } - child = (ImmutablePath)child.previousPath; - continue; - } - // split path - // clone child - ImmutablePath clone = cloneImmutablePath(child); - clone.currentLabels.removeAll(labels); - if (clone.currentLabels.isEmpty()) { - clone.currentObject = null; - } - - // walk back up and build parent clones or reuse - // other previously cloned paths - boolean headFound = false; - if (parents.size() > 0) { - boolean first = true; - // construct parents up to this point - ImmutablePath newPath = cloneImmutablePath((ImmutablePath)parents.get(0)); - // replace the previous - ImmutablePath prevPath = newPath; - ImmutablePath lastPath = prevPath; - if (!headFound) { - head = newPath; - } - for (int i = 1; i < parents.size(); i++) { - ImmutablePath clonedPrev = cloneImmutablePath((ImmutablePath) parents.get(i)); - prevPath.previousPath = clonedPrev; - lastPath = clonedPrev; - prevPath = clonedPrev; - } - - if (clone.currentLabels.isEmpty()) { - lastPath.previousPath = clone.previousPath; - } else { - lastPath.previousPath = clone; - } - - parents = new ArrayList<>(); - parents.add(lastPath); - - if (child.previousPath instanceof TailPath) { - break; - } - - child = (ImmutablePath)child.previousPath; - } - } - - return head; - } - - private static ImmutablePath cloneImmutablePath(final ImmutablePath path) { - return new ImmutablePath(path.previousPath, path.currentObject, new HashSet<>(path.currentLabels)); + return newPath; } @Override @@ -315,7 +221,9 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo @Override public Path extend(final Set<String> labels) { - if (labels.size() == 0) { return this; } + if (labels.size() == 0) { + return this; + } throw new UnsupportedOperationException("A head path can not have labels added to it"); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a8bcd7dc/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutablePath.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutablePath.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutablePath.java index fd86e2d..f97879f 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutablePath.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutablePath.java @@ -80,7 +80,7 @@ public class MutablePath implements Path, Serializable { @Override public Path extend(final Set<String> labels) { - if(labels.size() > 0) { + if (labels.size() > 0) { this.labels.get(this.labels.size() - 1).addAll(labels); } return this; @@ -89,22 +89,10 @@ public class MutablePath implements Path, Serializable { @Override public Path retract(final Set<String> removeLabels) { for (int i = this.labels.size() - 1; i >= 0; i--) { - for (final String label : removeLabels) { - synchronized (this.labels.get(i)) { - if (this.labels.get(i).contains(label)) { - this.labels.get(i).remove(label); - boolean empty = false; - if (this.labels.get(i).size() == 0) { - this.labels.remove(i); - this.objects.remove(i); - empty = true; - } - // label was found, so break out - if (empty) { - break; - } - } - } + this.labels.get(i).removeAll(removeLabels); + if (this.labels.get(i).isEmpty()) { + this.labels.remove(i); + this.objects.remove(i); } } return this; http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a8bcd7dc/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java index 793ead6..ce70c5c 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java @@ -23,11 +23,9 @@ import org.apache.tinkerpop.gremlin.process.traversal.Pop; import org.apache.tinkerpop.gremlin.process.traversal.Step; import org.apache.tinkerpop.gremlin.process.traversal.Traverser; import org.apache.tinkerpop.gremlin.process.traversal.step.util.ImmutablePath; -import org.apache.tinkerpop.gremlin.process.traversal.step.util.MutablePath; import org.apache.tinkerpop.gremlin.structure.util.reference.ReferenceFactory; import java.util.HashSet; -import java.util.List; import java.util.Set; /** @@ -89,6 +87,32 @@ public class B_LP_O_S_SE_SL_Traverser<T> extends B_O_S_SE_SL_Traverser<T> { @Override public void keepLabels(final Set<String> labels) { + final Set<String> retractLabels = new HashSet<>(); + for (final Set<String> stepLabels : this.path.labels()) { + for (final String l : stepLabels) { + if (!labels.contains(l)) + retractLabels.add(l); + } + } + this.path = this.path.retract(retractLabels); + } + + @Override + public void dropLabels(final Set<String> labels) { + if (!labels.isEmpty()) + this.path = path.retract(labels); + } + + @Override + public void dropPath() { + this.path = ImmutablePath.make(); + } + + + + + /*@Override + public void keepLabels(final Set<String> labels) { if (!labels.isEmpty()) { Set<String> retractLabels = new HashSet<>(); List<Set<String>> existingLabels = this.path.labels(); @@ -108,23 +132,7 @@ public class B_LP_O_S_SE_SL_Traverser<T> extends B_O_S_SE_SL_Traverser<T> { this.path = this.path.retract(retractLabels); } } - } - - @Override - public void dropLabels(final Set<String> labels) { - if(!labels.isEmpty()) { - this.path = this.path.retract(labels); - } - } - - @Override - public void dropPath() { - if(path instanceof ImmutablePath) { - this.path = ImmutablePath.make(); - } else { - this.path = MutablePath.make(); - } - } + }*/ @Override public int hashCode() { http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a8bcd7dc/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/LP_O_OB_P_S_SE_SL_Traverser.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/LP_O_OB_P_S_SE_SL_Traverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/LP_O_OB_P_S_SE_SL_Traverser.java index ee951c1..97b79a4 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/LP_O_OB_P_S_SE_SL_Traverser.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/LP_O_OB_P_S_SE_SL_Traverser.java @@ -26,7 +26,6 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.util.ImmutablePath; import org.apache.tinkerpop.gremlin.structure.util.reference.ReferenceFactory; import java.util.HashSet; -import java.util.List; import java.util.Set; /** @@ -84,25 +83,20 @@ public class LP_O_OB_P_S_SE_SL_Traverser<T> extends O_OB_S_SE_SL_Traverser<T> { @Override public void keepLabels(final Set<String> labels) { - if (labels != null) { - Set<String> retractLabels = new HashSet<>(); - List<Set<String>> existingLabels = this.path.labels(); - for (Set<String> labelSet : existingLabels) { - for (String l : labelSet) { - if (labels.isEmpty() || labels.contains(l) == false) { - retractLabels.add(l); - } - } + final Set<String> retractLabels = new HashSet<>(); + for (final Set<String> stepLabels : this.path.labels()) { + for (final String l : stepLabels) { + if (!labels.contains(l)) + retractLabels.add(l); } - this.path = this.path.retract(retractLabels); } + this.path = this.path.retract(retractLabels); } @Override public void dropLabels(final Set<String> labels) { - if(!labels.isEmpty()) { - this.path = path.retract(new HashSet(labels)); - } + if (!labels.isEmpty()) + this.path = path.retract(labels); } @Override http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/a8bcd7dc/neo4j-gremlin/src/test/java/org/apache/tinkerpop/gremlin/neo4j/process/NativeNeo4jCypherCheck.java ---------------------------------------------------------------------- diff --git a/neo4j-gremlin/src/test/java/org/apache/tinkerpop/gremlin/neo4j/process/NativeNeo4jCypherCheck.java b/neo4j-gremlin/src/test/java/org/apache/tinkerpop/gremlin/neo4j/process/NativeNeo4jCypherCheck.java index a758eea..c98e8f9 100644 --- a/neo4j-gremlin/src/test/java/org/apache/tinkerpop/gremlin/neo4j/process/NativeNeo4jCypherCheck.java +++ b/neo4j-gremlin/src/test/java/org/apache/tinkerpop/gremlin/neo4j/process/NativeNeo4jCypherCheck.java @@ -201,7 +201,7 @@ public class NativeNeo4jCypherCheck extends AbstractNeo4jGremlinTest { () -> g.V().match( as("a").out("followedBy").as("b"), as("b").out("followedBy").as("c")).select("a").by("name"), - () -> n.cypher("MATCH ((a)-[:followedBy]->(b), (b)-[:followedBy]->(c) RETURN a.name") + () -> n.cypher("MATCH (a)-[:followedBy]->(b), (b)-[:followedBy]->(c) RETURN a.name") /// /*() -> g.V().match( as("a").out("followedBy").as("b"),
