tinkerpop-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ok...@apache.org
Subject [06/10] tinkerpop git commit: Refactored traversal strategy performance tests.
Date Thu, 30 Jun 2016 13:16:19 GMT
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 <daniel_kuppitz@hotmail.com>
Authored: Wed Jun 29 17:07:54 2016 +0200
Committer: Daniel Kuppitz <daniel_kuppitz@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;
                 }
-            }
+            };
         }
     }
 }


Mime
View raw message