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

[Eelis <eelis at eelis dot net>]

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

Index: libstdc++-v3/include/bits/stl_algo.h
===================================================================
--- libstdc++-v3/include/bits/stl_algo.h	(revision 235680)
+++ libstdc++-v3/include/bits/stl_algo.h	(working copy)
@@ -3738,12 +3738,40 @@
 	_DistanceType;
 
       typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
-      typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
-      typedef typename __distr_type::param_type __p_type;
-      __distr_type __d;
+      typedef typename std::remove_reference<_UniformRandomNumberGenerator>::type _Gen;
+      typedef typename std::common_type<typename _Gen::result_type, __ud_type>::type __uc_type;
 
-      for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
-	std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
+      const __uc_type __urngrange =
+	_Gen::max() - _Gen::min() + 1; // +1 because the generator range is inclusive
+
+      const __uc_type __urange = __uc_type(__last - __first);
+
+      if (__urngrange >= __urange)
+      {
+	const __uc_type __scaling = __urngrange / __urange;
+	const __uc_type __past = __urange * __scaling;
+
+	for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
+	{
+	  __uc_type __j;
+	  do
+	  {
+	    __j = __uc_type(__g()) - _Gen::min();
+	  }
+	  while (__j >= __past);
+
+	  std::iter_swap(__i, __first + __j / __scaling);
+	}
+      }
+      else
+      {
+	typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
+	typedef typename __distr_type::param_type __p_type;
+	__distr_type __d;
+
+        for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
+	  std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
+      }
     }
 #endif