subject:"mozilla\:\:Hash\{Map,Set\}"

Re: mozilla::Hash{Map,Set}

2018-08-16 Thread Nicholas Nethercote

On Fri, Aug 17, 2018 at 3:31 AM, Eric Rahm  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

Re: mozilla::Hash{Map,Set}

2018-08-16 Thread Nicholas Nethercote

On Fri, Aug 17, 2018 at 3:10 AM, Kris Maglione 
wrote:

>
> It would probably worth converging the APIs, if only because the
> nsTHashtable APIs are arcane and antiquated. But it's easier said than
> done. There are a lot of consumers of all of the hashtable APIs, and the
> code is... not very easy to work with.
>

Also, the APIs are *very* different.

Nick
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: mozilla::Hash{Map,Set}

2018-08-16 Thread Kris Maglione

On Thu, Aug 16, 2018 at 09:07:57AM -0400, Alex Gaynor wrote:

Similarly, would it make sense to consolidate the APIs, as much as
possible, if the primary differences are around implementation details like
"how much is templated/inlined"?

It would probably worth converging the APIs, if only because the
nsTHashtable APIs are arcane and antiquated. But it's easier
said than done. There are a lot of consumers of all of the
hashtable APIs, and the code is... not very easy to work with.

On Wed, Aug 15, 2018 at 5:39 AM Nicholas Nethercote
wrote:

Hi,

I recently moved Spidermonkey's js::Hash{Map,Set} classes from
js/public/HashTable.h into mfbt/HashTable.h and renamed them as
mozilla::Hash{Map,Set}. They can now be used throughout Gecko.

(js/public/HashTable.h still exists in order to provide renamings of
mozilla::Hash{Map,Set} as js::Hash{Map,Set}.)

Why might you use mozilla::Hash{Map,Set} instead of PLDHashTable (or
nsTHashtable and other descendants)?

- Better API: these types provide proper HashMap and HashSet instances, and
(in my opinion) are easier to use.

- Speed: the microbenchmark in xpcom/rust/gtest/bench-collections/Bench.cpp
shows that mozilla::HashSet is 2x or more faster than PLDHashTable. E.g.
compare "MozHash" against "PLDHash" in this graph:

https://treeherder.mozilla.org/perf.html#/graphs?timerange=604800=mozilla-central,1730159,1,6=mozilla-central,1730162,1,6=mozilla-central,1730164,1,6=mozilla-central,1732092,1,6=mozilla-central,1730163,1,6=mozilla-central,1730160,1,6

Bug 1477627 converted a hot hash table from PLDHashTable to
mozilla::HashSet and appears to have sped up cycle collection in some cases
by 7%. If you know of another PLDHashTable that is hot, it might be worth
converting it to mozilla::HashTable.

Both mozilla::Hash{Map,Set} and PLDHashTable use the same double-hashing
algorithm; the speed difference is due to mozilla::HashSet's extensive use
of templating and inlining. The downside of this is that mozilla::HashSet
will increase binary size more than PLDHashTable.

There are overview comments at the top of mfbt/HashTable.h, and the classes
themselves have more detailed comments about every method.

Nick
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

--
Kris Maglione
Senior Firefox Add-ons Engineer
Mozilla Corporation

He who joyfully marches to music in rank and file has already earned
my contempt. He has been given a large brain by mistake, since for
him the spinal cord would suffice.
--Albert Einstein

___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: mozilla::Hash{Map,Set}

2018-08-16 Thread Eric Rahm

On Thu, Aug 16, 2018 at 6:07 AM, Alex Gaynor  wrote:

> Would it make sense to consider giving nsTHashtable and PLDHashTable
> different names? Right now the names suggest that we have 3 general purpose
> hash tables, but it might be easier if the names better suggested their
> purpose, e.g. PLDHashTable -> MinimalCodeSizeHashTable (I'm sure we can do
> better than that).
>

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.

[1]
https://developer.mozilla.org/en-US/docs/Mozilla/Tech/XPCOM/Guide/Hashtables



