RFR: 8282043: IGV: speed up schedule approximation
Roberto Castañeda Lozano
rcastanedalo at openjdk.java.net
Wed Mar 30 11:50:10 UTC 2022
Schedule approximation for building the _clustered sea-of-nodes_ and _control-flow graph_ views is an expensive computation that can sometimes take as much time as computing the layout of the graph itself. This change removes the main bottleneck in schedule approximation by computing common dominators on-demand instead of pre-computing them.
Pre-computation of common dominators requires _(no. blocks)^2_ calls to `getCommonDominator()`. On-demand computation requires, in the worst case, _(no. Ideal nodes)^2_ calls, but in practice the number of calls is linear due to the sparseness of the Ideal graph, and the change speeds up scheduling by more than an order of magnitude (see details below).
#### Testing
##### Functionality
- Tested manually the approximated schedule on a small selection of graphs.
- Tested automatically that scheduling and viewing thousands of graphs in the _clustered sea-of-nodes_ and _control-flow graph_ views does not trigger any assertion failure (by instrumenting IGV to schedule and view graphs as they are loaded and running `java -Xcomp -XX:-TieredCompilation -XX:PrintIdealGraphLevel=4`).
##### Performance
Measured the scheduling time for a selection of 100 large graphs (2511-7329 nodes). On average, this change speeds up scheduling by more than an order of magnitude (15x), where the largest improvements are seen on the largest graphs. The performance results are [attached](https://github.com/openjdk/jdk/files/8380091/performance-evaluation.ods) (note that each measurement in the sheet corresponds to the median of ten runs).
-------------
Commit messages:
- Do not precompute common dominators
Changes: https://git.openjdk.java.net/jdk/pull/8037/files
Webrev: https://webrevs.openjdk.java.net/?repo=jdk&pr=8037&range=00
Issue: https://bugs.openjdk.java.net/browse/JDK-8282043
Stats: 24 lines in 1 file changed: 0 ins; 22 del; 2 mod
Patch: https://git.openjdk.java.net/jdk/pull/8037.diff
Fetch: git fetch https://git.openjdk.java.net/jdk pull/8037/head:pull/8037
PR: https://git.openjdk.java.net/jdk/pull/8037
More information about the build-dev
mailing list