3 ms·
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
by fovc 3y ago
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 3y agoNot 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 3y agoentryIndex is read before being assigned.
- fovc 3y agoCan’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.