Rollup merge of #51394 - nnethercote:NCA-depths, r=nikomatsakis
Use scope tree depths to speed up `nearest_common_ancestor`.
This patch adds depth markings to all entries in the `ScopeTree`'s
`parent_map`. This change increases memory usage somewhat, but permits a
much faster algorithm to be used:
- If one scope has a greater depth than the other, the deeper scope is
moved upward until they are at equal depths.
- Then we move the two scopes upward in lockstep until they match.
This avoids the need to keep track of which scopes have already been
seen, which was the major part of the cost of the old algorithm. It also
reduces the number of child-to-parent moves (which are hash table
lookups) when the scopes start at different levels, because it never
goes past the nearest common ancestor the way the old algorithm did.
Finally, the case where one of the scopes is the root is now handled in
advance, because that is moderately common and lets us skip everything.
This change speeds up runs of several rust-perf benchmarks, the best by
6%.
A selection of the bigger improvements:
```
clap-rs-check
avg: -2.6% min: -6.6% max: 0.0%
syn-check
avg: -2.2% min: -5.0% max: 0.0%
style-servo-check
avg: -2.9%? min: -4.8%? max: 0.0%?
cargo-check
avg: -1.3% min: -2.8% max: 0.0%
sentry-cli-check
avg: -1.0% min: -2.1% max: 0.0%
webrender-check
avg: -0.9% min: -2.0% max: 0.0%
style-servo
avg: -0.9%? min: -1.8%? max: -0.0%?
ripgrep-check
avg: -0.7% min: -1.8% max: 0.1%
clap-rs
avg: -0.9% min: -1.6% max: -0.2%
regex-check
avg: -0.2% min: -1.3% max: 0.1%
syn
avg: -0.6% min: -1.3% max: 0.1%
hyper-check
avg: -0.5% min: -1.1% max: 0.0%
```
The idea came from multiple commenters on my blog and on Reddit. Thank you!