diff mbox

libstdc++: Make std::shuffle faster by avoiding std::uniform_int_distribution

Message ID ng308p$gv4$1@ger.gmane.org
State New
Headers show

Commit Message

Eelis April 30, 2016, 7:15 p.m. UTC 
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

Comments

Eelis April 30, 2016, 7:50 p.m. UTC | #1 
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
diff mbox

Patch

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