1351947 - Skiplist tower height probability distribution is skewed

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Steve Fink [:sfink] [:s:]]

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.

Comment 1

[Steve Fink [:sfink] [:s:]]

Doh! I got clever by putting a unicode character in the commit comment, which broke my own code in bzexport. :-(

Comment 2

[Steve Fink [:sfink] [:s:]]

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.

Comment 3

[Steve Fink [:sfink] [:s:]]

Attachment: fix bias in skiplist probability distribution

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.

Comment 4

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/b20d152b6a8e
Remove bias in skiplist tower height, r=shu

Comment 5

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/b20d152b6a8e