liyafan82 commented on a change in pull request #1832: [CALCITE-3827] Reduce
the time complexity of finding in-edges of a vertex in the graph
URL: https://github.com/apache/calcite/pull/1832#discussion_r384953180
##########
File path:
core/src/main/java/org/apache/calcite/util/graph/DefaultDirectedGraph.java
##########
@@ -110,8 +122,8 @@ public E addEdge(V vertex, V targetVertex) {
public E getEdge(V source, V target) {
// REVIEW: could instead use edges.get(new DefaultEdge(source, target))
- final VertexInfo<V, E> info = vertexMap.get(source);
- for (E outEdge : info.outEdges) {
+ final VertexInfo<V, E> info = vertexOutMap.get(source);
+ for (E outEdge : info.edges) {
if (outEdge.target.equals(target)) {
Review comment:
@chunweilei I have added a benchmark to measure performance difference. It
uses a 8-level binary tree as the graph. The results show that the change
significantly improves the performance:
Before:
Benchmark Mode Cnt Score
Error Units
DefaultDirectedGraphBenchmark.getInwardEdgesBenchmark avgt 25 21.663 ±
0.956 us/op
After:
Benchmark Mode Cnt Score
Error Units
DefaultDirectedGraphBenchmark.getInwardEdgesBenchmark avgt 25 0.073 ±
0.001 us/op
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
[email protected]
With regards,
Apache Git Services
