Closed Bug 1351947 Opened 3 years ago Closed 3 years ago

Skiplist tower height probability distribution is skewed

Categories

(Core :: JavaScript Engine, enhancement)

enhancement
Not set

Tracking

()

RESOLVED FIXED
mozilla55
Tracking Status
firefox55 --- fixed

People

(Reporter: sfink, Assigned: sfink)

References

Details

Attachments

(1 file)

This was generating a random int, counting number of consecutive low-order bits, and returning max(that, 1), which would result in a 3/4 chance of returning 1, 1/8 of returning 2, 1/16 of returning 3, etc. But we don't want the spike in probably at height 1. So instead, just add one to the number of bits to get a plain ½^i distribution of i=1..MAX_HEIGHT.
Doh! I got clever by putting a unicode character in the commit comment, which broke my own code in bzexport. :-(
Second, I totally thought there was a 1 in 2^MAX_HEIGHT chance of overflowing the tower height and having a buffer overrun, which here is 1 in 4 billion but we roll the dice many, many times. But blame pointed me to bug 1234147, which explained that it was already properly capped due to the for loop bounds. And the original version had exactly this bug in it (heh).

All of which means that using a hardcoded 32 rather than MAX_HEIGHT in the loop bound was... perhaps not the best way to go about it. I also expanded the comment to be extra clear.
Er... that last comment was meant to go with the attachment. This code and everything relating to it is cursed. Or maybe I've just completely forgotten how to manually submit patches without bzexport to hold my hand.
Attachment #8852760 - Flags: review?(shu)
Attachment #8852760 - Flags: review?(shu) → review+
Pushed by sfink@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/b20d152b6a8e
Remove bias in skiplist tower height, r=shu
https://hg.mozilla.org/mozilla-central/rev/b20d152b6a8e
Status: ASSIGNED → RESOLVED
Closed: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
You need to log in before you can comment on or make changes to this bug.