1477626 - Move js::Hash{Set,Map} into MFBT

Status: RESOLVED FIXED

(Core :: MFBT, enhancement)

Description

[Nicholas Nethercote [inactive]]

The benchmarks added in bug 1477622 show that js::Hash{Set,Map} are *much* faster than PLDHashTable. So we should make them more broadly available. (As an added bonus, js::Hash{Set,Map} have a much nicer API.)

For reference: bug 891177 did the same thing for js::Vector.

Comment 1

[Olli Pettay [:smaug]]

Is there any reason to not make nsTHashtable to use HashMap?

Comment 2

[Nathan Froyd [:froydnj]]

(In reply to Olli Pettay [:smaug] (vacation Jul 15->) from comment #1)
> Is there any reason to not make nsTHashtable to use HashMap?

The usual reason that we've avoided doing something like this (and more generally, argued against templatify-ing PLDHashTable) is code bloat.  I think templatifying single tables offers a nice middle ground.  Though once njn imports everything, it would be interesting to see the numbers on code size and performance to see if the intuition about code bloat holds true.

Comment 3

[Nathan Froyd [:froydnj]]

OTOH, it's possible that if we did care about the code size of js::Hash*, we could start applying tricks like https://searchfox.org/mozilla-central/source/xpcom/ds/nsTHashtable.h#498-503 to it and see how far that gets us.

Comment 4

[Nicholas Nethercote [inactive]]

Also, nsTHashTable's API is very different to js::Hash{Set,Map}. It would be a challenge to get them to play nicely together.

Comment 5

[Nicholas Nethercote [inactive]]

AFAICT, the main reason js::Hash is so much faster than PLDHash is that it inlines *everything* -- the type is entirely defined in a header, and full templating means there are no "virtual ops".

Comment 6

[Nicholas Nethercote [inactive]]

Attachment: Bug 1477626 - Replace some bespoke code with a call to CeilingLog2().

After all, bug 543034 was fixed 9 years ago.

Review commit: https://reviewboard.mozilla.org/r/259544/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/259544/

Comment 7

[Nicholas Nethercote [inactive]]

Attachment: Bug 1477626 - Use `uint32_t` instead of `unsigned` in HashTable.h.

Because it's more precise, and gives us more consistency.

Review commit: https://reviewboard.mozilla.org/r/259546/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/259546/

Comment 8

[Nicholas Nethercote [inactive]]

Attachment: Bug 1477626 - Introduce mozilla::HashNumber and use it in various places.

Currently we have three ways of representing hash values.

- uint32_t: used in HashFunctions.h.

- PLDHashNumber: defined in PLDHashTable.{h,cpp}.

- js::HashNumber: defined in js/public/Utility.h.

Functions that create hash values with functions from HashFunctions.h use a mix
of these three types. It's a bit of a mess.

This patch introduces mozilla::HashNumber, and redefines PLDHashNumber and
js::HashNumber as synonyms. It also changes HashFunctions.h to use
mozilla::HashNumber throughout instead of uint32_t.

This leaves plenty of places that still use uint32_t that should use
mozilla::HashNumber or one of its synonyms, but I didn't want to tackle that
now.

The patch also:

- Does similar things for the constants defining the number of bits in each
  hash number type.

- Moves js::HashNumber from Utility.h to HashTable.h, which is a better spot
  for it. (This required changing the signature of ScrambleHashCode(); that's
  ok, it'll get moved by the next patch anyway.)

Review commit: https://reviewboard.mozilla.org/r/259548/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/259548/

Comment 9

[Nicholas Nethercote [inactive]]

Attachment: Bug 1477626 - Move ScrambleHashCode() from js/src/Utility.h to mfbt/HashFunctions.h.

And use it in PLDHashTable.cpp.

Review commit: https://reviewboard.mozilla.org/r/259550/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/259550/

Comment 10

[Nicholas Nethercote [inactive]]

Attachment: Bug 1477626 - Remove use of JS_BIT in js/src/HashTable.h.

Review commit: https://reviewboard.mozilla.org/r/259552/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/259552/

Comment 11

[Nicholas Nethercote [inactive]]

Attachment: Bug 1477626 - Move js::Hash{Set,Map} into MFBT.

The main change is that the patch copies js/public/HashTable.h to
mfbt/HashTable.h, and then changes it as follows.

- Changes `js` namespaces to `mozilla`.

- Changes the default AllocPolicy from the SpiderMonkey-specific
  `TempAllocPolicy` to the generic `MallocAllocPolicy`.

- Adds `#include "AllocPolicy.h"` (like mfbt/Vector.h).

- Changes `JS_DEBUG` use to `DEBUG`.

- Minor comment updates, as necessary.

js/public/HashTable.h is now tiny, holding just a few renamings of things from
the `mozilla` namespace into the `js` namespace to minimize churn elsewhere.
(Those renamings keep `TempAllocPolicy` as the default AllocPolicy for
js::Hash{Set,Map}.)

Also, various template specializations had to be moved from the `js` namespace
to the `mozilla` namespace to avoid compile errors.

Review commit: https://reviewboard.mozilla.org/r/259554/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/259554/

Comment 12

[Nicholas Nethercote [inactive]]

Attachment: Bug 1477626 - Document some differences between mozilla::HashTable and PLDHashTable.

Review commit: https://reviewboard.mozilla.org/r/259556/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/259556/

Comment 13

[Nicholas Nethercote [inactive]]

Attachment: Bug 1477626 - Use mozilla::HashTable instead of JS::HashTable in DMD.

Also use mozilla::HashNumber where appropriate.

Review commit: https://reviewboard.mozilla.org/r/259558/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/259558/

Comment 14

[Nicholas Nethercote [inactive]]

Attachment: Bug 1477626 - Use mozilla::HashTable instead of js::HashTable in Bench.cpp.

Review commit: https://reviewboard.mozilla.org/r/259560/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/259560/

Comment 15

[Nicholas Nethercote [inactive]]

Comment on attachment 8995057 [details]
Bug 1477626 - Replace some bespoke code with a call to CeilingLog2().

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/259544/diff/1-2/

Comment 16

[Nicholas Nethercote [inactive]]

Comment on attachment 8995058 [details]
Bug 1477626 - Use `uint32_t` instead of `unsigned` in HashTable.h.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/259546/diff/1-2/

Comment 17

[Nicholas Nethercote [inactive]]

Comment on attachment 8995059 [details]
Bug 1477626 - Introduce mozilla::HashNumber and use it in various places.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/259548/diff/1-2/

Comment 18

[Nicholas Nethercote [inactive]]

Comment on attachment 8995060 [details]
Bug 1477626 - Move ScrambleHashCode() from js/src/Utility.h to mfbt/HashFunctions.h.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/259550/diff/1-2/

Comment 19

[Nicholas Nethercote [inactive]]

Comment on attachment 8995061 [details]
Bug 1477626 - Remove use of JS_BIT in js/src/HashTable.h.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/259552/diff/1-2/

Comment 20

[Nicholas Nethercote [inactive]]

Comment on attachment 8995062 [details]
Bug 1477626 - Move js::Hash{Set,Map} into MFBT.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/259554/diff/1-2/

Comment 21

[Nicholas Nethercote [inactive]]

Comment on attachment 8995063 [details]
Bug 1477626 - Document some differences between mozilla::HashTable and PLDHashTable.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/259556/diff/1-2/

Comment 22

[Nicholas Nethercote [inactive]]

Comment on attachment 8995064 [details]
Bug 1477626 - Use mozilla::HashTable instead of JS::HashTable in DMD.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/259558/diff/1-2/

Comment 23

[Nicholas Nethercote [inactive]]

Comment on attachment 8995065 [details]
Bug 1477626 - Use mozilla::HashTable instead of js::HashTable in Bench.cpp.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/259560/diff/1-2/

Comment 24

[Nathan Froyd [:froydnj]]

Comment on attachment 8995065 [details]
Bug 1477626 - Use mozilla::HashTable instead of js::HashTable in Bench.cpp.

https://reviewboard.mozilla.org/r/259560/#review266704

Comment 25

[Eric Rahm [:erahm]]

Comment on attachment 8995064 [details]
Bug 1477626 - Use mozilla::HashTable instead of JS::HashTable in DMD.

https://reviewboard.mozilla.org/r/259558/#review266712

Comment 26

[Jeff Walden [:Waldo]]

Comment on attachment 8995057 [details]
Bug 1477626 - Replace some bespoke code with a call to CeilingLog2().

https://reviewboard.mozilla.org/r/259544/#review267424

Comment 27

[Jeff Walden [:Waldo]]

Comment on attachment 8995058 [details]
Bug 1477626 - Use `uint32_t` instead of `unsigned` in HashTable.h.

https://reviewboard.mozilla.org/r/259546/#review267426

Comment 28

[Jeff Walden [:Waldo]]

Comment on attachment 8995058 [details]
Bug 1477626 - Use `uint32_t` instead of `unsigned` in HashTable.h.

https://reviewboard.mozilla.org/r/259546/#review267428

Comment 29

[Jeff Walden [:Waldo]]

Comment on attachment 8995059 [details]
Bug 1477626 - Introduce mozilla::HashNumber and use it in various places.

https://reviewboard.mozilla.org/r/259548/#review267430

::: mfbt/HashFunctions.h:11
(Diff revision 2)
>  
>  /* Utilities for hashing. */
>  
>  /*
> - * This file exports functions for hashing data down to a 32-bit value,
> - * including:
> + * This file exports functions for hashing data down to a uint32_t (a.k.a.
> + * mozilla::HashNumber), including:

It would be nice for HashNumber to not be an integral type but some sort of container -- to force people to explicitly convert to and from uint32_t -- but that can happen after this bug at some point, if indeed it doesn't actually happen in this patch-stack.

::: mfbt/HashFunctions.h:61
(Diff revision 2)
>  
>  #include <stdint.h>
>  
>  namespace mozilla {
>  
> +typedef uint32_t HashNumber;

using HashNumber = uint32_t;

(generally everywhere should be doing C++11-style typedefs now)

Comment 30

[Jeff Walden [:Waldo]]

Comment on attachment 8995060 [details]
Bug 1477626 - Move ScrambleHashCode() from js/src/Utility.h to mfbt/HashFunctions.h.

https://reviewboard.mozilla.org/r/259550/#review267432

::: js/public/HashTable.h:1285
(Diff revision 2)
>          return Entry::isLiveHash(hash);
>      }
>  
>      static HashNumber prepareHash(const Lookup& l)
>      {
> -        HashNumber keyHash = ScrambleHashCode(HashPolicy::hash(l));
> +        HashNumber keyHash = mozilla::detail::ScrambleHashCode(HashPolicy::hash(l));

Hrm.  Not so cool for a detail function to be used outside its own file, but okay for temporarily.  Maybe a separate header for this one function is not a bad idea eventually.

Comment 31

[Jeff Walden [:Waldo]]

Comment on attachment 8995061 [details]
Bug 1477626 - Remove use of JS_BIT in js/src/HashTable.h.

https://reviewboard.mozilla.org/r/259552/#review267436

Excellent.  I always hated JS_BIT, seemed to obscure more than it helped.

Comment 32

[Jeff Walden [:Waldo]]

Comment on attachment 8995062 [details]
Bug 1477626 - Move js::Hash{Set,Map} into MFBT.

https://reviewboard.mozilla.org/r/259554/#review267440

::: mfbt/HashTable.h:770
(Diff revision 2)
> -} // namespace js
> -
> -namespace mozilla {
> -
>  template <typename K, typename V>
> -struct IsPod<js::HashMapEntry<K, V> >
> +struct IsPod<mozilla::HashMapEntry<K, V> >

You're inside namespace mozilla, so you should just un-qualify this.  The class is defined literally three lines up, after all.  :-)

::: mfbt/HashTable.h:939
(Diff revision 2)
>      class Ptr
>      {
>          friend class HashTable;
>  
>          Entry* entry_;
> -#ifdef JS_DEBUG
> +#ifdef DEBUG

So this is a bit bleh, and I'm moderately sure it's enough to r-.

We added JS_DEBUG, distinct from DEBUG, back in the day because it was possible to link user non-debug code against debug SpiderMonkey libraries, or vice versa.  And if you did that, the type declarations in the headers would end up not matching with what was actually in the library and things would Go Very Bad as field offsets would be wrong, constructor calls wouldn't initialize everything or would initialize the wrong things, and so on.  See bug 948099.

Just changing to DEBUG is going to bring back that problem in force for this.  :-\

I do not know what equivalent Mozilla code has, that could be used to equivalent effect for field-omitting purposes.  But we need to figure that out and use that instead here.

::: js/src/ds/OrderedHashTable.h:41
(Diff revision 2)
>   *     bool isEmpty(const Key&);
>   *     void makeEmpty(Key*);
>   */
>  
>  #include "mozilla/HashFunctions.h"
> +#include "mozilla/HashTable.h"

Seeing as this isn't using anything hashy from mozilla::, this should be js/HashTable.h.  Or all the implicit dependencies should be made explicit mozilla:: dependencies.

Comment 33

[Jeff Walden [:Waldo]]

Comment on attachment 8995063 [details]
Bug 1477626 - Document some differences between mozilla::HashTable and PLDHashTable.

https://reviewboard.mozilla.org/r/259556/#review267446

FWIW I think we probably should bite the bullet at some point and define HashTable specializations necessary to common up code for certain disparate hash table instantiations -- e.g. when key/value are pointers and you could have a void* version that the T* versions would delegate to -- but these comments are fine and accurate as to the state of the world now.

Comment 34

[Nicholas Nethercote [inactive]]

> Just changing to DEBUG is going to bring back that problem in force for this.  :-\

mfbt/Vector.h has similar DEBUG-only fields.

Comment 35

[Nicholas Nethercote [inactive]]

> You're inside namespace mozilla, so you should just un-qualify this

Oh, there's a bunch more `mozilla::` qualifications that I can remove now.

Comment 36

[Jeff Walden [:Waldo]]

Comment on attachment 8995062 [details]
Bug 1477626 - Move js::Hash{Set,Map} into MFBT.

https://reviewboard.mozilla.org/r/259554/#review267472

Mm, so I guess the JS_DEBUG thing already is sort of inconsistently applied with respect to JS::Vector at least, so I guess this is good enough.  But we should figure out a followup that addresses this for all mfbt.  I guess we've just gotten lucky so far, or something.

Comment 37

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/6ef5c1f956f9
Replace some bespoke code with a call to CeilingLog2(). r=Waldo
https://hg.mozilla.org/integration/mozilla-inbound/rev/cff709da0b23
Use `uint32_t` instead of `unsigned` in HashTable.h. r=Waldo
https://hg.mozilla.org/integration/mozilla-inbound/rev/9cf98793e243
Introduce mozilla::HashNumber and use it in various places. r=Waldo
https://hg.mozilla.org/integration/mozilla-inbound/rev/2ce09953e25b
Move ScrambleHashCode() from js/src/Utility.h to mfbt/HashFunctions.h. r=Waldo
https://hg.mozilla.org/integration/mozilla-inbound/rev/f953e6b321c5
Remove use of JS_BIT in js/src/HashTable.h. r=Waldo

Comment 38

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/e3a286413269
Move js::Hash{Set,Map} into MFBT. r=Waldo

Comment 39

[Stefan Hindli [:stefan_hindli]]

https://hg.mozilla.org/mozilla-central/rev/6ef5c1f956f9
https://hg.mozilla.org/mozilla-central/rev/cff709da0b23
https://hg.mozilla.org/mozilla-central/rev/9cf98793e243
https://hg.mozilla.org/mozilla-central/rev/2ce09953e25b
https://hg.mozilla.org/mozilla-central/rev/f953e6b321c5
https://hg.mozilla.org/mozilla-central/rev/e3a286413269

Comment 40

[Nicholas Nethercote [inactive]]

Reopening; there are three more patches still to land.

Comment 41

[Chris Peterson [:cpeterson]]

Should new code prefer MFBT's HashMap/HashSet over PLDHashTable (or QMEHashTable, bug 1402910)?

The new comments at the top of mfbt/HashTable.h (https://reviewboard.mozilla.org/r/259556/diff/2#index_header) describe the differences between (detail class) HashTable and PLDHashTable, but don't mention HashMap or explicitly recommend when to use which class.

Comment 42

[Nicholas Nethercote [inactive]]

cpeterson: I have some more work to do to improve mozilla::HashTable's API (see the dependent bugs). I also want to see if I can reduce the code size a bit, e.g. by un-inlining some of the colder functions.

Once that is done, we may be in a position to clearly prefer mozilla::HashTable, and then I will make an announcement on dev-platform, and we can discuss whether an official recommendation is appropriate.

Comment 43

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/a75c5a2a6bea
Document some differences between mozilla::HashTable and PLDHashTable. r=Waldo
https://hg.mozilla.org/integration/mozilla-inbound/rev/8d22622b5264
Use mozilla::HashTable instead of JS::HashTable in DMD. r=erahm
https://hg.mozilla.org/integration/mozilla-inbound/rev/e33429d58f23
Use mozilla::HashTable instead of js::HashTable in Bench.cpp. r=froydnj

Comment 44

[Dorel Luca [:dluca]]

https://hg.mozilla.org/mozilla-central/rev/a75c5a2a6bea
https://hg.mozilla.org/mozilla-central/rev/8d22622b5264
https://hg.mozilla.org/mozilla-central/rev/e33429d58f23