Memory explosion on some projects

[Runi-c]

Tried to use this on the Bevy project like so:

stacktower parse rust bevy -o bevy.json
stacktower render bevy.json -t tower -o bevy.svg

and it pretty much instantly OOMs my machine. Someone else tried it and found stacktower tries to acquire upwards of 300gb of memory.

[matzehuels]

That doesn't sound good! Will check it out. How many nodes in bevy?

[Runi-c]

Here's the output before the OOM:

22:18:05.25 INFO Rendering bevy.json
22:18:05.25 INFO Loaded graph: 97 nodes, 219 edges
22:18:05.25 INFO Normalized: 336 nodes (+239), 384 edges
22:18:05.25 INFO Computing tower layout using optimal ordering

[matzehuels]

Try the barycenter heuristic instead of optimal search (see readme).

Need to investigate why search has issues with larger graphs.

[matzehuels]

Root Cause
In pqtree.go, childPermutations generates ALL permutations for P-nodes before checking limits:

indexPerms := Generate(len(node.children), -1)  // -1 = no limit!

When a PQ-tree has a P-node with many unconstrained children (common in sparse graphs like Bevy's), it tries to materialize n! permutations before Enumerate's limit kicks in.

Why Bevy Triggers This
Bevy's dependency graph is "wide and shallow", many sibling crates at the same depth with few inter-dependencies. After subdivider insertion (343 nodes), some layers likely have 15+ nodes sharing a common parent in the PQ-tree. That P-node triggers: 15 children → 1.3 trillion allocations

Fix
Make childPermutations lazy/streaming

--> Unfortunately, the tower for bevy doesn't look great after 1 minute of search, it probably needs much longer. At least the memory issue is fixed.