contrib/gcc-8.0/libstdc++-v3/include/parallel/random_shuffle.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007-2018 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file parallel/random_shuffle.h
  26  *  @brief Parallel implementation of std::random_shuffle().
  27  *  This file is a GNU parallel extension to the Standard C++ Library.
  28  */
  29
  30 // Written by Johannes Singler.
  31
  32 #ifndef _GLIBCXX_PARALLEL_RANDOM_SHUFFLE_H
  33 #define _GLIBCXX_PARALLEL_RANDOM_SHUFFLE_H 1
  34
  35 #include <limits>
  36 #include <bits/stl_numeric.h>
  37 #include <parallel/parallel.h>
  38 #include <parallel/random_number.h>
  39
  40 namespace __gnu_parallel
  41 {
  42   /** @brief Type to hold the index of a bin.
  43     *
  44     *  Since many variables of this type are allocated, it should be
  45     *  chosen as small as possible.
  46     */
  47   typedef unsigned short _BinIndex;
  48
  49   /** @brief Data known to every thread participating in
  50       __gnu_parallel::__parallel_random_shuffle(). */
  51   template<typename _RAIter>
  52     struct _DRandomShufflingGlobalData
  53     {
  54       typedef std::iterator_traits<_RAIter> _TraitsType;
  55       typedef typename _TraitsType::value_type _ValueType;
  56       typedef typename _TraitsType::difference_type _DifferenceType;
  57
  58       /** @brief Begin iterator of the __source. */
  59       _RAIter& _M_source;
  60
  61       /** @brief Temporary arrays for each thread. */
  62       _ValueType** _M_temporaries;
  63
  64       /** @brief Two-dimensional array to hold the thread-bin distribution.
  65        *
  66        *  Dimensions (_M_num_threads + 1) __x (_M_num_bins + 1). */
  67       _DifferenceType** _M_dist;
  68
  69       /** @brief Start indexes of the threads' __chunks. */
  70       _DifferenceType* _M_starts;
  71
  72       /** @brief Number of the thread that will further process the
  73           corresponding bin. */
  74       _ThreadIndex* _M_bin_proc;
  75
  76       /** @brief Number of bins to distribute to. */
  77       int _M_num_bins;
  78
  79       /** @brief Number of bits needed to address the bins. */
  80       int _M_num_bits;
  81
  82       /** @brief Constructor. */
  83       _DRandomShufflingGlobalData(_RAIter& __source)
  84       : _M_source(__source) { }
  85     };
  86
  87   /** @brief Local data for a thread participating in
  88       __gnu_parallel::__parallel_random_shuffle().
  89     */
  90   template<typename _RAIter, typename _RandomNumberGenerator>
  91     struct _DRSSorterPU
  92     {
  93       /** @brief Number of threads participating in total. */
  94       int _M_num_threads;
  95
  96       /** @brief Begin index for bins taken care of by this thread. */
  97       _BinIndex _M_bins_begin;
  98
  99       /** @brief End index for bins taken care of by this thread. */
 100       _BinIndex __bins_end;
 101
 102       /** @brief Random _M_seed for this thread. */
 103       uint32_t _M_seed;
 104
 105       /** @brief Pointer to global data. */
 106       _DRandomShufflingGlobalData<_RAIter>* _M_sd;
 107     };
 108
 109   /** @brief Generate a random number in @c [0,2^__logp).
 110     *  @param __logp Logarithm (basis 2) of the upper range __bound.
 111     *  @param __rng Random number generator to use.
 112     */
 113   template<typename _RandomNumberGenerator>
 114     inline int
 115     __random_number_pow2(int __logp, _RandomNumberGenerator& __rng)
 116     { return __rng.__genrand_bits(__logp); }
 117
 118   /** @brief Random shuffle code executed by each thread.
 119     *  @param __pus Array of thread-local data records. */
 120   template<typename _RAIter, typename _RandomNumberGenerator>
 121     void
 122     __parallel_random_shuffle_drs_pu(_DRSSorterPU<_RAIter,
 123                                      _RandomNumberGenerator>* __pus)
 124     {
 125       typedef std::iterator_traits<_RAIter> _TraitsType;
 126       typedef typename _TraitsType::value_type _ValueType;
 127       typedef typename _TraitsType::difference_type _DifferenceType;
 128
 129       _ThreadIndex __iam = omp_get_thread_num();
 130       _DRSSorterPU<_RAIter, _RandomNumberGenerator>* __d = &__pus[__iam];
 131       _DRandomShufflingGlobalData<_RAIter>* __sd = __d->_M_sd;
 132
 133       // Indexing: _M_dist[bin][processor]
 134       _DifferenceType __length = (__sd->_M_starts[__iam + 1]
 135                                   - __sd->_M_starts[__iam]);
 136       _BinIndex* __oracles = new _BinIndex[__length];
 137       _DifferenceType* __dist = new _DifferenceType[__sd->_M_num_bins + 1];
 138       _BinIndex* __bin_proc = new _BinIndex[__sd->_M_num_bins];
 139       _ValueType** __temporaries = new _ValueType*[__d->_M_num_threads];
 140
 141       // Compute oracles and count appearances.
 142       for (_BinIndex __b = 0; __b < __sd->_M_num_bins + 1; ++__b)
 143         __dist[__b] = 0;
 144       int __num_bits = __sd->_M_num_bits;
 145
 146       _RandomNumber __rng(__d->_M_seed);
 147
 148       // First main loop.
 149       for (_DifferenceType __i = 0; __i < __length; ++__i)
 150         {
 151           _BinIndex __oracle = __random_number_pow2(__num_bits, __rng);
 152           __oracles[__i] = __oracle;
 153
 154           // To allow prefix (partial) sum.
 155           ++(__dist[__oracle + 1]);
 156         }
 157
 158       for (_BinIndex __b = 0; __b < __sd->_M_num_bins + 1; ++__b)
 159         __sd->_M_dist[__b][__iam + 1] = __dist[__b];
 160
 161 #     pragma omp barrier
 162
 163 #     pragma omp single
 164       {
 165         // Sum up bins, __sd->_M_dist[__s + 1][__d->_M_num_threads] now
 166         // contains the total number of items in bin __s
 167         for (_BinIndex __s = 0; __s < __sd->_M_num_bins; ++__s)
 168           __gnu_sequential::partial_sum(__sd->_M_dist[__s + 1],
 169                                         __sd->_M_dist[__s + 1]
 170                                         + __d->_M_num_threads + 1,
 171                                         __sd->_M_dist[__s + 1]);
 172       }
 173
 174 #     pragma omp barrier
 175
 176       _SequenceIndex __offset = 0, __global_offset = 0;
 177       for (_BinIndex __s = 0; __s < __d->_M_bins_begin; ++__s)
 178         __global_offset += __sd->_M_dist[__s + 1][__d->_M_num_threads];
 179
 180 #     pragma omp barrier
 181
 182       for (_BinIndex __s = __d->_M_bins_begin; __s < __d->__bins_end; ++__s)
 183         {
 184           for (int __t = 0; __t < __d->_M_num_threads + 1; ++__t)
 185             __sd->_M_dist[__s + 1][__t] += __offset;
 186           __offset = __sd->_M_dist[__s + 1][__d->_M_num_threads];
 187         }
 188
 189       __sd->_M_temporaries[__iam] = static_cast<_ValueType*>
 190         (::operator new(sizeof(_ValueType) * __offset));
 191
 192 #     pragma omp barrier
 193
 194       // Draw local copies to avoid false sharing.
 195       for (_BinIndex __b = 0; __b < __sd->_M_num_bins + 1; ++__b)
 196         __dist[__b] = __sd->_M_dist[__b][__iam];
 197       for (_BinIndex __b = 0; __b < __sd->_M_num_bins; ++__b)
 198         __bin_proc[__b] = __sd->_M_bin_proc[__b];
 199       for (_ThreadIndex __t = 0; __t < __d->_M_num_threads; ++__t)
 200         __temporaries[__t] = __sd->_M_temporaries[__t];
 201
 202       _RAIter __source = __sd->_M_source;
 203       _DifferenceType __start = __sd->_M_starts[__iam];
 204
 205       // Distribute according to oracles, second main loop.
 206       for (_DifferenceType __i = 0; __i < __length; ++__i)
 207         {
 208           _BinIndex __target_bin = __oracles[__i];
 209           _ThreadIndex __target_p = __bin_proc[__target_bin];
 210
 211           // Last column [__d->_M_num_threads] stays unchanged.
 212           ::new(&(__temporaries[__target_p][__dist[__target_bin + 1]++]))
 213               _ValueType(*(__source + __i + __start));
 214         }
 215
 216       delete[] __oracles;
 217       delete[] __dist;
 218       delete[] __bin_proc;
 219       delete[] __temporaries;
 220
 221 #     pragma omp barrier
 222
 223       // Shuffle bins internally.
 224       for (_BinIndex __b = __d->_M_bins_begin; __b < __d->__bins_end; ++__b)
 225         {
 226           _ValueType* __begin =
 227             (__sd->_M_temporaries[__iam]
 228              + (__b == __d->_M_bins_begin
 229                 ? 0 : __sd->_M_dist[__b][__d->_M_num_threads])),
 230             *__end = (__sd->_M_temporaries[__iam]
 231                       + __sd->_M_dist[__b + 1][__d->_M_num_threads]);
 232
 233           __sequential_random_shuffle(__begin, __end, __rng);
 234           std::copy(__begin, __end, __sd->_M_source + __global_offset
 235                     + (__b == __d->_M_bins_begin
 236                        ? 0 : __sd->_M_dist[__b][__d->_M_num_threads]));
 237         }
 238
 239       for (_SequenceIndex __i = 0; __i < __offset; ++__i)
 240         __sd->_M_temporaries[__iam][__i].~_ValueType();
 241       ::operator delete(__sd->_M_temporaries[__iam]);
 242     }
 243
 244   /** @brief Round up to the next greater power of 2.
 245     *  @param __x _Integer to round up */
 246   template<typename _Tp>
 247     _Tp
 248     __round_up_to_pow2(_Tp __x)
 249     {
 250       if (__x <= 1)
 251         return 1;
 252       else
 253         return (_Tp)1 << (__rd_log2(__x - 1) + 1);
 254     }
 255
 256   /** @brief Main parallel random shuffle step.
 257     *  @param __begin Begin iterator of sequence.
 258     *  @param __end End iterator of sequence.
 259     *  @param __n Length of sequence.
 260     *  @param __num_threads Number of threads to use.
 261     *  @param __rng Random number generator to use.
 262     */
 263   template<typename _RAIter, typename _RandomNumberGenerator>
 264     void
 265     __parallel_random_shuffle_drs(_RAIter __begin, _RAIter __end,
 266                                   typename std::iterator_traits
 267                                   <_RAIter>::difference_type __n,
 268                                   _ThreadIndex __num_threads,
 269                                   _RandomNumberGenerator& __rng)
 270     {
 271       typedef std::iterator_traits<_RAIter> _TraitsType;
 272       typedef typename _TraitsType::value_type _ValueType;
 273       typedef typename _TraitsType::difference_type _DifferenceType;
 274
 275       _GLIBCXX_CALL(__n)
 276
 277       const _Settings& __s = _Settings::get();
 278
 279       if (__num_threads > __n)
 280         __num_threads = static_cast<_ThreadIndex>(__n);
 281
 282       _BinIndex __num_bins, __num_bins_cache;
 283
 284 #if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1
 285       // Try the L1 cache first.
 286
 287       // Must fit into L1.
 288       __num_bins_cache =
 289         std::max<_DifferenceType>(1, __n / (__s.L1_cache_size_lb
 290                                             / sizeof(_ValueType)));
 291       __num_bins_cache = __round_up_to_pow2(__num_bins_cache);
 292
 293       // No more buckets than TLB entries, power of 2
 294       // Power of 2 and at least one element per bin, at most the TLB size.
 295       __num_bins = std::min<_DifferenceType>(__n, __num_bins_cache);
 296
 297 #if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB
 298       // 2 TLB entries needed per bin.
 299       __num_bins = std::min<_DifferenceType>(__s.TLB_size / 2, __num_bins);
 300 #endif
 301       __num_bins = __round_up_to_pow2(__num_bins);
 302
 303       if (__num_bins < __num_bins_cache)
 304         {
 305 #endif
 306           // Now try the L2 cache
 307           // Must fit into L2
 308           __num_bins_cache = static_cast<_BinIndex>
 309             (std::max<_DifferenceType>(1, __n / (__s.L2_cache_size
 310                                                  / sizeof(_ValueType))));
 311           __num_bins_cache = __round_up_to_pow2(__num_bins_cache);
 312
 313           // No more buckets than TLB entries, power of 2.
 314           __num_bins = static_cast<_BinIndex>
 315             (std::min(__n, static_cast<_DifferenceType>(__num_bins_cache)));
 316           // Power of 2 and at least one element per bin, at most the TLB size.
 317 #if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB
 318           // 2 TLB entries needed per bin.
 319           __num_bins = std::min(static_cast<_DifferenceType>(__s.TLB_size / 2),
 320                                 __num_bins);
 321 #endif
 322             __num_bins = __round_up_to_pow2(__num_bins);
 323 #if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1
 324         }
 325 #endif
 326
 327       __num_bins = __round_up_to_pow2(
 328                         std::max<_BinIndex>(__num_threads, __num_bins));
 329
 330       if (__num_threads <= 1)
 331       {
 332         _RandomNumber __derived_rng(
 333                             __rng(std::numeric_limits<uint32_t>::max()));
 334         __sequential_random_shuffle(__begin, __end, __derived_rng);
 335         return;
 336       }
 337
 338       _DRandomShufflingGlobalData<_RAIter> __sd(__begin);
 339       _DRSSorterPU<_RAIter, _RandomNumber >* __pus;
 340       _DifferenceType* __starts;
 341
 342 #     pragma omp parallel num_threads(__num_threads)
 343       {
 344         _ThreadIndex __num_threads = omp_get_num_threads();
 345 #       pragma omp single
 346         {
 347           __pus = new _DRSSorterPU<_RAIter, _RandomNumber>[__num_threads];
 348
 349           __sd._M_temporaries = new _ValueType*[__num_threads];
 350           __sd._M_dist = new _DifferenceType*[__num_bins + 1];
 351           __sd._M_bin_proc = new _ThreadIndex[__num_bins];
 352           for (_BinIndex __b = 0; __b < __num_bins + 1; ++__b)
 353             __sd._M_dist[__b] = new _DifferenceType[__num_threads + 1];
 354           for (_BinIndex __b = 0; __b < (__num_bins + 1); ++__b)
 355             {
 356               __sd._M_dist[0][0] = 0;
 357               __sd._M_dist[__b][0] = 0;
 358             }
 359           __starts = __sd._M_starts = new _DifferenceType[__num_threads + 1];
 360           int __bin_cursor = 0;
 361           __sd._M_num_bins = __num_bins;
 362           __sd._M_num_bits = __rd_log2(__num_bins);
 363
 364           _DifferenceType __chunk_length = __n / __num_threads,
 365                                  __split = __n % __num_threads,
 366                                  __start = 0;
 367           _DifferenceType __bin_chunk_length = __num_bins / __num_threads,
 368                                  __bin_split = __num_bins % __num_threads;
 369           for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
 370             {
 371               __starts[__i] = __start;
 372               __start += (__i < __split
 373                           ? (__chunk_length + 1) : __chunk_length);
 374               int __j = __pus[__i]._M_bins_begin = __bin_cursor;
 375
 376               // Range of bins for this processor.
 377               __bin_cursor += (__i < __bin_split
 378                                ? (__bin_chunk_length + 1)
 379                                : __bin_chunk_length);
 380               __pus[__i].__bins_end = __bin_cursor;
 381               for (; __j < __bin_cursor; ++__j)
 382                 __sd._M_bin_proc[__j] = __i;
 383               __pus[__i]._M_num_threads = __num_threads;
 384               __pus[__i]._M_seed = __rng(std::numeric_limits<uint32_t>::max());
 385               __pus[__i]._M_sd = &__sd;
 386             }
 387           __starts[__num_threads] = __start;
 388         } //single
 389           // Now shuffle in parallel.
 390         __parallel_random_shuffle_drs_pu(__pus);
 391       }  // parallel
 392
 393       delete[] __starts;
 394       delete[] __sd._M_bin_proc;
 395       for (int __s = 0; __s < (__num_bins + 1); ++__s)
 396         delete[] __sd._M_dist[__s];
 397       delete[] __sd._M_dist;
 398       delete[] __sd._M_temporaries;
 399
 400       delete[] __pus;
 401     }
 402
 403   /** @brief Sequential cache-efficient random shuffle.
 404    *  @param __begin Begin iterator of sequence.
 405    *  @param __end End iterator of sequence.
 406    *  @param __rng Random number generator to use.
 407    */
 408   template<typename _RAIter, typename _RandomNumberGenerator>
 409     void
 410     __sequential_random_shuffle(_RAIter __begin, _RAIter __end,
 411                                 _RandomNumberGenerator& __rng)
 412     {
 413       typedef std::iterator_traits<_RAIter> _TraitsType;
 414       typedef typename _TraitsType::value_type _ValueType;
 415       typedef typename _TraitsType::difference_type _DifferenceType;
 416
 417       _DifferenceType __n = __end - __begin;
 418       const _Settings& __s = _Settings::get();
 419
 420       _BinIndex __num_bins, __num_bins_cache;
 421
 422 #if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1
 423       // Try the L1 cache first, must fit into L1.
 424       __num_bins_cache = std::max<_DifferenceType>
 425         (1, __n / (__s.L1_cache_size_lb / sizeof(_ValueType)));
 426       __num_bins_cache = __round_up_to_pow2(__num_bins_cache);
 427
 428       // No more buckets than TLB entries, power of 2
 429       // Power of 2 and at least one element per bin, at most the TLB size
 430       __num_bins = std::min(__n, (_DifferenceType)__num_bins_cache);
 431 #if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB
 432       // 2 TLB entries needed per bin
 433       __num_bins = std::min((_DifferenceType)__s.TLB_size / 2, __num_bins);
 434 #endif
 435       __num_bins = __round_up_to_pow2(__num_bins);
 436
 437       if (__num_bins < __num_bins_cache)
 438         {
 439 #endif
 440           // Now try the L2 cache, must fit into L2.
 441           __num_bins_cache = static_cast<_BinIndex>
 442             (std::max<_DifferenceType>(1, __n / (__s.L2_cache_size
 443                                                  / sizeof(_ValueType))));
 444           __num_bins_cache = __round_up_to_pow2(__num_bins_cache);
 445
 446           // No more buckets than TLB entries, power of 2
 447           // Power of 2 and at least one element per bin, at most the TLB size.
 448           __num_bins = static_cast<_BinIndex>
 449             (std::min(__n, static_cast<_DifferenceType>(__num_bins_cache)));
 450
 451 #if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB
 452           // 2 TLB entries needed per bin
 453           __num_bins = std::min<_DifferenceType>(__s.TLB_size / 2, __num_bins);
 454 #endif
 455           __num_bins = __round_up_to_pow2(__num_bins);
 456 #if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1
 457         }
 458 #endif
 459
 460       int __num_bits = __rd_log2(__num_bins);
 461
 462       if (__num_bins > 1)
 463         {
 464           _ValueType* __target =
 465             static_cast<_ValueType*>(::operator new(sizeof(_ValueType) * __n));
 466           _BinIndex* __oracles = new _BinIndex[__n];
 467           _DifferenceType* __dist0 = new _DifferenceType[__num_bins + 1],
 468                          * __dist1 = new _DifferenceType[__num_bins + 1];
 469
 470           for (int __b = 0; __b < __num_bins + 1; ++__b)
 471             __dist0[__b] = 0;
 472
 473           _RandomNumber __bitrng(__rng(0xFFFFFFFF));
 474
 475           for (_DifferenceType __i = 0; __i < __n; ++__i)
 476             {
 477               _BinIndex __oracle = __random_number_pow2(__num_bits, __bitrng);
 478               __oracles[__i] = __oracle;
 479
 480               // To allow prefix (partial) sum.
 481               ++(__dist0[__oracle + 1]);
 482             }
 483
 484           // Sum up bins.
 485           __gnu_sequential::partial_sum(__dist0, __dist0 + __num_bins + 1,
 486                                         __dist0);
 487
 488           for (int __b = 0; __b < __num_bins + 1; ++__b)
 489             __dist1[__b] = __dist0[__b];
 490
 491           // Distribute according to oracles.
 492           for (_DifferenceType __i = 0; __i < __n; ++__i)
 493             ::new(&(__target[(__dist0[__oracles[__i]])++]))
 494                 _ValueType(*(__begin + __i));
 495
 496           for (int __b = 0; __b < __num_bins; ++__b)
 497             __sequential_random_shuffle(__target + __dist1[__b],
 498                                         __target + __dist1[__b + 1], __rng);
 499
 500           // Copy elements back.
 501           std::copy(__target, __target + __n, __begin);
 502
 503           delete[] __dist0;
 504           delete[] __dist1;
 505           delete[] __oracles;
 506
 507           for (_DifferenceType __i = 0; __i < __n; ++__i)
 508             __target[__i].~_ValueType();
 509           ::operator delete(__target);
 510         }
 511       else
 512         __gnu_sequential::random_shuffle(__begin, __end, __rng);
 513     }
 514
 515   /** @brief Parallel random public call.
 516    *  @param __begin Begin iterator of sequence.
 517    *  @param __end End iterator of sequence.
 518    *  @param __rng Random number generator to use.
 519    */
 520   template<typename _RAIter, typename _RandomNumberGenerator>
 521     inline void
 522     __parallel_random_shuffle(_RAIter __begin, _RAIter __end,
 523                               _RandomNumberGenerator __rng = _RandomNumber())
 524     {
 525       typedef std::iterator_traits<_RAIter> _TraitsType;
 526       typedef typename _TraitsType::difference_type _DifferenceType;
 527       _DifferenceType __n = __end - __begin;
 528       __parallel_random_shuffle_drs(__begin, __end, __n,
 529                                     __get_max_threads(), __rng);
 530     }
 531 }
 532
 533 #endif /* _GLIBCXX_PARALLEL_RANDOM_SHUFFLE_H */