1483062 - A couple more mozilla::HashTable tweaks

Status: RESOLVED FIXED

(Core :: MFBT, enhancement)

Comment 1

[Nicholas Nethercote [inactive]]

Attachment: Remove HashTable::maybeCreateTable

It's dead.

Comment 2

[Nicholas Nethercote [inactive]]

Attachment: Rename HashTable::findFreeEntry() as findNonLiveEntry()

Because that's a more accurate description of what it does -- it finds free
*and* removed entries.

Comment 3

[Nicholas Nethercote [inactive]]

Attachment: Rename some HashTable methods

Specifically:
- checkOverloaded  -> rehashIfOverloaded
- checkUnderloaded -> shrinkIfUnderloaded
- checkOverRemoved -> rehashIfOverRemoved

Because I've always found that the `check` prefix doesn't clearly explain that
the table might be changed,

And:
- shouldCompressTable -> overRemoved

Because that matches `overloaded` and `underloaded`.

Comment 4

[Nicholas Nethercote [inactive]]

Attachment: Rework HashTable::rehashIfOverRemoved()

I'm not sure about this one. This function is only called after rekeying.

Comment 5

[Luke Wagner [:luke]]

Comment on attachment 8999826 [details] [diff] [review]
Rename HashTable::findFreeEntry() as findNonLiveEntry()

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

Agreed, much better name.

Comment 6

[Luke Wagner [:luke]]

Comment on attachment 8999827 [details] [diff] [review]
Rename some HashTable methods

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

Good point!  I have also found "check" to be a tempting verb to reach for initially, but ultimately ambiguous to everyone thereafter.

Comment 7

[Luke Wagner [:luke]]

Comment on attachment 8999828 [details] [diff] [review]
Rework HashTable::rehashIfOverRemoved()

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

::: mfbt/HashTable.h
@@ +1894,5 @@
>  
>    // Infallibly rehash the table if we are overloaded with removals.
>    void rehashIfOverRemoved()
>    {
> +    if (overRemoved()) {

Good question, this obviously looks "wrong" given your renamings.

So the question is how overloaded() compares to overRemoved().  The big difference is that overloaded() takes into account (mEntryCount+mRemovedCount) whereas overRemoved() only takes into account mRemovedCount.

For the current (before this patch) only use case of overRemoved()/shouldCompressTable() in rehashIfOverloaded()/checkOverloaded(), the question is: if I'm going to rehash *anyway* (b/c overloaded()==true), should I grow or not.  Rehashing sets mRemovedCount back to 0, so it makes sense that if a sufficient % of the table is removed, there's no need to grow given that overloaded().  IIUC, with shouldCompressTable() = 1/4 of table is removed, and overloaded() = 3/4 of table is (removed+live), this is perfect: when we rehash it will leave us at 1/2 utilized.

But getting back to this method the question is: should we only rehash based on mRemovedCount or also mEntryCount?  My feeling is we need to take into account mEntryCount: otherwise we could have a table that is 3/4 full of live stuff, then we rekey a bunch leaving almost-but-not-quite 1/4 removed, and now we're near 100% full!  So maybe this method should be killed and rehashIfOverloaded() used instead.

(Also maybe overRemoved() should be removed and inlined into its one caller.)

Comment 8

[Luke Wagner [:luke]]

Comment on attachment 8999828 [details] [diff] [review]
Rework HashTable::rehashIfOverRemoved()

(Clearing; feel free to re-request if I misunderstood.)

Comment 9

[Nicholas Nethercote [inactive]]

Attachment: Rename HashTable::rehashIfOverRemoved()

New version!

Comment 10

[Nicholas Nethercote [inactive]]

Attachment: Inline and remove HashTable::overRemoved()

Comment 11

[Nicholas Nethercote [inactive]]

Attachment: Merge HashTable::wouldBeUnderloaded() into underloaded()

Comment 12

[Nicholas Nethercote [inactive]]

Attachment: Inline and remove HashTable::{over,under}loaded()

Luke, what do you think about this?

Comment 13

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/e483b91eafbc
Remove HashTable::maybeCreateTable. r=luke
https://hg.mozilla.org/integration/mozilla-inbound/rev/f1e1cf1d42ec
Rename HashTable::findFreeEntry() as findNonLiveEntry(). r=luke
https://hg.mozilla.org/integration/mozilla-inbound/rev/43e351bda401
Rename some HashTable methods. r=luke
https://hg.mozilla.org/integration/mozilla-inbound/rev/2d9e3360e858
Rename HashTable::rehashIfOverRemoved(). r=luke
https://hg.mozilla.org/integration/mozilla-inbound/rev/a3bf3a494b0b
Inline and remove HashTable::overRemoved(). r=luke
https://hg.mozilla.org/integration/mozilla-inbound/rev/ca2edc3b4c1a
Merge HashTable::wouldBeUnderloaded() into underloaded(). r=luke
https://hg.mozilla.org/integration/mozilla-inbound/rev/da46bfc2c089
Inline and remove HashTable::{over,under}loaded(). r=luke
https://hg.mozilla.org/integration/mozilla-inbound/rev/17896e16e10b
Trivial comment fixes. r=me

Comment 14

[Tiberius Oros[:tiberius_oros]]

https://hg.mozilla.org/mozilla-central/rev/e483b91eafbc
https://hg.mozilla.org/mozilla-central/rev/f1e1cf1d42ec
https://hg.mozilla.org/mozilla-central/rev/43e351bda401
https://hg.mozilla.org/mozilla-central/rev/2d9e3360e858
https://hg.mozilla.org/mozilla-central/rev/a3bf3a494b0b
https://hg.mozilla.org/mozilla-central/rev/ca2edc3b4c1a
https://hg.mozilla.org/mozilla-central/rev/da46bfc2c089
https://hg.mozilla.org/mozilla-central/rev/17896e16e10b