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

[Jonathan Wakely]

On 02/09/16 20:53 +0200, Eelis wrote:
>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.


I've finally got round to committing this patch to trunk.

Thanks for your patience, and sorry for the delay!

-------------- next part --------------
A non-text attachment was scrubbed...
Name: patch.txt
Type: text/x-patch
Size: 2384 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20161014/30e2e800/attachment.bin>