An easy-to-implement, arena-friendly hash map

[grep_it]

https://nullprogram.com/blog/2023/09/30/

[agumonkey]

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]

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 → fovc]

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 → fovc]

entryIndex is read before being assigned.

[fovc → MaxBarraclough]

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.

[chris_wot]

I finally understand arenas by reading https://www.rfleury.com/p/untangling-lifetimes-the-arena-all...

[hnrj95]

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 → hnrj95]

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 → cruegge]

“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 → hnrj95]

> 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.

[vitiral]

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...

[ithkuil]

Related data structure: https://en.m.wikipedia.org/wiki/Hash_array_mapped_trie

[eterm]

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.