# HashInterner **URL:** \ **Category:** Uncategorized\ **Created:** [May 6, 2015, 4:27pm UTC](https://internals.rust-lang.org/t/hashinterner/1999 "2015-05-06T16:27:44Z")\ **Posts on this page:** 13\ **Page:** 1
**Author:** ![arielb1](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/arielb1/32/3044_2.png) [@arielb1](https://internals.rust-lang.org/u/arielb1)\ **Post date:** [May 6, 2015, 4:27pm UTC](https://internals.rust-lang.org/t/hashinterner/1999/1 "2015-05-06T16:27:44Z")
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 ```rust impl<'cx, T: Hash> HashInterner<'cx, T> { fn new() -> Self { /* .. */ } fn intern(&mut self, k: K, f: F) -> &'cx T where K: PartialEq + Hash, F: FnOnce(K) -> &'cx T { /* .. */ } } ``` ---
**Author:** ![frankmcsherry](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/frankmcsherry/32/3115_2.png) [@frankmcsherry](https://internals.rust-lang.org/u/frankmcsherry)\ **Post date:** [May 6, 2015, 8:53pm UTC](https://internals.rust-lang.org/t/hashinterner/1999/2 "2015-05-06T20:53:53Z")
It sounds like you need … _dramatic pause_ … Recycler! [https://github.com/frankmcsherry/recycler](https://github.com/frankmcsherry/recycler) At least, I wrote it for you. Maybe it will help! ---
**Author:** ![llogiq](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/llogiq/32/13692_2.png) [@llogiq](https://internals.rust-lang.org/u/llogiq)\ **Post date:** [May 7, 2015, 5:35am UTC](https://internals.rust-lang.org/t/hashinterner/1999/3 "2015-05-07T05:35:21Z")
Do I get this right? You want to hash an object that does not yet exist? ---
**Author:** ![arielb1](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/arielb1/32/3044_2.png) [@arielb1](https://internals.rust-lang.org/u/arielb1)\ **Post date:** [May 7, 2015, 9:09am UTC](https://internals.rust-lang.org/t/hashinterner/1999/4 "2015-05-07T09:09:09Z")
I don’t want dead objects, I want live ones. I basically want some version of [Hash Consing](https://en.wikipedia.org/wiki/Hash_consing). ---
**Author:** ![arielb1](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/arielb1/32/3044_2.png) [@arielb1](https://internals.rust-lang.org/u/arielb1)\ **Post date:** [May 7, 2015, 9:09am UTC](https://internals.rust-lang.org/t/hashinterner/1999/5 "2015-05-07T09:09:50Z")
I can already hash such an object. I just want to check whether it exists within a hash table. ---
**Author:** ![frankmcsherry](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/frankmcsherry/32/3115_2.png) [@frankmcsherry](https://internals.rust-lang.org/u/frankmcsherry)\ **Post date:** [May 7, 2015, 9:22am UTC](https://internals.rust-lang.org/t/hashinterner/1999/6 "2015-05-07T09:22:31Z")
The intent here is that you could re-use the dead-but-memory-backed objects rather than repeatedly dropping and re-allocating them. It is a different solution to the problem that you actually have, that churning the allocator is expensive. ---
**Author:** ![arielb1](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/arielb1/32/3044_2.png) [@arielb1](https://internals.rust-lang.org/u/arielb1)\ **Post date:** [May 7, 2015, 12:16pm UTC](https://internals.rust-lang.org/t/hashinterner/1999/7 "2015-05-07T12:16:35Z")
The dead-but-memory-backed objects here are just vectors of a bunch of different sizes. ---
**Author:** ![frankmcsherry](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/frankmcsherry/32/3115_2.png) [@frankmcsherry](https://internals.rust-lang.org/u/frankmcsherry)\ **Post date:** [May 8, 2015, 5:45am UTC](https://internals.rust-lang.org/t/hashinterner/1999/8 "2015-05-08T05:45:42Z")
As I understand your post, repeatedly acquiring and releasing new “vectors of a bunch of different sizes” from the allocator is what makes your code slow at the moment. If, rather than ask the allocator to hand you two new fresh vectors for your `Substs`, you take two empty but allocated vectors from a `Recycler`, use them exactly as if you had allocated fresh vectors, and return them to the `Recycler` rather than let them drop, your code may go faster. ---
**Author:** ![comex](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/comex/32/2587_2.png) [@comex](https://internals.rust-lang.org/u/comex)\ **Post date:** [May 8, 2015, 9:02am UTC](https://internals.rust-lang.org/t/hashinterner/1999/9 "2015-05-08T09:02:02Z")
Incidentally, this sort of situation is where an inline allocator could shine. Since Rust has sized deallocation, both allocation and deallocation could in theory be optimized based on object sizes known at compile time, and they could turn into a handful of instructions each in the fast path. (Especially if you had constant offsets from %fs/%gs, but I guess that’s just fantasy in code that can be called from C.) Though I suppose even that would find it hard to compete with stack allocation. ---
**Author:** ![arielb1](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/arielb1/32/3044_2.png) [@arielb1](https://internals.rust-lang.org/u/arielb1)\ **Post date:** [May 8, 2015, 11:15am UTC](https://internals.rust-lang.org/t/hashinterner/1999/10 "2015-05-08T11:15:06Z")
what is an inline allocator? ---
**Author:** ![comex](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/comex/32/2587_2.png) [@comex](https://internals.rust-lang.org/u/comex)\ **Post date:** [May 9, 2015, 4:11am UTC](https://internals.rust-lang.org/t/hashinterner/1999/11 "2015-05-09T04:11:24Z")
Sorry, I wasn’t clear; I just mean an allocator whose code gets inlined - the fast path, anyway. Like some modern mallocs, it would probably give each size class its own free list (singly linked?), cached in thread local storage, so there wouldn’t be a need for free slot merging, synchronization, etc in that path; it would just be popping and pushing an entry from the appropriate TLS linked list. I don’t know if anyone has tried this in C or C++; maybe there’s some dealbreaker I haven’t thought of. ---
**Author:** ![gsingh93](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gsingh93/32/6884_2.png) [@gsingh93](https://internals.rust-lang.org/u/gsingh93)\ **Post date:** [May 14, 2015, 10:17pm UTC](https://internals.rust-lang.org/t/hashinterner/1999/12 "2015-05-14T22:17:23Z")
Did you ever figure out a solution to this issue? I’m running into this exact issue. ---
**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\ **Post date:** [March 25, 2019, 8:24am UTC](https://internals.rust-lang.org/t/hashinterner/1999/13 "2019-03-25T08:24:25Z")
This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.