Repository: tinkerpop Updated Branches: refs/heads/tp32 3b57bd440 -> 909627428
removed call stack recursion in ImmutablePath. All is while(true) based with a break on 'tail path.' ImmutablePath.TailPath is no longer required as the 'tail' is a the path segmanet with currentObject == null. Some preliminary tests show a significant speed up. Benchmark to follow suit. Added more test cases to PathTest. Removed TailPath Class.forName() in GryoRegistrator as it is no longer an existing class. Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/04fe38a2 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/04fe38a2 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/04fe38a2 Branch: refs/heads/tp32 Commit: 04fe38a28d3dce2a910c40c49658c083785b6473 Parents: 1eac35b Author: Marko A. Rodriguez <okramma...@gmail.com> Authored: Tue Nov 1 06:39:45 2016 -0600 Committer: Marko A. Rodriguez <okramma...@gmail.com> Committed: Tue Nov 1 06:39:45 2016 -0600 ---------------------------------------------------------------------- CHANGELOG.asciidoc | 2 + .../traversal/step/util/ImmutablePath.java | 262 +++++++------------ .../traversal/step/util/ImmutablePathImpl.java | 2 + .../gremlin/process/traversal/PathTest.java | 18 ++ .../structure/io/gryo/GryoRegistrator.java | 5 - 5 files changed, 118 insertions(+), 171 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/04fe38a2/CHANGELOG.asciidoc ---------------------------------------------------------------------- diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc index cf8c007..1659619 100644 --- a/CHANGELOG.asciidoc +++ b/CHANGELOG.asciidoc @@ -26,6 +26,8 @@ image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima TinkerPop 3.2.4 (Release Date: NOT OFFICIALLY RELEASED YET) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +* Removed `ImmutablePath.TailPath` as it is no longer required with new recursion model. +* Removed call stack recursion in `ImmutablePath`. * `SparkGraphComputer` no longer starts a worker iteration if the worker's partition is empty. * Added `ProjectStep.getProjectKeys()` for strategies that rely on such information. * Added `VertexFeatures.supportsDuplicateMultiProperties()` for graphs that only support unique values in multi-properties. http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/04fe38a2/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 729b4f3..d64cdb4 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 @@ -31,18 +31,16 @@ import java.util.Set; /** * @author Marko A. Rodriguez (http://markorodriguez.com) */ -public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Cloneable { +public class ImmutablePath implements Path, Serializable, Cloneable { - private ImmutablePathImpl previousPath = TailPath.instance(); + private static final ImmutablePath TAIL_PATH = new ImmutablePath(null, null, Collections.emptySet()); + + private ImmutablePath previousPath; private Object currentObject; private Set<String> currentLabels = new LinkedHashSet<>(); - protected ImmutablePath() { - - } - public static Path make() { - return TailPath.instance(); + return TAIL_PATH; } @SuppressWarnings("CloneDoesntCallSuperClone,CloneDoesntDeclareCloneNotSupportedException") @@ -51,15 +49,25 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo return this; } - private ImmutablePath(final ImmutablePathImpl previousPath, final Object currentObject, final Set<String> currentLabels) { + private ImmutablePath(final ImmutablePath previousPath, final Object currentObject, final Set<String> currentLabels) { this.previousPath = previousPath; this.currentObject = currentObject; this.currentLabels.addAll(currentLabels); } + private final boolean isTail() { + return null == this.currentObject; + } + @Override public int size() { - return this.previousPath.size() + 1; + int counter = 0; + ImmutablePath currentPath = this; + while (true) { + if (currentPath.isTail()) return counter; + counter++; + currentPath = currentPath.previousPath; + } } @Override @@ -69,10 +77,10 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo @Override public Path extend(final Set<String> labels) { - final Set<String> temp = new LinkedHashSet<>(); - temp.addAll(this.currentLabels); - temp.addAll(labels); - return new ImmutablePath(this.previousPath, this.currentObject, temp); + final Set<String> newLabels = new LinkedHashSet<>(); + newLabels.addAll(this.currentLabels); + newLabels.addAll(labels); + return new ImmutablePath(this.previousPath, this.currentObject, newLabels); } @Override @@ -82,16 +90,15 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo // get all the immutable path sections final List<ImmutablePath> immutablePaths = new ArrayList<>(); - ImmutablePath currentPathSection = this; + ImmutablePath currentPath = this; while (true) { - immutablePaths.add(0, currentPathSection); - if (currentPathSection.previousPath instanceof TailPath) + if (currentPath.isTail()) break; - else - currentPathSection = (ImmutablePath) currentPathSection.previousPath; + immutablePaths.add(0, currentPath); + currentPath = currentPath.previousPath; } // build a new immutable path using the respective path sections that are not to be retracted - Path newPath = TailPath.instance(); + Path newPath = TAIL_PATH; for (final ImmutablePath immutablePath : immutablePaths) { final Set<String> temp = new LinkedHashSet<>(immutablePath.currentLabels); temp.removeAll(labels); @@ -106,40 +113,37 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo return (this.size() - 1) == index ? (A) this.currentObject : this.previousPath.get(index); } - @Override - public <A> A getSingleHead(final String label) { - // Recursively search for the single value to avoid building throwaway collections, and to stop looking when we - // find it. - A single; - // See if we have a value. - if (this.currentLabels.contains(label)) { - single = (A) this.currentObject; - } else { - // Look for a previous value. - single = this.previousPath.getSingleHead(label); + + private final <A> A getSingleHead(final String label) { + ImmutablePath currentPath = this; + while (true) { + if (currentPath.isTail()) + return null; + else if (currentPath.currentLabels.contains(label)) + return (A) currentPath.currentObject; + else + currentPath = currentPath.previousPath; } - return single; } - @Override - public <A> A getSingleTail(final String label) { - // Recursively search for the single value to avoid building throwaway collections, and to stop looking when we - // find it. - A single = this.previousPath.getSingleTail(label); - if (null == single) { - // See if we have a value. - if (this.currentLabels.contains(label)) { - single = (A) this.currentObject; - } + + private final <A> A getSingleTail(final String label) { + A found = null; + ImmutablePath currentPath = this; + while (true) { + if (currentPath.isTail()) + return found; + else if (currentPath.currentLabels.contains(label)) + found = (A) currentPath.currentObject; + currentPath = currentPath.previousPath; } - return single; } @Override public <A> A get(final Pop pop, final String label) { if (Pop.all == pop) { // Recursively build the list to avoid building objects/labels collections. - final List<A> list = this.previousPath.get(Pop.all, label); + final List<A> list = null == this.previousPath ? new ArrayList<>() : this.previousPath.get(Pop.all, label); // Add our object, if our step labels match. if (this.currentLabels.contains(label)) list.add((A) currentObject); @@ -156,27 +160,26 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo @Override public boolean hasLabel(final String label) { - ImmutablePath currentPathSection = this; + ImmutablePath currentPath = this; while (true) { - if (currentPathSection.currentLabels.contains(label)) - return true; - if (currentPathSection.previousPath instanceof TailPath) + if (currentPath.isTail()) return false; + else if (currentPath.currentLabels.contains(label)) + return true; else - currentPathSection = (ImmutablePath) currentPathSection.previousPath; + currentPath = currentPath.previousPath; } } @Override public List<Object> objects() { final List<Object> objects = new ArrayList<>(); - ImmutablePath currentPathSection = this; + ImmutablePath currentPath = this; while (true) { - objects.add(0, currentPathSection.currentObject); - if (currentPathSection.previousPath instanceof TailPath) + if (currentPath.isTail()) break; - else - currentPathSection = (ImmutablePath) currentPathSection.previousPath; + objects.add(0, currentPath.currentObject); + currentPath = currentPath.previousPath; } return Collections.unmodifiableList(objects); } @@ -184,13 +187,12 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo @Override public List<Set<String>> labels() { final List<Set<String>> labels = new ArrayList<>(); - ImmutablePath currentPathSection = this; + ImmutablePath currentPath = this; while (true) { - labels.add(0, currentPathSection.currentLabels); - if (currentPathSection.previousPath instanceof TailPath) + if (currentPath.isTail()) break; - else - currentPathSection = (ImmutablePath) currentPathSection.previousPath; + labels.add(0, currentPath.currentLabels); + currentPath = currentPath.previousPath; } return Collections.unmodifiableList(labels); } @@ -202,7 +204,22 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo @Override public int hashCode() { - return this.objects().hashCode(); + // hashCode algorithm from AbstractList + int[] hashCodes = new int[this.size()]; + int index = hashCodes.length - 1; + ImmutablePath currentPath = this; + while (true) { + if (currentPath.isTail()) + break; + hashCodes[index] = currentPath.currentObject.hashCode(); + currentPath = currentPath.previousPath; + index--; + } + int hashCode = 1; + for (final int hash : hashCodes) { + hashCode = hashCode * 31 + hash; + } + return hashCode; } @Override @@ -214,124 +231,37 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo if (otherPath.size() != size) return false; if (size > 0) { - ImmutablePath currentPathSection = this; + ImmutablePath currentPath = this; final List<Object> otherObjects = otherPath.objects(); final List<Set<String>> otherLabels = otherPath.labels(); for (int i = otherLabels.size() - 1; i >= 0; i--) { - if (!currentPathSection.currentObject.equals(otherObjects.get(i))) - return false; - if (!currentPathSection.currentLabels.equals(otherLabels.get(i))) + if (currentPath.isTail()) + return true; + else if (!currentPath.currentObject.equals(otherObjects.get(i)) || + !currentPath.currentLabels.equals(otherLabels.get(i))) return false; - if (currentPathSection.previousPath instanceof TailPath) - break; else - currentPathSection = (ImmutablePath) currentPathSection.previousPath; + currentPath = currentPath.previousPath; } } return true; } - - private static class TailPath implements Path, ImmutablePathImpl, Serializable { - private static final TailPath INSTANCE = new TailPath(); - - private TailPath() { - - } - - @Override - public int size() { - return 0; - } - - @Override - public Path extend(final Object object, final Set<String> labels) { - return new ImmutablePath(TailPath.instance(), object, labels); - } - - @Override - public Path extend(final Set<String> labels) { - if (labels.isEmpty()) - return this; - throw new UnsupportedOperationException("A head path can not have labels added to it"); - } - - @Override - public Path retract(final Set<String> labels) { - return this; - } - - @Override - public <A> A get(final String label) { - throw Path.Exceptions.stepWithProvidedLabelDoesNotExist(label); - } - - @Override - public <A> A get(final int index) { - return (A) Collections.emptyList().get(index); - } - - - @Override - public <A> A get(final Pop pop, final String label) { - return pop == Pop.all ? (A) new ArrayList<>() : null; - } - - @Override - public <A> A getSingleHead(final String label) { - // Provide a null to bounce the search back to ImmutablePath.getSingleHead. - return null; - } - - @Override - public <A> A getSingleTail(final String label) { - // Provide a null to bounce the search back to ImmutablePath.getSingleTail. - return null; - } - - @Override - public boolean hasLabel(final String label) { + @Override + public boolean popEquals(final Pop pop, final Object other) { + if (!(other instanceof Path)) return false; + final Path otherPath = (Path) other; + ImmutablePath currentPath = this; + while (true) { + if (currentPath.isTail()) + break; + for (final String label : currentPath.currentLabels) { + if (!otherPath.hasLabel(label) || !this.get(pop, label).equals(otherPath.get(pop, label))) + return false; + } + currentPath = currentPath.previousPath; } - - @Override - public List<Object> objects() { - return Collections.emptyList(); - } - - @Override - public List<Set<String>> labels() { - return Collections.emptyList(); - } - - @Override - public boolean isSimple() { - return true; - } - - @SuppressWarnings("CloneDoesntCallSuperClone,CloneDoesntDeclareCloneNotSupportedException") - @Override - public TailPath clone() { - return this; - } - - public static TailPath instance() { - return INSTANCE; - } - - @Override - public String toString() { - return Collections.emptyList().toString(); - } - - @Override - public int hashCode() { - return Collections.emptyList().hashCode(); - } - - @Override - public boolean equals(final Object other) { - return other instanceof Path && ((Path) other).size() == 0; - } + return true; } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/04fe38a2/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePathImpl.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePathImpl.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePathImpl.java index 2bb84ba..16203c5 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePathImpl.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePathImpl.java @@ -27,7 +27,9 @@ import java.util.List; * Internal interface used by ImmutablePath to provide more efficient implementation. * * @author Matt Frantz (http://github.com/mhfrantz) + * @deprecated Since 3.2.3 ({@link ImmutablePath} contains all requisite behavior) */ +@Deprecated interface ImmutablePathImpl extends Path { /** http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/04fe38a2/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/PathTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/PathTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/PathTest.java index 1b37502..5087667 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/PathTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/PathTest.java @@ -340,6 +340,24 @@ public class PathTest { assertTrue(pathA1.popEquals(Pop.last, pathA2)); assertTrue(pathA2.popEquals(Pop.last, pathB1)); assertTrue(pathB1.popEquals(Pop.last, pathB2)); + + /// + pathA1 = pathA1.extend("stephen", Collections.singleton("c")); + pathA2 = pathA2.extend("stephen", Collections.singleton("d")); + pathB1 = pathB1.extend("marko", Collections.singleton("e")); + pathB2 = pathB2.extend("stephen", Collections.singleton("f")); + assertTrue(pathA1.popEquals(Pop.all, pathA1)); + assertFalse(pathA1.popEquals(Pop.all, pathA2)); + assertFalse(pathA2.popEquals(Pop.all, pathB1)); + assertFalse(pathB1.popEquals(Pop.all, pathB2)); + assertFalse(pathA1.popEquals(Pop.first, pathA2)); + assertFalse(pathA2.popEquals(Pop.first, pathB1)); + assertFalse(pathB1.popEquals(Pop.first, pathB2)); + assertTrue(pathB1.popEquals(Pop.first, pathB1)); + assertFalse(pathA1.popEquals(Pop.last, pathA2)); + assertFalse(pathA2.popEquals(Pop.last, pathB1)); + assertFalse(pathB1.popEquals(Pop.last, pathB2)); + assertTrue(pathB2.popEquals(Pop.last, pathB2)); }); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/04fe38a2/spark-gremlin/src/main/java/org/apache/tinkerpop/gremlin/spark/structure/io/gryo/GryoRegistrator.java ---------------------------------------------------------------------- diff --git a/spark-gremlin/src/main/java/org/apache/tinkerpop/gremlin/spark/structure/io/gryo/GryoRegistrator.java b/spark-gremlin/src/main/java/org/apache/tinkerpop/gremlin/spark/structure/io/gryo/GryoRegistrator.java index ffd731a..aff8f49 100644 --- a/spark-gremlin/src/main/java/org/apache/tinkerpop/gremlin/spark/structure/io/gryo/GryoRegistrator.java +++ b/spark-gremlin/src/main/java/org/apache/tinkerpop/gremlin/spark/structure/io/gryo/GryoRegistrator.java @@ -211,11 +211,6 @@ public class GryoRegistrator implements KryoRegistrator { // m.put(MutablePath.class, new UnshadedSerializerAdapter<>(new GryoSerializers.PathSerializer())); m.put(ImmutablePath.class, new UnshadedSerializerAdapter<>(new GryoSerializers.PathSerializer())); - try { - m.put(Class.forName(ImmutablePath.class.getCanonicalName() + "$TailPath"), new UnshadedSerializerAdapter<>(new GryoSerializers.PathSerializer())); - } catch (final ClassNotFoundException e) { - throw new IllegalStateException(e.getMessage(), e); - } // m.put(CompactBuffer[].class, null); // TODO: VoidSerializer is a default serializer and thus, may not be needed (if it is, you can't use FieldSerializer)
