My favourite small hash table
corsix.org
My favourite small hash table
1–10 of 39 posts
Re: My favourite small hash table
#2Awesome 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?
Re: My favourite small hash table
#3Is 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;
}Re: My favourite small hash table
#4> The table occupies at most 32 GiB of memory.
This constraint allows making a linear array of all the 4 billion values, with the key as array index, which fits in 16 GiB. Another 500 MiB is enough to have a bit indicating present or not for each.
Perhaps text strings as keys and values would give a more interesting example...
Re: My favourite small hash table
#5Is 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; }
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`.
Re: My favourite small hash table
#6Is 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.
Re: My favourite small hash table
#7I 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.
Re: My favourite small hash table
#8Awesome 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?
Re: My favourite small hash table
#9Is 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; }
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.
Re: My favourite small hash table
#10Is 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.
[deleted]