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

perf: don't reuse the same incompatibility repeatedly #88

Closed Eh2406 closed 3 years ago

Eh2406 commented 3 years ago

This includes #87, the only new part is the last commit. It is intended to be merged after it.

Most of the time relation for an incompatibility (like A depends on B) is called at least twice, once when A gets added and when B gets added. After the first call we get AlmostSatisfied and change the partial_solution so that it will be contradicted the next time. This adds a HashSet to keep track of all the IncompIds we know will stay contradicted until the next backtrack. IncompId are just a small integer so hash very quickly.

It is possible to figure out witch IncompIds are still used after a backtrack, but so far nothing that is pulls its weight. 

Warning: Unable to complete 100 samples in 20.0s. You may wish to increase target time to 23.6s, or reduce sample count to 80.
large_cases/elm_str_SemanticVersion.ron
                        time:   [244.05 ms 244.40 ms 244.79 ms]
                        change: [-9.0431% -8.8780% -8.7172%] (p = 0.00 < 0.05)
                        Performance has improved.
large_cases/large_case_u16_NumberVersion.ron
                        time:   [9.3124 ms 9.3213 ms 9.3302 ms]
                        change: [-13.284% -13.164% -13.049%] (p = 0.00 < 0.05)
                        Performance has improved.
Benchmarking large_cases/zuse_str_SemanticVersion.ron: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 20.0s. You may wish to increase target time to 35.2s, or reduce sample count to 50.
large_cases/zuse_str_SemanticVersion.ron
                        time:   [351.46 ms 351.77 ms 352.08 ms]
                        change: [-12.531% -12.418% -12.310%] (p = 0.00 < 0.05)
                        Performance has improved.
Eh2406 commented 3 years ago

There are more complicated structures that can support backtracking or filter out items faster than a HashSet.contains, but this was a simple change with a significant perf improvement. Love to play with a bigger PR, but only after the Range Trait.

Eh2406 commented 3 years ago

@mpizenberg Yes, No, or after 0.2.1? Thoughts?

mpizenberg commented 3 years ago

@Eh2406 sorry haven't had time to check this out. Seems like a good idea but I'll have to wait until the weekend I think to review

Eh2406 commented 3 years ago

No rush! Thank you for the thorough reviews. Just wanted to make shore it was still on your radar.

Eh2406 commented 3 years ago

I am feeling the urge to try some of the more complicated options. Will you have time to take a look at this before I succumb?

mpizenberg commented 3 years ago

Indeed, I should have time this afternoon

On Fri, May 21, 2021, 04:24 Jacob Finkelman @.***> wrote:

I am feeling the urge to try some of the more complicated options. Will you have time to take a look at this before I succumb?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/pubgrub-rs/pubgrub/pull/88#issuecomment-845604890, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAWFOCMUCGV4UGQCVBY35JTTOW74LANCNFSM44DHLUFA .

Eh2406 commented 3 years ago

That is fabulous, thank you! Do you think the rename should trigger a new 10 day open time or can we merge now?

mpizenberg commented 3 years ago

Nah I think nobody else is gonna complain if you merge this ^^

On Sat, May 22, 2021, 02:12 Jacob Finkelman @.***> wrote:

That is fabulous, thank you! Do you think the rename should trigger a new 10 day open time or can we merge now?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/pubgrub-rs/pubgrub/pull/88#issuecomment-846317382, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAWFOCOTZXJUXXLYX37SC33TO3ZITANCNFSM44DHLUFA .