You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by "steigma (via GitHub)" <gi...@apache.org> on 2024/02/23 11:40:08 UTC
[PR] Avoiding expensive hash computation in filter ranking strategy [tinkerpop]
steigma opened a new pull request, #2504:
URL: https://github.com/apache/tinkerpop/pull/2504
Avoiding expensive hash computation for complex steps with many children in filter ranking strategy by using identity hash map instead of linked hash map. With the linked hash map, a hash computation is repeated for the traversal parent with each child, which can be quite costly when there are several hundreds of children.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Avoiding expensive hash computation in filter ranking strategy [tinkerpop]
Posted by "steigma (via GitHub)" <gi...@apache.org>.
steigma commented on code in PR #2504:
URL: https://github.com/apache/tinkerpop/pull/2504#discussion_r1513391247
##########
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategyCacheInitializationTest.java:
##########
@@ -0,0 +1,449 @@
+/*
+ * 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.traversal.strategy.optimization;
+
+import org.apache.tinkerpop.gremlin.process.traversal.Step;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.DefaultGraphTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.step.LambdaHolder;
+import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep;
+import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
+import org.apache.tinkerpop.gremlin.util.function.Lambda;
+import org.javatuples.Pair;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.where;
+
+/**
+ * Testing whether the cache for the FilterRankingStrategy is correctly initialized,
+ * which includes gathering/collecting the traversal parents and their children steps
+ * in the correct deep first manner.
+ */
+@RunWith(JUnit4.class)
+public class FilterRankingStrategyCacheInitializationTest {
+
+
+ @Test
+ public void test_collection_lambda_nested() {
Review Comment:
Thanks, I fixed the test names in the new version
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Avoiding expensive hash computation in filter ranking strategy [tinkerpop]
Posted by "steigma (via GitHub)" <gi...@apache.org>.
steigma commented on code in PR #2504:
URL: https://github.com/apache/tinkerpop/pull/2504#discussion_r1504375887
##########
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategyTest.java:
##########
@@ -85,44 +86,148 @@ public void doTest() {
@Parameterized.Parameters(name = "{0}")
public static Iterable<Object[]> generateTestParameters() {
final Predicate testP = t -> true;
+
return Arrays.asList(new Object[][]{
- {__.dedup().order(), __.dedup().order(), Collections.emptyList()},
- {__.has("name", "marko").as("a").out().as("b").has("age", 32).where("a", neq("b")).as("c").out(), __.has("name", "marko").as("a").out().has("age", 32).as("b").where("a", neq("b")).as("c").out(), Collections.emptyList()},
- {__.has("name", "marko").as("a").out().has("age", 32).as("b").where("a", neq("b")), __.has("name", "marko").as("a").out().has("age", 32).as("b").where("a", neq("b")), Collections.emptyList()},
- {__.has("name", "marko").has("age", 32).dedup().has("name", "bob").as("a"), __.has("name", "marko").has("age", 32).has("name", "bob").dedup().as("a"), Collections.singletonList(InlineFilterStrategy.instance())},
- {__.has("name", "marko").dedup().as("a").has("age", 32).has("name", "bob").as("b"), __.has("name", "marko").has("age", 32).has("name", "bob").dedup().as("b", "a"), Collections.singletonList(InlineFilterStrategy.instance())},
- {__.where("b", eq("c")).as("a").dedup("a").has("name", "marko"), __.has("name", "marko").where("b", eq("c")).as("a").dedup("a"), Collections.emptyList()},
- {__.where("b", eq("c")).has("name", "bob").as("a").dedup("a").has("name", "marko"), __.has("name", "bob").has("name", "marko").where("b", eq("c")).as("a").dedup("a"), Collections.singletonList(InlineFilterStrategy.instance())},
- {__.has("name", "marko").as("a").out().has("name", "bob").dedup().as("b").where(__.as("a").out().as("b")), __.has("name", "marko").as("a").out().has("name", "bob").dedup().as("b").where(__.as("a").out().as("b")), Collections.singletonList(InlineFilterStrategy.instance())},
- {__.has("name", "marko").as("a").out().has("name", "bob").as("b").dedup().where(__.as("a").out().as("b")), __.has("name", "marko").as("a").out().has("name", "bob").dedup().as("b").where(__.as("a").out().as("b")), Collections.singletonList(InlineFilterStrategy.instance())},
- {__.has("name", "marko").as("a").out().has("name", "bob").dedup().as("c").where(__.as("a").out().as("b")), __.has("name", "marko").as("a").out().has("name", "bob").where(__.as("a").out().as("b")).dedup().as("c"), Collections.singletonList(InlineFilterStrategy.instance())},
- {__.order().dedup(), __.dedup().order(), Collections.emptyList()},
- {__.order().filter(testP).dedup(), __.order().filter(testP).dedup(), Collections.emptyList()},
- {__.order().as("a").dedup(), __.dedup().order().as("a"), Collections.emptyList()},
- {__.order().as("a").dedup("a"), __.order().as("a").dedup("a"), Collections.emptyList()},
- {__.order().as("a").dedup("a").has("name", "marko"), __.has("name", "marko").as("a").dedup("a").order(), Collections.emptyList()},
- {__.order().as("a").dedup("a").has("name", "marko").out(), __.has("name", "marko").as("a").dedup("a").order().out(), Collections.emptyList()},
- {__.order().as("a").dedup("a").has("name", "marko").where("a", eq("b")).out(), __.has("name", "marko").as("a").where("a", eq("b")).dedup("a").order().out(), Collections.emptyList()},
- {__.identity().order().dedup(), __.dedup().order(), Collections.singletonList(IdentityRemovalStrategy.instance())},
- {__.order().identity().dedup(), __.dedup().order(), Collections.singletonList(IdentityRemovalStrategy.instance())},
- {__.order().out().dedup(), __.order().out().dedup(), Collections.emptyList()},
- {has("value", 0).filter(out()).dedup(), has("value", 0).filter(out()).dedup(), Collections.emptyList()},
- {__.dedup().has("value", 0).or(not(has("age")), has("age", 10)).has("value", 1), __.has("value", 0).has("value", 1).or(not(has("age")), has("age", 10)).dedup(), Collections.singletonList(InlineFilterStrategy.instance())},
- {__.dedup().filter(out()).has("value", 0), has("value", 0).filter(out()).dedup(), Collections.emptyList()},
- {filter(out()).dedup().has("value", 0), has("value", 0).filter(out()).dedup(), Collections.emptyList()},
- {__.as("a").out().has("age").where(P.eq("a")), __.as("a").out().where(P.eq("a")).has("age"), Collections.emptyList()},
- {__.as("a").out().has("age").where(P.eq("a")).by("age"), __.as("a").out().has("age").where(P.eq("a")).by("age"), Collections.emptyList()},
- {__.as("a").out().and(has("age"), has("name")).where(P.eq("a")).by("age"), __.as("a").out().and(has("age"), has("name")).where(P.eq("a")).by("age"), Collections.emptyList()},
- {__.as("a").out().and(has("age"), has("name")).where(P.eq("a")), __.as("a").out().where(P.eq("a")).and(has("age"), has("name")), Collections.emptyList()},
- {__.as("a").out().and(has("age"), has("name")).where(P.eq("a")).by("age"), __.as("a").out().has("age").has("name").where(P.eq("a")).by("age"), Collections.singletonList(InlineFilterStrategy.instance())},
- {__.as("a").out().and(has("age"), has("name")).where(P.eq("a")), __.as("a").out().where(P.eq("a")).has("age").has("name"), Collections.singletonList(InlineFilterStrategy.instance())},
- {__.as("a").out().and(has("age"), has("name")).filter(__.where(P.eq("a"))), __.as("a").out().where(P.eq("a")).has("age").has("name"), Collections.singletonList(InlineFilterStrategy.instance())},
- {__.as("a").out().and(has("age"), has("name")).filter(__.where(P.eq("a")).by("age")), __.as("a").out().has("age").has("name").where(P.eq("a")).by("age"), Collections.singletonList(InlineFilterStrategy.instance())},
- {has("value", 0).filter(out()).dedup(), has("value", 0).filter(out()).dedup(), Collections.emptyList()},
- {has("value", 0).or(has("name"), has("age")).has("value", 1).dedup(), has("value", 0).has("value", 1).or(has("name"), has("age")).dedup(), Collections.singletonList(InlineFilterStrategy.instance())},
- {has("value", 0).or(out(), in()).as(Graph.Hidden.hide("x")).has("value", 1).dedup(), has("value", 0).has("value", 1).or(outE(), inE()).dedup(), TraversalStrategies.GlobalCache.getStrategies(Graph.class).toList()},
- {has("value", 0).and(has("age"), has("name", "marko")).is(10), __.is(10).has("value", 0).has("age").has("name", "marko"), Collections.singletonList(InlineFilterStrategy.instance())},
- {has("value", 0).filter(or(not(has("age")), has("age", 1))).has("value", 1).dedup(), has("value", 0).has("value", 1).or(not(filter(properties("age"))), has("age", 1)).dedup(), TraversalStrategies.GlobalCache.getStrategies(Graph.class).toList()},
Review Comment:
I reformatted these tests slightly and added some new ones on the top
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Avoiding expensive hash computation in filter ranking strategy [tinkerpop]
Posted by "steigma (via GitHub)" <gi...@apache.org>.
steigma commented on PR #2504:
URL: https://github.com/apache/tinkerpop/pull/2504#issuecomment-1966731520
Thanks for the feedback. I added a few tests and renamed some variables. I also found that the lambda handling was not really working since the step collection was restricted to TraversalParent subclasses. This should now also be fixed and I added some basic test coverage for this.
In our experiments with queries of the form
```
g.V('vertex')...
coalesce(
and(
values('property').is('val1'),
values('property').is('val2'),
...
values('property').is('val800')
),
sideEffect(properties('property').drop()).
property(set, 'propery', 'val1').
property(set, 'propery', 'val2').
...
property(set, 'propery', 'val800')
)...
```
we have seen improvement of around 25% including all strategies and executing the queries, i.e,. the FilterRankingStrategy improved significantly (as also other strategies taking some significant amount of time).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Avoiding expensive hash computation in filter ranking strategy [tinkerpop]
Posted by "vkagamlyk (via GitHub)" <gi...@apache.org>.
vkagamlyk merged PR #2504:
URL: https://github.com/apache/tinkerpop/pull/2504
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Avoiding expensive hash computation in filter ranking strategy [tinkerpop]
Posted by "vkagamlyk (via GitHub)" <gi...@apache.org>.
vkagamlyk commented on code in PR #2504:
URL: https://github.com/apache/tinkerpop/pull/2504#discussion_r1507070049
##########
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategyCacheInitializationTest.java:
##########
@@ -0,0 +1,449 @@
+/*
+ * 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.traversal.strategy.optimization;
+
+import org.apache.tinkerpop.gremlin.process.traversal.Step;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.DefaultGraphTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.step.LambdaHolder;
+import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep;
+import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
+import org.apache.tinkerpop.gremlin.util.function.Lambda;
+import org.javatuples.Pair;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.where;
+
+/**
+ * Testing whether the cache for the FilterRankingStrategy is correctly initialized,
+ * which includes gathering/collecting the traversal parents and their children steps
+ * in the correct deep first manner.
+ */
+@RunWith(JUnit4.class)
+public class FilterRankingStrategyCacheInitializationTest {
+
+
+ @Test
+ public void test_collection_lambda_nested() {
+ // traversal
+ final Traversal<?, ?> traversal = __.V().as("n").
+ where(
+ __.or(
+ __.select("n").hasLabel("software"),
+ __.select("n").map(Lambda.function("it.get().out()"))
+ )
+ ).
+ select("n").by("name");
+
+ // expected order of traversal parents
+ final List<Traversal<?, ?>> collectedTraversalParents = Arrays.asList(
+ __.or(
+ __.select("n").hasLabel("software"),
+ __.select("n").map(Lambda.function("it.get().out()"))
+ ),
+ __.where(
+ __.or(
+ __.select("n").hasLabel("software"),
+ __.select("n").map(Lambda.function("it.get().out()"))
+ )
+ ));
+
+ // cache entries
+ final List<Pair<Boolean, Set<String>>> expectedTraversalParentCacheEntries = Arrays.asList(
+ new Pair<>(true, new HashSet<>(Collections.emptyList())),
Review Comment:
Why need to pass `Collections.emptyList()` to `HashSet` constructor?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Avoiding expensive hash computation in filter ranking strategy [tinkerpop]
Posted by "vkagamlyk (via GitHub)" <gi...@apache.org>.
vkagamlyk commented on PR #2504:
URL: https://github.com/apache/tinkerpop/pull/2504#issuecomment-1961752266
Good to have some test cases, especially for traversal where there are steps with nested global and local children
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Avoiding expensive hash computation in filter ranking strategy [tinkerpop]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #2504:
URL: https://github.com/apache/tinkerpop/pull/2504#issuecomment-1961635169
## [Codecov](https://app.codecov.io/gh/apache/tinkerpop/pull/2504?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Project coverage is 75.40%. Comparing base [(`d9e34fb`)](https://app.codecov.io/gh/apache/tinkerpop/commit/d9e34fb4678c29ffa167066de45a9fa7329a319a?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) to head [(`1463738`)](https://app.codecov.io/gh/apache/tinkerpop/pull/2504?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
> Report is 17 commits behind head on 3.6-dev.
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## 3.6-dev #2504 +/- ##
=============================================
+ Coverage 75.14% 75.40% +0.26%
- Complexity 12346 12357 +11
=============================================
Files 1058 1033 -25
Lines 63610 59887 -3723
Branches 6962 6971 +9
=============================================
- Hits 47801 45159 -2642
+ Misses 13225 12331 -894
+ Partials 2584 2397 -187
```
</details>
[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/apache/tinkerpop/pull/2504?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Avoiding expensive hash computation in filter ranking strategy [tinkerpop]
Posted by "vkagamlyk (via GitHub)" <gi...@apache.org>.
vkagamlyk commented on code in PR #2504:
URL: https://github.com/apache/tinkerpop/pull/2504#discussion_r1500988717
##########
gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategy.java:
##########
@@ -232,4 +243,64 @@ public Set<Class<? extends OptimizationStrategy>> applyPrior() {
public static FilterRankingStrategy instance() {
return INSTANCE;
}
+
+ /**
+ * Get steps of the specified class throughout the traversal and grouping them based on the traversal parent
+ * collecting them in a fashion that orders them from the deepest steps first
+ */
+ public static List<Pair<TraversalParent, List<Step<?,?>>>> collectStepsOfAssignableClassRecursivelyFromDepthGroupedByParent(
+ final Traversal.Admin<?, ?> traversal, final Class<?> stepClass) {
+
+ final List<Pair<TraversalParent, List<Step<?,?>>>> collectionList = new ArrayList<>();
+ final Stack<Step<?,?>> stack = new Stack<>();
Review Comment:
nit: not informative variable names. may be something like `unprocessedSteps` will be better?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Avoiding expensive hash computation in filter ranking strategy [tinkerpop]
Posted by "vkagamlyk (via GitHub)" <gi...@apache.org>.
vkagamlyk commented on PR #2504:
URL: https://github.com/apache/tinkerpop/pull/2504#issuecomment-1979502367
Thank you @steigma!
VOTE +1
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Avoiding expensive hash computation in filter ranking strategy [tinkerpop]
Posted by "steigma (via GitHub)" <gi...@apache.org>.
steigma commented on code in PR #2504:
URL: https://github.com/apache/tinkerpop/pull/2504#discussion_r1512759971
##########
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategyCacheInitializationTest.java:
##########
@@ -0,0 +1,449 @@
+/*
+ * 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.traversal.strategy.optimization;
+
+import org.apache.tinkerpop.gremlin.process.traversal.Step;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.DefaultGraphTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.step.LambdaHolder;
+import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep;
+import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
+import org.apache.tinkerpop.gremlin.util.function.Lambda;
+import org.javatuples.Pair;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.where;
+
+/**
+ * Testing whether the cache for the FilterRankingStrategy is correctly initialized,
+ * which includes gathering/collecting the traversal parents and their children steps
+ * in the correct deep first manner.
+ */
+@RunWith(JUnit4.class)
+public class FilterRankingStrategyCacheInitializationTest {
+
+
+ @Test
+ public void test_collection_lambda_nested() {
+ // traversal
+ final Traversal<?, ?> traversal = __.V().as("n").
+ where(
+ __.or(
+ __.select("n").hasLabel("software"),
+ __.select("n").map(Lambda.function("it.get().out()"))
+ )
+ ).
+ select("n").by("name");
+
+ // expected order of traversal parents
+ final List<Traversal<?, ?>> collectedTraversalParents = Arrays.asList(
+ __.or(
+ __.select("n").hasLabel("software"),
+ __.select("n").map(Lambda.function("it.get().out()"))
+ ),
+ __.where(
+ __.or(
+ __.select("n").hasLabel("software"),
+ __.select("n").map(Lambda.function("it.get().out()"))
+ )
+ ));
+
+ // cache entries
+ final List<Pair<Boolean, Set<String>>> expectedTraversalParentCacheEntries = Arrays.asList(
+ new Pair<>(true, new HashSet<>(Collections.emptyList())),
Review Comment:
It is not necessary. I removed it in the new revision. Also changed some arguments to Optional to make it clear that they do not need to be provided (where we then just compare with the old cache initialization method).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Avoiding expensive hash computation in filter ranking strategy [tinkerpop]
Posted by "steigma (via GitHub)" <gi...@apache.org>.
steigma commented on code in PR #2504:
URL: https://github.com/apache/tinkerpop/pull/2504#discussion_r1512756366
##########
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategyCacheInitializationTest.java:
##########
@@ -0,0 +1,449 @@
+/*
+ * 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.traversal.strategy.optimization;
+
+import org.apache.tinkerpop.gremlin.process.traversal.Step;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.DefaultGraphTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.step.LambdaHolder;
+import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep;
+import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
+import org.apache.tinkerpop.gremlin.util.function.Lambda;
+import org.javatuples.Pair;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.where;
+
+/**
+ * Testing whether the cache for the FilterRankingStrategy is correctly initialized,
+ * which includes gathering/collecting the traversal parents and their children steps
+ * in the correct deep first manner.
+ */
+@RunWith(JUnit4.class)
+public class FilterRankingStrategyCacheInitializationTest {
+
+
+ @Test
+ public void test_collection_lambda_nested() {
Review Comment:
Not completely sure what you mean, but I tried to improve the names of the test cases.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Avoiding expensive hash computation in filter ranking strategy [tinkerpop]
Posted by "vkagamlyk (via GitHub)" <gi...@apache.org>.
vkagamlyk commented on code in PR #2504:
URL: https://github.com/apache/tinkerpop/pull/2504#discussion_r1513178457
##########
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategyCacheInitializationTest.java:
##########
@@ -0,0 +1,449 @@
+/*
+ * 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.traversal.strategy.optimization;
+
+import org.apache.tinkerpop.gremlin.process.traversal.Step;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.DefaultGraphTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.step.LambdaHolder;
+import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep;
+import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
+import org.apache.tinkerpop.gremlin.util.function.Lambda;
+import org.javatuples.Pair;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.where;
+
+/**
+ * Testing whether the cache for the FilterRankingStrategy is correctly initialized,
+ * which includes gathering/collecting the traversal parents and their children steps
+ * in the correct deep first manner.
+ */
+@RunWith(JUnit4.class)
+public class FilterRankingStrategyCacheInitializationTest {
+
+
+ @Test
+ public void test_collection_lambda_nested() {
Review Comment:
test naming convention is camelCase and `shouldDescribeWhatTestDo`.
please look at the names of other tests
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Avoiding expensive hash computation in filter ranking strategy [tinkerpop]
Posted by "vkagamlyk (via GitHub)" <gi...@apache.org>.
vkagamlyk commented on code in PR #2504:
URL: https://github.com/apache/tinkerpop/pull/2504#discussion_r1507068313
##########
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/FilterRankingStrategyCacheInitializationTest.java:
##########
@@ -0,0 +1,449 @@
+/*
+ * 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.traversal.strategy.optimization;
+
+import org.apache.tinkerpop.gremlin.process.traversal.Step;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.DefaultGraphTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.step.LambdaHolder;
+import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep;
+import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
+import org.apache.tinkerpop.gremlin.util.function.Lambda;
+import org.javatuples.Pair;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.where;
+
+/**
+ * Testing whether the cache for the FilterRankingStrategy is correctly initialized,
+ * which includes gathering/collecting the traversal parents and their children steps
+ * in the correct deep first manner.
+ */
+@RunWith(JUnit4.class)
+public class FilterRankingStrategyCacheInitializationTest {
+
+
+ @Test
+ public void test_collection_lambda_nested() {
Review Comment:
nit: test name
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Avoiding expensive hash computation in filter ranking strategy [tinkerpop]
Posted by "Cole-Greer (via GitHub)" <gi...@apache.org>.
Cole-Greer commented on PR #2504:
URL: https://github.com/apache/tinkerpop/pull/2504#issuecomment-1961841550
I agree with @vkagamlyk that some additional tests would be beneficial here. It is quite hard to prove that `collectStepsOfAssignableClassRecursivelyFromDepthGroupedByParent()` does not effect the order of the resulting map in a meaningful way through reasoning alone. I would also be curious to know how substantial the performance difference can be in a "worst case" scenario with hundreds of child steps.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Avoiding expensive hash computation in filter ranking strategy [tinkerpop]
Posted by "kenhuuu (via GitHub)" <gi...@apache.org>.
kenhuuu commented on PR #2504:
URL: https://github.com/apache/tinkerpop/pull/2504#issuecomment-1977710799
I don't completely follow the changes being made here but they seem to be well tested so my VOTE is +1.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Avoiding expensive hash computation in filter ranking strategy [tinkerpop]
Posted by "Cole-Greer (via GitHub)" <gi...@apache.org>.
Cole-Greer commented on PR #2504:
URL: https://github.com/apache/tinkerpop/pull/2504#issuecomment-1979511823
Thanks @steigma, the new tests LGTM. VOTE +1
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tinkerpop.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org