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