Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8282043

IGV: speed up schedule approximation

XMLWordPrintable

    • Icon: Enhancement Enhancement
    • Resolution: Fixed
    • Icon: P4 P4
    • 19
    • 19
    • hotspot
    • b18

      Schedule approximation for clustering and showing the control-flow graph is an expensive computation that can take as much time as computing the layout of a graph and rendering it.

      A preliminary study on a large graph (attached) shows that the majority of schedule approximation time is spent pre-computing the common dominators (getCommonDominator(b1, b2)) of all pairs of blocks, while the core of the scheduling algorithm (scheduleLatest()) only typically requires knowing a small subset of these.

      Calling getCommonDominator() directly in scheduleLatest() instead of fetching pre-computed results speeds up the schedule approximation of the large graph attached by around 20x, from ~4s to ~200ms. This is because the graph has 1309 blocks, so pre-computation performs 1713481 calls to getCommonDominator() (no. blocks x no. blocks), but then it is only used 14952 times by scheduleLatest().

      In the worst case, scheduleLatest() performs (no. nodes x no. nodes) calls to getCommonDominator(), but in practice it is closer to no. nodes only, because the graph is very sparse - nodes tend to have few successors.

            rcastanedalo Roberto Castaneda Lozano
            rcastanedalo Roberto Castaneda Lozano
            Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

              Created:
              Updated:
              Resolved: