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:19 UTC
[33/50] tinkerpop git commit: using memoization in MatchEndStep so
referenced labels don't need to be computed over and over again. Simplified
PathUtil -- removed two methods that are now inlined.
using memoization in MatchEndStep so referenced labels don't need to be computed over and over again. Simplified PathUtil -- removed two methods that are now inlined.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/b900de27
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/b900de27
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/b900de27
Branch: refs/heads/TINKERPOP-1278
Commit: b900de27546d7a10263a34808301726cb3f48fca
Parents: 632a67d
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Mon Jul 11 12:11:41 2016 -0600
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Mon Jul 11 12:11:41 2016 -0600
----------------------------------------------------------------------
.../process/traversal/step/PathProcessor.java | 13 +---
.../process/traversal/step/map/MatchStep.java | 66 ++++++++++----------
.../optimization/PathRetractionStrategy.java | 4 +-
.../process/traversal/util/PathUtil.java | 27 +-------
.../neo4j/process/NativeNeo4jCypherCheck.java | 4 +-
5 files changed, 40 insertions(+), 74 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b900de27/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java
index 8ad5181..0c8ed47 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java
@@ -65,18 +65,7 @@ public interface PathProcessor {
public Set<String> getKeepLabels();
public static <S> Traverser.Admin<S> processTraverserPathLabels(final Traverser.Admin<S> traverser, final Set<String> labels) {
- if (null != labels)
- traverser.keepLabels(labels);
+ if (null != labels) traverser.keepLabels(labels);
return traverser;
}
-
- static void keepLabels(final Traverser traverser, final Set<String> labels) {
- if(labels == null) {
- return;
- } else {
- traverser.asAdmin().keepLabels(labels);
- }
- }
-
-
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b900de27/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java
index 998b7d3..e1f6d8f 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java
@@ -351,16 +351,15 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
}
}
final Traverser.Admin traverser;
- if (this.standardAlgorithmBarrier.isEmpty()) {
+ if (this.standardAlgorithmBarrier.isEmpty()) { // pull from previous step
traverser = this.starts.next();
if (!traverser.getTags().contains(this.getId())) {
traverser.getTags().add(this.getId()); // so the traverser never returns to this branch ever again
if (!this.hasPathLabel(traverser.path(), this.matchStartLabels))
traverser.addLabels(Collections.singleton(this.computedStartLabel)); // if the traverser doesn't have a legal start, then provide it the pre-computed one
}
- } else {
- traverser = this.standardAlgorithmBarrier.remove();
- }
+ } else
+ traverser = this.standardAlgorithmBarrier.remove(); // pull from internal lazy barrier
///
if (!this.isDuplicate(traverser)) {
if (hasMatched(this.connective, traverser))
@@ -424,18 +423,8 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
final Set<String> tags = traverser.getTags();
final List<Traversal.Admin<?, ?>> remainingTraversals = new ArrayList<>();
for (final Traversal.Admin<?, ?> matchTraversal : matchTraversals) {
- if (!tags.contains(matchTraversal.getStartStep().getId())) {
+ if (!tags.contains(matchTraversal.getStartStep().getId()))
remainingTraversals.add(matchTraversal);
- } /*else {
- // include the current traversal that the traverser is executing in the list of
- // remaining traversals
- for (final Step<?, ?> s : matchTraversal.getSteps()) {
- if (s.getId().equals(traverser.getStepId())) {
- remainingTraversals.add(matchTraversal);
- break;
- }
- }
- } */
}
return remainingTraversals;
}
@@ -461,7 +450,7 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
//////////////////////////////
- public static class MatchStartStep extends AbstractStep<Object, Object> implements Scoping {
+ public static final class MatchStartStep extends AbstractStep<Object, Object> implements Scoping {
private final String selectKey;
private Set<String> scopeKeys = null;
@@ -510,9 +499,12 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
}
}
- public static class MatchEndStep extends EndStep<Object> {
+ public static final class MatchEndStep extends EndStep<Object> {
private final String matchKey;
+ // memoization of referenced labels Map<startStepId, referencedLabels>
+ private final Map<String, Set<String>> referencedLabelsMap = new HashMap<>();
+ private MatchStep<?, ?> parent = null;
public MatchEndStep(final Traversal.Admin traversal, final String matchKey) {
super(traversal);
@@ -520,42 +512,48 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
}
- private void retractUnnecessaryLabels(final Traverser.Admin<Object> traverser) {
- MatchStep parent = ((MatchStep) this.getTraversal().getParent().asStep());
- if (null != parent.getKeepLabels()) {
- final Set<String> keepers = new HashSet<>();
- for (final Traversal.Admin<?, ?> traversal : (List<Traversal.Admin<?, ?>>) parent.getRemainingTraversals(traverser)) {
- keepers.addAll(PathUtil.getReferencedLabels(traversal));
+ private <S> Traverser.Admin<S> retractUnnecessaryLabels(final Traverser.Admin<S> traverser) {
+ if (null == this.parent.getKeepLabels())
+ return traverser;
+
+ final Set<String> keepers = new HashSet<>(this.parent.getKeepLabels());
+ for (final Traversal.Admin<?, ?> traversal : this.parent.getRemainingTraversals(traverser)) {
+ Set<String> referencedLabels = this.referencedLabelsMap.get(traversal.getStartStep().getId());
+ if (null == referencedLabels) {
+ referencedLabels = new HashSet<>();
+ for (final Step<?, ?> step : traversal.getSteps()) {
+ referencedLabels.addAll(PathUtil.getReferencedLabels(step));
+ }
+ this.referencedLabelsMap.put(traversal.getStartStep().getId(), referencedLabels);
}
- keepers.addAll(parent.getKeepLabels());
- PathProcessor.processTraverserPathLabels(traverser, keepers);
+ keepers.addAll(referencedLabels);
}
+ return PathProcessor.processTraverserPathLabels(traverser, keepers);
}
@Override
protected Traverser.Admin<Object> processNextStart() throws NoSuchElementException {
-
+ if (null == this.parent)
+ this.parent = ((MatchStep) this.getTraversal().getParent().asStep());
while (true) {
final Traverser.Admin traverser = this.starts.next();
// no end label
if (null == this.matchKey) {
if (this.traverserStepIdAndLabelsSetByChild)
- traverser.setStepId(((MatchStep<?, ?>) this.getTraversal().getParent()).getId());
- ((MatchStep<?, ?>) this.getTraversal().getParent()).getMatchAlgorithm().recordEnd(traverser, this.getTraversal());
- retractUnnecessaryLabels(traverser);
- return traverser;
+ traverser.setStepId(this.parent.getId());
+ this.parent.getMatchAlgorithm().recordEnd(traverser, this.getTraversal());
+ return this.retractUnnecessaryLabels(traverser);
}
// TODO: sideEffect check?
// path check
final Path path = traverser.path();
if (!path.hasLabel(this.matchKey) || traverser.get().equals(path.get(Pop.last, this.matchKey))) {
if (this.traverserStepIdAndLabelsSetByChild)
- traverser.setStepId(((MatchStep<?, ?>) this.getTraversal().getParent()).getId());
+ traverser.setStepId(this.parent.getId());
traverser.addLabels(Collections.singleton(this.matchKey));
- ((MatchStep<?, ?>) this.getTraversal().getParent()).getMatchAlgorithm().recordEnd(traverser, this.getTraversal());
- retractUnnecessaryLabels(traverser);
- return traverser;
+ this.parent.getMatchAlgorithm().recordEnd(traverser, this.getTraversal());
+ return this.retractUnnecessaryLabels(traverser);
}
}
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b900de27/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java
index 2ff22ba..a85b752 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java
@@ -120,7 +120,9 @@ public final class PathRetractionStrategy extends AbstractTraversalStrategy<Trav
Step<?, ?> parent = traversal.getParent().asStep();
final List<Pair<Step, Set<String>>> parentKeeperPairs = new ArrayList<>();
while (!parent.equals(EmptyStep.instance())) {
- parentKeeperPairs.add(new Pair<>(parent, PathUtil.whichLabelsReferencedFromHereForward(parent)));
+ Set<String> parentKeepLabels = new HashSet<>(PathUtil.getReferencedLabels(parent));
+ parentKeepLabels.addAll(PathUtil.getReferencedLabelsAfterStep(parent));
+ parentKeeperPairs.add(new Pair<>(parent, parentKeepLabels));
parent = parent.getTraversal().getParent().asStep();
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b900de27/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PathUtil.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PathUtil.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PathUtil.java
index 64e418f..ab97836 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PathUtil.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PathUtil.java
@@ -26,7 +26,6 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.map.MatchStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.Parameters;
-import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
@@ -40,34 +39,12 @@ public class PathUtil {
}
public static Set<String> getReferencedLabelsAfterStep(Step<?, ?> step) {
- if (step.getNextStep().equals(EmptyStep.instance())) {
- return Collections.emptySet();
- }
final Set<String> labels = new HashSet<>();
- while (!(step = step.getNextStep()).equals(EmptyStep.instance())) {
+ while (!(step instanceof EmptyStep)) {
labels.addAll(PathUtil.getReferencedLabels(step));
- }
- return labels;
- }
-
- public static Set<String> getReferencedLabels(final Traversal.Admin<?, ?> traversal) {
- final Set<String> referencedLabels = new HashSet<>();
- for (final Step<?, ?> step : traversal.getSteps()) {
- referencedLabels.addAll(getReferencedLabels(step));
- }
- return referencedLabels;
- }
-
- public static Set<String> whichLabelsReferencedFromHereForward(Step<?, ?> step) {
- final Set<String> found = new HashSet<>();
- while (!step.equals(EmptyStep.instance())) {
- final Set<String> referencedLabels = getReferencedLabels(step);
- for (final String refLabel : referencedLabels) {
- found.add(refLabel);
- }
step = step.getNextStep();
}
- return found;
+ return labels;
}
public static Set<String> getReferencedLabels(final Step step) {
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b900de27/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 390c749..a758eea 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
@@ -199,8 +199,8 @@ public class NativeNeo4jCypherCheck extends AbstractNeo4jGremlinTest {
() -> n.cypher("MATCH (a)<-[:writtenBy]-(b), (b)-[:followedBy]->(c), (c)-[:writtenBy]->(d) WHERE a <> d AND a.name = 'Garcia' AND 'artist' IN labels(a) RETURN a.name, d.name"),
///
() -> g.V().match(
- as("a").out("followed").as("b"),
- as("b").out("followed").as("c")).select("a").by("name"),
+ 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")
///
/*() -> g.V().match(