Closed Bug 1477626 Opened 3 years ago Closed 3 years ago

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

Categories

(Core :: MFBT, enhancement)

enhancement
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla63
Tracking Status
firefox63 --- fixed

People

(Reporter: n.nethercote, Assigned: n.nethercote)

References

Details

Attachments

(9 files)

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
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.
Blocks: 1477627
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.
Also, nsTHashTable's API is very different to js::Hash{Set,Map}. It would be a challenge to get them to play nicely together.
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 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 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+
Blocks: 1478879
Blocks: 1478885
Blocks: 1478896
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 on attachment 8995058 [details]
Bug 1477626 - Use `uint32_t` instead of `unsigned` in HashTable.h.

https://reviewboard.mozilla.org/r/259546/#review267426
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 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 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 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 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 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+
> Just changing to DEBUG is going to bring back that problem in force for this.  :-\

mfbt/Vector.h has similar DEBUG-only fields.
> 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 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+
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
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.
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.
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
Blocks: 1479954
You need to log in before you can comment on or make changes to this bug.