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

[Eelis <eelis at eelis dot net>]

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