RFR: 8309463: IGV: Dynamic graph layout algorithm [v7]

Tue Aug 22 13:14:44 UTC 2023

On Fri, 18 Aug 2023 17:26:18 GMT, emmyyin <duke at openjdk.org> wrote:

>> ### Purpose
>> 
>> IGV currently uses a static layout algorithm to visualize graphs. However, this is problematic due to the use cases of IGV. Most often, the graphs that are visualized are dynamic, meaning the graphs change over time. A dynamic graph can be thought of as a sequence of graphs where a given graph in the sequence is the state of the dynamic graph at that point in time. Static layout algorithms do not account for the rest of the sequence when visualizing a given graph. On one hand, it makes each layout more readable. But on the other hand, the layout for two consecutive graphs in the sequence can be vastly different even though the difference between the graphs is small. This makes it difficult to identify the changes that has occurred to the graph and can damage the internal understanding of the graph that the viewer has obtained. A dynamic layout algorithm takes the changes into account when visualizing a graph. To enhance IGV, such an algorithm has been implemented in this PR.
>> 
>> The layout drawn by the static layout algorithm is called "sea of nodes", while the layout drawn by the dynamic algorithm is called "stable sea of nodes".
>> 
>> The difference between the algorithms is illustrated in the following video:
>> 
>> 
>> https://github.com/openjdk/jdk/assets/52547536/35023362-a191-425e-b066-c7474db631f1
>> 
>> 
>> This work is the result of my Master's thesis which can be found [here](https://kth.diva-portal.org/smash/get/diva2:1770643/FULLTEXT01.pdf).
>> 
>> 
>> ### Implementation
>> 
>> The algorithm is based on update actions that are applied incrementally to a graph layout in order to obtain the layout of the next graph in the sequence. By doing so, the nodes that appears in both graphs remain in their relative positions. A new layout manager called `HierarchicalStableLayoutManager` has been added which holds the core algorithm. The corresponding layout manager with the static layout algorithm is called `HierarchicalLayoutManager`.
>> 
>> If no layouts have been drawn yet, the `HierarchicalLayoutManager` is used. This is because the dynamic algorithm needs an initial layout to apply the update actions on.
>> 
>> The whole graph is represented by `LayoutNode` and `LayoutEdge` objects, that holds the positions of the nodes and edges along with other relevant information such as ID, name and size. These are updated, added and removed in accordance with the update actions.
>> 
>> Since `HierarchicalStableLayoutManager` tries to preserve the node positi...
>
> emmyyin has updated the pull request incrementally with one additional commit since the last revision:
> 
>   fixing trailing ws

Great work Emmy! I've played around with some graphs and it works quite well for small sets of nodes.

While clicking around in IGV, I've noticed that sometimes it takes a long time to open a new graph. 

Example:
1. Open IGV
2. Run: `java -XX:CompileOnly=*::putUTF8 -XX:+PrintIdealGraph -XX:PrintIdealGraphLevel=3 HelloWorld.java`
3. Open the graph `PhaseCCP1` of the `putUTF8` compilation.
4. Switch to `stable sea of nodes` layout.
5. Open the graph `Before RemoveUseless` -> hangs for ~1min

I've had a closer look at that example with a profiler and it seems that over 90% of the time is spent in `sanityCheckNodesAndLayerNodes()` (~66%) and `sanityCheckEdges()` (~25%) which seems quite a lot for just sanity checks. @robcasloz double checked the example and then ran the same steps from above with the two sanity check methods disabled. On his machine, the time went down from 64s to 2s which is a huge improvement. 

We therefore suggest to either completely disable sanity checking with these two methods or limit it to a few places (not sure how easy that is). If we disable it, we could still think about sanity checking with them in IGV unit tests only.

I'm not very familiar with the IGV code base, so I only have some more general code comments.

Thanks,
Christian

src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalStableLayoutManager.java line 77:

> 75:     }
> 76: 
> 77:     private class LinkAction {

Can be made static:
Suggestion:

    private static class LinkAction {

src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalStableLayoutManager.java line 97:

> 95:     }
> 96: 
> 97:     private int calculateOptimalBoth(LayoutNode n) {

`calculateOptimalBoth()` in `HierarchicalLayoutManager` is now ununsed and can be removed.

src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalStableLayoutManager.java line 98:

> 96: 
> 97:     private int calculateOptimalBoth(LayoutNode n) {
> 98:         if (n.preds.size() == 0 && n.succs.size() == 0) {

Suggestion:

        if (n.preds.isEmpty() && n.succs.isEmpty()) {

There are also other locations where you can replace `size() >/== 0` by `!empty()/empty()`.

src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalStableLayoutManager.java line 189:

> 187:                     assert e.to.layer == n.layer + 1;
> 188:                 } else {
> 189:                     n.succs.remove(e);

This removal and the one in the next loop seem unexpected being in a sanity check method where the expectation would be to only query and not modify. Do we really need these removals for the correctness of the algorithm?

src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalStableLayoutManager.java line 265:

> 263:             if (!addedVertices.contains(to) && !addedVertices.contains(from)) {
> 264:                 linkActions.add(a);
> 265:             }

This code looks identical to the code on L269-281. Could this be shared?

src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalStableLayoutManager.java line 454:

> 452:      */
> 453:     private void copyOldNodes() {
> 454:         oldNodes.clear();

Is `oldNodes` a leftover? It does not seem to be used.

src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalStableLayoutManager.java line 511:

> 509:             if (shouldComputeLayoutScore) {
> 510:                 new ComputeLayoutScore().run();
> 511:             }

Since `shouldCompuateLayoutScore` is always false, do we still need this code?

src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalStableLayoutManager.java line 757:

> 755:          */
> 756:         private void insertNode(LayoutNode node, int layer) {
> 757:             assert layers.keySet().contains(layer) || layer == 0;

Suggestion:

            assert layers.containsKey(layer) || layer == 0;

There are also other locations where you could replace `keySet().contains()` with `containsKey()`.

src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalStableLayoutManager.java line 807:

> 805:             n.preds.add(result);
> 806:             result.to = n;
> 807:             result.relativeTo = n.width / 2;

`n.width` equals `DUMMY_WIDTH` here which is 1. `n.width / 2` is therefore always zero. Is it intended to set `result.relativeTo` and `e.relativeFrom` to zero? Same further down in `expandNewLayerBeneath()`.

src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalStableLayoutManager.java line 1450:

> 1448:         }
> 1449: 
> 1450:         public void insert(LayoutNode n, int pos) {

This method and also other code is duplicated from `HierarchicalLayoutManager`. Could the code be shared somehow?

-------------

PR Review: https://git.openjdk.org/jdk/pull/14349#pullrequestreview-1589076106
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1301423595
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1301428472
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1301424349
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1301476336
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1301421264
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1301419240
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1301416659
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1301514857
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1301513317
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1301532721