Fulfillment context should support DAGs better, integrate with caching better #30977
Labels
A-trait-system
Area: Trait system
C-enhancement
Category: An issue proposing an enhancement or a PR with one.
I-compiletime
Issue: Problems and improvements with respect to compile times.
T-compiler
Relevant to the compiler team, which will review and decide on the PR/issue.
Comments
nikomatsakis
added
C-enhancement
|
Refreshing inference variables is quite expensive - we don't want to do it |
|
One thought was that we could cache recently refreshed types, so that refreshing twice in a row is cheap. But it seems best if we can identify a clear "pinch point" |
bors
added a commit
that referenced
this issue
Feb 5, 2016
…he, r=aturon Have the `ObligationForest` keep some per-tree state (or type `T`) and have it give a mutable reference for use when processing obligations. In this case, it will be a hashmap. This obviously affects the work that @soltanmm has been doing on snapshotting. I partly want to toss this out there for discussion. Fixes #31157. (The test in question goes to approx. 30s instead of 5 minutes for me.) cc #30977. cc @aturon @arielb1 @soltanmm r? @aturon who reviewed original `ObligationForest`
|
Triage: I'm not aware of any changes here, but it's not my area of specialty either. |
bors
added a commit
that referenced
this issue
Sep 30, 2018
Add a per-tree error cache to the obligation forest This implements part of what @nikomatsakis mentioned in #30533 (comment): > 1. If you find that a new obligation is a duplicate of one already in the tree, the proper processing is: > * if that other location is your parent, you should abort with a cycle error (or accept it, if coinductive) > * if that other location is not an ancestor, you can safely ignore the new obligation In particular it implements the "if that other location is your parent accept it, if coinductive" part. This fixes #40827. I have to say that I'm not 100% confident that this is rock solid. This is my first pull request 🎉, and I didn't know anything about the trait resolver before this. In particular I'm not totally sure that comparing predicates is enough (for instance, do we need to compare `param_env` as well?). Also, I'm not sure what @nikomatsakis mentions [here](#30977 (comment)), but it might be something that affects this PR: > In particular, I am wary of getting things wrong around inference variables! We can always add things to the set in their current state, and if unifications occur then the obligation is just kind of out-of-date, but I want to be sure we don't accidentally fail to notice that something is our ancestor. I decided this was subtle enough to merit its own PR. Anyway, go ahead and review 🙂. Ref #30977. # Performance We are now copying vectors around, so I decided to do some benchmarking. A simple benchmark shows that this does not seem to affect performance in a measurable way: I ran `cargo clean && cargo build` 20 times on actix-web (84b27db) and these are the results: ```text rustc master: Mean Std.Dev. Min Median Max real 66.637 2.996 57.220 67.714 69.314 user 307.293 14.741 258.093 312.209 320.702 sys 12.524 0.653 10.499 12.726 13.193 rustc fix-bug-overflow-send: Mean Std.Dev. Min Median Max real 66.297 4.310 53.532 67.516 70.348 user 306.812 22.371 236.917 314.748 326.229 sys 12.757 0.952 9.671 13.125 13.544 ``` I will do a more comprehensive benchmark (compiling rustc stage1) and post the results. r? @nikomatsakis, @nnethercote PS: It is better to review this commit-by-commit.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The new fulfillment context introduced in #30533 could be more efficient in a number of ways in terms of pruning the work it has to do. First, it currently considers obligations to be formed in a tree, but really it ought to detect arbitrary DAGs and avoiding adding needless work. In particular, if a given obligation O is also found elsewhere in the tree -- but NOT as an ancestor! -- then we can drop it. We have some limited support for this where we drop duplicate siblings. This may be good enough, but we can do better.
It seems like we could integrate this with cycle detection. Currently, we wait until the overflow counter trips and then walk back up and look for a cycle. This is perfectly fine. But I could also imagine that we might have some kind of per-tree hashtable (the current
ObligationForestdoesn't support "per-tree" data, but it seems like an easy enough extension) that tracks obligations currently in the tree. If we find when adding a new obligation O that it is already present, then we could go look for a cycle and otherwise consider it a duplicate. This seems nice, but there is a wrinkle.In particular, I am wary of getting things wrong around inference variables! We can always add things to the set in their current state, and if unifications occur then the obligation is just kind of out-of-date, but I want to be sure we don't accidentally fail to notice that something is our ancestor. I decided this was subtle enough to merit its own PR.
Another related issue is that it's not clear when is the best time to refresh inference variables. We might be able to find a perfect time, or maybe we should just make it very cheap to do and then do it all over the place.
cc @aturon @arielb1
The text was updated successfully, but these errors were encountered: