On Fri, Aug 17, 2018 at 3:31 AM, Eric Rahm <er...@mozilla.com> wrote:
>
> nsTHashTable is just a templated wrapper around PLDHashTable. For
> reference we also have nsDataHashtable, nsClassHashtable,
> nsRefPtrHashtable, nsInterfaceHashtable [1] all of which are rather
> convenient wrappers around PLDHashTable. These have also been implemented
> in such a way that the templates have lower code size overhead (thanks
> froydnj!). I somewhat prefer their interfaces to mfbt::HashMap (default
> infallible, plenty of predefined hashers, nice lookup for add semantics,
> etc), but to each their own.
>
About that last sentence:
- Default infallible: true, although I removed the init() function from
mozilla::Hash{Map,Set} (by making allocation lazy, waiting until first
insertion) so at least you don't have to worry about that any more.
- Plenty of predefined hashes: mozilla::Hash{Map,Set} does the right thing
by default if your key is an integer, pointer, UniquePtr, float, or double.
There's also the predefined CStringHasher for C string keys. Nothing at the
moment for RefPtr or nsCOMPtr, though.
- Nice lookup for add semantics: mozilla::Hash{Map,Set} has this too. You
use put() for an unconditional insertion, or lookupForAdd() + add() for a
conditional insertion.
If you ever looked at the old js::Hash{Map,Set} and found it confusing,
it's worth taking another look at mozilla::Hash{Map,Set}, because I
improved the high-level and per-method documentation a lot. I also
completely reordered the classes code so that operations are grouped
logically and are much easier to find.
Additionally we've been thinking about implementing a better hash algorithm
> such as round-robin hashing [2] , I'm not sure if that would work w/
> mfbt::HashMap, but it would be nice to implement it in one place rather
> than two.
>
The main takeaway I got from doing the microbenchmarks in bug 1477622 was
that Robin Hood hashing is probably on a minor improvement. It's probably
worth doing, but:
(a) for C++ hash tables, full templating and inlining makes the biggest
difference;
(b) for Rust hash tables (which already use Robin Hood), choosing a fast
hash function makes the biggest difference.
Point (a) was the reason I decided to move js::Hash{Map,Set} into MFBT.
Nick
_______________________________________________
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform
