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 30 forks source link

perf: more efficient intersection #157

Closed Eh2406 closed 7 months ago

Eh2406 commented 7 months ago

I got nerds not by https://github.com/zanieb/pubgrub/pull/6. Which points out that intersection is slower than it needs to be when the basic operations on version are expensive. Here's what I've come up with.

The ideas are:

  1. Like that PR, avoid cloning till the end
  2. Instead of using next_if and eq keep track of which iter to advance directly.
  3. Because we know which iter end came from, and we know that for each iterator start < end, check for validity before determining start
  4. Don't redundantly check e > i
branch clone to reject compares to reject clones to accept comparisons to accept
dev 2 5 2 5
zanieb/#6 0 5 2 5
this 0 2 2 3

I tested this synthetically by making a version that increasing a global counter every time eq/cmp/clone/drop is called. This global counter goes up much (~30%) less after this PR. Even on our normal benchmarks, where these operations are very cheap (a handful of CPU cycles), we see improvements (although only a few percent).

cc @konstin for real-world impact. cc @baszalmstra https://github.com/mamba-org/resolvo/issues/2#issuecomment-1744436726 I don't know if these are improvements you'd be interested in include in your copy of this type.

konstin commented 7 months ago

I tried this branch on a pathological test case and it reduced the time from 10s to 3.6s!

Eh2406 commented 7 months ago

That is wonderful to hear! As soon as this gets a review, let's get this merged!

Eh2406 commented 7 months ago

I rarely provide enough documentation or use good names for things. Always feel comfortable asking me to improve! Anything in particular you want me to clarify?

zanieb commented 7 months ago

I think basically anywhere you're doing something unintuitive for performance reasons as outlined in your bullets in the pull request summary you'd benefit from adding a comment explaining what's going on e.g.

// We can conclude e > i and do not check again for perf

Eh2406 commented 7 months ago

Here's a small dissertation. Let me know if any of it made sense.

Eh2406 commented 7 months ago

If people think of improvements to the documentation I added, PR's are welcome. So I'm going to merge.