21–30 of 39 posts
> 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...
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; }
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.
> 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...
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"
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.
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.
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; }
Earlier quoted context omitted.
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.
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.
Earlier quoted context omitted.
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.
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.
If you would have asked me to bet on which one would have had the bigger impact I would have split the difference.
My second favorite was similar. Two functions making a call instead of sharing the answer. Profiler said 10% cumulative. I removed half. Instead of 5% I got 20%. Which just demonstrates how much data a profiler cannot show you.
Earlier quoted context omitted.
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.
I'm wondering how do you folk even come up with this kind of optimisations.
Profilers lie and some more than most. I’ve gotten 3x from code with a perfectly rectangular profile output.
Part of it comes down to a trick game devs steal from finance: give each task a budget and keep it to the budget even if it’s not the tall tent pole.
You should not spend 10% of your response time on telemetry and logging combined. Yet I pulled 10% TTFB out of just the logging and telemetry code on a project. It was a frog boiling situation. Every new epic used the new code and determining the cumulative cost wasn’t easy.
Yay, we've got an equivalent of SIB byte but as three (six?) separate opcodes. Well, sub-opcodes.
It's a shame though that Zcmp extension didn't get into RVA23 even as an optional extension.
> 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...
If you actually only have a handful of entries in the table, it is measurable in bytes.
A linear array of all 4 billion possible values will occupy 16 GiB (of virtual memory) upfront. We have then essentially replaced the hash table with a radix tree --- that made up of the page directories and tables of the VM system. If only the highest and lowest value are present in the table, then we only need the highest and lowest page (4 kB or whatever) to be mapped. It's not very compact for small sets; storing N numbers in random locations could require as many as N virtual memory pages to be committed.