search

pubgrub-rs / pubgrub

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

Use smallvec for unit propagation buffer #90

Closed mpizenberg closed 3 years ago

mpizenberg commented 3 years ago

It occurred to me while reading your last PR that the unit propagation buffer follows most of the time a succession of push/pop, making it rather small during most operations. So I tried using SmallVec for it and I seem to be getting roughly 10% perf improvements on the elm and synthetic benchmarks. Let me know if you get the same.

The one thing that's a bit annoying me is that I didn't handle the case when pop should make the small vec not a Vec anymore. I didn't do it both because I was lazy, and because I thought it would prevent the optimization of having that vec only allocated once (but I didn't check).

Eh2406 commented 3 years ago

I found a bug, I am a little troubled that our existing tests did not find it, but it is fix and tested now. I also tried doubling down on only allocating the vec once, by adding a clear method to hang on to the vec once we have it. All tolled I am seeing 8% on elm, 13% on synthetic, and 2% on zule. So it looks good to me!

mpizenberg commented 3 years ago

Woops, thanks for spotting that!

Eh2406 commented 3 years ago

Had to fix the commit message, after merge. Sorry for the noise.