TINKERPOP-1642 Cached the Traversal list in Parameters This leads to a pretty good boost in performance from the prior commit especially for long chained mutating traversals that add vertices and edges as there is a 3X improvement in those cases.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/3dea5bdd Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/3dea5bdd Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/3dea5bdd Branch: refs/heads/tp32 Commit: 3dea5bdd9b8ce2bf6d28882e38e07d93162bcb11 Parents: da02d96 Author: Stephen Mallette <sp...@genoprime.com> Authored: Fri Mar 3 06:47:56 2017 -0500 Committer: Stephen Mallette <sp...@genoprime.com> Committed: Wed Mar 29 11:20:43 2017 -0400 ---------------------------------------------------------------------- .../process/traversal/step/util/Parameters.java | 59 ++++++++++++-------- .../traversal/step/util/ParametersTest.java | 50 +++++++++++++++++ 2 files changed, 87 insertions(+), 22 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/3dea5bdd/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/Parameters.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/Parameters.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/Parameters.java index 67cb2f9..3f0cb7c 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/Parameters.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/Parameters.java @@ -26,6 +26,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent; import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalUtil; import org.apache.tinkerpop.gremlin.structure.Element; import org.apache.tinkerpop.gremlin.structure.T; +import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils; import java.io.Serializable; import java.util.ArrayList; @@ -49,9 +50,11 @@ public final class Parameters implements Cloneable, Serializable { private Map<Object, List<Object>> parameters = new HashMap<>(); /** - * Determines if there are traversals present in the parameters {@code Map}. + * A cached list of traversals that server as parameter values. The list is cached on calls to + * {@link #set(Object...)} because when the parameter map is large the cost of iterating it repeatedly on the + * high number of calls to {@link #getTraversals()} and {@link #integrateTraversals(TraversalParent)} is great. */ - private boolean traversalsPresent = false; + private List<Traversal.Admin> traversals = new ArrayList<>(); /** * Checks for existence of key in parameter set. @@ -73,6 +76,10 @@ public final class Parameters implements Cloneable, Serializable { this.parameters.put(newKey, this.parameters.remove(oldKey)); } + /** + * Gets the list of values for a key, while resolving the values of any parameters that are {@link Traversal} + * objects. + */ public <S, E> List<E> get(final Traverser.Admin<S> traverser, final Object key, final Supplier<E> defaultValue) { final List<E> values = (List<E>) this.parameters.get(key); if (null == values) return Collections.singletonList(defaultValue.get()); @@ -102,9 +109,28 @@ public final class Parameters implements Cloneable, Serializable { * @return the value of the removed key */ public Object remove(final Object key) { - return parameters.remove(key); + final List<Object> o = parameters.remove(key); + + // once a key is removed, it's possible that the traversal cache will need to be regenerated + if (IteratorUtils.anyMatch(o.iterator(), p -> p instanceof Traversal.Admin)) { + traversals.clear(); + traversals = new ArrayList<>(); + for (final List<Object> list : this.parameters.values()) { + for (final Object object : list) { + if (object instanceof Traversal.Admin) { + traversals.add((Traversal.Admin) object); + } + } + } + } + + return o; } + /** + * Gets the array of keys/values of the parameters while resolving parameter values that contain + * {@link Traversal} instances + */ public <S> Object[] getKeyValues(final Traverser.Admin<S> traverser, final Object... exceptKeys) { if (this.parameters.size() == 0) return EMPTY_ARRAY; final List<Object> keyValues = new ArrayList<>(); @@ -143,10 +169,10 @@ public final class Parameters implements Cloneable, Serializable { Parameters.legalPropertyKeyValueArray(keyValues); for (int i = 0; i < keyValues.length; i = i + 2) { if (keyValues[i + 1] != null) { - // track whether or not traversals are present so that elsewhere in Parameters there is no need + // track the list of traversals that are present so that elsewhere in Parameters there is no need // to iterate all values to not find any. - if (!traversalsPresent && keyValues[i + 1] instanceof Traversal.Admin) - traversalsPresent = true; + if (keyValues[i + 1] instanceof Traversal.Admin) + traversals.add((Traversal.Admin) keyValues[i + 1]); List<Object> values = this.parameters.get(keyValues[i]); if (null == values) { @@ -167,14 +193,8 @@ public final class Parameters implements Cloneable, Serializable { * do its work. */ public void integrateTraversals(final TraversalParent step) { - if (traversalsPresent) { - for (final List<Object> values : this.parameters.values()) { - for (final Object object : values) { - if (object instanceof Traversal.Admin) { - step.integrateChild((Traversal.Admin) object); - } - } - } + for (Traversal.Admin t : traversals) { + step.integrateChild(t); } } @@ -182,15 +202,10 @@ public final class Parameters implements Cloneable, Serializable { * Gets all the {@link Traversal.Admin} objects in the map of parameters. */ public <S, E> List<Traversal.Admin<S, E>> getTraversals() { - if (!traversalsPresent) return Collections.emptyList(); - + // stupid generics - just need to return "traversals" final List<Traversal.Admin<S, E>> result = new ArrayList<>(); - for (final List<Object> list : this.parameters.values()) { - for (final Object object : list) { - if (object instanceof Traversal.Admin) { - result.add((Traversal.Admin) object); - } - } + for (Traversal.Admin t : traversals) { + result.add(t); } return result; } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/3dea5bdd/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ParametersTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ParametersTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ParametersTest.java index 27b9293..9c96c1c 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ParametersTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ParametersTest.java @@ -18,6 +18,7 @@ */ package org.apache.tinkerpop.gremlin.process.traversal.step.util; +import org.apache.tinkerpop.gremlin.process.traversal.Traversal; import org.apache.tinkerpop.gremlin.process.traversal.Traverser; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent; @@ -31,6 +32,7 @@ import java.util.Map; import static org.hamcrest.CoreMatchers.is; import static org.hamcrest.MatcherAssert.assertThat; import static org.hamcrest.Matchers.contains; +import static org.hamcrest.core.IsInstanceOf.instanceOf; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertNotEquals; import static org.mockito.Mockito.mock; @@ -153,6 +155,39 @@ public class ParametersTest { } @Test + public void shouldRemoveRefreshTraversalCache() { + final Parameters parameters = new Parameters(); + parameters.set("a", "axe", "b", "bat", "c", "cat", "c", mock(Traversal.Admin.class), "t", mock(Traversal.Admin.class)); + + final Map<Object,List<Object>> before = parameters.getRaw(); + assertEquals(4, before.size()); + assertEquals(2, parameters.getTraversals().size()); + assertEquals("axe", before.get("a").get(0)); + assertEquals("bat", before.get("b").get(0)); + assertEquals("cat", before.get("c").get(0)); + assertThat(before.get("c").get(1), instanceOf(Traversal.Admin.class)); + assertThat(before.get("t").get(0), instanceOf(Traversal.Admin.class)); + + parameters.remove("t"); + + final Map<Object,List<Object>> afterRemoveT = parameters.getRaw(); + assertEquals(3, afterRemoveT.size()); + assertEquals(1, parameters.getTraversals().size()); + assertEquals("axe", afterRemoveT.get("a").get(0)); + assertEquals("bat", afterRemoveT.get("b").get(0)); + assertEquals("cat", afterRemoveT.get("c").get(0)); + assertThat(afterRemoveT.get("c").get(1), instanceOf(Traversal.Admin.class)); + + parameters.remove("c"); + + final Map<Object,List<Object>> afterRemoveC = parameters.getRaw(); + assertEquals(2, afterRemoveC.size()); + assertEquals(0, parameters.getTraversals().size()); + assertEquals("axe", afterRemoveC.get("a").get(0)); + assertEquals("bat", afterRemoveC.get("b").get(0)); + } + + @Test public void shouldRename() { final Parameters parameters = new Parameters(); parameters.set("a", "axe", "b", "bat", "c", "cat"); @@ -215,6 +250,21 @@ public class ParametersTest { final Parameters parametersClone = parameters.clone(); assertEquals(parameters.getRaw(), parametersClone.getRaw()); + assertEquals(parameters.getTraversals(), parametersClone.getTraversals()); + } + + @Test + public void shouldCloneWithTraversals() { + final Traversal.Admin t = mock(Traversal.Admin.class); + when(t.clone()).thenReturn(t); + + final Parameters parameters = new Parameters(); + parameters.set("a", "axe", "a", "ant", "b", "bat", "b", "ball", "c", "cat", "t", t); + + final Parameters parametersClone = parameters.clone(); + + assertEquals(parameters.getRaw(), parametersClone.getRaw()); + assertEquals(parameters.getTraversals().size(), parametersClone.getTraversals().size()); } @Test