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

Roberto Castañeda Lozano rcastanedalo at openjdk.org
Mon Aug 21 11:32:42 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

Looks good! I have tested the patch and checked that no major performance regression is introduced in the existing sea-of-nodes view. I only have a few minor comments about the code.

src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/Figure.java line 394:

> 392:         return getInputNode().equals(((Figure)o).getInputNode());
> 393:     }
> 394:     @Override

Nit: please insert an empty line between these two methods.

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

> 37:     public static final int X_OFFSET = 8;
> 38:     public static final int LAYER_OFFSET = 8;
> 39:     // Algorithm global datastructures

Suggestion:

    // Algorithm global data structures

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

> 123:             return values[values.length / 2];
> 124:         }
> 125:     }

This method is duplicated from `HierarchicalLayoutManager`, could you make it static and extract it into some class (or possibly a new one, e.g. `Math.java` or `Statistics.java`) in the `Util` module?

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

> 129:      * been inserted at that layer
> 130:      *
> 131:      * @param layer

No need to list the parameters if there is no associated description of each of them, in my opinion. The same holds for all other cases in this file.

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

> 154: 
> 155:     /**
> 156:      * Ensure that the datastructures nodes and layerNodes are consistent

Suggestion:

     * Ensure that the data structures nodes and layerNodes are consistent

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

> 540:     private class BuildDatastructure {
> 541: 
> 542:         // In case there are changes in the node size, it's layer must be updated

Suggestion:

        // In case there are changes in the node size, its layer must be updated

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

> 667:                 if (layers.keySet().contains(layer - 1)) {
> 668:                     List<LayoutNode> predNodes = layers.get(layer - 1);
> 669:                     // For each link with an end point in vertex, check how many edges crosses it

Suggestion:

                    // For each link with an end point in vertex, check how many edges cross it

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

> 704:                 if (layers.keySet().contains(layer + 1)) {
> 705:                     List<LayoutNode> succsNodes = layers.get(layer + 1);
> 706:                     // For each link with an end point in vertex, check how many edges crosses it

Suggestion:

                    // For each link with an end point in vertex, check how many edges cross it

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

> 1102:          * Calculate which layer the given vertex should be inserted at to minimize
> 1103:          * reversed edges and edge lengths
> 1104:          * If there are multiple options, choose the bottom most layer

Suggestion:

         * If there are multiple options, choose the bottom-most layer

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

> 1120:             int layer = -1;
> 1121:             for (int i = 0; i < layers.keySet().size(); i++) {
> 1122:                 // System.out.println("Testing layer " + i);

Please remove this line.

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

> 1531:     private class ComputeLayoutScore {
> 1532:         /**
> 1533:          * https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

Please replace this reference with a standalone comment describing the method.

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

> 1545:         /**
> 1546:          * To find orientation of ordered triplet (p, q, r).
> 1547:          * https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

Please remove this reference.

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

> 1562: 
> 1563:         /**
> 1564:          * https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

Please remove this reference.

src/utils/IdealGraphVisualizer/View/src/main/java/com/sun/hotspot/igv/view/EditorTopComponent.java line 200:

> 198: 
> 199:         diagramViewModel.getGraphChangedEvent().addListener(model -> {
> 200:             // HierarchicalStableLayoutManager is not stable for difference graphs

Perhaps use a different term than "stable" here to avoid confusion (e.g. "reliable").

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

Changes requested by rcastanedalo (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/14349#pullrequestreview-1586749389
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1299961862
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1299968734
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1299973675
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1299975429
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1299975759
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1299976753
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1299977675
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1299978015
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1299979189
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1299979475
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1299981492
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1299981974
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1299982124
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1299967688

More information about the hotspot-compiler-dev mailing list