🛠 improve canonicalization by using a hashing scheme

[nikomatsakis]

The canonicalization scheme created in #48411 works by first folding types into a canonical form, which is then hashed and interned. This is not necessary, and it shows up in the profiles: we could augment the TypeFolder trait to have a method for hashing as it goes (e.g., a hash_with method, and some hash_ty / hash_region callbacks). Then we can begin by hashing the value-to-be-canonicalized, producing a hash (this would be a kind of "stable hash", hence big enough to be presumed unique). We would then look for an interned value with that hash and return it if found, avoiding all the folding. If no interned value is found, then we would fold and put the resulting value into the interning table. Ideally, this hash can then be kept for later, making the "stable hash" code quite cheap.

(This might actually not make things faster, of course, we would want to measure.)

[nikomatsakis]

That said, in all profiles I've looked at, canonicalization doesn't seem to be a hot spot.

[JaimeValdemoros]

Hi @nikomatsakis! I'm keen to have a look at this if you don't mind giving me a couple of hints along the way? I have some rust experience but this would be my first time contributing to the compiler.

[JaimeValdemoros]

I had an initial go a adding the hash_with method in a branch here: https://github.com/JaimeValdemoros/rust/tree/pre-canonicalization-hashing

[technicalguy]

@JaimeValdemoros Are you still working on this? If you make a pull request (even if it's not "finished" or "ready") then it will be much easier for everyone to see your code (rather than getting GitHub to diff your branch against rust/master directly).

[nikomatsakis]

I'm tagging this with WG-compiler-nll and NLL-performant since this is also an important issue for non-lexical lifetimes. canonicalization takes about 5% of NLL time.

[JaimeValdemoros]

Sorry about the delay - I'm still keen give this a shot! I've just made a PR here: #51837 following @technicalguy's suggestion.

[nikomatsakis]

@JaimeValdemoros, @technicalguy -- think you two could join the rust-lang Zulip? I've created a thread where we could chat about this.

[nikomatsakis]

Current measurements are showing canonicalization as 11% of NLL check, with the latest optimizations, so this is becoming increasingly relevant.

[technicalguy]

@nikomatsakis I think I have joined Zulip now...yet another chat application!

[nikomatsakis]

So, this is a big refactoring, and my measurements suggest that while it would help NLL, it would not make a huge difference. I'm going to remove this from the milestone.

[nikomatsakis]

Perhaps, in any case, this was a bit much too chew at once, I'm going to see if I can break it down into smaller steps.