[HN Gopher] My favourite small hash table
___________________________________________________________________
My favourite small hash table
Author : speckx
Score : 109 points
Date : 2025-12-09 14:47 UTC (8 hours ago)
(HTM) web link (www.corsix.org)
(TXT) w3m dump (www.corsix.org)
| clbrmbr wrote:
| Awesome 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?
| LargoLasskhyfv wrote:
| https://github.com/corsix
| loeg wrote:
| He's done some interesting work with crc32 ~recently:
|
| https://www.corsix.org/content/fast-crc32c-4k
|
| https://github.com/corsix/fast-crc32/
| judofyr wrote:
| Is 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;
| }
| zimpenfish wrote:
| 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`.
| simonask wrote:
| 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.
| zimpenfish wrote:
| TIL! Thanks!
| nitnelave wrote:
| 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.
| Asooka wrote:
| 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 object
| representation of the new type". Meaning, you can initialise
| keyvalue and that will initialise both key and value, so
| writing "union slot s{0}" initialises everything to 0. One
| issue is that the exact layout for bit fields is
| implementation defined, so if you absolutely need to know
| where key and value are in memory, you will have to read
| GCC's manual (or just experiment). Another is that you cannot
| take the address of key or value individually, but if your
| code was already using uint64_t, you probably don't need to.
|
| 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.
| nitnelave wrote:
| You can probably get away with just a union between a 64
| bit and 2 32 bit integers.
| crest wrote:
| C has finally gained `alignas` so you can avoid the union
| hack or you could just rely on malloc to alway return the
| maximum alignment anyway.
| loeg wrote:
| No real reason. Slightly terser to compare with zero to find an
| empty slot.
| mwkaufma wrote:
| Or better, just store keys and values in separate arrays, so
| you can have compact cache lines of just keys when probing.
| Aardwolf wrote:
| > 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...
| dragontamer wrote:
| This hashtable implements a multiset. Not (merely) a simple
| set.
| re wrote:
| > a linear array of all the 4 billion values, with the key as
| array index, which fits in 16 GiB
|
| The hash table has the significant advantage of having a _much_
| smaller _minimum_ size.
|
| > Perhaps text strings as keys and values would give a more
| interesting example
|
| Keep reading to "If keys and values are larger than 32 bits"
| artur44 wrote:
| I 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.
| hinkley wrote:
| 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.
| crest wrote:
| My best improvment was just bit-interleaving both axes of a
| 2x32bit integer coordinate (aka z-curve). I obtained factor
| ~100x (yes factor not percent) throughput improvement over
| locality in only one dimension. All it took was ~10 lines of
| bit twiddling. The runtime went from a bit above 300ms to
| slightly less then 3ms.
| throw-the-towel wrote:
| I'm wondering how do you folk even come up with this kind
| of optimisations.
| hinkley wrote:
| [delayed]
| saltcured wrote:
| 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.
| ww520 wrote:
| 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.
| air217 wrote:
| Used Gemini to explain this. Very interesting and I think Gemini
| did a good job explaining the Robin hood fairness mechanism
|
| https://gemini.google.com/share/5add15a1c12f
___________________________________________________________________
(page generated 2025-12-09 23:00 UTC)