Comments (9)
std::mem::take(&mut self.history)
would be the escape hatch that will work there, when that clone becomes significant. (it did not change the runtime of the current benchmarks.)
from pubgrub.
One thing I was wondering about is how this works with backtracking. If we backtrack to before a decision that introduced that derivation then does that mean that some terms need to come out of that intersection? If so how do we do that? Even if this is a problem, it is not insurmountable, we can keep the Vec
of derivations and a pre computed intersection. In the case of backtracking, the vec gets smaller and the intersection needs to be recomputed.
from pubgrub.
That's a very relevant question! Backtracking is currently operated thanks to history
which is a chronological vec of all the assignments. Once we backtrack to a given level, we iterate on assignments with a lower level and rebuild the memory.
Conflict resolution is not common I think in a normal setting since newer versions tend to be compatible with older ones, and we choose newer versions by default. Also, once we've found the root cause for a conflict, I don't see a reason we should have another conflict soon. But backtracking happens once per prior cause until the root cause is found so it could typically happen multiple times until we've found the root cause. <- woops, that is wrong, there is 1 backtrack per conflict resolution
It's probably worth having two things for memory derivations, a precomputed intersection, and terms that have not been intersected yet in a complementary vec. Something like this in the Memory.assignments
.
struct PackageAssignments<V: Version> {
decision: Option<(V, Term<V>)>,
derivations_intersected: Term,
derivations_not_intersected_yet: Vec<Term<V>>,
}
The Memory
method terms_for_package(&self, p: &P)
would become terms_intersection_for_package(&mut self, p: &P)
. It should empty the derivations_not_intersected_yet
vec into the derivations_intersected
term and return that. There should also be changes in the potential_packages
.
This would provide both the benefit of never computing that intersection more than once, and not computing the intersection if it's not required yet (for backtracking for example).
Slightly unrelated, but related performance-wise, I couldn't figure how to mutate in place the history and memory and so had to clone the whole history which is quite bad. Is this another case where interior mutability is needed? is there a better way to do that?
from pubgrub.
I've had a try at this today. I chose better-heuristic
(smart package choice) as a base and ran benchmark large_case_1
, then cherry-picked the improvements from dont-readd-deps
and finally implemented the improvement discussed here on top. The timings I got for large_case_1
on my computer are the following:
better-heuristic
: 160 ms / iter+
dont-readd-deps
: 115 ms / iter+
this
: 60 ms / iter
So on the large_case_1
benchmark, this looks like a 2x speedup. It is not cleaned up (few things are not needed anymore) but the commit is here (f803428) in branch precompute_intersections
.
from pubgrub.
And on large_case_2
im seeing:
better-heuristic
: 312 ms / iter+
dont-readd-deps
: 220 ms / iter+
this
: 122 ms / iter
from pubgrub.
On my computer the improvements are similarly grate! I look forward to that getting polished into a PR!
from pubgrub.
I was excited, so pushed a commit to your branch with some cleaned ups. If that was rude I am sorry and ignore the commit.
from pubgrub.
ahah don't worry, I didn't even plan to make a PR of this soon. I used the commits for the two new benchmarks, which definitely shouldn't end in Git (we'll have to re-assess that git LFS situation, but that's another subject). I see that branch more as exploration stuff. Feel free to fill it with all the ideas and cleanup you want ^^
from pubgrub.
Done in #37 which is on its way to being merged.
from pubgrub.
Related Issues (20)
- Root package version should be optional HOT 6
- Dependency version with invalid direct dependencies should be tracked as incompatibility HOT 3
- Allow an arbitrary, custom incompatibilities HOT 3
- Why do error messages start with no version? HOT 1
- Remove `Reporter` trait
- Create a contributions guide HOT 1
- Update reporter implementations to use `&mut Write` instead of buffering strings
- When can the algorithm use `simplify` HOT 2
- Move off actions-rs HOT 1
- Update criterion or replace it
- How to get the report formatting presented in the README HOT 8
- Tests fail when using semantic Eq for Term HOT 7
- Out of date documentation for Dev HOT 1
- Build a benchmark based on UV slow case HOT 5
- A new release and switching the default branch to dev HOT 6
- Declare minimum Rust version HOT 1
- Switch to `swatinem/rust-cache` instead of bespoke `actions/cache` in CI
- CI is failing on dev. HOT 2
- Allow changing the `Display` of `Range` HOT 4
- Panic: "add_derivation should not be called after a decision" HOT 4
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from pubgrub.