You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by ok...@apache.org on 2016/07/13 04:20:20 UTC
[34/50] tinkerpop git commit: 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 NativeN
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 <ok...@gmail.com>
Authored: Mon Jul 11 13:09:31 2016 -0600
Committer: Marko A. Rodriguez <ok...@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"),