[rust-dev] hashmap benchmark

Stefan Plantikow stefan.plantikow at googlemail.com
Mon Apr 9 04:20:42 PDT 2012


Hi again,

Am Sonntag, 8. April 2012 um 23:23 schrieb Sebastian Sylvan: 
> On Sun, Apr 8, 2012 at 1:55 PM, Stefan Plantikow
> <stefan.plantikow at googlemail.com (mailto:stefan.plantikow at googlemail.com)> wrote:
> > > > Feedback/Suggestions?
> > > 
> > 
> > Is going for hopscotch a good idea? Ah well, will try in any case ;)
> 
> 
> One of the most surprisingly awesome hash table algorithms (to me at
> least) is open addressing based on "robin hood hashing". It's been
> around for ages, but almost nobody knows about it. It's *such* a
> simple (i.e. fast!) tweak to the regular algorithm, and it makes all
> the difference. I implemented the basic ops in C++ and it was
> something like two orders of magnitude faster than the built in
> unordered_set in Visual Studio for insertions and one order of
> magnitude for lookups.
> 

Thanks for the pointer, that is definitely an algorithm to keep in mind!

I read the hopscotch paper today and among other things they evaluate hopscotch against a highly optimized linear probing algorithm.  Hopscotch outperforms that linear probing approach by a noticeable margin, likely due to better cache alignment (hopscotch on average requires < 1 cache miss!). Though it is not completely clear how much that carries over to another linear probing algorithm, I still tend towards implementing single core hopscotch with key displacement for now. Actually, it may be possible to combine robin hood probe counts with hopscotch hashing to get the reduced variance effect and I probably will try that.

While digging through papers, I also notices that there are new results that limit the memory requirements of near perfect hash functions (fixed key sets), and stumbled upon judy arrays (which I didn't know before and may be interesting to try, too, even though they are badly described by the authors).

May rust get more and faster data structures,


Cheers, 


Stefan


More information about the Rust-dev mailing list