Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Fix bug where original order is not respected in some cases #335

Closed
wants to merge 1 commit into from

Conversation

scottyantipa
Copy link

@scottyantipa scottyantipa commented Nov 19, 2022

Fixes #336

This fix accomplishes two things:

  1. This fixes a layout bug where some graphs will have an incorrect node ordering. This happens because the original ordering is already optimal (zero crosses) but the cross minimization in order/index.js will permute the nodes several times anyways even though it can't decrease the cross count.

  2. This is a perf optimization. If cross count gets to 0 then we should stop the loop. I noticed that running make bench shows an increase in the ops/sec for the order phase of around 700 to 840.

Note that this breaks atleast one case of compound graphs (the failing tests) and I'm not entirely sure why compound graphs are required to go through the sweepLayer pass in order to get a proper layout. It seems that the cross minimization should be separated from the compound graph layout. I did notice that moving the cross minimization check to within the for-loop (after sweepLayer) fixes the test. That may be one possible fix and I'll put up a separate PR. However, it does not fix the original bug that I was trying to fix.

Before:
console-repro-bad

After:
console-show-fix

Perf before:

          longest-path ranker:    469,894.67 ops/sec ± 0.12% ( 94 run(s) sampled)
            tight-tree ranker:    125,875.60 ops/sec ± 0.08% (101 run(s) sampled)
       network-simplex ranker:     26,225.72 ops/sec ± 0.13% ( 95 run(s) sampled)
                       layout:        707.90 ops/sec ± 1.39% ( 86 run(s) sampled)

Perf after:

          longest-path ranker:    462,488.92 ops/sec ± 0.14% ( 95 run(s) sampled)
            tight-tree ranker:    125,875.39 ops/sec ± 0.09% ( 98 run(s) sampled)
       network-simplex ranker:     26,180.47 ops/sec ± 0.18% ( 97 run(s) sampled)
                       layout:        847.17 ops/sec ± 1.26% ( 87 run(s) sampled)

The main issue with this fix is that it breaks compound graph layout. It breaks a unit test, and I confirmed by rendering the graph from that unit test using test/console.html.
Screen Shot 2022-11-18 at 3 07 34 PM

The test is layout-test.js: can layout subgraphs with different rankdirs. And the graph looks like:

    g.setNode("a", { width: 50, height: 50 });
    g.setNode("sg", {});
    g.setParent("a", "sg");

I'm not familiar enough with the compound graph layout additions to order.js to know if its actually essential that we run the cross minimization iterations in order to layout compound graphs, or if there's a way to do what we need for compound graphs but still return early if cross count is 0 before doing all those iterations. I'm going to look at putting up another PR that tries to meet in the middle by returning early after 1 iteration, which I think fixes compound graph layout but also gives perf benefits of not running all the iterations.

This is both a bug fix in the order pass, as well as a perf
optimization. If the cross count is already zero from the original
ordering then there's no need to run the cross minimization steps.

1. This fixes a layout bug where some graphs will have an incorrect node
   ordering. This happens because the original ordering is already
   optimal (zero crosses) but the cross minimization in order/index.js
   will permute the nodes several times anyways even though it can't
   decrease the cross count.

2. This is a perf optimization. If cross count gets to 0 then we should
   stop the loop. I noticed that running `make bench` shows an increase
   in the ops/sec for the order phase of around 700 to 840.

Note that this breaks atleast one case of compound graphs (the failing
tests) and I'm not entirely sure why compound graphs are required to go
through the sweepLayer pass in order to get a proper layout. It seems
that the cross minimization should be separated from the compound graph
layout. I did notice that moving the cross minimization check to within
the for-loop (after sweepLayer) fixes the test. That may be one possible
fix and I'll put up a separate PR. However, it does not fix the original
bug that I was trying to fix.
@scottyantipa scottyantipa changed the title Order: Return early in order/index.js if cross count is 0 Fix bug where original order is not respected in some cases Nov 19, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Original ordering is not respected in some cases when cross-count is already 0
1 participant