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/06/30 13:16:19 UTC
[06/10] tinkerpop git commit: Refactored traversal strategy
performance tests.
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/master
Commit: f87ef1240bb8376862e960c848129837f049bdb5
Parents: e6071c0
Author: Daniel Kuppitz <da...@hotmail.com>
Authored: Wed Jun 29 17:07:54 2016 +0200
Committer: Daniel Kuppitz <da...@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;
}
- }
+ };
}
}
}