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

[Eelis van der Weegen]

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.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: new-double-step-shuffle.patch
Type: text/x-patch
Size: 1940 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20160902/1361ffac/attachment.bin>