Hello Dean,
> Whilst it has been interesting learning and discussing all these
> different techniques, I think it's probably best to stick with the
> bitmask method, rather than making the code too complex and difficult
> to follow.
Yes.
> The bitmask method has the advantage of being very simple, easy to
> understand and fast (fastest in many of the benchmarks, and close enough
> in others to make me think that the difference won't matter for our
> purposes).
>
> To test the current patch, I hacked up a simple SQL-callable server
> function: random(bigint, bigint) returns bigint, similar to the one in
> pgbench. After doing so, I couldn't help thinking that it would be
> useful to have such a function in core, so maybe that could be a
> follow-on patch.
Yep.
> Anyway, that led to the following observations:
>
> Firstly, there's a bug in the existing mask_u64() code -- if
> pg_leftmost_one_pos64(u) returns 63, you end up with a mask equal to
> 0, and it breaks down.
Oops:-(
> Secondly, I think it would be simpler to implement this as a bitshift,
> rather than a bitmask, using the high bits from the random number. That
> might not make much difference for xoroshiro**, but in general, PRNGs
> tend to be weaker in the lower bits, so it seems preferable on that
> basis. But also, it makes the code simpler and less error-prone.
Indeed, that looks like a good option.
> Finally, I think it would be better to treat the upper bound of the
> range as inclusive.
This bothered me as well, but the usual approach seems to use range as the
number of values, so I was hesitant to depart from that. I'm still
hesitant to go that way.
> Doing so makes the function able to cover all
> possible 64-bit ranges. It would then be easy (perhaps in another
> follow-on patch) to make the pgbench random() function work for all
> 64-bit bounds (as long as max >= min), without the weird overflow
> checking it currently has.
>
> Putting those 3 things together, the code (minus comments) becomes:
>
> if (range > 0)
> {
> int rshift = 63 - pg_leftmost_one_pos64(range);
>
> do
> {
> val = xoroshiro128ss(state) >> rshift;
> }
> while (val > range);
> }
> else
> val = 0;
>
> which reduces the complexity a bit.
Indeed.
Attached v9 follows this approach but for the range being inclusive, as
most sources I found understand the range as the number of values.
--
Fabien.
