> 1 random generation per element, vs. log(n) or log(u)

The expected height of an element is 2, and the maximum height is 32. So there is at most a constant-factor performance difference, and in practice we should find this constant to be small.

It's not clear whether any small performance gain is worth the loss of clarity in presentation of the algorithm and code.