Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Fulfillment context should support DAGs better, integrate with caching better #30977

Open
nikomatsakis opened this issue Jan 17, 2016 · 3 comments
Open

Fulfillment context should support DAGs better, integrate with caching better #30977

nikomatsakis opened this issue Jan 17, 2016 · 3 comments
Labels
A-traits 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
Copy link
Contributor

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 ObligationForest doesn'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
@nikomatsakis nikomatsakis added C-enhancement Category: An issue proposing an enhancement or a PR with one. A-traits Area: Trait system 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. labels Jan 17, 2016
@arielb1
Copy link
Contributor

arielb1 commented Jan 17, 2016

Refreshing inference variables is quite expensive - we don't want to do it O(n^2)-ically. But some form of amortized deduplication would be fine I think.

@nikomatsakis
Copy link
Contributor Author

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"

@nikomatsakis nikomatsakis mentioned this issue Feb 1, 2016
Merged
bors added a commit that referenced this issue Feb 5, 2016
@bors
Auto merge of #31349 - nikomatsakis:issue-31157-obligation-forest-cac…
6dc112d 
…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`
@steveklabnik
Copy link
Member

Triage: I'm not aware of any changes here, but it's not my area of specialty either.

@orium orium mentioned this issue Aug 10, 2018
Merged
bors added a commit that referenced this issue Sep 30, 2018
@bors
Auto merge of #53255 - orium:fix-bug-overflow-send, r=arielb1
fc403ad 
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
Assignees
No one assigned
Labels
A-traits 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.
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@steveklabnik @nikomatsakis @arielb1