Re:Show HN: A Graphviz Implementation in Rust
by fibonacci112358 on Thursday March 17, 2022 @06:13PM
(#30716440)
How is performance compared to Graphviz?
There are some large compiler Control flow graphs with 500+ nodes where Graphviz really starts to take a long time to build a layout (dozens of seconds or worse). Profiling dot a bit, saw that most time was spent doing some DFS, and a lot of the data structs seem to be linked lists, the opposite of cache friendly.
[ Parent
| on HN ]
Re:Show HN: A Graphviz Implementation in Rust
by graphviz on Thursday March 17, 2022 @10:10PM
(#30718044)
That DFS is in the network simplex algorithm that solves node coordinates.
Some nice clever person could probably code up that clever algorithm of Brandes and Köpf, https://link.springer.com/chapter/10.1007/3-540-45848-4_3
Some nice clever person could probably replace our 1990s-style network simplex solver with something that takes advantage of multiple CPU cores, too.