Closed Bug 1351947 Opened 3 years ago Closed 3 years ago

Skiplist tower height probability distribution is skewed


(Core :: JavaScript Engine, enhancement)

Not set



Tracking Status
firefox55 --- fixed


(Reporter: sfink, Assigned: sfink)




(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
Remove bias in skiplist tower height, r=shu
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.