Closed Bug 1483062 Opened Last year Closed Last year

A couple more mozilla::HashTable tweaks

Categories

(Core :: MFBT, enhancement)

enhancement
Not set

Tracking

()

RESOLVED FIXED
mozilla63
Tracking Status
firefox63 --- fixed

People

(Reporter: njn, Assigned: njn)

Details

Attachments

(7 files, 1 obsolete file)

No description provided.
It's dead.
Attachment #8999825 - Flags: review?(luke)
Assignee: nobody → n.nethercote
Status: NEW → ASSIGNED
Because that's a more accurate description of what it does -- it finds free
*and* removed entries.
Attachment #8999826 - Flags: review?(luke)
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`.
Attachment #8999827 - Flags: review?(luke)
I'm not sure about this one. This function is only called after rekeying.
Attachment #8999828 - Flags: review?(luke)
Attachment #8999825 - Flags: review?(luke) → review+
Comment on attachment 8999826 [details] [diff] [review]
Rename HashTable::findFreeEntry() as findNonLiveEntry()

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

Agreed, much better name.
Attachment #8999826 - Flags: review?(luke) → review+
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.
Attachment #8999827 - Flags: review?(luke) → review+
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 on attachment 8999828 [details] [diff] [review]
Rework HashTable::rehashIfOverRemoved()

(Clearing; feel free to re-request if I misunderstood.)
Attachment #8999828 - Flags: review?(luke)
New version!
Attachment #9000134 - Flags: review?(luke)
Attachment #8999828 - Attachment is obsolete: true
Attachment #9000134 - Flags: review?(luke) → review+
Attachment #9000135 - Flags: review?(luke) → review+
Attachment #9000136 - Flags: review?(luke) → review+
Luke, what do you think about this?
Attachment #9001431 - Flags: review?(luke)
Attachment #9001431 - Flags: review?(luke) → review+
Pushed by nnethercote@mozilla.com:
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
You need to log in before you can comment on or make changes to this bug.