came up with a nice optimization. If the step after the repeat() is a Barrier, then there is no need to add a NoOpBarrier on the last loop serialization. Also, discovered a severe clone() bug in AbstractStep around label cloning. Can't believe this never popped up before now.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/6208b90b Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/6208b90b Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/6208b90b Branch: refs/heads/TINKERPOP-1254 Commit: 6208b90b2ca297186b4f75f356e0093d4b6ed280 Parents: 8753366 Author: Marko A. Rodriguez <[email protected]> Authored: Tue Jun 28 13:03:15 2016 -0600 Committer: Marko A. Rodriguez <[email protected]> Committed: Tue Jun 28 13:03:15 2016 -0600 ---------------------------------------------------------------------- .../process/traversal/step/util/AbstractStep.java | 5 +++-- .../optimization/RepeatUnrollStrategy.java | 17 ++++++++++++----- .../optimization/RepeatUnrollStrategyTest.java | 1 + 3 files changed, 16 insertions(+), 7 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/6208b90b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/AbstractStep.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/AbstractStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/AbstractStep.java index 2f83e9e..9eb1b3c 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/AbstractStep.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/AbstractStep.java @@ -124,7 +124,7 @@ public abstract class AbstractStep<S, E> implements Step<S, E> { } } else { while (true) { - if(Thread.interrupted()) throw new TraversalInterruptedException(); + if (Thread.interrupted()) throw new TraversalInterruptedException(); final Traverser.Admin<E> traverser = this.processNextStart(); if (null != traverser.get() && 0 != traverser.bulk()) return this.prepareTraversalForNextStep(traverser); @@ -139,7 +139,7 @@ public abstract class AbstractStep<S, E> implements Step<S, E> { else { try { while (true) { - if(Thread.interrupted()) throw new TraversalInterruptedException(); + if (Thread.interrupted()) throw new TraversalInterruptedException(); this.nextEnd = this.processNextStart(); if (null != this.nextEnd.get() && 0 != this.nextEnd.bulk()) return true; @@ -179,6 +179,7 @@ public abstract class AbstractStep<S, E> implements Step<S, E> { clone.nextStep = EmptyStep.instance(); clone.nextEnd = null; clone.traversal = EmptyTraversal.instance(); + clone.labels = new LinkedHashSet<>(this.labels); clone.reset(); return clone; } catch (final CloneNotSupportedException e) { http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/6208b90b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategy.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategy.java index 9047478..2139e81 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategy.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategy.java @@ -23,6 +23,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.Step; import org.apache.tinkerpop.gremlin.process.traversal.Traversal; import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy; import org.apache.tinkerpop.gremlin.process.traversal.lambda.LoopTraversal; +import org.apache.tinkerpop.gremlin.process.traversal.step.Barrier; import org.apache.tinkerpop.gremlin.process.traversal.step.branch.RepeatStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.NoOpBarrierStep; import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy; @@ -50,18 +51,24 @@ public final class RepeatUnrollStrategy extends AbstractTraversalStrategy<Traver if (null == repeatStep.getEmitTraversal() && repeatStep.getUntilTraversal() instanceof LoopTraversal) { final Traversal.Admin<?, ?> repeatTraversal = repeatStep.getGlobalChildren().get(0); final int repeatLength = repeatTraversal.getSteps().size() - 1; - repeatTraversal.removeStep(repeatLength); + repeatTraversal.removeStep(repeatLength); // removes the RepeatEndStep int insertIndex = i; final int loops = (int) ((LoopTraversal) repeatStep.getUntilTraversal()).getMaxLoops(); for (int j = 0; j < loops; j++) { - TraversalHelper.insertTraversal(insertIndex, repeatTraversal.clone(), traversal); // removes the RepeatEndStep + TraversalHelper.insertTraversal(insertIndex, repeatTraversal.clone(), traversal); insertIndex = insertIndex + repeatLength + 1; traversal.addStep(insertIndex, new NoOpBarrierStep<>(traversal)); } - if (!repeatStep.getLabels().isEmpty()) { - final Step<?, ?> lastStep = (Step) traversal.getSteps().get(insertIndex); - repeatStep.getLabels().forEach(lastStep::addLabel); + + final NoOpBarrierStep<?> lastStep = (NoOpBarrierStep) traversal.getSteps().get(insertIndex); + Step<?, ?> labelStep = lastStep; + if (lastStep.getNextStep() instanceof Barrier) { + labelStep = traversal.getSteps().get(insertIndex - 1); + traversal.removeStep(insertIndex); // remove last NoOpBarrierStep } + if (!repeatStep.getLabels().isEmpty()) + repeatStep.getLabels().forEach(labelStep::addLabel); + traversal.removeStep(i); // remove the RepeatStep } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/6208b90b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategyTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategyTest.java index 1c4c4b7..b819331 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategyTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategyTest.java @@ -90,6 +90,7 @@ public class RepeatUnrollStrategyTest { {__.repeat(__.out()).until(predicate), __.repeat(__.out()).until(predicate)}, {__.repeat(__.out()).until(predicate).repeat(__.out()).times(2), __.repeat(__.out()).until(predicate).out().barrier().out().barrier()}, {__.repeat(__.union(__.both(), __.identity())).times(2).out(), __.union(__.both(), __.identity()).barrier().union(__.both(), __.identity()).barrier().out()}, + {__.in().repeat(__.out("knows")).times(3).as("a").count().is(0), __.in().out("knows").barrier().out("knows").barrier().out("knows").as("a").count().is(0)}, }); }
