Make mozilla::Hash{Map,Set}'s entry storage allocation lazy

RESOLVED FIXED in Firefox 63

Status

()

enhancement
RESOLVED FIXED
11 months ago
4 months ago

People

(Reporter: njn, Assigned: njn)

Tracking

(Blocks 1 bug)

unspecified
mozilla63
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox63 fixed)

Details

(Whiteboard: [overhead:45k])

Attachments

(3 attachments, 2 obsolete attachments)

Assignee

Description

11 months ago
Bug 1050035 did likewise for PLDHashTable/nsTHashtable.

The main motivation is to make the API nicer, by avoiding the need for init() calls. It also can save memory because some tables never are inserted into.
Assignee

Comment 1

11 months ago
GCHashMap will shortly lose its initialized() function, so we need another way
to indicate whether this table has been created. This patch changes it to use a
pointer instead.
Attachment #8998709 - Flags: review?(luke)
Assignee

Comment 2

11 months ago
Posted patch Remove putNewInfallible() (obsolete) — Splinter Review
It's not compatible with lazy entry storage, because lazy entry storage
prevents us from definitely allocating a known number of entries ahead of time.

Fortunately it's only used in a small number of places.
Attachment #8998710 - Flags: review?(luke)
Assignee

Comment 3

11 months ago
The two functions are almost identical. This change minimizes duplication.
Attachment #8998711 - Flags: review?(luke)
Assignee

Comment 4

11 months ago
luke: please review the changes to mfbt/HashTable.h and
js/src/jsapi-tests/testHashTable.cpp.

sfink: please review the rest. Apologies for the tedium.
Attachment #8998712 - Flags: review?(sphink)
Attachment #8998712 - Flags: review?(luke)

Updated

11 months ago
Attachment #8998709 - Flags: review?(luke) → review+

Comment 6

11 months ago
Comment on attachment 8998710 [details] [diff] [review]
Remove putNewInfallible()

Review of attachment 8998710 [details] [diff] [review]:
-----------------------------------------------------------------

