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).
I also think persistent collections would be very useful.
Hashing algorithms (hopscotch, bloom filters) could greatly benefit from having
access to the llvm bit manipulation intrinsics (ctpop, ctlz, cttz, bswap).
I was going to say that we should just build them into the compiler as
intrinsics (after Marijn's work on intrinsics, this should be fairly
straightforward). But Brian's e-mail also looks pretty nice, actually.
In general I'd rather avoid introducing arbitrary LLVM assembly---the
further we can avoid exposing our use of LLVM, the better imo---but
packaging things as "native" functions helps to keep us relatively
portable should we move away from LLVM in the future.
Niko
_______________________________________________
Rust-dev mailing list
[email protected]
https://mail.mozilla.org/listinfo/rust-dev
