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

Clean up / rewrite resolve #1935

Closed
marijnh opened this issue Mar 6, 2012 · 5 comments
Closed

Clean up / rewrite resolve #1935

marijnh opened this issue Mar 6, 2012 · 5 comments
Assignees
@pcwalton
Labels
A-resolve Area: Name resolution E-hard Call for participation: Hard difficulty. Experience needed to fix: A lot.
Milestone
0.4

Comments

@marijnh
Copy link
Contributor

marijnh commented Mar 6, 2012

Resolve has organically grown into a very complicated, rather slow, probably partially redundant tangle. When a decision is made on #1893 , some work should be done on cleaning it up.
@ghost ghost assigned marijnh Mar 8, 2012
@catamorphism
Copy link
Contributor

labelled as postponed since it depends on another bug, and assigning to you, @marijnh , since you seem like the most qualified person to do it.

@catamorphism catamorphism mentioned this issue Apr 13, 2012
Closed
@brson
Copy link
Contributor

brson commented Apr 27, 2012

I should mention that rustdoc uses resolve to locate reexports and needs it to be tolerant of errors.

@ghost ghost assigned catamorphism May 15, 2012
@catamorphism
Copy link
Contributor

We agreed that I will finish this, in Marijn's absence.

@ghost ghost assigned pcwalton May 29, 2012
@catamorphism
Copy link
Contributor

Reassigned to @pcwalton to reflect reality...

This was referenced Jun 21, 2012
Closed
Closed
Closed
@graydon graydon mentioned this issue Jun 23, 2012
Closed
@catamorphism catamorphism mentioned this issue Jun 28, 2012
Closed
@catamorphism
Copy link
Contributor

This is done; if any subsidiary issues show up, file separate bugs.

bors added a commit to rust-lang-ci/rust that referenced this issue Sep 22, 2022
@bors
Auto merge of rust-lang#1935 - saethlin:optimize-sb, r=RalfJung
cfad9d1 
Optimizing Stacked Borrows (part 1?): Cache locations of Tags in a Borrow Stack

Before this PR, a profile of Miri under almost any workload points quite squarely at these regions of code as being incredibly hot (each being ~40% of cycles):

https://github.com/rust-lang/miri/blob/dadcbebfbd017aac2358cf652a4bd71a91694edc/src/stacked_borrows.rs#L259-L269

https://github.com/rust-lang/miri/blob/dadcbebfbd017aac2358cf652a4bd71a91694edc/src/stacked_borrows.rs#L362-L369

This code is one of at least three reasons that stacked borrows analysis is super-linear: These are both linear in the number of borrows in the stack and they are positioned along the most commonly-taken paths.

I'm addressing the first loop (which is in `Stack::find_granting`) by adding a very very simple sort of LRU cache implemented on a `VecDeque`, which maps recently-looked-up tags to their position in the stack. For `Untagged` access we fall back to the same sort of linear search. But as far as I can tell there are never enough `Untagged` items to be significant.

I'm addressing the second loop by keeping track of the region of stack where there could be items granting `Permission::Unique`. This optimization is incredibly effective because `Read` access tends to dominate and many trips through this code path now skip the loop entirely.

These optimizations result in pretty enormous improvements:
Without raw pointer tagging, `mse` 34.5s -> 2.4s, `serde1` 5.6s -> 3.6s
With raw pointer tagging, `mse` 35.3s -> 2.4s, `serde1` 5.7s -> 3.6s

And there is hardly any impact on memory usage:
Memory usage on `mse` 844 MB -> 848 MB, `serde1` 184 MB -> 184 MB (jitter on these is a few MB).
celinval pushed a commit to celinval/rust-dev that referenced this issue Jun 4, 2024
@aaronbembenek-aws
Update kani-driver to use clap v4 (rust-lang#1935)
f957044
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@pcwalton pcwalton

Labels
A-resolve Area: Name resolution E-hard Call for participation: Hard difficulty. Experience needed to fix: A lot.
Projects
None yet
Milestone
0.4
Development

No branches or pull requests
4 participants
@marijnh @brson @pcwalton @catamorphism