[rust-dev] hashmap benchmark

Brian Anderson banderson at mozilla.com
Sun Apr 8 14:16:34 PDT 2012


On 04/08/2012 01:55 PM, Stefan Plantikow wrote:
> Hi,
>
>
> Am Sonntag, 8. April 2012 um 22:32 schrieb Brian Anderson:
>
>>> 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.
>>
> That would be nice. For hash table algorithms, ctpop/ctlz/cttz will be really useful (should also speedup the sudoku benchmark :). And swap is quite helpful for dealing with utf8 byte order swapping. How would one call these via the rust intrinsics? I am not deep enough into the llvm-rust-bits.

As a rust intrinsic perhaps like

     #[abi = "rust-intrinsic"]
     native mod intrinsics {
         fn bswap_i16(i: i16) -> i16;
     }

The rust intrinsics would all just be hardcoded into the compiler to 
translate to the appropriate llvm intrinsics.

As an llvm intrinsic:

     #[abi = "llvm-intrinsic"]
     native mod intrinsics {
         #[link_name = "bswap.i16"]
         fn bswap_i16(i16: i16) -> i16;
     }

In this case rustc probably doesn't need to know anything specific about 
the intrinsic - we just generate an intrinsic instruction with the given 
name and types.

>
>>> Feedback/Suggestions?
>>>
> Is going for hopscotch a good idea? Ah well, will try in any case ;)

I'm not really familiar with the subject. If the intent is to replace 
std::map then presumably anything that demonstrates better performance 
is a good idea.

>>> 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.
> Ok, that makes sense to some extent, though things like comparison etc already could move towards using interfaces, I guess.
>
>



More information about the Rust-dev mailing list