826951 - JS::HashTable does not compact enough if most of its elements are removed by an Enum

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Justin Lebar (not reading bugmail)]

In ~Enum(), we call checkUnderloaded().  As I understand it, this compacts the table by half if it's underloaded.

But what if we removed more than half of the table's elements during the Enum()?  Shouldn't we compact more, in this case?

I ran into this in bug 826515; there, we may well delete a large portion of a large (tens of mb) hashtable in one go.

Comment 1

[Justin Lebar (not reading bugmail)]

https://tbpl.mozilla.org/?tree=Try&rev=d70f27a5f320

Comment 2

[Justin Lebar (not reading bugmail)]

I picked a bad base rev for that last push, but I think it was basically fine aside from the known failures.  I pushed again to be sure.  https://tbpl.mozilla.org/?tree=Try&rev=38fadb1f935c

Comment 3

[Justin Lebar (not reading bugmail)]

Attachment: Patch, v1

I think we could be more efficient with how we calculate the new size, but it's not simple, and I'm not sure it's worth worrying about.  What do you think?

Comment 4

[Luke Wagner [:luke]]

Great find!

Could you factor out the underloaded computation (capacity > sMinSize && entryCount < ((sMinAlphaFrac * capacity) >> 8)) between underloaded() and compactIfUnderloaded() into a static function?

Comment 5

[Justin Lebar (not reading bugmail)]

Attachment: Patch, v2

Comment 6

[Luke Wagner [:luke]]

Comment on attachment 698940 [details] [diff] [review]
Patch, v2

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

Very nice

::: js/public/HashTable.h
@@ +956,5 @@
> +    // Would the table be underloaded if it had the given capacity and entryCount?
> +    static bool wouldBeUnderloaded(uint32_t capacity, uint32_t entryCount)
> +    {
> +        return capacity > sMinSize &&
> +               entryCount <= ((sMinAlphaFrac * capacity) >> 8);

We've extended the column limit to 99, so this can all be on one line.

Comment 7

[Justin Lebar (not reading bugmail)]

I noticed that the comment on compactIfUnderloaded was out of date.  I changed it to:

    // Resize the table down to the largest capacity which doesn't underload the
    // table.

Comment 8

[Justin Lebar (not reading bugmail)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/013c0badc42c

Comment 9

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/013c0badc42c