Closed
Bug 1477626
Opened 3 years ago
Closed 3 years ago
Move js::Hash{Set,Map} into MFBT
Categories
(Core :: MFBT, enhancement)
Core
MFBT
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.
Comment 1•3 years ago
|
||
Is there any reason to not make nsTHashtable to use HashMap?
![]() |
||
Comment 2•3 years ago
|
||
(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•3 years ago
|
||
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•3 years 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•3 years 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 hidden (mozreview-request) |
Comment hidden (mozreview-request) |
Comment hidden (mozreview-request) |
![]() |
||
Comment 24•3 years 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•3 years 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+
Comment 26•3 years 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•3 years 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•3 years 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•3 years 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•3 years 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•3 years 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•3 years 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•3 years 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•3 years 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•3 years 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•3 years 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•3 years 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•3 years ago
|
||
Pushed by nnethercote@mozilla.com: https://hg.mozilla.org/integration/mozilla-inbound/rev/e3a286413269 Move js::Hash{Set,Map} into MFBT. r=Waldo
Comment 39•3 years ago
|
||
bugherder |
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
Status: ASSIGNED → RESOLVED
Closed: 3 years ago
status-firefox63:
--- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla63
![]() |
Assignee | |
Comment 40•3 years ago
|
||
Reopening; there are three more patches still to land.
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Comment 41•3 years ago
|
||
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•3 years 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•3 years 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
Comment 44•3 years 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
Closed: 3 years ago → 3 years ago
Resolution: --- → FIXED
You need to log in
before you can comment on or make changes to this bug.
Description
•