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

[Eelis]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: shuffle_faster.patch
Type: text/x-patch
Size: 1769 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20160430/5a4a73c1/attachment.bin>