Repository: tinkerpop Updated Branches: refs/heads/TINKERPOP-1349 e6071c0e4 -> f87ef1240
Refactored traversal strategy performance tests. Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/f87ef124 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/f87ef124 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/f87ef124 Branch: refs/heads/TINKERPOP-1349 Commit: f87ef1240bb8376862e960c848129837f049bdb5 Parents: e6071c0 Author: Daniel Kuppitz <daniel_kupp...@hotmail.com> Authored: Wed Jun 29 17:07:54 2016 +0200 Committer: Daniel Kuppitz <daniel_kupp...@hotmail.com> Committed: Wed Jun 29 17:07:54 2016 +0200 ---------------------------------------------------------------------- .../TraversalStrategyPerformanceTest.java | 102 +++++++++++++++++++ .../IdentityRemovalStrategyTest.java | 72 ++++++------- .../optimization/RepeatUnrollStrategyTest.java | 86 ++++++++-------- 3 files changed, 174 insertions(+), 86 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f87ef124/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/TraversalStrategyPerformanceTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/TraversalStrategyPerformanceTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/TraversalStrategyPerformanceTest.java new file mode 100644 index 0000000..5e496f1 --- /dev/null +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/TraversalStrategyPerformanceTest.java @@ -0,0 +1,102 @@ +package org.apache.tinkerpop.gremlin.process.traversal.strategy; + +import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies; +import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal; +import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies; +import org.apache.tinkerpop.gremlin.util.TimeUtil; +import org.junit.Test; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +import java.util.Iterator; +import java.util.List; +import java.util.Random; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; + +/** + * @author Daniel Kuppitz (http://gremlin.guru) + */ +public abstract class TraversalStrategyPerformanceTest { + + private static final Logger LOGGER = LoggerFactory.getLogger(TraversalStrategyPerformanceTest.class); + private static final Random RANDOM = new Random(); + + protected int getClockRuns() { + return 1000; + } + + /** + * Specifies for how many percent of all comparisons the optimized traversal must be faster than the + * original traversal. Default is 100. + */ + protected double getAssertionPercentile() { + return 100.0; + } + + protected abstract Class<? extends TraversalStrategy> getStrategyUnderTest(); + + protected TraversalStrategy<?> getStrategyUnderTestInstance() throws Exception { + return (TraversalStrategy) getStrategyUnderTest().getMethod("instance").invoke(null); + } + + protected abstract Iterator<GraphTraversal> getTraversalIterator(); + + @Test + public void shouldBeFaster() throws Exception { + + final TraversalStrategies withStrategyUnderTest = new DefaultTraversalStrategies(); + withStrategyUnderTest.addStrategies(getStrategyUnderTestInstance()); + + final TraversalStrategies withoutStrategyUnderTest = new DefaultTraversalStrategies(); + withoutStrategyUnderTest.removeStrategies(getStrategyUnderTest()); + + final int clockRuns = getClockRuns(); + final Iterator<GraphTraversal> iterator = getTraversalIterator(); + int faster = 0, numTraversals = 0; + while (iterator.hasNext()) { + + final GraphTraversal traversal = iterator.next(); + final GraphTraversal.Admin original = traversal.asAdmin(); + final GraphTraversal.Admin optimized = original.clone(); + + original.setStrategies(withoutStrategyUnderTest); + optimized.setStrategies(withStrategyUnderTest); + + final double originalTime, optimizedTime; + + if (RANDOM.nextBoolean()) { + originalTime = TimeUtil.clock(clockRuns, () -> original.clone().iterate()); + optimizedTime = TimeUtil.clock(clockRuns, () -> optimized.clone().iterate()); + } else { + optimizedTime = TimeUtil.clock(clockRuns, () -> optimized.clone().iterate()); + originalTime = TimeUtil.clock(clockRuns, () -> original.clone().iterate()); + } + + final List originalResult = original.toList(); + final List optimizedResult = optimized.toList(); + + if (originalTime > optimizedTime) { + LOGGER.debug("Original traversal ({} ms): {}", originalTime, original); + LOGGER.debug("Optimized traversal ({} ms): {}", optimizedTime, optimized); + } else { + LOGGER.warn("Original traversal ({} ms): {}", originalTime, original); + LOGGER.warn("Optimized traversal ({} ms): {}", optimizedTime, optimized); + } + + if (getAssertionPercentile() >= 100) assertTrue(originalTime > optimizedTime); + else { + if (originalTime > optimizedTime) + faster++; + numTraversals++; + } + + assertEquals(originalResult, optimizedResult); + } + + if (getAssertionPercentile() < 100) + assertTrue(((faster * 100.0) / numTraversals) >= getAssertionPercentile()); + } +} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f87ef124/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IdentityRemovalStrategyTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IdentityRemovalStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IdentityRemovalStrategyTest.java index c5099f9..065dc53 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IdentityRemovalStrategyTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IdentityRemovalStrategyTest.java @@ -20,20 +20,21 @@ package org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization; import org.apache.tinkerpop.gremlin.process.traversal.Traversal; import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies; +import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.TraversalStrategyPerformanceTest; import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies; -import org.apache.tinkerpop.gremlin.util.TimeUtil; import org.junit.Test; import org.junit.experimental.runners.Enclosed; import org.junit.runner.RunWith; import org.junit.runners.Parameterized; import java.util.Arrays; -import java.util.Random; +import java.util.Iterator; +import java.util.stream.IntStream; import static org.junit.Assert.assertEquals; -import static org.junit.Assert.assertTrue; /** @@ -82,52 +83,39 @@ public class IdentityRemovalStrategyTest { } - public static class NonParameterizedTests { + public static class PerformanceTest extends TraversalStrategyPerformanceTest { - private static final Random RANDOM = new Random(); + @Override + protected Class<? extends TraversalStrategy> getStrategyUnderTest() { + return IdentityRemovalStrategy.class; + } - @Test - public void shouldBeFaster() { - - final int startSize = 1000; - final int clockRuns = 2000; - final int maxIdentities = 10; - final int minIdentities = 3; - final Integer[] starts = new Integer[startSize]; - for (int i = 0; i < startSize; i++) { - starts[i] = i; - } - - for (int i = minIdentities; i < maxIdentities; i++) { - final int numberOfIdentities = i; - final Runnable original = () -> { - final GraphTraversal<Integer, Integer> traversal = __.inject(starts); - for (int j = 0; j < numberOfIdentities; j++) { - traversal.identity(); - } - traversal.iterate(); - }; + @Override + protected Iterator<GraphTraversal> getTraversalIterator() { + + return new Iterator<GraphTraversal>() { + + final int minIdentities = 3; + final int maxIdentities = 10; + final Integer[] starts = IntStream.range(0, 1000).boxed().toArray(Integer[]::new); + + private int numberOfIdentities = minIdentities; + + @Override + public boolean hasNext() { + return numberOfIdentities <= maxIdentities; + } - final TraversalStrategies strategies = new DefaultTraversalStrategies(); - strategies.addStrategies(IdentityRemovalStrategy.instance()); - final Runnable optimized = () -> { - final GraphTraversal<Integer, Integer> traversal = __.inject(starts); + @Override + public GraphTraversal next() { + final GraphTraversal traversal = __.inject(starts); for (int j = 0; j < numberOfIdentities; j++) { traversal.identity(); } - traversal.asAdmin().setStrategies(strategies); - traversal.iterate(); - }; - - //System.out.println(TimeUtil.clock(clockRuns, original) + "---" + TimeUtil.clock(clockRuns, optimized)); - if (RANDOM.nextBoolean()) { - assertTrue(TimeUtil.clock(clockRuns, original) > TimeUtil.clock(clockRuns, optimized)); - assertTrue(TimeUtil.clock(clockRuns, optimized) < TimeUtil.clock(clockRuns, original)); - } else { - assertTrue(TimeUtil.clock(clockRuns, optimized) < TimeUtil.clock(clockRuns, original)); - assertTrue(TimeUtil.clock(clockRuns, original) > TimeUtil.clock(clockRuns, optimized)); + numberOfIdentities++; + return traversal; } - } + }; } } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f87ef124/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 91ab2ae..d409cc2 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 @@ -21,25 +21,24 @@ package org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization; import org.apache.tinkerpop.gremlin.process.traversal.Traversal; import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies; +import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy; import org.apache.tinkerpop.gremlin.process.traversal.Traverser; +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.TraversalStrategyPerformanceTest; import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies; import org.apache.tinkerpop.gremlin.structure.Vertex; -import org.apache.tinkerpop.gremlin.util.TimeUtil; -import org.javatuples.Pair; import org.junit.Test; import org.junit.experimental.runners.Enclosed; import org.junit.runner.RunWith; import org.junit.runners.Parameterized; import java.util.Arrays; -import java.util.HashSet; -import java.util.Random; +import java.util.Iterator; import java.util.function.Predicate; -import java.util.function.Supplier; +import java.util.stream.IntStream; import static org.junit.Assert.assertEquals; -import static org.junit.Assert.assertTrue; /** * @author Marko A. Rodriguez (http://markorodriguez.com) @@ -48,8 +47,6 @@ import static org.junit.Assert.assertTrue; @RunWith(Enclosed.class) public class RepeatUnrollStrategyTest { - private static final Random RANDOM = new Random(); - @RunWith(Parameterized.class) public static class ParameterizedTests { @@ -98,46 +95,47 @@ public class RepeatUnrollStrategyTest { } } - public static class NonParameterizedTests { + public static class PerformanceTest extends TraversalStrategyPerformanceTest { - @Test - public void shouldBeFaster() { - final int startSize = 1000; - final int clockRuns = 1000; - for (int i = 100; i <= startSize; i = i + 200) { - final Integer[] starts = new Integer[startSize]; - for (int j = 0; j < startSize; j++) { - starts[j] = j % i; + @Override + protected double getAssertionPercentile() { + return 95.0; + } + + @Override + protected Class<? extends TraversalStrategy> getStrategyUnderTest() { + return RepeatUnrollStrategy.class; + } + + @Override + protected Iterator<GraphTraversal> getTraversalIterator() { + + return new Iterator<GraphTraversal>() { + + final int minLoops = 2; + final int maxLoops = 5; + final int minModulo = 100; + final int maxModulo = 1000; + + private int numberOfLoops = minLoops; + private int modulo = minModulo; + + @Override + public boolean hasNext() { + return modulo <= maxModulo; } - assertEquals(i, new HashSet<>(Arrays.asList(starts)).size()); - /// - for (int j = 2; j < 6; j++) { - final int times = j; - final Supplier<Long> original = () -> __.inject(starts).repeat(__.identity()).times(times).<Long>sum().next(); - - final TraversalStrategies strategies = new DefaultTraversalStrategies(); - strategies.addStrategies(RepeatUnrollStrategy.instance()); - final Supplier<Long> optimized = () -> { - final Traversal<Integer, Long> traversal = __.inject(starts).repeat(__.identity()).times(times).sum(); - traversal.asAdmin().setStrategies(strategies); - return traversal.next(); - }; - - final Pair<Double, Long> originalResult; - final Pair<Double, Long> optimizedResult; - if (RANDOM.nextBoolean()) { - originalResult = TimeUtil.clockWithResult(clockRuns, original); - optimizedResult = TimeUtil.clockWithResult(clockRuns, optimized); - } else { - optimizedResult = TimeUtil.clockWithResult(clockRuns, optimized); - originalResult = TimeUtil.clockWithResult(clockRuns, original); - } - // System.out.println(originalResult + "---" + optimizedResult); - assertEquals(originalResult.getValue1(), optimizedResult.getValue1()); - assertTrue(originalResult.getValue0() > optimizedResult.getValue0()); + @Override + public GraphTraversal next() { + final Integer[] starts = IntStream.range(0, 1000).map(i -> i % modulo).boxed().toArray(Integer[]::new); + final GraphTraversal traversal = __.inject(starts).repeat(__.identity()).times(numberOfLoops).sum(); + if (++numberOfLoops > maxLoops) { + numberOfLoops = minLoops; + modulo += 200; + } + return traversal; } - } + }; } } }
