[patch, libstdc++] std::shuffle: Generate two swap positions at a time if possible

[Eelis]

On 2016-09-02 20:20, Eelis van der Weegen wrote:
> On 2016-08-31 14:45, Jonathan Wakely wrote:
>> Is this significantly faster than just using
>> uniform_int_distribution<_IntType>{0, __bound - 1}(__g) so we don't
>> need to duplicate the logic? (And people maintaining the code won't
>> reconvince themselves it's correct every time they look at it :-)
>>
>> [..]
>>
>> Could we hoist this test out of the loop somehow?
>>
>> If we change the loop condition to be __i+1 < __last we don't need to
>> test it on every iteration, and then after the loop we can just do
>> the final swap if (__urange % 2).
>
> Reusing std::uniform_int_distribution seems just as fast, so I've removed __generate_random_index_below.
>
> I've hoisted the (__i + 1 == __last) check out of the loop (in a slightly different way), and it seems to shave off a couple more cycles, yay!
>
> Updated patch attached.
>

Please ignore that patch, I used __g()&1 but that's invalid (the new "UniformRandomBitGenerator" name is misleading).

Updated patch (which uses a proper distribution even for the [0,1] case) attached.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: newer-double-step-shuffle.patch
Type: text/x-patch
Size: 1965 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20160902/21817448/attachment.bin>