Stuck or slow with big graph

[gratianlup]

Hi,

Wanted to compare the perf. of your lib with Graphviz dot on some examples where dot is really slow at making the layout. The DOT file I tried may have hit either a bug in the lib, or there is some algorithm that is slow.

The input file has around 700 nodes and at least that many edges - it's the CFG of a function being optimized by MSVC. With Graphviz, dot took 1m 52s to complete. layout after >10 min is still not done. Built it on a Mac and took with the Process monitor several samples, all seem to be similar, with this deep call tree showing up each time. Build is done in release mode.

2330 layout::topo::layout::VisualGraph::do_it::h4815c5196694548a (in run) + 181 [0x104ef6fd5] 2330 layout::topo::layout::VisualGraph::to_valid_dag::hd5e8ba77059eb154 (in run) + 1129 [0x104ef7a19] 2330 layout::adt::dag::DAG::verify::h0fcd6cdb9de61321 (in run) + 406 [0x104eec266] 2330 layout::adt::dag::DAG::is_reachable_inner::h765e6031c3bd508a (in run) + 152 [0x104eec488] 2330 layout::adt::dag::DAG::is_reachable_inner::h765e6031c3bd508a (in run) + 152 [0x104eec488] 2330 layout::adt::dag::DAG::is_reachable_inner::h765e6031c3bd508a (in run) + 152 [0x104eec488] and lots more calls to is_reachable_inner

Sharing the input DOT file here: https://gist.github.com/gratianlup/f51dd6efc7ebc314d12a317dd0b01c60

And the sampling summary with the call graph here: https://gist.github.com/gratianlup/8e7d8fd3c9883108ba9e55a87f0464eb

Thanks, Gratian

[webbiscuit]

It seems to sometimes get stuck in an infinite loop (I think complex graphs cause it to double back on itself too many times). I removed this line: visited[from.idx] = false; and is_reachable_innercan then eventually return.

[s0l0ist]

If you just want to render the graph and don't need a library, try www.vizdom.dev

Tested on my M1 mac and it renders it in roughly a second.

Only downside is that the URL becomes too long after you've pasted in the graph and you'll get a 414 if you refresh the page.

Here's the downloaded rendering:

[xenon]

I got the test file to render. It took over an hour on my machine even with some changes to speed it up.

Changes made to get compile to work:

• In the VisualGraph::to_valid_dag loop remove self.dag.verify() call
• In VisualGraph::split_long_edges remove self.dag.verify() call
• When running VisualGraph::do_it set disable_opt parameter to true

Where the code is spending a lot of time bug not hanging

• Scheduler::schedule called in BK::do_it repeatedly calling self.is_vertical_ready and self.place_vertical in a loop seems to take a long time per iteration and requires thousands of iterations. This part takes over an hour. Seems to have an O(n^3) or slower operation.
• split_long_edges: takes around 10 seconds
• Scheduler::schedule loop of Scheduler::verify_vertical takes a few seconds

The issue

• The recursion in is_reachable_inner has an infinite loop because of the final visited[from.idx] = false;
• After removing this line the function seems to finish in a reasonable amount of time.
• Scheduler::schedule takes a really long time

The output svg

[jamisonjiang]

If you just want to render the graph and don't need a library, try www.vizdom.dev

Tested on my M1 mac and it renders it in roughly a second.

Only downside is that the URL becomes too long after you've pasted in the graph and you'll get a 414 if you refresh the page.

Here's the downloaded rendering:

Excellent work, do you know any related background of this project?