tinkerpop-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ok...@apache.org
Subject [1/8] tinkerpop git commit: 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 preliminar
Date Wed, 02 Nov 2016 20:58:18 GMT
Repository: tinkerpop
Updated Branches:
  refs/heads/master 91e82c4ef -> 1541e8435


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/master
Commit: 04fe38a28d3dce2a910c40c49658c083785b6473
Parents: 1eac35b
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Authored: Tue Nov 1 06:39:45 2016 -0600
Committer: Marko A. Rodriguez <okrammarko@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)


Mime
View raw message