Currently, rustc spends 10% of no-opt time creating and destroying Substs structs. More specifically, Substs structs are interned, but they each contain 2 Vec-s, which have to be allocated and then freed when an already-interned Substs is re-interned, so I would like some way to intern Substs without allocating.
This could be done relatively easily with find_equiv: create a variant of Substs whose Vec-s are allocated on the stack, and look it up. If it isn’t found, create a real Substs and intern it.
However, the core team thinks find_equiv isn’t a good API for a hash-table. I think a good solution would be to add a HashInterner. I would like to use parts of std::collections::hash for it - so it should probably be in std.
An API would be something like
impl<'cx, T: Hash> HashInterner<'cx, T> {
fn new() -> Self { /* .. */ }
fn intern<K, F>(&mut self, k: K, f: F) -> &'cx T
where K: PartialEq<T> + Hash,
F: FnOnce(K) -> &'cx T
{ /* .. */ }
}
