Dynamic hash tables [LWN.net]

Dynamic hash tables

Posted Sep 26, 2014 19:55 UTC (Fri) by perlwolf (guest, #46060)
In reply to: Dynamic hash tables by Wol
Parent article: Relativistic hash tables, part 1: Algorithms

The cost is more significant where it is some random buckets that have been split rather than having a clean break between the unsplit and the split buckets. There, you have to take the linked list pointer and add a flag to determine whether it is really pointing to a linked list or if it is actually a link to a split bucket structure. So, the code has a boolean test before traversing the list for an unsplit bucket, or before the logic to process the lower level split in some way, eventually getting down (perhaps) to a linked list to traverse.

to post comments

Dynamic hash tables

Posted Sep 26, 2014 20:50 UTC (Fri) by Wol (subscriber, #4433) [Link] (2 responses)

> The cost is more significant where it is some random buckets that have been split

Which is exactly what my algorithm does NOT do.

Chances are, my algorithm converts the key to the bucket rather faster than a standard hash algorithm (it uses and(), not mod().). And there's no fancy logic past that - the bucket is the right bucket, first time, EVERY TIME. There's no such thing as a "split bucket" structure.

(And if it hits a linked list, it's a failure mode ... it's intended to identify the right disk block first time every time - a disk miss is *expensive*. It handles it - it has to - but because it's expensive it's not a good idea. The miss rate is typically 5%)

Cheers,
Wol

Dynamic hash tables

Posted Sep 26, 2014 21:17 UTC (Fri) by perlwolf (guest, #46060) [Link] (1 responses)

Ok, you are back to the structure that always splits the last of the large buckets. That is unlikely to be the bucket that has the longest chain, the one most in need of being split, so the split gains no significant benefit. A useful dynamic splitter would split a bucket when it reaches some threshold, but that is unlikely to be conveniently placed as the last large bucket. You either get a fast determination of which buckets have an extra split, or the ability to split the bucket that needs it, but not both.

Dynamic hash tables

Posted Sep 26, 2014 23:27 UTC (Fri) by Wol (subscriber, #4433) [Link]

Yes, but the thing is, it works. Statistically, the split bucket is likely to have a longer-than-average chain. And, on average, at *no* time does *any* bucket have a chain :-) So it's quite possible for me that a "split the largest bucket" would fail because it wouldn't find a "largest" bucket to split!

And in my use case (multiple items per allocation block) it doesn't seem to matter. If the average block is 80% full, I'll find the item I'm looking for in the first block I try 19 times out of 20. That's pretty good ...

It's all a tradeoff. I trade uneven clumping for a simple algorithm and a perfect modulo. I also trade multiple items per allocation block to reduce chains.

You're trading unrestricted access most of the time, and accepting that you have an imperfect modulo and every now and then you're going to get a bit of a hit as the table resizes.

I'm trading the cost of scanning a bucket, and the occasional stall as I hit a locked bucket, for the fact that most of the time I have no chains, and it's damn bad luck if a read hits a bucket that's splitting.

Both trades are appropriate for our use circumstances - a chain causes me an unwanted disk i/o stall, you're not worried about memory usage but need to prevent chains getting too long.

Cheers,
Wol