Regression in resolver performance #5130
Comments
bors
added a commit
that referenced
this issue
Mar 6, 2018
don't clone a BacktrackFrame if we are not going to backtrack I think this is a fix for #5130. Currently the only recoverable `activate` error does not corrupt `cx`, so this is definitely ok. We should be careful as we add more recoverable `activate` errors that they don't corrupt `cx` to the point where the error messages are affected.
|
Move to close? |
|
Oh yes indeed! |
bors
added a commit
that referenced
this issue
Nov 21, 2018
Persistent data structures by im-rs There has been a long standing "TODO: We should switch to persistent hash maps if we can" in the resolver. This PR introduces a dependency on [im-rs](bodil/im-rs#26) to provide persistent hash maps. It then uses `im_rc::OrdSet` to store the priority list of dependencies, instead of `std::BinaryHeap`, as cloning the `Heap` was one of the most expensive things we did. In Big O terms these changes are very big wins, in practice the improvement is small. This is do to a number of factors like, `std::collections` are very fast, N is usually only in the hundreds, we only clone when the borrow checker insists on it, and we use `RC` and other tricks to avoid cloning. I would advocate that we accept this PR, as: - Things are only going to get more complicated in the future. It would be nice to have Big O on our side. - When developing a new feature finding each place to add `RC` should be an afterthought not absolutely required before merge. (cc #6129 witch is stuck on this kind of per tick performance problem as well as other things). - As the code gets more complex, making sure we never break any of the tricks becomes harder. It would be easier to work on this if such mistakes are marginal instead of show stoppers. (cc #5130 a bug report of one of these bing removed and affecting `./x.py build` enough to trigger an investigation). - The resolver is already very complicated with a lot of moving parts to keep in your head at the same time, this will only get worse as we add features. There are a long list of tricks that are *critical* before and `~5%` after, it would be nice to consider if each one is worth the code complexity. (I can list some of the ones I have tried to remove but are still small wins, if that would help the discussion). Overall, I think it is worth doing now, but can see that if is not a slam dunk.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Noticed at #5044 (comment) it looks like the resolver loop was tweaked in #5000 to unconditionally clone the
Contextbefore each invocation ofactivateinstead of only ifhas_anotheris true later on, some more info at #5044 (comment).The line in question looks to be
cargo/src/cargo/core/resolver/mod.rs
Line 897 in ae796ad
@Eh2406 says they're gonna look into this, so just wanted to open a tracking issue for it!
The text was updated successfully, but these errors were encountered: