[
https://issues.apache.org/jira/browse/CALCITE-3827?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17078448#comment-17078448
]
Julian Hyde commented on CALCITE-3827:
--------------------------------------
I ran some benchmarks. All on JDK 11.
In the {{Benchmark}} column below, {{removeAllVertices10}} is short-hand for
{{DefaultDirectedGraphBenchmark.removeAllVertices10}}, a test which removes 10%
of vertices from the graph, and similarly for 20, ... 90.
1. Using the 'minority' algorithm
{noformat}
Benchmark Mode Cnt Score Error Units
removeAllVertices10 avgt 25 2.218 ± 0.045 us/op
removeAllVertices20 avgt 25 4.513 ± 0.065 us/op
removeAllVertices30 avgt 25 6.942 ± 0.253 us/op
removeAllVertices40 avgt 25 8.899 ± 0.338 us/op
removeAllVertices50 avgt 25 10.954 ± 0.124 us/op
removeAllVertices60 avgt 25 12.872 ± 0.974 us/op
removeAllVertices70 avgt 25 11.965 ± 0.099 us/op
{noformat}
2. Using the 'minority' algorithm, converting Collection to HashSet
{noformat}
Benchmark Mode Cnt Score Error Units
removeAllVertices10 avgt 25 2.742 ± 0.038 us/op
removeAllVertices20 avgt 25 5.427 ± 0.073 us/op
removeAllVertices30 avgt 25 8.264 ± 0.272 us/op
removeAllVertices40 avgt 25 10.779 ± 0.318 us/op
removeAllVertices50 avgt 25 13.691 ± 0.302 us/op
removeAllVertices60 avgt 25 15.137 ± 0.210 us/op
removeAllVertices70 avgt 25 16.558 ± 0.283 us/op
removeAllVertices80 avgt 25 17.522 ± 0.488 us/op
removeAllVertices90 avgt 25 19.306 ± 0.588 us/op
removeAllVertices100 avgt 25 19.968 ± 0.366 us/op
{noformat}
3. Using the 'majority' algorithm
{noformat}
Benchmark Mode Cnt Score Error Units
removeAllVertices10 avgt 25 18.262 ± 0.598 us/op
removeAllVertices20 avgt 25 25.580 ± 0.636 us/op
removeAllVertices30 avgt 25 30.749 ± 7.329 us/op
removeAllVertices40 avgt 25 25.266 ± 0.629 us/op
removeAllVertices50 avgt 25 19.088 ± 0.540 us/op
removeAllVertices60 avgt 25 16.034 ± 0.090 us/op
removeAllVertices70 avgt 25 13.966 ± 0.497 us/op
{noformat}
4. Using the 'majority' algorithm, converting Collection to HashSet
{noformat}
Benchmark Mode Cnt Score Error Units
removeAllVertices10 avgt 25 7.926 ± 0.173 us/op
removeAllVertices20 avgt 25 7.934 ± 0.208 us/op
removeAllVertices30 avgt 25 7.863 ± 0.117 us/op
removeAllVertices40 avgt 25 8.096 ± 0.182 us/op
removeAllVertices50 avgt 25 8.229 ± 0.209 us/op
removeAllVertices60 avgt 25 8.445 ± 0.142 us/op
removeAllVertices70 avgt 25 8.234 ± 0.220 us/op
removeAllVertices80 avgt 25 8.939 ± 0.252 us/op
removeAllVertices90 avgt 25 9.404 ± 0.492 us/op
removeAllVertices100 avgt 25 8.646 ± 0.142 us/op
{noformat}
>From the above 4 runs, I concluded that it is worth converting Collection to a
>HashSet for the 'majority' algorithm, and that the 'majority' algorithm should
>be used if collection contains more than 35% of the vertices in the graph.
5. Hybrid (if collection contains more than 35% of vertices, convert it to a
HashSet and use the 'majority' algorithm)
{noformat}
Benchmark Mode Cnt Score Error Units
removeAllVertices10 avgt 25 2.367 ± 0.062 us/op
removeAllVertices20 avgt 25 4.606 ± 0.130 us/op
removeAllVertices30 avgt 25 6.867 ± 0.378 us/op
removeAllVertices40 avgt 25 8.322 ± 0.365 us/op
removeAllVertices50 avgt 25 7.950 ± 0.388 us/op
removeAllVertices60 avgt 25 8.235 ± 0.146 us/op
removeAllVertices70 avgt 25 8.800 ± 0.297 us/op
removeAllVertices80 avgt 25 8.954 ± 0.297 us/op
removeAllVertices90 avgt 25 9.410 ± 0.233 us/op
removeAllVertices100 avgt 25 9.057 ± 0.257 us/op
{noformat}
> Reduce the time complexity of finding in-edges of a vertex in the graph
> -----------------------------------------------------------------------
>
> Key: CALCITE-3827
> URL: https://issues.apache.org/jira/browse/CALCITE-3827
> Project: Calcite
> Issue Type: Improvement
> Components: core
> Reporter: Liya Fan
> Assignee: Julian Hyde
> Priority: Major
> Labels: pull-request-available
> Time Spent: 2h 40m
> Remaining Estimate: 0h
>
> In the current graph implementation, it takes O(1) time to find the out-edges
> of a vertex, but O(e) time (where e is the total number of edges in the
> graph) to find the in-edges of a vertex.
> In some scenarios (e.g. clearing cache in hep planner), this may have severe
> performance penalty. To solve this problem, we add a inward edge table, in
> addition to the existing outward edge table, to the graph. This helps to
> reduce the time complexity for finding in-edges to O(1).
> Please note that, there is extra performance overhead for maintaining the in
> edge table, when adding/deleting vertices to the graph. However, the added
> overhead only takes O(1) time.
> Finally, it should be noted that, some existing operations can benefit from
> this improvement (e.g. topological sort).
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
