bytecodealliance / bytecodealliance/wasmtime
Alternative ScopedHashMap implementation
- Dominant language
- Rust
- Stars
- 18.6k
- Forks
- 1.8k
- Avg merge
- 1d 18h
- Merged PRs (30d)
- 126
Description
(This is not really an issue but a heads-up; a discussion would've been more appropriate had those been enabled. Feel free to close for any reason.)
I was reading https://github.com/bytecodealliance/rfcs/pull/27, and was pleasantly surprised to find a "scoped hashmap" data structure being used in the wild.
A couple of years ago I wrote an optimized version of such a structure, with the motivating use case being the lexically-scoped context in a compiler: https://gist.github.com/glaebhoerl/d62d2b19365ae0d7c29102d0a5a6ab03. Feel free to take this and use it if you think it's worthwhile.
I'm not really sure of all the tradeoffs w.r.t. wasmtime's [own implementation](https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/codegen/src/scoped_hash_map.rs), especially as regards the particular use case, although what's visible at a glance is that the wasmtime version requires a loop when decrementing a level (leaving a scope) to restore the previous state, whereas the other doesn't (unless there is shadowing, which is N/A here), that having been the whole motivation for its existence.
The basic idea is reminiscent of a generational arena: upon popping a scope, stale entries aren't physically removed (or even touched); rather, based on what is effectively a generation ID (called a scope ID in the code), they're ignored/overwritten in subsequent gets/inserts.
(The version in the gist builds on hashbrown's RawTable to make the hash table aware of stale entries on a low level; there was [also](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=e9a06ccbe73b999f68d6d723b3ad6901) an earlier sketch without that integration which was simpler and didn't involve `unsafe` code.)
Contributor guide
Assessment
This issue has not been assessed yet.