[rust-dev] hashmap benchmark

Masklinn masklinn at masklinn.net
Mon Apr 9 05:48:55 PDT 2012


On 2012-04-08, at 23:21 , Niko Matsakis wrote:

> On 4/8/12 12:15 PM, Stefan Plantikow wrote:
>> Hi,
>> 
>> I was thinking about this, too. One of the state-of-the art algorithms seems to be hopscotch hashing, wikipedia has a quite good introduction to it.  Even though it has been developed for concurrent access, it should also be quite good in a single core scenario and has a really low memory footprint (90% full hash table still works reasonably). I was thinking about implementing that for fun once the currently ongoing changes to regions and vectors are complete.
> 
> I am totally excited about offering a variety of map abstractions.  One additional thing I would particularly like (which is kind of orthogonal) is a default map implementation that begins as a straight-up list of some fixed size and then shifts to another algorithm as the table is populated.  Of course we'd want to test and tune to see where it makes sense to shift, but I believe that a lot of hash tables are generally small (but not always) and thus can benefit from changing strategies as they fill up.  In fact I would like to have a similar approach to each of the basic container types (a default implementation that adjusts and does the right thing, plus a variety of more specific implementations).

Cocoa has a lot of that kind of things, if somebody wants to do it.


More information about the Rust-dev mailing list