The article <a href="https://www.rfleury.com/p/untangling-lifetimes-the-arena-allocator" rel="nofollow noreferrer">https://www.rfleury.com/p/untangling-lifetimes-the-arena-all...</a>, linked 2 level deep to this article, is beyond fascinating.<p>discussed here :<p><a href="https://news.ycombinator.com/item?id=33379079">https://news.ycombinator.com/item?id=33379079</a><p><a href="https://old.reddit.com/r/programming/comments/xmnfo8/untangling_lifetimes_the_arena_allocator/" rel="nofollow noreferrer">https://old.reddit.com/r/programming/comments/xmnfo8/untangl...</a><p><a href="https://old.reddit.com/r/C_Programming/comments/xmxmex/untangling_lifetimes_the_arena_allocator/" rel="nofollow noreferrer">https://old.reddit.com/r/C_Programming/comments/xmxmex/untan...</a><p>PS:it also ties with forth different stacks. Interesting design space.
IIRC, NRK started down this path because normal hash tables without free leak memory on every resize.<p>The original series of articles had me thinking about how to implement the normal hash table without leaking. I think it’s possible:<p>First consider a hash table using linear probing with a dedicated arena (restriction will be lifted later). That means memory can grow for free. However, resizing is still tricky because we need to rehash in place while ensuring we don’t “strand” any entries. This can be accomplished by iterating through the hash table entries in order, but starting at an empty entry and looping around. (Proof left as an exercise for the reader)<p>So now we have a hash table that can use realloc to grow. How to generalize for arenas? The key is that the HT will maintain a page map of sorts. The first page is of size M, the second is of size M, and thereafter they’ll be of size 2^n * M. Basically on each resize we double the total capacity by adding a new page. Since the pages are of variable width, though, how to map indexes to pages quickly? The key is to use ffs or ctz to get a rounded log2.
I finally understand arenas by reading <a href="https://www.rfleury.com/p/untangling-lifetimes-the-arena-allocator" rel="nofollow noreferrer">https://www.rfleury.com/p/untangling-lifetimes-the-arena-all...</a>
Great article, but slight issue. The iteration expression shifts left by 2, effectively limiting the height of the tree to 32. You probably want a rotation instead; otherwise you’ll be locked into child 0 from depth 32 down. I suppose with a good hash the manifestation would be rare.
I had a similar idea and called them "Shifted Search Trees". I can see how they are also a kind of Trie<p>I've written about how they can not only be used for hashes but also for storing sparse indexes. I'm hoping to write an extremely tiny Lua implementation which uses only slab allocation (even better than arena IMO! Though I do love arena allocators)<p><a href="https://github.com/civboot/civboot/blob/main/blog/0013-civboot-languages.md#shifted-index-tree-sit">https://github.com/civboot/civboot/blob/main/blog/0013-civbo...</a>
Related data structure: <a href="https://en.m.wikipedia.org/wiki/Hash_array_mapped_trie" rel="nofollow noreferrer">https://en.m.wikipedia.org/wiki/Hash_array_mapped_trie</a>
Fantastic! I've been working on a project to benchmark different data structures such as this, I'll have to have a go at implementing this to see how it fares.