Closed Bug 1352889 Opened 3 years ago Closed 2 years ago

Ensure that PLDHashTable's second hash doesn't have padding with 0 bits for tables with capacity larger than 2^16

Categories

(Core :: XPCOM, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla55
Tracking Status
firefox55 --- fixed

People

(Reporter: dbaron, Assigned: dbaron)

References

(Blocks 1 open bug)

Details

(Whiteboard: [qf:p1])

Attachments

(1 file)

PLDHashTable takes the result of the hash function and multiplies it by
kGoldenRatio to ensure that it has a good distribution of bits across
the 32-bit hash value, and then zeroes out the low bit so that it can be
used for the collision flag.  This result is called hash0.  From hash0
it computes two different numbers used to find entries in the table
storage:  hash1 is used to find an initial position in the table to
begin searching for an entry; hash2 is then used to repeatedly offset
that position (mod the size of the table) to build a chain of positions
to search.

In a table with capacity 2^c entries, hash1 is simply the upper c bits
of hash0.  This patch does not change this.

Prior to this patch, hash2 was the c bits below hash1, padded at the low
end with zeroes when c > 16.  (Note that bug 927705, changeset
1a02bec165e16f370cace3da21bb2b377a0a7242, increased the maximum capacity
from 2^23 to 2^26 since 2^23 was sometimes insufficient!)  This manner
of computing hash2 is problematic because it increases the risk of long
chains for very large tables, since there is less variation in the hash2
result due to the zero padding.

So this patch changes the hash2 computation by using the low bits of
hash0 instead of shifting it around, thus avoiding 0 bits in parts of
the hash2 value that are significant.

Note that this changes what hash2 is in all cases except when the table
capacity is exactly 2^16, so it does change our hashing characteristics.
For tables with capacity less than 2^16, it should be using a different
second hash, but with the same amount of random-ish data.  For tables
with capacity greater than 2^16, it should be using more random-ish
data.

MozReview-Commit-ID: JvnxAMBY711
Comment on attachment 8853817 [details] [diff] [review]
Ensure that PLDHashTable's second hash doesn't have padding with 0 bits for tables with capacity larger than 2^16

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

Seems reasonable, though I have a couple of question.

- How did you discover this? Code inspection? Something else?

- Have you done any evaluation to see if it reduces the number of probes needed in large tables? (Or that it doesn't make any significant difference to small tables?)
Attachment #8853817 - Flags: review?(n.nethercote) → review+
(In reply to Nicholas Nethercote [:njn] from comment #2)
> - How did you discover this? Code inspection? Something else?

Code inspection while working on bug 1352890, which was an idea I had while talking to dmajor and jet about hashtable performance, which Ehsan had raised as a concern.  (I also noticed bug 1352888 by code inspection while looking into it, but it's less related.)

> - Have you done any evaluation to see if it reduces the number of probes
> needed in large tables? (Or that it doesn't make any significant difference
> to small tables?)

No.  I might try to look into a little further investigation next week, though.
https://hg.mozilla.org/integration/mozilla-inbound/rev/dfdb5742823ae4ad1c54aa4aa293347336ed6c7f
Bug 1352889 - Ensure that PLDHashTable's second hash doesn't have padding with 0 bits for tables with capacity larger than 2^16.  r=njn
Depends on: 1353458
Thanks for backing that out.

Relanding needs a resolution to bug 1353458.
Flags: needinfo?(dbaron)
Whiteboard: [qf]
Whiteboard: [qf] → [qf:p1]
https://hg.mozilla.org/integration/mozilla-inbound/rev/52fff3b1e209f29f139295a65f4ed40458ff1954
Bug 1352889 - Ensure that PLDHashTable's second hash doesn't have padding with 0 bits for tables with capacity larger than 2^16.  r=njn
https://hg.mozilla.org/mozilla-central/rev/52fff3b1e209
Status: ASSIGNED → RESOLVED
Closed: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
https://hg.mozilla.org/integration/mozilla-inbound/rev/eab2a4a241a6ba6c1a578e93d9bd5186d372dfa8
Backed out changeset 52fff3b1e209 (bug 1352889) to see if it is responsible for input latency regressions in bug 1365334 or bug 1366156.
Status: RESOLVED → REOPENED
Flags: needinfo?(dbaron)
Resolution: FIXED → ---
Merge of backout:
https://hg.mozilla.org/mozilla-central/rev/eab2a4a241a6
Target Milestone: mozilla55 → ---
https://hg.mozilla.org/integration/mozilla-inbound/rev/65251b0ed973675e2d490458fedfc5cb75753abb
Bug 1352889 - Ensure that PLDHashTable's second hash doesn't have padding with 0 bits for tables with capacity larger than 2^16.  r=njn
https://hg.mozilla.org/mozilla-central/rev/65251b0ed973
Status: REOPENED → RESOLVED
Closed: 3 years ago2 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
Flags: needinfo?(dbaron)
You need to log in before you can comment on or make changes to this bug.