From 38e34671fa2bb8a686cd2e2c770937b8c9be8f1e Mon Sep 17 00:00:00 2001 From: Eelis van der Weegen Date: Fri, 14 Oct 2016 19:40:32 +0000 Subject: [PATCH] Optimize std::shuffle by using generator to get two values at once 2016-10-14 Eelis van der Weegen * include/bits/stl_algo.h (shuffle): Extract two random numbers from each generator invocation when its range is large enough. From-SVN: r241184 --- libstdc++-v3/ChangeLog | 5 +++++ libstdc++-v3/include/bits/stl_algo.h | 41 ++++++++++++++++++++++++++++++++++++ 2 files changed, 46 insertions(+) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 497744e..1537793 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,8 @@ +2016-10-14 Eelis van der Weegen + + * include/bits/stl_algo.h (shuffle): Extract two random numbers from + each generator invocation when its range is large enough. + 2016-10-14 Jonathan Wakely * testsuite/experimental/algorithm/sample.cc: Qualify calls to diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 0538a79..db99cb8 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -3772,6 +3772,47 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION 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; + + typedef typename std::remove_reference<_UniformRandomNumberGenerator>::type _Gen; + typedef typename std::common_type::type __uc_type; + + const __uc_type __urngrange = __g.max() - __g.min(); + const __uc_type __urange = __uc_type(__last - __first); + + if (__urngrange / __urange >= __urange) + // I.e. (__urngrange >= __urange * __urange) but without wrap issues. + { + _RandomAccessIterator __i = __first + 1; + + // Since we know the range isn't empty, an even number of elements + // means an uneven number of elements /to swap/, in which case we + // do the first one up front: + + if ((__urange % 2) == 0) + { + __distr_type __d{0, 1}; + std::iter_swap(__i++, __first + __d(__g)); + } + + // Now we know that __last - __i is even, so we do the rest in pairs, + // using a single distribution invocation to produce swap positions + // for two successive elements at a time: + + while (__i != __last) + { + const __uc_type __swap_range = __uc_type(__i - __first) + 1; + const __uc_type __comp_range = __swap_range * (__swap_range + 1); + + std::uniform_int_distribution<__uc_type> __d{0, __comp_range - 1}; + const __uc_type __pospos = __d(__g); + + std::iter_swap(__i++, __first + (__pospos % __swap_range)); + std::iter_swap(__i++, __first + (__pospos / __swap_range)); + } + + return; + } + __distr_type __d; for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) -- 2.7.4