Re: [patch] libstdc++: Make std::shuffle faster by avoiding std::uniform_int_distribution

[Eelis]

Please ignore this, I made the error described here:

  
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Implementation_errors

:)

On 2016-04-30 21:15, Eelis wrote:

Hi,

The attached patch makes std::shuffle about 33% faster for the following 
testcase:

     #include <random>
     #include <iostream>
     #include <algorithm>

     int main()
     {
         std::mt19937 gen;

         std::vector<int> v;
         v.reserve(10000);

         for (int i = 0; i != 10000; ++i)
         {
             v.push_back(i);
             std::shuffle(v.begin(), v.end(), gen);
         }

         std::cout << v.front() << '\n';
     }

It achieves this by avoiding std::uniform_int_distribution when the generator's
range is large enough, which is almost always the case. This helps a lot, 
because
std::uniform_int_distribution::op() recomputes scaling factors every time.

Thoughts?

Thanks,

Eelis