This is an automated email from the ASF dual-hosted git repository. spmallette pushed a commit to branch TINKERPOP-3100 in repository https://gitbox.apache.org/repos/asf/tinkerpop.git
commit 34890c3eac70de2b56eeaee4203002ef88b90ae8 Author: Stephen Mallette <[email protected]> AuthorDate: Thu Jul 3 07:24:09 2025 -0400 TINKERPOP-3100 Fix problem in recursive calls to Traversal lock() Drastically improves the performance of lock() as you lose the excessive recursion and avoid having to reidentify steps repeatedly. --- CHANGELOG.asciidoc | 1 + .../process/traversal/util/DefaultTraversal.java | 6 +- .../traversal/util/DefaultTraversalTest.java | 93 ++++++++++++++ .../gremlin/process/ApplyStrategiesBenchmark.java | 136 ++++++++++++++++++++ .../gremlin/process/TraversalLockBenchmark.java | 137 +++++++++++++++++++++ 5 files changed, 371 insertions(+), 2 deletions(-) diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc index e2e74564d5..565ebf9587 100644 --- a/CHANGELOG.asciidoc +++ b/CHANGELOG.asciidoc @@ -24,6 +24,7 @@ image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima === TinkerPop 3.7.4 (NOT OFFICIALLY RELEASED YET) * Fixed bug in server `Settings` where it was referencing a property that was back in 3.3.0 and generating a warning log. +* Improved performance of `Traversal.lock()` which was being called excessively. * Added log entry in `WsAndHttpChannelizerHandler` to catch general errors that escape the handlers. * Added a `MessageSizeEstimator` implementation to cover `Frame` allowing Gremlin Server to better estimate message sizes for the direct buffer. * Improved logging around triggers of the `writeBufferHighWaterMark` so that they occur more than once but do not excessively fill the logs. diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversal.java index 499fa26551..ec92b35464 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversal.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversal.java @@ -329,8 +329,10 @@ public class DefaultTraversal<S, E> implements Traversal.Admin<S, E> { // lock the parent before the children this.locked = true; - // now lock all the children - TraversalHelper.applyTraversalRecursively(Admin::lock, this, true); + // now lock all the children. since it's being called recursively here, we don't need each child to then + // also call this recursively TINKERPOP-3100 + if (isRoot() || parent instanceof VertexProgramStep) + TraversalHelper.applyTraversalRecursively(Admin::lock, this, true); } /** diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversalTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversalTest.java index b779386e3f..3f0e57a7e7 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversalTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversalTest.java @@ -20,12 +20,16 @@ package org.apache.tinkerpop.gremlin.process.traversal.util; import org.apache.tinkerpop.gremlin.process.traversal.Operator; +import org.apache.tinkerpop.gremlin.process.traversal.P; import org.apache.tinkerpop.gremlin.process.traversal.Step; import org.apache.tinkerpop.gremlin.process.traversal.Traversal; import org.apache.tinkerpop.gremlin.process.traversal.TraversalSideEffects; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.DefaultGraphTraversal; +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversalSource; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent; +import org.apache.tinkerpop.gremlin.structure.Graph; +import org.apache.tinkerpop.gremlin.structure.util.empty.EmptyGraph; import org.apache.tinkerpop.gremlin.util.function.ConstantSupplier; import org.apache.tinkerpop.gremlin.util.function.HashSetSupplier; import org.hamcrest.CoreMatchers; @@ -42,6 +46,7 @@ import java.util.function.Supplier; import java.util.stream.Collectors; import java.util.stream.IntStream; +import static org.apache.tinkerpop.gremlin.process.traversal.AnonymousTraversalSource.traversal; import static org.hamcrest.number.OrderingComparison.greaterThan; import static org.hamcrest.number.OrderingComparison.lessThan; import static org.junit.Assert.assertEquals; @@ -49,6 +54,7 @@ import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertNotEquals; import static org.junit.Assert.assertNotSame; import static org.hamcrest.MatcherAssert.assertThat; +import static org.hamcrest.core.Is.is; import static org.junit.Assert.assertTrue; /** @@ -127,6 +133,93 @@ public class DefaultTraversalTest { recursiveTestTraversals(traversal, sideEffects, new HashSet<>(Arrays.asList("marko", "bob", "x")), 13); } + @Test + public void shouldLock() { + final Traversal t = getBigDeepTraversal(); + t.asAdmin().lock(); + recursiveTestLock(t.asAdmin()); + } + + + @Test + public void shouldLockAfterApplyingStrategies() { + final Traversal t = getBigDeepTraversal(); + t.asAdmin().applyStrategies(); + recursiveTestLock(t.asAdmin()); + } + + private static Traversal getBigDeepTraversal() { + final Graph graph = EmptyGraph.instance(); + final GraphTraversalSource g = traversal().withEmbedded(graph); + + final Traversal t = g.V().or( + __.has("name", P.within(new HashSet<>(Arrays.asList("DARK STAR", "ST. STEPHEN", "CHINA CAT SUNFLOWER")))), + __.has("songType", P.eq("cover"))).where( + __.coalesce( + __.where( + __.union( + __.as("a").inE("sungBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).outV().filter(__.has("weight", P.lt(1))), + __.as("a").outE("followedBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).inV().where( + __.coalesce( + __.where( + __.union( + __.as("a").outE("followedBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).inV().has("songType", P.neq("cover")).where( + __.coalesce( + __.where( + __.union( + __.as("a").outE("followedBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).inV().where( + __.coalesce( + __.where( + __.union( + __.as("a").outE("followedBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).inV().where( + __.coalesce( + __.where( + __.union( + __.as("a").outE("followedBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).inV().has("songType", P.within("original")) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ).dedup().select("a") + ) + )); + return t; + } + + private void recursiveTestLock(final Traversal.Admin<?, ?> traversal) { + assertThat(traversal.isLocked(), is(true)); + for (final Step<?, ?> step : traversal.getSteps()) { + if (step instanceof TraversalParent) { + ((TraversalParent) step).getGlobalChildren().forEach(this::recursiveTestLock); + ((TraversalParent) step).getLocalChildren().forEach(this::recursiveTestLock); + } + } + } + private void recursiveTestTraversals(final Traversal.Admin<?, ?> traversal, final TraversalSideEffects sideEffects, final Set aValue, final int bValue) { assertTrue(traversal.getSideEffects() == sideEffects); assertEquals(sideEffects.keys().size(), traversal.getSideEffects().keys().size()); diff --git a/gremlin-tools/gremlin-benchmark/src/main/java/org/apache/tinkerpop/gremlin/process/ApplyStrategiesBenchmark.java b/gremlin-tools/gremlin-benchmark/src/main/java/org/apache/tinkerpop/gremlin/process/ApplyStrategiesBenchmark.java new file mode 100644 index 0000000000..cdb2135f1b --- /dev/null +++ b/gremlin-tools/gremlin-benchmark/src/main/java/org/apache/tinkerpop/gremlin/process/ApplyStrategiesBenchmark.java @@ -0,0 +1,136 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ +package org.apache.tinkerpop.gremlin.process; + +import org.apache.tinkerpop.benchmark.util.AbstractBenchmarkBase; +import org.apache.tinkerpop.gremlin.process.traversal.P; +import org.apache.tinkerpop.gremlin.process.traversal.Traversal; +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversalSource; +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; +import org.apache.tinkerpop.gremlin.structure.Graph; +import org.apache.tinkerpop.gremlin.structure.util.empty.EmptyGraph; +import org.openjdk.jmh.annotations.Benchmark; +import org.openjdk.jmh.annotations.Level; +import org.openjdk.jmh.annotations.OutputTimeUnit; +import org.openjdk.jmh.annotations.Scope; +import org.openjdk.jmh.annotations.Setup; +import org.openjdk.jmh.annotations.State; + +import java.util.Arrays; +import java.util.HashSet; +import java.util.concurrent.TimeUnit; + +import static org.apache.tinkerpop.gremlin.process.traversal.AnonymousTraversalSource.traversal; + +/** + * Benchmark for measuring the performance of applying strategies to a complex traversal. + * + * @author TinkerPop Community + */ +@OutputTimeUnit(TimeUnit.MILLISECONDS) +@State(Scope.Thread) +public class ApplyStrategiesBenchmark extends AbstractBenchmarkBase { + + private Graph graph = EmptyGraph.instance(); + private GraphTraversalSource g = traversal().withEmbedded(graph); + private Traversal<?, ?> traversal; + + /** + * Setup method that constructs the complex traversal before benchmarking on each invocation of the test. + */ + @Setup(Level.Invocation) + public void setup() { + traversal = g.V().or( + __.has("name", P.within(new HashSet<>(Arrays.asList("DARK STAR", "ST. STEPHEN", "CHINA CAT SUNFLOWER")))), + __.has("songType", P.eq("cover"))).where( + __.coalesce( + __.where( + __.union( + __.as("a").inE("sungBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).outV().filter(__.has("weight", P.lt(1))), + __.as("a").outE("followedBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).inV().where( + __.coalesce( + __.where( + __.union( + __.as("a").outE("followedBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).inV().has("songType", P.neq("cover")).where( + __.coalesce( + __.where( + __.union( + __.as("a").outE("followedBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).inV().where( + __.coalesce( + __.where( + __.union( + __.as("a").outE("followedBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).inV().where( + __.coalesce( + __.where( + __.union( + __.as("a").outE("followedBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).inV().has("songType", P.within("original")) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ).dedup().select("a") + ) + )); + } + + @Override + protected int getWarmupIterations() { + return 1; + } + + @Override + protected int getForks() { + return 1; + } + + /** + * Benchmark that measures only the time it takes to apply strategies to a complex traversal. + */ + @Benchmark + public Traversal testLockTraversal() { + if (traversal.asAdmin().isLocked()) + throw new RuntimeException("Traversal is locked - that shouldn't be possible if the traversal is new"); + traversal.asAdmin().applyStrategies(); + return traversal; + } +} diff --git a/gremlin-tools/gremlin-benchmark/src/main/java/org/apache/tinkerpop/gremlin/process/TraversalLockBenchmark.java b/gremlin-tools/gremlin-benchmark/src/main/java/org/apache/tinkerpop/gremlin/process/TraversalLockBenchmark.java new file mode 100644 index 0000000000..3189140b85 --- /dev/null +++ b/gremlin-tools/gremlin-benchmark/src/main/java/org/apache/tinkerpop/gremlin/process/TraversalLockBenchmark.java @@ -0,0 +1,137 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ +package org.apache.tinkerpop.gremlin.process; + +import org.apache.tinkerpop.benchmark.util.AbstractBenchmarkBase; +import org.apache.tinkerpop.gremlin.process.traversal.P; +import org.apache.tinkerpop.gremlin.process.traversal.Traversal; +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversalSource; +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; +import org.apache.tinkerpop.gremlin.structure.Graph; +import org.apache.tinkerpop.gremlin.structure.util.empty.EmptyGraph; +import org.openjdk.jmh.annotations.Benchmark; +import org.openjdk.jmh.annotations.Level; +import org.openjdk.jmh.annotations.OutputTimeUnit; +import org.openjdk.jmh.annotations.Scope; +import org.openjdk.jmh.annotations.Setup; +import org.openjdk.jmh.annotations.State; + +import java.util.Arrays; +import java.util.HashSet; +import java.util.concurrent.TimeUnit; + +import static org.apache.tinkerpop.gremlin.process.traversal.AnonymousTraversalSource.traversal; + +/** + * Benchmark for measuring the performance of locking a complex traversal. + * This benchmark is based on the shouldLock test in the DefaultTraversalTest class. + * + * @author TinkerPop Community + */ +@OutputTimeUnit(TimeUnit.MILLISECONDS) +@State(Scope.Benchmark) +public class TraversalLockBenchmark extends AbstractBenchmarkBase { + + private Graph graph = EmptyGraph.instance(); + private GraphTraversalSource g = traversal().withEmbedded(graph); + private Traversal<?, ?> traversal; + + /** + * Setup method that constructs the complex traversal before benchmarking on each invocation of the test. + */ + @Setup(Level.Invocation) + public void setup() { + traversal = g.V().or( + __.has("name", P.within(new HashSet<>(Arrays.asList("DARK STAR", "ST. STEPHEN", "CHINA CAT SUNFLOWER")))), + __.has("songType", P.eq("cover"))).where( + __.coalesce( + __.where( + __.union( + __.as("a").inE("sungBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).outV().filter(__.has("weight", P.lt(1))), + __.as("a").outE("followedBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).inV().where( + __.coalesce( + __.where( + __.union( + __.as("a").outE("followedBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).inV().has("songType", P.neq("cover")).where( + __.coalesce( + __.where( + __.union( + __.as("a").outE("followedBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).inV().where( + __.coalesce( + __.where( + __.union( + __.as("a").outE("followedBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).inV().where( + __.coalesce( + __.where( + __.union( + __.as("a").outE("followedBy").choose( + __.has("weight"), __.has("weight", P.gt(1)), __.identity() + ).inV().has("songType", P.within("original")) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ).dedup().select("a") + ) + )); + } + + @Override + protected int getWarmupIterations() { + return 1; + } + + @Override + protected int getForks() { + return 1; + } + + /** + * Benchmark that measures only the time it takes to lock a complex traversal. + */ + @Benchmark + public Traversal testLockTraversal() { + if (traversal.asAdmin().isLocked()) + throw new RuntimeException("Traversal is locked - that shouldn't be possible if the traversal is new"); + traversal.asAdmin().lock(); + return traversal; + } +}
