[rust-dev] hashmap benchmark
stefan.plantikow at googlemail.com
Sun Apr 8 12:15:31 PDT 2012
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.
Hashing algorithms (hopscotch, bloom filters) could greatly benefit from having access to the llvm bit manipulation intrinsics (ctpop, ctlz, cttz, bswap). I think the general plan was to access these using some form of inline llvm asm. However in the absence of that I wonder wether we should just have support for those directly in core or std for all the integer types (quite some languages do that).
PS: Is there yet a plan on how to move towards more use of interfaces in the libs, and (by extension) rustc?
More information about the Rust-dev