// -*- C++ -*-
-// Copyright (C) 2007 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
-// Foundation; either version 2, or (at your option) any later
+// Foundation; either version 3, or (at your option) any later
// version.
// This library is distributed in the hope that it will be useful, but
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
-// You should have received a copy of the GNU General Public License
-// along with this library; see the file COPYING. If not, write to
-// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
-// MA 02111-1307, USA.
-
-// As a special exception, you may use this file as part of a free
-// software library without restriction. Specifically, if other files
-// instantiate templates or use macros or inline functions from this
-// file, or you compile this file and link it with other files to
-// produce an executable, this file does not by itself cause the
-// resulting executable to be covered by the GNU General Public
-// License. This exception does not however invalidate any other
-// reasons why the executable file might be covered by the GNU General
-// Public License.
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// <http://www.gnu.org/licenses/>.
/** @file parallel/random_shuffle.h
* @brief Parallel implementation of std::random_shuffle().
namespace __gnu_parallel
{
-/** @brief Type to hold the index of a bin.
- *
- * Since many variables of this type are allocated, it should be
- * chosen as small as possible.
- */
-typedef unsigned short bin_index;
-
-/** @brief Data known to every thread participating in
- __gnu_parallel::parallel_random_shuffle(). */
-template<typename RandomAccessIterator>
- struct DRandomShufflingGlobalData
- {
- typedef std::iterator_traits<RandomAccessIterator> traits_type;
- typedef typename traits_type::value_type value_type;
- typedef typename traits_type::difference_type difference_type;
-
- /** @brief Begin iterator of the source. */
- RandomAccessIterator& source;
-
- /** @brief Temporary arrays for each thread. */
- value_type** temporaries;
-
- /** @brief Two-dimensional array to hold the thread-bin distribution.
- *
- * Dimensions (num_threads + 1) x (num_bins + 1). */
- difference_type** dist;
-
- /** @brief Start indexes of the threads' chunks. */
- difference_type* starts;
-
- /** @brief Number of the thread that will further process the
- corresponding bin. */
- thread_index_t* bin_proc;
-
- /** @brief Number of bins to distribute to. */
- int num_bins;
-
- /** @brief Number of bits needed to address the bins. */
- int num_bits;
-
- /** @brief Constructor. */
- DRandomShufflingGlobalData(RandomAccessIterator& _source)
- : source(_source) { }
- };
-
-/** @brief Local data for a thread participating in
- __gnu_parallel::parallel_random_shuffle().
- */
-template<typename RandomAccessIterator, typename RandomNumberGenerator>
- struct DRSSorterPU
- {
- /** @brief Number of threads participating in total. */
- int num_threads;
-
- /** @brief Begin index for bins taken care of by this thread. */
- bin_index bins_begin;
-
- /** @brief End index for bins taken care of by this thread. */
- bin_index bins_end;
-
- /** @brief Random seed for this thread. */
- uint32 seed;
-
- /** @brief Pointer to global data. */
- DRandomShufflingGlobalData<RandomAccessIterator>* sd;
- };
-
-/** @brief Generate a random number in @c [0,2^logp).
- * @param logp Logarithm (basis 2) of the upper range bound.
- * @param rng Random number generator to use.
- */
-template<typename RandomNumberGenerator>
- inline int
- random_number_pow2(int logp, RandomNumberGenerator& rng)
- { return rng.genrand_bits(logp); }
-
-/** @brief Random shuffle code executed by each thread.
- * @param pus Array of thread-local data records. */
-template<typename RandomAccessIterator, typename RandomNumberGenerator>
- inline void
- parallel_random_shuffle_drs_pu(DRSSorterPU<RandomAccessIterator,
- RandomNumberGenerator>* pus)
- {
- typedef std::iterator_traits<RandomAccessIterator> traits_type;
- typedef typename traits_type::value_type value_type;
- typedef typename traits_type::difference_type difference_type;
-
- thread_index_t iam = omp_get_thread_num();
- DRSSorterPU<RandomAccessIterator, RandomNumberGenerator>* d = &pus[iam];
- DRandomShufflingGlobalData<RandomAccessIterator>* sd = d->sd;
-
- // Indexing: dist[bin][processor]
- difference_type length = sd->starts[iam + 1] - sd->starts[iam];
- bin_index* oracles = new bin_index[length];
- difference_type* dist = new difference_type[sd->num_bins + 1];
- bin_index* bin_proc = new bin_index[sd->num_bins];
- value_type** temporaries = new value_type*[d->num_threads];
-
- // Compute oracles and count appearances.
- for (bin_index b = 0; b < sd->num_bins + 1; ++b)
- dist[b] = 0;
- int num_bits = sd->num_bits;
-
- random_number rng(d->seed);
-
- // First main loop.
- for (difference_type i = 0; i < length; ++i)
- {
- bin_index oracle = random_number_pow2(num_bits, rng);
- oracles[i] = oracle;
+ /** @brief Type to hold the index of a bin.
+ *
+ * Since many variables of this type are allocated, it should be
+ * chosen as small as possible.
+ */
+ typedef unsigned short _BinIndex;
+
+ /** @brief Data known to every thread participating in
+ __gnu_parallel::__parallel_random_shuffle(). */
+ template<typename _RAIter>
+ struct _DRandomShufflingGlobalData
+ {
+ typedef std::iterator_traits<_RAIter> _TraitsType;
+ typedef typename _TraitsType::value_type _ValueType;
+ typedef typename _TraitsType::difference_type _DifferenceType;
- // To allow prefix (partial) sum.
- ++(dist[oracle + 1]);
- }
+ /** @brief Begin iterator of the __source. */
+ _RAIter& _M_source;
- for (bin_index b = 0; b < sd->num_bins + 1; ++b)
- sd->dist[b][iam + 1] = dist[b];
+ /** @brief Temporary arrays for each thread. */
+ _ValueType** _M_temporaries;
-# pragma omp barrier
+ /** @brief Two-dimensional array to hold the thread-bin distribution.
+ *
+ * Dimensions (_M_num_threads + 1) __x (_M_num_bins + 1). */
+ _DifferenceType** _M_dist;
-# pragma omp single
- {
- // Sum up bins, sd->dist[s + 1][d->num_threads] now contains the
- // total number of items in bin s
- for (bin_index s = 0; s < sd->num_bins; ++s)
- __gnu_sequential::partial_sum(sd->dist[s + 1],
- sd->dist[s + 1] + d->num_threads + 1,
- sd->dist[s + 1]);
- }
+ /** @brief Start indexes of the threads' __chunks. */
+ _DifferenceType* _M_starts;
-# pragma omp barrier
+ /** @brief Number of the thread that will further process the
+ corresponding bin. */
+ _ThreadIndex* _M_bin_proc;
- sequence_index_t offset = 0, global_offset = 0;
- for (bin_index s = 0; s < d->bins_begin; ++s)
- global_offset += sd->dist[s + 1][d->num_threads];
+ /** @brief Number of bins to distribute to. */
+ int _M_num_bins;
-# pragma omp barrier
+ /** @brief Number of bits needed to address the bins. */
+ int _M_num_bits;
- for (bin_index s = d->bins_begin; s < d->bins_end; ++s)
- {
- for (int t = 0; t < d->num_threads + 1; ++t)
- sd->dist[s + 1][t] += offset;
- offset = sd->dist[s + 1][d->num_threads];
- }
+ /** @brief Constructor. */
+ _DRandomShufflingGlobalData(_RAIter& __source)
+ : _M_source(__source) { }
+ };
+
+ /** @brief Local data for a thread participating in
+ __gnu_parallel::__parallel_random_shuffle().
+ */
+ template<typename _RAIter, typename _RandomNumberGenerator>
+ struct _DRSSorterPU
+ {
+ /** @brief Number of threads participating in total. */
+ int _M_num_threads;
+
+ /** @brief Begin index for bins taken care of by this thread. */
+ _BinIndex _M_bins_begin;
+
+ /** @brief End index for bins taken care of by this thread. */
+ _BinIndex __bins_end;
+
+ /** @brief Random _M_seed for this thread. */
+ uint32_t _M_seed;
+
+ /** @brief Pointer to global data. */
+ _DRandomShufflingGlobalData<_RAIter>* _M_sd;
+ };
+
+ /** @brief Generate a random number in @c [0,2^__logp).
+ * @param __logp Logarithm (basis 2) of the upper range __bound.
+ * @param __rng Random number generator to use.
+ */
+ template<typename _RandomNumberGenerator>
+ inline int
+ __random_number_pow2(int __logp, _RandomNumberGenerator& __rng)
+ { return __rng.__genrand_bits(__logp); }
+
+ /** @brief Random shuffle code executed by each thread.
+ * @param __pus Array of thread-local data records. */
+ template<typename _RAIter, typename _RandomNumberGenerator>
+ void
+ __parallel_random_shuffle_drs_pu(_DRSSorterPU<_RAIter,
+ _RandomNumberGenerator>* __pus)
+ {
+ typedef std::iterator_traits<_RAIter> _TraitsType;
+ typedef typename _TraitsType::value_type _ValueType;
+ typedef typename _TraitsType::difference_type _DifferenceType;
- sd->temporaries[iam] = static_cast<value_type*>(
- ::operator new(sizeof(value_type) * offset));
+ _ThreadIndex __iam = omp_get_thread_num();
+ _DRSSorterPU<_RAIter, _RandomNumberGenerator>* __d = &__pus[__iam];
+ _DRandomShufflingGlobalData<_RAIter>* __sd = __d->_M_sd;
-# pragma omp barrier
+ // Indexing: _M_dist[bin][processor]
+ _DifferenceType __length = (__sd->_M_starts[__iam + 1]
+ - __sd->_M_starts[__iam]);
+ _BinIndex* __oracles = new _BinIndex[__length];
+ _DifferenceType* __dist = new _DifferenceType[__sd->_M_num_bins + 1];
+ _BinIndex* __bin_proc = new _BinIndex[__sd->_M_num_bins];
+ _ValueType** __temporaries = new _ValueType*[__d->_M_num_threads];
- // Draw local copies to avoid false sharing.
- for (bin_index b = 0; b < sd->num_bins + 1; ++b)
- dist[b] = sd->dist[b][iam];
- for (bin_index b = 0; b < sd->num_bins; ++b)
- bin_proc[b] = sd->bin_proc[b];
- for (thread_index_t t = 0; t < d->num_threads; ++t)
- temporaries[t] = sd->temporaries[t];
+ // Compute oracles and count appearances.
+ for (_BinIndex __b = 0; __b < __sd->_M_num_bins + 1; ++__b)
+ __dist[__b] = 0;
+ int __num_bits = __sd->_M_num_bits;
- RandomAccessIterator source = sd->source;
- difference_type start = sd->starts[iam];
+ _RandomNumber __rng(__d->_M_seed);
- // Distribute according to oracles, second main loop.
- for (difference_type i = 0; i < length; ++i)
- {
- bin_index target_bin = oracles[i];
- thread_index_t target_p = bin_proc[target_bin];
+ // First main loop.
+ for (_DifferenceType __i = 0; __i < __length; ++__i)
+ {
+ _BinIndex __oracle = __random_number_pow2(__num_bits, __rng);
+ __oracles[__i] = __oracle;
- // Last column [d->num_threads] stays unchanged.
- new(&(temporaries[target_p][dist[target_bin + 1]++])) value_type(
- *(source + i + start));
- }
+ // To allow prefix (partial) sum.
+ ++(__dist[__oracle + 1]);
+ }
- delete[] oracles;
- delete[] dist;
- delete[] bin_proc;
- delete[] temporaries;
+ for (_BinIndex __b = 0; __b < __sd->_M_num_bins + 1; ++__b)
+ __sd->_M_dist[__b][__iam + 1] = __dist[__b];
-# pragma omp barrier
+# pragma omp barrier
- // Shuffle bins internally.
- for (bin_index b = d->bins_begin; b < d->bins_end; ++b)
+# pragma omp single
{
- value_type* begin =
- sd->temporaries[iam] +
- ((b == d->bins_begin) ? 0 : sd->dist[b][d->num_threads]),
- * end =
- sd->temporaries[iam] + sd->dist[b + 1][d->num_threads];
- sequential_random_shuffle(begin, end, rng);
- std::copy(begin, end, sd->source + global_offset +
- ((b == d->bins_begin) ? 0 : sd->dist[b][d->num_threads]));
+ // Sum up bins, __sd->_M_dist[__s + 1][__d->_M_num_threads] now
+ // contains the total number of items in bin __s
+ for (_BinIndex __s = 0; __s < __sd->_M_num_bins; ++__s)
+ __gnu_sequential::partial_sum(__sd->_M_dist[__s + 1],
+ __sd->_M_dist[__s + 1]
+ + __d->_M_num_threads + 1,
+ __sd->_M_dist[__s + 1]);
}
- delete[] sd->temporaries[iam];
- }
-
-/** @brief Round up to the next greater power of 2.
- * @param x Integer to round up */
-template<typename T>
- T
- round_up_to_pow2(T x)
- {
- if (x <= 1)
- return 1;
- else
- return (T)1 << (log2(x - 1) + 1);
- }
-
-/** @brief Main parallel random shuffle step.
- * @param begin Begin iterator of sequence.
- * @param end End iterator of sequence.
- * @param n Length of sequence.
- * @param num_threads Number of threads to use.
- * @param rng Random number generator to use.
- */
-template<typename RandomAccessIterator, typename RandomNumberGenerator>
- inline void
- parallel_random_shuffle_drs(
- RandomAccessIterator begin,
- RandomAccessIterator end,
- typename std::iterator_traits<RandomAccessIterator>::difference_type n,
- thread_index_t num_threads,
- RandomNumberGenerator& rng)
- {
- typedef std::iterator_traits<RandomAccessIterator> traits_type;
- typedef typename traits_type::value_type value_type;
- typedef typename traits_type::difference_type difference_type;
-
- _GLIBCXX_CALL(n)
-
- if (num_threads > n)
- num_threads = static_cast<thread_index_t>(n);
-
- bin_index num_bins, num_bins_cache;
+# pragma omp barrier
+
+ _SequenceIndex __offset = 0, __global_offset = 0;
+ for (_BinIndex __s = 0; __s < __d->_M_bins_begin; ++__s)
+ __global_offset += __sd->_M_dist[__s + 1][__d->_M_num_threads];
+
+# pragma omp barrier
+
+ for (_BinIndex __s = __d->_M_bins_begin; __s < __d->__bins_end; ++__s)
+ {
+ for (int __t = 0; __t < __d->_M_num_threads + 1; ++__t)
+ __sd->_M_dist[__s + 1][__t] += __offset;
+ __offset = __sd->_M_dist[__s + 1][__d->_M_num_threads];
+ }
+
+ __sd->_M_temporaries[__iam] = static_cast<_ValueType*>
+ (::operator new(sizeof(_ValueType) * __offset));
+
+# pragma omp barrier
+
+ // Draw local copies to avoid false sharing.
+ for (_BinIndex __b = 0; __b < __sd->_M_num_bins + 1; ++__b)
+ __dist[__b] = __sd->_M_dist[__b][__iam];
+ for (_BinIndex __b = 0; __b < __sd->_M_num_bins; ++__b)
+ __bin_proc[__b] = __sd->_M_bin_proc[__b];
+ for (_ThreadIndex __t = 0; __t < __d->_M_num_threads; ++__t)
+ __temporaries[__t] = __sd->_M_temporaries[__t];
+
+ _RAIter __source = __sd->_M_source;
+ _DifferenceType __start = __sd->_M_starts[__iam];
+
+ // Distribute according to oracles, second main loop.
+ for (_DifferenceType __i = 0; __i < __length; ++__i)
+ {
+ _BinIndex __target_bin = __oracles[__i];
+ _ThreadIndex __target_p = __bin_proc[__target_bin];
+
+ // Last column [__d->_M_num_threads] stays unchanged.
+ ::new(&(__temporaries[__target_p][__dist[__target_bin + 1]++]))
+ _ValueType(*(__source + __i + __start));
+ }
+
+ delete[] __oracles;
+ delete[] __dist;
+ delete[] __bin_proc;
+ delete[] __temporaries;
+
+# pragma omp barrier
+
+ // Shuffle bins internally.
+ for (_BinIndex __b = __d->_M_bins_begin; __b < __d->__bins_end; ++__b)
+ {
+ _ValueType* __begin =
+ (__sd->_M_temporaries[__iam]
+ + (__b == __d->_M_bins_begin
+ ? 0 : __sd->_M_dist[__b][__d->_M_num_threads])),
+ * __end = (__sd->_M_temporaries[__iam]
+ + __sd->_M_dist[__b + 1][__d->_M_num_threads]);
+
+ __sequential_random_shuffle(__begin, __end, __rng);
+ std::copy(__begin, __end, __sd->_M_source + __global_offset
+ + (__b == __d->_M_bins_begin
+ ? 0 : __sd->_M_dist[__b][__d->_M_num_threads]));
+ }
+
+ ::operator delete(__sd->_M_temporaries[__iam]);
+ }
+
+ /** @brief Round up to the next greater power of 2.
+ * @param __x _Integer to round up */
+ template<typename _Tp>
+ _Tp
+ __round_up_to_pow2(_Tp __x)
+ {
+ if (__x <= 1)
+ return 1;
+ else
+ return (_Tp)1 << (__rd_log2(__x - 1) + 1);
+ }
+
+ /** @brief Main parallel random shuffle step.
+ * @param __begin Begin iterator of sequence.
+ * @param __end End iterator of sequence.
+ * @param __n Length of sequence.
+ * @param __num_threads Number of threads to use.
+ * @param __rng Random number generator to use.
+ */
+ template<typename _RAIter, typename _RandomNumberGenerator>
+ void
+ __parallel_random_shuffle_drs(_RAIter __begin, _RAIter __end,
+ typename std::iterator_traits
+ <_RAIter>::difference_type __n,
+ _ThreadIndex __num_threads,
+ _RandomNumberGenerator& __rng)
+ {
+ typedef std::iterator_traits<_RAIter> _TraitsType;
+ typedef typename _TraitsType::value_type _ValueType;
+ typedef typename _TraitsType::difference_type _DifferenceType;
+
+ _GLIBCXX_CALL(__n)
+
+ const _Settings& __s = _Settings::get();
+
+ if (__num_threads > __n)
+ __num_threads = static_cast<_ThreadIndex>(__n);
+
+ _BinIndex __num_bins, __num_bins_cache;
#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1
- // Try the L1 cache first.
+ // Try the L1 cache first.
- // Must fit into L1.
- num_bins_cache = std::max<difference_type>(
- 1, n / (Settings::L1_cache_size_lb / sizeof(value_type)));
- num_bins_cache = round_up_to_pow2(num_bins_cache);
+ // Must fit into L1.
+ __num_bins_cache =
+ std::max<_DifferenceType>(1, __n / (__s.L1_cache_size_lb
+ / sizeof(_ValueType)));
+ __num_bins_cache = __round_up_to_pow2(__num_bins_cache);
- // No more buckets than TLB entries, power of 2
- // Power of 2 and at least one element per bin, at most the TLB size.
- num_bins = std::min<difference_type>(n, num_bins_cache);
+ // No more buckets than TLB entries, power of 2
+ // Power of 2 and at least one element per bin, at most the TLB size.
+ __num_bins = std::min<_DifferenceType>(__n, __num_bins_cache);
#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB
- // 2 TLB entries needed per bin.
- num_bins = std::min<difference_type>(Settings::TLB_size / 2, num_bins);
+ // 2 TLB entries needed per bin.
+ __num_bins = std::min<_DifferenceType>(__s.TLB_size / 2, __num_bins);
#endif
- num_bins = round_up_to_pow2(num_bins);
+ __num_bins = __round_up_to_pow2(__num_bins);
- if (num_bins < num_bins_cache)
- {
+ if (__num_bins < __num_bins_cache)
+ {
#endif
- // Now try the L2 cache
- // Must fit into L2
- num_bins_cache = static_cast<bin_index>(std::max<difference_type>(
- 1, n / (Settings::L2_cache_size / sizeof(value_type))));
- num_bins_cache = round_up_to_pow2(num_bins_cache);
-
- // No more buckets than TLB entries, power of 2.
- num_bins = static_cast<bin_index>(
- std::min(n, static_cast<difference_type>(num_bins_cache)));
- // Power of 2 and at least one element per bin, at most the TLB size.
+ // Now try the L2 cache
+ // Must fit into L2
+ __num_bins_cache = static_cast<_BinIndex>
+ (std::max<_DifferenceType>(1, __n / (__s.L2_cache_size
+ / sizeof(_ValueType))));
+ __num_bins_cache = __round_up_to_pow2(__num_bins_cache);
+
+ // No more buckets than TLB entries, power of 2.
+ __num_bins = static_cast<_BinIndex>
+ (std::min(__n, static_cast<_DifferenceType>(__num_bins_cache)));
+ // Power of 2 and at least one element per bin, at most the TLB size.
#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB
- // 2 TLB entries needed per bin.
- num_bins = std::min(
- static_cast<difference_type>(Settings::TLB_size / 2), num_bins);
+ // 2 TLB entries needed per bin.
+ __num_bins = std::min(static_cast<_DifferenceType>(__s.TLB_size / 2),
+ __num_bins);
#endif
- num_bins = round_up_to_pow2(num_bins);
+ __num_bins = __round_up_to_pow2(__num_bins);
#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1
- }
+ }
#endif
- num_threads = std::min<bin_index>(num_threads, num_bins);
+ __num_bins = __round_up_to_pow2(
+ std::max<_BinIndex>(__num_threads, __num_bins));
- if (num_threads <= 1)
- return sequential_random_shuffle(begin, end, rng);
+ if (__num_threads <= 1)
+ {
+ _RandomNumber __derived_rng(
+ __rng(std::numeric_limits<uint32_t>::max()));
+ __sequential_random_shuffle(__begin, __end, __derived_rng);
+ return;
+ }
- DRandomShufflingGlobalData<RandomAccessIterator> sd(begin);
- DRSSorterPU<RandomAccessIterator, random_number >* pus;
- difference_type* starts;
+ _DRandomShufflingGlobalData<_RAIter> __sd(__begin);
+ _DRSSorterPU<_RAIter, _RandomNumber >* __pus;
+ _DifferenceType* __starts;
-# pragma omp parallel num_threads(num_threads)
+# pragma omp parallel num_threads(__num_threads)
{
+ _ThreadIndex __num_threads = omp_get_num_threads();
# pragma omp single
- {
- pus = new DRSSorterPU<RandomAccessIterator, random_number>
- [num_threads];
-
- sd.temporaries = new value_type*[num_threads];
- sd.dist = new difference_type*[num_bins + 1];
- sd.bin_proc = new thread_index_t[num_bins];
- for (bin_index b = 0; b < num_bins + 1; ++b)
- sd.dist[b] = new difference_type[num_threads + 1];
- for (bin_index b = 0; b < (num_bins + 1); ++b)
- {
- sd.dist[0][0] = 0;
- sd.dist[b][0] = 0;
- }
- starts = sd.starts = new difference_type[num_threads + 1];
- int bin_cursor = 0;
- sd.num_bins = num_bins;
- sd.num_bits = log2(num_bins);
-
- difference_type chunk_length = n / num_threads,
- split = n % num_threads, start = 0;
- difference_type bin_chunk_length = num_bins / num_threads,
- bin_split = num_bins % num_threads;
- for (thread_index_t i = 0; i < num_threads; ++i)
- {
- starts[i] = start;
- start += (i < split) ? (chunk_length + 1) : chunk_length;
- int j = pus[i].bins_begin = bin_cursor;
-
- // Range of bins for this processor.
- bin_cursor += (i < bin_split) ?
- (bin_chunk_length + 1) : bin_chunk_length;
- pus[i].bins_end = bin_cursor;
- for (; j < bin_cursor; ++j)
- sd.bin_proc[j] = i;
- pus[i].num_threads = num_threads;
- pus[i].seed = rng(std::numeric_limits<uint32>::max());
- pus[i].sd = &sd;
- }
- starts[num_threads] = start;
- } //single
- // Now shuffle in parallel.
- parallel_random_shuffle_drs_pu(pus);
+ {
+ __pus = new _DRSSorterPU<_RAIter, _RandomNumber>[__num_threads];
+
+ __sd._M_temporaries = new _ValueType*[__num_threads];
+ __sd._M_dist = new _DifferenceType*[__num_bins + 1];
+ __sd._M_bin_proc = new _ThreadIndex[__num_bins];
+ for (_BinIndex __b = 0; __b < __num_bins + 1; ++__b)
+ __sd._M_dist[__b] = new _DifferenceType[__num_threads + 1];
+ for (_BinIndex __b = 0; __b < (__num_bins + 1); ++__b)
+ {
+ __sd._M_dist[0][0] = 0;
+ __sd._M_dist[__b][0] = 0;
+ }
+ __starts = __sd._M_starts = new _DifferenceType[__num_threads + 1];
+ int __bin_cursor = 0;
+ __sd._M_num_bins = __num_bins;
+ __sd._M_num_bits = __rd_log2(__num_bins);
+
+ _DifferenceType __chunk_length = __n / __num_threads,
+ __split = __n % __num_threads,
+ __start = 0;
+ _DifferenceType __bin_chunk_length = __num_bins / __num_threads,
+ __bin_split = __num_bins % __num_threads;
+ for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
+ {
+ __starts[__i] = __start;
+ __start += (__i < __split
+ ? (__chunk_length + 1) : __chunk_length);
+ int __j = __pus[__i]._M_bins_begin = __bin_cursor;
+
+ // Range of bins for this processor.
+ __bin_cursor += (__i < __bin_split
+ ? (__bin_chunk_length + 1)
+ : __bin_chunk_length);
+ __pus[__i].__bins_end = __bin_cursor;
+ for (; __j < __bin_cursor; ++__j)
+ __sd._M_bin_proc[__j] = __i;
+ __pus[__i]._M_num_threads = __num_threads;
+ __pus[__i]._M_seed = __rng(std::numeric_limits<uint32_t>::max());
+ __pus[__i]._M_sd = &__sd;
+ }
+ __starts[__num_threads] = __start;
+ } //single
+ // Now shuffle in parallel.
+ __parallel_random_shuffle_drs_pu(__pus);
+ } // parallel
+
+ delete[] __starts;
+ delete[] __sd._M_bin_proc;
+ for (int __s = 0; __s < (__num_bins + 1); ++__s)
+ delete[] __sd._M_dist[__s];
+ delete[] __sd._M_dist;
+ delete[] __sd._M_temporaries;
+
+ delete[] __pus;
}
- delete[] starts;
- delete[] sd.bin_proc;
- for (int s = 0; s < (num_bins + 1); ++s)
- delete[] sd.dist[s];
- delete[] sd.dist;
- delete[] sd.temporaries;
-
- delete[] pus;
- }
-
-/** @brief Sequential cache-efficient random shuffle.
- * @param begin Begin iterator of sequence.
- * @param end End iterator of sequence.
- * @param rng Random number generator to use.
- */
-template<typename RandomAccessIterator, typename RandomNumberGenerator>
- inline void
- sequential_random_shuffle(RandomAccessIterator begin,
- RandomAccessIterator end,
- RandomNumberGenerator& rng)
- {
- typedef std::iterator_traits<RandomAccessIterator> traits_type;
- typedef typename traits_type::value_type value_type;
- typedef typename traits_type::difference_type difference_type;
+ /** @brief Sequential cache-efficient random shuffle.
+ * @param __begin Begin iterator of sequence.
+ * @param __end End iterator of sequence.
+ * @param __rng Random number generator to use.
+ */
+ template<typename _RAIter, typename _RandomNumberGenerator>
+ void
+ __sequential_random_shuffle(_RAIter __begin, _RAIter __end,
+ _RandomNumberGenerator& __rng)
+ {
+ typedef std::iterator_traits<_RAIter> _TraitsType;
+ typedef typename _TraitsType::value_type _ValueType;
+ typedef typename _TraitsType::difference_type _DifferenceType;
- difference_type n = end - begin;
+ _DifferenceType __n = __end - __begin;
+ const _Settings& __s = _Settings::get();
- bin_index num_bins, num_bins_cache;
+ _BinIndex __num_bins, __num_bins_cache;
#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1
- // Try the L1 cache first, must fit into L1.
- num_bins_cache =
- std::max<difference_type>
- (1, n / (Settings::L1_cache_size_lb / sizeof(value_type)));
- num_bins_cache = round_up_to_pow2(num_bins_cache);
-
- // No more buckets than TLB entries, power of 2
- // Power of 2 and at least one element per bin, at most the TLB size
- num_bins = std::min(n, (difference_type)num_bins_cache);
+ // Try the L1 cache first, must fit into L1.
+ __num_bins_cache = std::max<_DifferenceType>
+ (1, __n / (__s.L1_cache_size_lb / sizeof(_ValueType)));
+ __num_bins_cache = __round_up_to_pow2(__num_bins_cache);
+
+ // No more buckets than TLB entries, power of 2
+ // Power of 2 and at least one element per bin, at most the TLB size
+ __num_bins = std::min(__n, (_DifferenceType)__num_bins_cache);
#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB
- // 2 TLB entries needed per bin
- num_bins = std::min((difference_type)Settings::TLB_size / 2, num_bins);
+ // 2 TLB entries needed per bin
+ __num_bins = std::min((_DifferenceType)__s.TLB_size / 2, __num_bins);
#endif
- num_bins = round_up_to_pow2(num_bins);
+ __num_bins = __round_up_to_pow2(__num_bins);
- if (num_bins < num_bins_cache)
- {
+ if (__num_bins < __num_bins_cache)
+ {
#endif
- // Now try the L2 cache, must fit into L2.
- num_bins_cache =
- static_cast<bin_index>(std::max<difference_type>(
- 1, n / (Settings::L2_cache_size / sizeof(value_type))));
- num_bins_cache = round_up_to_pow2(num_bins_cache);
+ // Now try the L2 cache, must fit into L2.
+ __num_bins_cache = static_cast<_BinIndex>
+ (std::max<_DifferenceType>(1, __n / (__s.L2_cache_size
+ / sizeof(_ValueType))));
+ __num_bins_cache = __round_up_to_pow2(__num_bins_cache);
- // No more buckets than TLB entries, power of 2
- // Power of 2 and at least one element per bin, at most the TLB size.
- num_bins = static_cast<bin_index>
- (std::min(n, static_cast<difference_type>(num_bins_cache)));
+ // No more buckets than TLB entries, power of 2
+ // Power of 2 and at least one element per bin, at most the TLB size.
+ __num_bins = static_cast<_BinIndex>
+ (std::min(__n, static_cast<_DifferenceType>(__num_bins_cache)));
#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB
- // 2 TLB entries needed per bin
- num_bins =
- std::min<difference_type>(Settings::TLB_size / 2, num_bins);
+ // 2 TLB entries needed per bin
+ __num_bins = std::min<_DifferenceType>(__s.TLB_size / 2, __num_bins);
#endif
- num_bins = round_up_to_pow2(num_bins);
+ __num_bins = __round_up_to_pow2(__num_bins);
#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1
- }
+ }
#endif
- int num_bits = log2(num_bins);
+ int __num_bits = __rd_log2(__num_bins);
- if (num_bins > 1)
- {
- value_type* target = static_cast<value_type*>(
- ::operator new(sizeof(value_type) * n));
- bin_index* oracles = new bin_index[n];
- difference_type* dist0 = new difference_type[num_bins + 1],
- * dist1 = new difference_type[num_bins + 1];
-
- for (int b = 0; b < num_bins + 1; ++b)
- dist0[b] = 0;
-
- random_number bitrng(rng(0xFFFFFFFF));
-
- for (difference_type i = 0; i < n; ++i)
- {
- bin_index oracle = random_number_pow2(num_bits, bitrng);
- oracles[i] = oracle;
-
- // To allow prefix (partial) sum.
- ++(dist0[oracle + 1]);
- }
-
- // Sum up bins.
- __gnu_sequential::partial_sum(dist0, dist0 + num_bins + 1, dist0);
-
- for (int b = 0; b < num_bins + 1; ++b)
- dist1[b] = dist0[b];
-
- // Distribute according to oracles.
- for (difference_type i = 0; i < n; ++i)
- new(&(target[(dist0[oracles[i]])++])) value_type(*(begin + i));
-
- for (int b = 0; b < num_bins; ++b)
- {
- sequential_random_shuffle(target + dist1[b],
- target + dist1[b + 1],
- rng);
- }
-
- delete[] dist0;
- delete[] dist1;
- delete[] oracles;
- delete[] target;
- }
- else
- __gnu_sequential::random_shuffle(begin, end, rng);
- }
-
-/** @brief Parallel random public call.
- * @param begin Begin iterator of sequence.
- * @param end End iterator of sequence.
- * @param rng Random number generator to use.
- */
-template<typename RandomAccessIterator, typename RandomNumberGenerator>
- inline void
- parallel_random_shuffle(RandomAccessIterator begin,
- RandomAccessIterator end,
- RandomNumberGenerator rng = random_number())
- {
- typedef std::iterator_traits<RandomAccessIterator> traits_type;
- typedef typename traits_type::difference_type difference_type;
- difference_type n = end - begin;
- parallel_random_shuffle_drs(begin, end, n, get_max_threads(), rng) ;
- }
+ if (__num_bins > 1)
+ {
+ _ValueType* __target =
+ static_cast<_ValueType*>(::operator new(sizeof(_ValueType) * __n));
+ _BinIndex* __oracles = new _BinIndex[__n];
+ _DifferenceType* __dist0 = new _DifferenceType[__num_bins + 1],
+ * __dist1 = new _DifferenceType[__num_bins + 1];
+
+ for (int __b = 0; __b < __num_bins + 1; ++__b)
+ __dist0[__b] = 0;
+
+ _RandomNumber __bitrng(__rng(0xFFFFFFFF));
+ for (_DifferenceType __i = 0; __i < __n; ++__i)
+ {
+ _BinIndex __oracle = __random_number_pow2(__num_bits, __bitrng);
+ __oracles[__i] = __oracle;
+
+ // To allow prefix (partial) sum.
+ ++(__dist0[__oracle + 1]);
+ }
+
+ // Sum up bins.
+ __gnu_sequential::partial_sum(__dist0, __dist0 + __num_bins + 1,
+ __dist0);
+
+ for (int __b = 0; __b < __num_bins + 1; ++__b)
+ __dist1[__b] = __dist0[__b];
+
+ // Distribute according to oracles.
+ for (_DifferenceType __i = 0; __i < __n; ++__i)
+ ::new(&(__target[(__dist0[__oracles[__i]])++]))
+ _ValueType(*(__begin + __i));
+
+ for (int __b = 0; __b < __num_bins; ++__b)
+ __sequential_random_shuffle(__target + __dist1[__b],
+ __target + __dist1[__b + 1], __rng);
+
+ // Copy elements back.
+ std::copy(__target, __target + __n, __begin);
+
+ delete[] __dist0;
+ delete[] __dist1;
+ delete[] __oracles;
+ ::operator delete(__target);
+ }
+ else
+ __gnu_sequential::random_shuffle(__begin, __end, __rng);
+ }
+
+ /** @brief Parallel random public call.
+ * @param __begin Begin iterator of sequence.
+ * @param __end End iterator of sequence.
+ * @param __rng Random number generator to use.
+ */
+ template<typename _RAIter, typename _RandomNumberGenerator>
+ inline void
+ __parallel_random_shuffle(_RAIter __begin, _RAIter __end,
+ _RandomNumberGenerator __rng = _RandomNumber())
+ {
+ typedef std::iterator_traits<_RAIter> _TraitsType;
+ typedef typename _TraitsType::difference_type _DifferenceType;
+ _DifferenceType __n = __end - __begin;
+ __parallel_random_shuffle_drs(__begin, __end, __n,
+ __get_max_threads(), __rng);
+ }
}
-#endif
+#endif /* _GLIBCXX_PARALLEL_RANDOM_SHUFFLE_H */
projects / gcc.git / blobdiff