Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

My favourite small hash table

corsix.org

Post reply on HN
Print view View original

31–39 of 39 posts

Re: My favourite small hash table

#31

Post by jasonwatkinspdx »

artur44 wrote: post #7

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.

I'm a big fan of the basic power of two choices hash table design. It's simple to understand and implement, has reasonable constant factors, and hits high load factors on real world datasets.

You can use more elaborate probe and relocation schemes, but just choosing the less full bucket and resizing if both choices are full gets you surprisingly far.

Re: My favourite small hash table

#32

Post by kccqzy »

jasonwatkinspdx wrote: post #31
artur44 wrote: post #7

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.

I'm a big fan of the basic power of two choices hash table design. It's simple to understand and implement, has reasonable constant factors, and hits high load factors on real world datasets. You can use more elaborate probe and relocation schemes, but just choosing the less full bucket and resizing if both choices are full gets you surprisingly far.

Power-of-two length is also the natural choice for a growable linear array where the designer has no idea how many elements there will be.

Re: My favourite small hash table

#33

Post by attractivechaos »

This is a smart implementation of Robin Hood hashing I am not aware of. In my understanding, a standard implementation keeps the probe length of each entry. This one avoids that due to its extra constraints. I don't quite understand the following strategy, though

> To meet property (3) [if the key 0 is present, its value is not 0] ... "array index plus one" can be stored rather than "array index".

If hash code can take any value in [0,2^32), how to define a special value for empty buckets? The more common solution is to have a special key, not a special hash code, for empty slots, which is easier to achieve. In addition, as the author points out, supporting generic keys requires to store 32-bit hash values. With the extra 4 bytes per bucket, it is not clear if this implementation is better than plain linear probing (my favorite). The fastest hash table implementations like boost and abseil don't often use Robin Hood hashing.

Re: My favourite small hash table

#36

Post by beeforpork »

Concerning hash algorithms, for me, it was cuckoo hashing that blew me away. The algorithm is so simple and yet has O(1) guaranteed lookup complexity, i.e., it is better on theoretical level than other open addressing. It is also versatile by having a configurable trade-off (the number of buckets) between time constant and fill ratio. Most impressive is its simplicity combined with that it was invented only so recently (2001).

https://en.wikipedia.org/wiki/Cuckoo_hashing

Re: My favourite small hash table

#37

Post by camel-cdr »

Joker_vD wrote: post #29

> If the Zba extension is present, sh3add.uw is a single instruction for zero-extending idx from 32 bits to 64, multiplying it by sizeof(uint64_t), and adding it to slots. 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.

> It's a shame though that Zcmp extension didn't get into RVA23 even as an optional extension

Zcmp is only for embedded applications without D support.

You wouldn't want an instruction with up to 13 destinations in high performance designs anyways.

If you want load/store pair, we already have that, you can just interpret two adjacent 16-bit load or stores as a single 32-bit instruction.

Re: My favourite small hash table

#38

Post by Joker_vD »

camel-cdr wrote: post #37
Joker_vD wrote: post #29

> If the Zba extension is present, sh3add.uw is a single instruction for zero-extending idx from 32 bits to 64, multiplying it by sizeof(uint64_t), and adding it to slots. 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.

> It's a shame though that Zcmp extension didn't get into RVA23 even as an optional extension Zcmp is only for embedded applications without D support. You wouldn't want an instruction with up to 13 destinations in high performance designs anyways. If you want load/store pair, we already have that, you can just interpret two adjacent 16-bit load or stores as a single 32-bit instruction.

> You wouldn't want an instruction with up to 13 destinations in high performance designs anyways.

Why not? Code density matters even in high-performance designs although I guess the "millicode routines" can help with that somewhat. Still, the ordering of stores/loads is undefined, and they are allowed to be re-done however many times, so... it shouldn't be onerous to implement? Expanding it into μops during the decoding stages seems straightforward.

Re: My favourite small hash table

#39

Post by camel-cdr »

Joker_vD wrote: post #38
camel-cdr wrote: post #37

Earlier quoted context omitted.

> It's a shame though that Zcmp extension didn't get into RVA23 even as an optional extension Zcmp is only for embedded applications without D support. You wouldn't want an instruction with up to 13 destinations in high performance designs anyways. If you want load/store pair, we already have that, you can just interpret two adjacent 16-bit load or stores as a single 32-bit instruction.

> You wouldn't want an instruction with up to 13 destinations in high performance designs anyways. Why not? Code density matters even in high-performance designs although I guess the "millicode routines" can help with that somewhat. Still, the ordering of stores/loads is undefined, and they are allowed to be re-done however many times, so... it shouldn't be onerous to implement? Expanding it into μops during the deco…

> Expanding it into μops during the decoding stages seems straightforward.

I wouldn't say so, because if you want to be able to crack an instruction into up to N uops, now the second instruction could be placed in any slot from the 2nd to the 1+Nth and you now have to create huge shuffle hardware tk support this.

Apple for example can only crack instructions that generate up to 3 μops at decode (or before rename) anything beyond needs to be microcoded and stall decoding other instructions.

Post reply on HN