Hello Yura,
>> However, I'm not enthousiastic at combining two methods depending on
>> the range, the function looks complex enough without that, so I would
>> suggest not to take this option. Also, the decision process adds to
>> the average cost, which is undesirable.
>
> Given 99.99% cases will be in the likely case, branch predictor should
> eliminate decision cost.
Hmmm. ISTM that a branch predictor should predict that unknown < small
should probably be false, so a hint should be given that it is really
true.
> And as Dean Rasheed correctly mentioned, mask method will have really
> bad pattern for branch predictor if range is not just below or equal to
> power of two.
On average the bitmask is the better unbiased method, if the online
figures are to be trusted. Also, as already said, I do not really want to
add code complexity, especially to get lower average performance, and
especially with code like "threshold = - range % range", where both
variables are unsigned, I have a headache just looking at it:-)
> And __builtin_clzl is not free lunch either, it has latency 3-4 cycles
> on modern processor.
Well, % is not cheap either.
> Well, probably it could run in parallel with some part of xoroshiro, but
> it depends on how compiler will optimize this function.
>
>> I would certainly select the unbias multiply method if we want a u32
>> range variant.
>
> There could be two functions.
Yep, but do we need them? Who is likely to want 32 bits pseudo random
ints in a range? pgbench needs 64 bits.
So I'm still inclined to just keep the faster-on-average bitmask method,
despite that it may be slower for some ranges. The average cost for the
worst case in PRNG calls is, if I'm not mistaken:
1 * 0.5 + 2 * 0.25 + 3 * 0.125 + ... ~ 2
which does not look too bad.
--
Fabien.
