search

pubgrub-rs / pubgrub

PubGrub version solving algorithm implemented in Rust
https://pubgrub-rs.github.io/pubgrub/pubgrub/
Mozilla Public License 2.0
337 stars 29 forks source link

feat!: no recursion and Rc for causes #184

Closed Eh2406 closed 4 months ago

Eh2406 commented 5 months ago

The existing code for generating a derivation tree had two performance pathologies.

Because derivations have reused subtrees (i.e. shared IDs) they are really more like DAGs then proper trees. Nonetheless the current API ignores the sharing and built a separate (Box) for each of these repeated sections of the output. By using shared ownership (Rc) for the shared IDs we can reduce the generation time and memory use for these complicated cases.

Because we generated derivation trees recursively, the stack memory usage was O(tree_depth). When dealing with complicated test cases that use larger Vs, it is quite possible to overflow the stack. There are probably ways to reduce the constant factors to make this problem even harder to come across, and I will need to investigate them if this PR is not accepted. But this PR solved the problem by simply removing the recursion.

This is a breaking change because the switch from Box to Rc is visible in our public API.

This is split up into several commits, each of one of which should be reviewable on its own.

zanieb commented 4 months ago

Send may actually may be important to use since we work in an async context

Eh2406 commented 4 months ago

Moved from Rc -> Arc. I doubt the perf will ever matter, and it helps you.