3 ms·
Hum, the nice thing with Robin Hood hashing is that you get close to 90% load factor without pathological performance degradation. If you have a fixed probe cou
by gpderetta 10y ago
Hum, the nice thing with Robin Hood hashing is that you get close to 90% load factor without pathological performance degradation. If you have a fixed probe count, wouldn't you be better just grouping your buckets in fixed size sub buckets and doing (trivially parallelizable) linear searches for lookups and to find empty insert positions?
On a related note, I have in general concerns about latency spikes due to rehashing. Is there a good, general, incremental rehashing scheme?
- throwawayish 10y ago> Is there a good, general, incremental rehashing scheme? Trees.
- gpderetta 10y agoAs a C++ programmer, my default dictionary is usually an std::map (which is just an RB-tree), so, yes agree 100%. But the amortized O(1) lookup of hash tables is hard to beat. edit: s/bass/beat/
- throwawayish 10y ago> But the amortized O(1) lookup of hash tables is hard to beat. On the other hand: the performance characteristics of trees are much easier to predict. And in many cases a HT lookup isn't distinguishable from a tree lookup, at least if it's a dedicated application data structure, like some index or so. I feel like HTs are very good for smaller structures (excellent example: dictionary/hashtable-based interpreters), but for larger data structures (e.g.: indices) ... not so much.
- leventov 10y agoThere is a good general segmented hashtable algorithm with ~100 times smaller rehash spikes than in classic hash tables: https://github.com/OpenHFT/SmoothieMap/blob/master/src/main/java/net/openhft/smoothie/SmoothieMap.java#L94 https://github.com/OpenHFT/SmoothieMap/blob/master/src/main/... The idea is not super clever so I'm sure many people found & implemented it in papers and other languages, but I didn't find them. Will be grateful if someone points me to prior work.
- _benedict 10y agoWell, if you're willing to incur a slight latency penalty on each access, incremental rehashing is terrifically easy. Just keep both the old and new backing arrays around, and consult a pointer to determine how far in the first backing array has been invalidated. If you follow a Shalev/Shavit hash-ordered-lists scheme the rehash doesn't even need to move anything, and can be done with a straight memcpy, or in a separate thread. The link below is an implementation that was intended for Cassandra (so is simplified and append-only, but also a concurrent map - which could be relaxed). It has the nice property that it will "fix" the backing array on-demand, so straight-up copying the existing contents of the backing array into the new region of the backing array, once doubled, will set things up for a gradual transition. Similarly, it's trivial for the backing array to instead grow incrementally, and for an extra level of indirection to prevent ever having to reallocate older regions (since their contents never changes on rehash). https://github.com/belliottsmith/cassandra/blob/47d970ead69035f5cd294ebae536dd3d5e985666/src/java/org/apache/cassandra/concurrent/NonBlockingHashOrderedMap.java https://github.com/belliottsmith/cassandra/blob/47d970ead690...
- gpderetta 10y agokeeping the old array around is the obvious solution, but the problem is that you might need to rehash the second array as well. Do you need to keep an arbitrary number of arrays around or there are hashing schemes that guarantee that you'll be done with rehashing by the time you need to rehash the second buffer? I'll read up on hash-ordered-lists.
- _benedict 10y agoWell, depending on your rehash trigger (i.e. if it is dictated by the load factor, not the number of reprobes), it can be guaranteed that the new array does not need to be rehashed before the in-progress migration, if you migrate at least one bucket per write operation. If you were to (sensibly) migrate many (say, >= 16) with each write, the likelihood of this happening is very low with any reasonable hash function, since the work of rehashing will typically be done many times faster than the skew can retrigger your rehash. This at least makes the incidence of a latency-inducing event of waiting for the prior rehash to complete very low. If you rehash based on something like "number of reprobes" then it's probably impossible to absolutely guarantee that a rehash cannot be triggered before a prior one begins, but the linked approach would permit growing the backing array discontiguously (assuming an extra level of indirection to the backing array). But this would obviously incur some extra overheads, and is not entirely dissimilar to hash-tries, which also avoid any costly global rehash. I think the class-level comment in the code I linked is perhaps the best introduction to split-ordered lists I know of (not hash-ordered; they're sorted by the reverse bitstring of the hash), since they're not widely discussed and not immediately intuitive.
- mirekrusin 10y agoFractal Trees have interesting gradual "rehashing".
- malisper 10y ago> On a related note, I have in general concerns about latency spikes due to rehashing. Is there a good, general, incremental rehashing scheme? One option is to move a few elements over from the old hash table on each operation[0]. A second option is to use linear hashing[1] (different from linear probing). Linear hashing let's you increase the size of your hash table by one bucket at a time. The general idea is once your hash table is full, you allocate a new bucket (generally from a preallocated array) and move half of the elements from an old bucket to the new bucket. I know Postgres used to use linear hashing, but I'm not sure about the current state. I heard they started using Robin Hood hashing, but I haven't looked at whether that is unrelated to the code that uses linear hashing.