I guess in theory a reserve() could be added (such that puts could be infallible, but given the low usage, that doesn't seem worth it).

::: js/public/UbiNodeDominatorTree.h
@@ +365,5 @@
>              return false;
> +        for (uint32_t i = 0; i < length; i++) {
> +            if (!map.putNew(postOrder[i], i)) {
> +                return false;
> +            }

nit: no {} around single-line then branch
Attachment #8998710 - Flags: review?(luke) → review+

Updated

11 months ago
Attachment #8998711 - Flags: review?(luke) → review+

Comment 7

11 months ago
I'd like some help understanding why the design of clear()/clearAndPrepareForLength() is the right one.  My concern is that clear() does not free memory, both in the C++ standard library, and traditionally for Hash{Map,Set}; it just calls destructors and changes the count() but leaves the memory allocation unchanged.

The methods I would've intuitively expected are:
 clear(): calls destructors
 compact(): reallocs (if non-empty and underloaded) or frees (if empty) the table
and then one of:
 reserve(len): eagerly allocates enough memory for len
 prepareForLength(len): request the next allocation prepare for len

The equivalent of clearAndPrepareForLength(len) could then be achieved by: clear();compact();prepareForLength(len).

That leaves the question of whether reserve() or prepareForLength() are better.  The former could justify keeping putNewInfallible() which *in theory* could be a valuable perf win, although it looks like in practice not.  Is the benefit of the latter that it might avoid allocation altogether if the add() never ended up happening?  Personally, I find the meaning of the former simpler and more consistent with other containers.

Comment 8

11 months ago
(ni so I can get a ping when you answer)
Flags: needinfo?(n.nethercote)
Comment on attachment 8998712 [details] [diff] [review]
Make mozilla::Hash{Map,Set}'s entry storage allocation lazy

Review of attachment 8998712 [details] [diff] [review]:
-----------------------------------------------------------------

Whee, that was fun. But it's an impressive amount of code removal. I like it.

And in another bug I was thinking of asking you if you could arrange for init() to be removed if you use InfallibleAllocPolicy. This is much better!

::: js/src/gc/WeakMap.h
@@ +176,5 @@
>  
>      void sweep() override;
>  
> +    void clearOut() override {
> +        Base::clear();

Why the clearOut() name? Could this just be `using Base::clear;` (There's a `using Base::remove` in this class already.)

::: js/src/vm/ObjectGroup.cpp
@@ +1745,2 @@
>          arrayObjectTable->clear();
> +    if (plainObjectTable) {

I sort of wonder whether it's necessary to make all these table pointers be lazy now that the tables themselves are lazy, but I guess that'd be a separate change if it's even a good idea.

::: mfbt/HashTable.h
@@ +406,5 @@
>  
>    // -- Clearing -------------------------------------------------------------
>  
> +  // Remove all elements and free the entry storage, leaving it in an empty
> +  // state read to be used again. Afterwards, when the first element is added

*ready

@@ +706,5 @@
>  
>    // -- Clearing -------------------------------------------------------------
>  
> +  // Remove all elements and free the entry storage, leaving it in an empty
> +  // state read to be used again. Afterwards, when the first element is added

*ready

@@ +1538,5 @@
> +                    sMaxInit,
> +                  "multiplication in numerator below could overflow");
> +    static_assert(sMaxInit * sAlphaDenominator <=
> +                    UINT32_MAX - sMaxAlphaNumerator,
> +                  "numerator calculation below could potentially overflow");

I think this could be loosened a little bit if you used newCapacity = 1 + ((aLen - 1) * sAlphaDenominator) / sMaxAlphaNumerator. But... why bother?

Oh. I just noticed this is just code motion. Yeah, don't change anything.

@@ +1849,5 @@
> +    // Compress if a quarter or more of all entries are removed. Note that this
> +    // always succeeds if capacity() == 0 (i.e. entry storage has not been
> +    // allocated), which is what we want, because it means changeTableSize will
> +    // allocate the requested capacity rather than doubling it.
> +    bool shouldCompressTable = mRemovedCount >= (capacity() >> 2);

Huh. It seems like this should be using the min-alpha stuff above (in some constexpr way that doesn't introduce any multiplications or divisions.) Or at least, I *thought* that was what min-alpha was meant to represent. static_assert(sMinAlphaNumerator == 1 && sAlphaDenominator == 1 << 2) or something? (Or file a followup if you don't think it belongs here.)
Attachment #8998712 - Flags: review?(sphink) → review+
Assignee

Comment 10

11 months ago
Comment on attachment 8998710 [details] [diff] [review]
Remove putNewInfallible()

The putNewInfallible() removal won't be necessary once the other changes are done.
Attachment #8998710 - Attachment is obsolete: true
Flags: needinfo?(n.nethercote)
Assignee

Comment 11

11 months ago
> It seems like this should be using the min-alpha stuff above

The "underloaded" check and the "rehash due to many removed entries" check both use 25% as their threshold, but there is no fundamental reason for that, which is why they don't share code. That could be clarified, but yes it would be better as a follow-up.
Assignee

Comment 12

11 months ago
Luke, I changed clear() et al as per our discussion this morning. It required
some slightly more extensive changes within HashTable.h. I also added
clearAndCompact(), which is more or less equivalent to the old finish() method,
because it's needed in quite a few places.
Attachment #8999103 - Flags: review?(luke)
Assignee

Updated

11 months ago
Attachment #8998712 - Attachment is obsolete: true
Attachment #8998712 - Flags: review?(luke)

Comment 13

11 months ago
Comment on attachment 8999103 [details] [diff] [review]
Make mozilla::Hash{Map,Set}'s entry storage allocation lazy

Review of attachment 8999103 [details] [diff] [review]:
-----------------------------------------------------------------

Great work, this simplifies a lot of code.

::: mfbt/HashTable.h
@@ +1595,5 @@
> +    // Reject all lengths whose initial computed capacity would exceed
> +    // sMaxCapacity. Round that maximum aLen down to the nearest power of two
> +    // for speedier code.
> +    if (MOZ_UNLIKELY(aLen > sMaxInit)) {
> +      MOZ_CRASH("initial length is too large");

Thinking about code bloat for something inlined in a bajillion places, I wonder if there would be non-negligible size impact for each MOZ_CRASH().

@@ +2049,5 @@
> +
> +  MOZ_MUST_USE bool reserve(uint32_t aLen)
> +  {
> +    if (aLen == 0) {
> +        return true;

nit: indent
Attachment #8999103 - Flags: review?(luke) → review+

Comment 14

11 months ago
Pushed by nnethercote@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/6bb61989d9ae
Change sJSObjWrappers initialization. r=luke
https://hg.mozilla.org/integration/mozilla-inbound/rev/223884f0ad76
Define lookup() in terms of readonlyThreadsafeLookup(). r=luke

Comment 15

11 months ago
Pushed by nnethercote@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/ad30dc53e38e
Make mozilla::Hash{Map,Set}'s entry storage allocation lazy. r=luke,sfink
Assignee

Comment 16

11 months ago
> > +    if (MOZ_UNLIKELY(aLen > sMaxInit)) {
> > +      MOZ_CRASH("initial length is too large");
> 
> Thinking about code bloat for something inlined in a bajillion places, I
> wonder if there would be non-negligible size impact for each MOZ_CRASH().

I tried replacing it with a (debug-only) assertion, but it only reduced the size of libxul by 800 bytes on Linux64 so I kept the MOZ_CRASH.

Comment 17

11 months ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/6bb61989d9ae
https://hg.mozilla.org/mozilla-central/rev/223884f0ad76
https://hg.mozilla.org/mozilla-central/rev/ad30dc53e38e
Status: ASSIGNED → RESOLVED
Closed: 11 months ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla63
This improved our base content JS numbers by 45K \o/
Whiteboard: [overhead:45k]
Assignee

Comment 19

11 months ago
Yay! I was doing this mostly for the API improvement, but the memory reduction is great news.
Assignee

Updated

10 months ago
Depends on: 1482881
Assignee

Updated

10 months ago
Depends on: 1483182
Depends on: 1530311
You need to log in before you can comment on or make changes to this bug.