[HN Gopher] An easy-to-implement, arena-friendly hash map
___________________________________________________________________
An easy-to-implement, arena-friendly hash map
Author : grep_it
Score : 123 points
Date : 2023-09-30 23:29 UTC (23 hours ago)
(HTM) web link (nullprogram.com)
(TXT) w3m dump (nullprogram.com)
| ithkuil wrote:
| Related data structure:
| https://en.m.wikipedia.org/wiki/Hash_array_mapped_trie
| agumonkey wrote:
| The article https://www.rfleury.com/p/untangling-lifetimes-the-
| arena-all..., linked 2 level deep to this article, is beyond
| fascinating.
|
| discussed here :
|
| https://news.ycombinator.com/item?id=33379079
|
| https://old.reddit.com/r/programming/comments/xmnfo8/untangl...
|
| https://old.reddit.com/r/C_Programming/comments/xmxmex/untan...
|
| PS:it also ties with forth different stacks. Interesting design
| space.
| fovc wrote:
| IIRC, NRK started down this path because normal hash tables
| without free leak memory on every resize.
|
| The original series of articles had me thinking about how to
| implement the normal hash table without leaking. I think it's
| possible:
|
| 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)
|
| 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.
| fovc wrote:
| Not much of a C programmer, but here's my ChatGPT assisted
| (painstakingly...) attempt at a lookup function. I think the
| log2 from math.h needs to be rewritten to use a fast bitwise
| implementation #include <stdint.h>
| #include <math.h> #include <stdbool.h>
| #define BASE_PAGE_BITS 14 #define MAX_PAGES 22
| struct KeyValue { keytype key; valtype val; bool inUse; };
| uint32_t hash(keytype key); int equals(keytype key1,
| keytype key2); struct HashTable {
| struct KeyValue pages[MAX_PAGES][]; uint8_t
| usedPages; }; typedef struct HashTable
| HashTable; struct KeyValue* lookup(HashTable*
| table, keytype key) { uint32_t hashed = hash(key);
| uint32_t lowerBits = hashed & ((1 << (BASE_PAGE_BITS +
| table->usedPages)) - 1); uint32_t pageIndex =
| (lowerBits == 0) ? 0 : (uint32_t)(log2(lowerBits >>
| BASE_PAGE_BITS) + 1); uint32_t entryIndex;
| for (;;) { uint32_t entryIndexRange =
| (pageIndex == 0) ? (1 << BASE_PAGE_BITS) : (1 << (pageIndex +
| BASE_PAGE_BITS - 1)); for (;
| entryIndex < entryIndexRange; entryIndex++) {
| struct KeyValue* page = table->pages[pageIndex];
| if (!page[entryIndex].inUse) return &page[entryIndex];
| if (equals(page[entryIndex].key, key)) return
| &page[entryIndex]; }
| pageIndex = (pageIndex + 1) % table->usedPages;
| entryIndex = 0; } }
| MaxBarraclough wrote:
| _entryIndex_ is read before being assigned.
| fovc wrote:
| Can't edit now, but it should be initialized to lowerBits -
| (1 << (pageIndex + BASE_PAGE_BITS - 1)) for pageIndex > 0,
| or just lowerBits if pageIndex = 0.
| hnrj95 wrote:
| 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.
| cruegge wrote:
| It's not limited to 32, but afterwards search will be linear
| along child[0]. Using rotation would not make a difference,
| since you're in the collision case already, so you would
| effectively always branch to the same child for levels below
| 32.
| hnrj95 wrote:
| "Afterwards search will be linear along child[0]"
|
| Yes, I thought this was clear from my statement.
|
| "Rotation would not make a difference"
|
| It would. The offsets generated by the hash would repeat
| every 32 shifts, but the absolute addresses given in the
| collision cases are a random construction based on the
| history of the tree at that point, so despite the offsets'
| repeating, the tree's invariants along the lookup are likely
| to be preserved.
| cruegge wrote:
| > Yes, I thought this was clear from my statement.
|
| Yeah, sorry, wasn't really necessary to repeat that point.
| I was too focused on the "limiting the height of the tree
| to 32" formulation.
|
| I have to admit that I don't quite understand what
| invariants along the lookup you mean. All lookups that
| reach a particular node on level 32 have the same hash, so
| regardless of how you compute the branch from the hash
| below level 32, they will always follow the same path
| starting from there (except for terminating at different
| levels, obviously). So nodes only ever have one child at
| most, and there's no loss in simply picking child 0 in all
| cases.
|
| Sorry if what I'm describing is again obvious, maybe I just
| don't understand your point correctly.
| chris_wot wrote:
| I finally understand arenas by reading
| https://www.rfleury.com/p/untangling-lifetimes-the-arena-all...
| eterm wrote:
| 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.
| vitiral wrote:
| I had a similar idea and called them "Shifted Search Trees". I
| can see how they are also a kind of Trie
|
| 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)
|
| https://github.com/civboot/civboot/blob/main/blog/0013-civbo...
___________________________________________________________________
(page generated 2023-10-01 23:02 UTC)