[rust-dev] hashmap benchmark
kobi2187 at gmail.com
Mon Apr 9 05:24:54 PDT 2012
the felix programming language uses Judy arrays (extensively?), and seem
to have a good understanding of them.
maybe you can check out what he came up with.
It's a nice language, too, with some interesting features.
On 4/9/2012 2:20 PM, Stefan Plantikow wrote:
> 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,
> Rust-dev mailing list
> Rust-dev at mozilla.org
More information about the Rust-dev