This hash table is pretty good. It has at best one memory read if there’s no collision. Randomized key might introduce any level of key collision though.
My favourite small hash table
11–20 of 39 posts
Re: My favourite small hash table
#12[deleted]
Re: My favourite small hash table
#13Is there a specific reason to store the key + value as an `uint64_t` instead of just using a struct like this? struct slot { uint32_t key; uint32_t value; }
The alignment constraint is different, which they use to be able to load both as a 64-bit integer and compare to 0 (the empty slot). You could work around that with a union or casts with explicit alignment constraints, but this is the shortest way to express that.
In that case you can use bit fields in a union:
union slot {
uint64_t keyvalue;
struct {
uint64_t key: 32;
uint64_t value: 32;
};
};
Edit: Note also that you can cast a pointer to slot to a pointer to uint64_t and that does not break strict aliasing rules.
Re: My favourite small hash table
#14Used Gemini to explain this. Very interesting and I think Gemini did a good job explaining the Robin hood fairness mechanism
Re: My favourite small hash table
#15Earlier quoted context omitted.
The alignment constraint is different, which they use to be able to load both as a 64-bit integer and compare to 0 (the empty slot). You could work around that with a union or casts with explicit alignment constraints, but this is the shortest way to express that.
In that case you can use bit fields in a union: union slot { uint64_t keyvalue; struct { uint64_t key: 32; uint64_t value: 32; }; }; Since both members of the union are effectively the exact same type, there is no issue. C99: "If the member used to access the contents of a union is not the same as the member last used to store a value, the object representation of the value that was stored is reinterpreted as an obje…
You can probably get away with just a union between a 64 bit and 2 32 bit integers.
Re: My favourite small hash table
#16Is there a specific reason to store the key + value as an `uint64_t` instead of just using a struct like this? struct slot { uint32_t key; uint32_t value; }
No real reason. Slightly terser to compare with zero to find an empty slot.
Re: My favourite small hash table
#17Awesome blog! Looking at the code I feel like there’s a kindred soul behind that keyboard, but there’s no About page afaict. Who beeth this mysterious writer?
He’s done some interesting work with crc32 ~recently:
Re: My favourite small hash table
#18Earlier quoted context omitted.
Maybe trying to avoid struct padding? Although having done a quick test on {arm64, amd64} {gcc, clang}, they all give the same `sizeof` for a struct with 2x`uint32_t`, a struct with a single `uint64_t`, or a bare `uint64_t`.
In any struct where all fields have the same size (and no field type requires higher alignment than its size), it is guaranteed on every (relevant) ABI that there is no padding bytes.
TIL! Thanks!
Re: My favourite small hash table
#19I always find it interesting how often the simplest hash table layouts end up performing best in real workloads. Once you avoid pointer chasing and keep everything in a compact array, CPU caches do most of the heavy lifting. It’s also a good reminder that clarity of layout often beats more “clever” designs, especially when the dataset fits comfortably in memory.
Until you get high memory contention from the rest of the code. Once eviction gets high you get some pretty counterintuitive improvements by fixing things that seem like they shouldn’t need to be fixed.
My best documented case was a 10x speed up from removing a double lookup that was killing caches.
Re: My favourite small hash table
#20I always find it interesting how often the simplest hash table layouts end up performing best in real workloads. Once you avoid pointer chasing and keep everything in a compact array, CPU caches do most of the heavy lifting. It’s also a good reminder that clarity of layout often beats more “clever” designs, especially when the dataset fits comfortably in memory.
To me, these sorts of examples always seem contrived. To the first order, I've never had a real hash table problem that was on machine word keys.
I've nearly always had a variable length string or other complex structure that was being hashed, not their handles.
Back in my early career in C, this would be a generic API to hash and store void pointers, but the pointers were not being hashed. The domain-specific hash function needed to downcast and perform the appropriate remote memory access to fetch the variable-length material that was actually being hashed.