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

RESOLVED FIXED in Firefox 63

Status

()

enhancement
RESOLVED FIXED
10 months ago
10 months ago

People

(Reporter: njn, Assigned: njn)

Tracking

unspecified
mozilla63
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox63 fixed)

Details

Attachments

(9 attachments)

59 bytes, text/x-review-board-request
Waldo
: review+
Details
59 bytes, text/x-review-board-request
Waldo
: review+
Details
59 bytes, text/x-review-board-request
Waldo
: review+
Details
59 bytes, text/x-review-board-request
Waldo
: review+
Details
59 bytes, text/x-review-board-request
Waldo
: review+
Details
59 bytes, text/x-review-board-request
Waldo
: review+
Details
59 bytes, text/x-review-board-request
Waldo
: review+
Details
59 bytes, text/x-review-board-request
erahm
: review+
Details
59 bytes, text/x-review-board-request
froydnj
: review+
Details
Assignee

Description

10 months ago
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.
Assignee

Updated

10 months ago
Blocks: 1477627

Comment 1

10 months ago
Is there any reason to not make nsTHashtable to use HashMap?
(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.
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.
Assignee

Comment 4

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

Comment 5

10 months ago
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 hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)

Comment 24

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

https://reviewboard.mozilla.org/r/259560/#review266704
Attachment #8995065 - Flags: review?(nfroyd) → review+

Comment 25

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

https://reviewboard.mozilla.org/r/259558/#review266712
Attachment #8995064 - Flags: review?(erahm) → review+
Assignee

Updated

10 months ago
Blocks: 1478879
Assignee

Updated

10 months ago
Blocks: 1478885
Assignee

Updated

10 months ago
Blocks: 1478896

Comment 26

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

https://reviewboard.mozilla.org/r/259544/#review267424
Attachment #8995057 - Flags: review?(jwalden+bmo) → review+

Comment 27

10 months ago
mozreview-review
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

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

https://reviewboard.mozilla.org/r/259546/#review267428
Attachment #8995058 - Flags: review?(jwalden+bmo) → review+

Comment 29

10 months ago
mozreview-review
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)
Attachment #8995059 - Flags: review?(jwalden+bmo) → review+

Comment 30

10 months ago
mozreview-review
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.
Attachment #8995060 - Flags: review?(jwalden+bmo) → review+

Comment 31

10 months ago
mozreview-review
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.
Attachment #8995061 - Flags: review?(jwalden+bmo) → review+

Comment 32

10 months ago
mozreview-review
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.
Attachment #8995062 - Flags: review?(jwalden+bmo) → review-

Comment 33

10 months ago
mozreview-review
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.
Attachment #8995063 - Flags: review?(jwalden+bmo) → review+
Assignee

Comment 34

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

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

Comment 35

10 months ago
> 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

10 months ago
mozreview-review
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.
Attachment #8995062 - Flags: review- → review+

Comment 37

10 months ago
Pushed by nnethercote@mozilla.com:
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

10 months ago
Pushed by nnethercote@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/e3a286413269
Move js::Hash{Set,Map} into MFBT. r=Waldo
Assignee

Comment 40

10 months ago
Reopening; there are three more patches still to land.
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
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.
Assignee

Comment 42

10 months ago
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

10 months ago
Pushed by nnethercote@mozilla.com:
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
Assignee

Updated

10 months ago
Blocks: 1479954

Comment 44

10 months ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/a75c5a2a6bea
https://hg.mozilla.org/mozilla-central/rev/8d22622b5264
https://hg.mozilla.org/mozilla-central/rev/e33429d58f23
Status: REOPENED → RESOLVED
Last Resolved: 10 months ago10 months ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.