> Similarly, would it make sense to consolidate the APIs, as much as
> possible, if the primary differences are around implementation details like
> "how much is templated/inlined"?
>
>
Really we just have PLDHashTable for historical reasons, not because of
text size. I'm not sure we even want to keep PLDHashTable at all. We *have*
found some issues where there's higher memory overhead due to the way our
template wrappers pad their key structures and having a much lower level,
but slightly annoying to use hashtable ended up being a good thing.
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.

[2] https://bugzilla.mozilla.org/show_bug.cgi?id=1402910

-e



> Alex
>
>
> On Wed, Aug 15, 2018 at 5:39 AM Nicholas Nethercote <
> n.netherc...@gmail.com>
> wrote:
>
> > Hi,
> >
> > I recently moved Spidermonkey's js::Hash{Map,Set} classes from
> > js/public/HashTable.h into mfbt/HashTable.h and renamed them as
> > mozilla::Hash{Map,Set}. They can now be used throughout Gecko.
> >
> > (js/public/HashTable.h still exists in order to provide renamings of
> > mozilla::Hash{Map,Set} as js::Hash{Map,Set}.)
> >
> > Why might you use mozilla::Hash{Map,Set} instead of PLDHashTable (or
> > nsTHashtable and other descendants)?
> >
> > - Better API: these types provide proper HashMap and HashSet instances,
> and
> > (in my opinion) are easier to use.
> >
> > - Speed: the microbenchmark in xpcom/rust/gtest/bench-
> collections/Bench.cpp
> > shows that mozilla::HashSet is 2x or more faster than PLDHashTable. E.g.
> > compare "MozHash" against "PLDHash" in this graph:
> >
> >
> > https://treeherder.mozilla.org/perf.html#/graphs?
> timerange=604800=mozilla-central,1730159,1,6&
> series=mozilla-central,1730162,1,6=mozilla-
> central,1730164,1,6=mozilla-central,1732092,1,6&
> series=mozilla-central,1730163,1,6=mozilla-central,1730160,1,6
> >
> > Bug 1477627 converted a hot hash table from PLDHashTable to
> > mozilla::HashSet and appears to have sped up cycle collection in some
> cases
> > by 7%. If you know of another PLDHashTable that is hot, it might be worth
> > converting it to mozilla::HashTable.
> >
> > Both mozilla::Hash{Map,Set} and PLDHashTable use the same double-hashing
> > algorithm; the speed difference is due to mozilla::HashSet's extensive
> use
> > of templating and inlining. The downside of this is that mozilla::HashSet
> > will increase binary size more than PLDHashTable.
> >
> > There are overview comments at the top of mfbt/HashTable.h, and the
> classes
> > themselves have more detailed comments about every method.
> >
> > Nick
> > ___
> > dev-platform mailing list
> > dev-platform@lists.mozilla.org
> > https://lists.mozilla.org/listinfo/dev-platform
> >
> ___
> dev-platform mailing list
> dev-platform@lists.mozilla.org
> https://lists.mozilla.org/listinfo/dev-platform
>
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: mozilla::Hash{Map,Set}

2018-08-16 Thread Alex Gaynor

Would it make sense to consider giving nsTHashtable and PLDHashTable
different names? Right now the names suggest that we have 3 general purpose
hash tables, but it might be easier if the names better suggested their
purpose, e.g. PLDHashTable -> MinimalCodeSizeHashTable (I'm sure we can do
better than that).

Similarly, would it make sense to consolidate the APIs, as much as
possible, if the primary differences are around implementation details like
"how much is templated/inlined"?

Alex


On Wed, Aug 15, 2018 at 5:39 AM Nicholas Nethercote 
wrote:

