Fix #3846 properly, so that subtrees can be skipped again

[JoJoDeveloping]

Issue #3846 was "fixed" by PR #3847, but this fix was a hotfix. After careful thinking about the invariants at play there, the more proper solution is to instead do some extra magic during retags. This PR re-adds the disabled functionality, and ensures that default-lazy new nodes introduced by a retag outside that retag's range do not break anything, by having such retags reset the state that tracks when subtrees can be skipped.

The details can be seen in the code comments.

Here's the difference in running times for the benchmark suite. Note that it's a log graph, since the differences are so large it would otherwise be unreadable:

[RalfJung]

Well those are some solid wins. :)

(How did you make those graphs?)

[JoJoDeveloping]

(How did you make those graphs?)

google sheets--the numbers were copied in there manually.

Well those are some solid wins. :)

Not really--it's more that #3847 was a solid loss :upside_down_face: this just brings the performance back to where it used to be.

[RalfJung]

Not really--it's more that https://github.com/rust-lang/miri/pull/3847 was a solid loss 🙃 this just brings the performance back to where it used to be.

The previous version of this cheated by being wrong, so it still counts. ;)

[JoJoDeveloping]

I pushed some quite large changes, which restructure a lot and rewrite most of the comments. Please have a look at it again, starting in the new file foreign_access_skipping.rs :slightly_smiling_face:

[JoJoDeveloping]

better now^^?

[JoJoDeveloping]

@rustbot ready

[JoJoDeveloping]

@rustbot ready

[RalfJung]

@rustbot author