[rust-dev] hashmap benchmark

Brian Anderson banderson at mozilla.com
Sun Apr 8 13:32:13 PDT 2012


On 04/08/2012 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.
>
> 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).

We used to have an 'llvm' ABI for native mods that was intended to give 
access to the llvm intrinsics. We could add that back, or just add them 
as rust intrinsics ('rust-intrinsic' ABI) as needed.

> Feedback/Suggestions?
>
> PS: Is there yet a plan on how to move towards more use of interfaces in the libs, and (by extension) rustc?
>

I don't think there's a plan yet. It's probably worth waiting for classes.



More information about the Rust-dev mailing list