> Hi,
>
> I recently moved Spidermonkey's js::Hash{Map,Set} classes from
> js/public/HashTable.h into mfbt/HashTable.h and renamed them as
> mozilla::Hash{Map,Set}. They can now be used throughout Gecko.
>
> (js/public/HashTable.h still exists in order to provide renamings of
> mozilla::Hash{Map,Set} as js::Hash{Map,Set}.)
>
> Why might you use mozilla::Hash{Map,Set} instead of PLDHashTable (or
> nsTHashtable and other descendants)?
>
> - Better API: these types provide proper HashMap and HashSet instances, and
> (in my opinion) are easier to use.
>
> - Speed: the microbenchmark in xpcom/rust/gtest/bench-collections/Bench.cpp
> shows that mozilla::HashSet is 2x or more faster than PLDHashTable. E.g.
> compare "MozHash" against "PLDHash" in this graph:
>
>
> https://treeherder.mozilla.org/perf.html#/graphs?timerange=604800=mozilla-central,1730159,1,6=mozilla-central,1730162,1,6=mozilla-central,1730164,1,6=mozilla-central,1732092,1,6=mozilla-central,1730163,1,6=mozilla-central,1730160,1,6
>
> Bug 1477627 converted a hot hash table from PLDHashTable to
> mozilla::HashSet and appears to have sped up cycle collection in some cases
> by 7%. If you know of another PLDHashTable that is hot, it might be worth
> converting it to mozilla::HashTable.
>
> Both mozilla::Hash{Map,Set} and PLDHashTable use the same double-hashing
> algorithm; the speed difference is due to mozilla::HashSet's extensive use
> of templating and inlining. The downside of this is that mozilla::HashSet
> will increase binary size more than PLDHashTable.
>
> There are overview comments at the top of mfbt/HashTable.h, and the classes
> themselves have more detailed comments about every method.
>
> Nick
> ___
> dev-platform mailing list
> dev-platform@lists.mozilla.org
> https://lists.mozilla.org/listinfo/dev-platform
>
___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: mozilla::Hash{Map,Set}

2018-08-16 Thread Kris Maglione


On Wed, Aug 15, 2018 at 07:28:26PM -0400, Ehsan Akhgari wrote:

On Wed, Aug 15, 2018 at 5:39 AM Nicholas Nethercote 
wrote:

Bug 1477627 converted a hot hash table from PLDHashTable to
mozilla::HashSet and appears to have sped up cycle collection in some cases
by 7%. If you know of another PLDHashTable that is hot, it might be worth
converting it to mozilla::HashTable.



Do you have any good suggestions of how to find such candidates?  One thing
that came to my mind was that the BHR data may be a useful source of
insight for this...  <
https://arewesmoothyet.com/?category=all=512_2048=explore=c8e925752fc94f78af9349665aad14c7=PLDHashTable%3A%3ASearchTable=0>
(for content processes, for example) suggests a few hashtables based on a
very quick skimming which aren't surprising to me (things like
nsHTMLDocument::mIdentifierMap, some XPCOM component manager hashtables,
memory reporter hashtables, some font hashtables, the preferences
hashtable, sEventListenerManagersHash, mJSHolderMap, etc.


Note I'm planning to replace most of the component manager hashtables with 
static hashtables (bug 1478124), so those probably aren't great candidates 
just yet.

___
dev-platform mailing list
dev-platform@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-platform

Re: mozilla::Hash{Map,Set}

2018-08-15 Thread Kris Maglione

On Wed, Aug 15, 2018 at 01:18:23PM -0700, Jeff Gilbert wrote:

What are the pros/cons to mozilla::Hash{Map,Set} vs
std::unordered_{map,set}? I'm assuming perf is the main draw? Do we
have a data on this too?

According to our benchmarks, mozilla::HashMap is much faster
than std::unordered_map. But that's not the reason you should
use it instead.

The main reason you shouldn't use std::unordered_map is that
it's not approved for use in mozilla-central (though it is on
the whitelist, and marked as unreviewed). Beyond that, we have
no control over the memory usage or performance characteristics
of unordered_map or unordered_set, and no way to add memory
reporters for them. Their performance and memory usage are likely
to vary from system to system, and from STL version to STL
version, without giving us any indication, unless we're lucky
and spot a talos or AWSY regression that we don't have any easy
way to track down.

On Mon, Aug 13, 2018 at 10:44 PM, Nicholas Nethercote
wrote: