libstdc++-v3/include/parallel/partition.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008, 2009 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/partition.h
  26  *  @brief Parallel implementation of std::partition(),
  27  *  std::nth_element(), and std::partial_sort().
  28  *  This file is a GNU parallel extension to the Standard C++ Library.
  29  */
  30
  31 // Written by Johannes Singler and Felix Putze.
  32
  33 #ifndef _GLIBCXX_PARALLEL_PARTITION_H
  34 #define _GLIBCXX_PARALLEL_PARTITION_H 1
  35
  36 #include <parallel/basic_iterator.h>
  37 #include <parallel/sort.h>
  38 #include <parallel/random_number.h>
  39 #include <bits/stl_algo.h>
  40 #include <parallel/parallel.h>
  41
  42 /** @brief Decide whether to declare certain variables volatile. */
  43 #define _GLIBCXX_VOLATILE volatile
  44
  45 namespace __gnu_parallel
  46 {
  47   /** @brief Parallel implementation of std::partition.
  48     *  @param __begin Begin iterator of input sequence to split.
  49     *  @param __end End iterator of input sequence to split.
  50     *  @param __pred Partition predicate, possibly including some kind
  51     *         of pivot.
  52     *  @param __num_threads Maximum number of threads to use for this task.
  53     *  @return Number of elements not fulfilling the predicate. */
  54   template<typename _RAIter, typename _Predicate>
  55     typename std::iterator_traits<_RAIter>::difference_type
  56     __parallel_partition(_RAIter __begin, _RAIter __end,
  57                          _Predicate __pred, _ThreadIndex __num_threads)
  58     {
  59       typedef std::iterator_traits<_RAIter> _TraitsType;
  60       typedef typename _TraitsType::value_type _ValueType;
  61       typedef typename _TraitsType::difference_type _DifferenceType;
  62
  63       _DifferenceType __n = __end - __begin;
  64
  65       _GLIBCXX_CALL(__n)
  66
  67       const _Settings& __s = _Settings::get();
  68
  69       // Shared.
  70       _GLIBCXX_VOLATILE _DifferenceType __left = 0, __right = __n - 1;
  71       _GLIBCXX_VOLATILE _DifferenceType __leftover_left, __leftover_right;
  72       _GLIBCXX_VOLATILE _DifferenceType __leftnew, __rightnew;
  73
  74       bool* __reserved_left = NULL, * __reserved_right = NULL;
  75
  76       _DifferenceType __chunk_size;
  77
  78       omp_lock_t __result_lock;
  79       omp_init_lock(&__result_lock);
  80
  81       //at least two chunks per thread
  82       if (__right - __left + 1 >= 2 * __num_threads * __chunk_size)
  83 #       pragma omp parallel num_threads(__num_threads)
  84         {
  85 #         pragma omp single
  86           {
  87             __num_threads = omp_get_num_threads();
  88             __reserved_left = new bool[__num_threads];
  89             __reserved_right = new bool[__num_threads];
  90
  91             if (__s.partition_chunk_share > 0.0)
  92               __chunk_size = std::max<_DifferenceType>
  93                 (__s.partition_chunk_size, (double)__n
  94                  * __s.partition_chunk_share / (double)__num_threads);
  95             else
  96               __chunk_size = __s.partition_chunk_size;
  97           }
  98
  99           while (__right - __left + 1 >= 2 * __num_threads * __chunk_size)
 100             {
 101 #             pragma omp single
 102               {
 103                 _DifferenceType __num_chunks = ((__right - __left + 1)
 104                                                 / __chunk_size);
 105
 106                 for (_ThreadIndex __r = 0; __r < __num_threads; ++__r)
 107                   {
 108                     __reserved_left[__r] = false;
 109                     __reserved_right[__r] = false;
 110                   }
 111                 __leftover_left = 0;
 112                 __leftover_right = 0;
 113               } //implicit barrier
 114
 115               // Private.
 116               _DifferenceType __thread_left, __thread_left_border,
 117                               __thread_right, __thread_right_border;
 118               __thread_left = __left + 1;
 119
 120               // Just to satisfy the condition below.
 121               __thread_left_border = __thread_left - 1;
 122               __thread_right = __n - 1;
 123               __thread_right_border = __thread_right + 1;
 124
 125               bool __iam_finished = false;
 126               while (!__iam_finished)
 127                 {
 128                   if (__thread_left > __thread_left_border)
 129                     {
 130                       omp_set_lock(&__result_lock);
 131                       if (__left + (__chunk_size - 1) > __right)
 132                         __iam_finished = true;
 133                       else
 134                         {
 135                           __thread_left = __left;
 136                           __thread_left_border = __left + (__chunk_size - 1);
 137                           __left += __chunk_size;
 138                         }
 139                       omp_unset_lock(&__result_lock);
 140                     }
 141
 142                   if (__thread_right < __thread_right_border)
 143                     {
 144                       omp_set_lock(&__result_lock);
 145                       if (__left > __right - (__chunk_size - 1))
 146                         __iam_finished = true;
 147                       else
 148                         {
 149                           __thread_right = __right;
 150                           __thread_right_border = __right - (__chunk_size - 1);
 151                           __right -= __chunk_size;
 152                         }
 153                       omp_unset_lock(&__result_lock);
 154                     }
 155
 156                   if (__iam_finished)
 157                     break;
 158
 159                   // Swap as usual.
 160                   while (__thread_left < __thread_right)
 161                     {
 162                       while (__pred(__begin[__thread_left])
 163                              && __thread_left <= __thread_left_border)
 164                         ++__thread_left;
 165                       while (!__pred(__begin[__thread_right])
 166                              && __thread_right >= __thread_right_border)
 167                         --__thread_right;
 168
 169                       if (__thread_left > __thread_left_border
 170                           || __thread_right < __thread_right_border)
 171                         // Fetch new chunk(__s).
 172                         break;
 173
 174                       std::swap(__begin[__thread_left],
 175                                 __begin[__thread_right]);
 176                       ++__thread_left;
 177                       --__thread_right;
 178                     }
 179                 }
 180
 181               // Now swap the leftover chunks to the right places.
 182               if (__thread_left <= __thread_left_border)
 183 #               pragma omp atomic
 184                 ++__leftover_left;
 185               if (__thread_right >= __thread_right_border)
 186 #               pragma omp atomic
 187                 ++__leftover_right;
 188
 189 #             pragma omp barrier
 190
 191 #             pragma omp single
 192               {
 193                 __leftnew = __left - __leftover_left * __chunk_size;
 194                 __rightnew = __right + __leftover_right * __chunk_size;
 195               }
 196
 197 #             pragma omp barrier
 198
 199               // <=> __thread_left_border + (__chunk_size - 1) >= __leftnew
 200               if (__thread_left <= __thread_left_border
 201                   && __thread_left_border >= __leftnew)
 202                 {
 203                   // Chunk already in place, reserve spot.
 204                 __reserved_left[(__left - (__thread_left_border + 1))
 205                                 / __chunk_size] = true;
 206                 }
 207
 208               // <=> __thread_right_border - (__chunk_size - 1) <= __rightnew
 209               if (__thread_right >= __thread_right_border
 210                   && __thread_right_border <= __rightnew)
 211                 {
 212                   // Chunk already in place, reserve spot.
 213                   __reserved_right[((__thread_right_border - 1) - __right)
 214                                    / __chunk_size] = true;
 215                 }
 216
 217 #             pragma omp barrier
 218
 219               if (__thread_left <= __thread_left_border
 220                   && __thread_left_border < __leftnew)
 221                 {
 222                   // Find spot and swap.
 223                   _DifferenceType __swapstart = -1;
 224                   omp_set_lock(&__result_lock);
 225                   for (_DifferenceType __r = 0; __r < __leftover_left; ++__r)
 226                     if (!__reserved_left[__r])
 227                       {
 228                         __reserved_left[__r] = true;
 229                         __swapstart = __left - (__r + 1) * __chunk_size;
 230                         break;
 231                       }
 232                   omp_unset_lock(&__result_lock);
 233
 234 #if _GLIBCXX_ASSERTIONS
 235                   _GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);
 236 #endif
 237
 238                   std::swap_ranges(__begin + __thread_left_border
 239                                    - (__chunk_size - 1),
 240                                    __begin + __thread_left_border + 1,
 241                                    __begin + __swapstart);
 242                 }
 243
 244               if (__thread_right >= __thread_right_border
 245                   && __thread_right_border > __rightnew)
 246                 {
 247                   // Find spot and swap
 248                   _DifferenceType __swapstart = -1;
 249                   omp_set_lock(&__result_lock);
 250                   for (_DifferenceType __r = 0; __r < __leftover_right; ++__r)
 251                     if (!__reserved_right[__r])
 252                       {
 253                         __reserved_right[__r] = true;
 254                         __swapstart = __right + __r * __chunk_size + 1;
 255                         break;
 256                       }
 257                   omp_unset_lock(&__result_lock);
 258
 259 #if _GLIBCXX_ASSERTIONS
 260                   _GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);
 261 #endif
 262
 263                   std::swap_ranges(__begin + __thread_right_border,
 264                                    __begin + __thread_right_border
 265                                    + __chunk_size, __begin + __swapstart);
 266               }
 267 #if _GLIBCXX_ASSERTIONS
 268 #             pragma omp barrier
 269
 270 #             pragma omp single
 271               {
 272                 for (_DifferenceType __r = 0; __r < __leftover_left; ++__r)
 273                   _GLIBCXX_PARALLEL_ASSERT(__reserved_left[__r]);
 274                 for (_DifferenceType __r = 0; __r < __leftover_right; ++__r)
 275                   _GLIBCXX_PARALLEL_ASSERT(__reserved_right[__r]);
 276               }
 277
 278 #             pragma omp barrier
 279 #endif
 280
 281 #             pragma omp barrier
 282
 283               __left = __leftnew;
 284               __right = __rightnew;
 285             }
 286
 287 #           pragma omp flush(__left, __right)
 288         } // end "recursion" //parallel
 289
 290         _DifferenceType __final_left = __left, __final_right = __right;
 291
 292         while (__final_left < __final_right)
 293           {
 294             // Go right until key is geq than pivot.
 295             while (__pred(__begin[__final_left])
 296                    && __final_left < __final_right)
 297               ++__final_left;
 298
 299             // Go left until key is less than pivot.
 300             while (!__pred(__begin[__final_right])
 301                    && __final_left < __final_right)
 302               --__final_right;
 303
 304             if (__final_left == __final_right)
 305               break;
 306             std::swap(__begin[__final_left], __begin[__final_right]);
 307             ++__final_left;
 308             --__final_right;
 309           }
 310
 311         // All elements on the left side are < piv, all elements on the
 312         // right are >= piv
 313         delete[] __reserved_left;
 314         delete[] __reserved_right;
 315
 316         omp_destroy_lock(&__result_lock);
 317
 318         // Element "between" __final_left and __final_right might not have
 319         // been regarded yet
 320         if (__final_left < __n && !__pred(__begin[__final_left]))
 321           // Really swapped.
 322           return __final_left;
 323         else
 324           return __final_left + 1;
 325     }
 326
 327   /**
 328     *  @brief Parallel implementation of std::nth_element().
 329     *  @param __begin Begin iterator of input sequence.
 330     *  @param __nth _Iterator of element that must be in position afterwards.
 331     *  @param __end End iterator of input sequence.
 332     *  @param __comp Comparator.
 333     */
 334   template<typename _RAIter, typename _Compare>
 335     void
 336     __parallel_nth_element(_RAIter __begin, _RAIter __nth,
 337                            _RAIter __end, _Compare __comp)
 338     {
 339       typedef std::iterator_traits<_RAIter> _TraitsType;
 340       typedef typename _TraitsType::value_type _ValueType;
 341       typedef typename _TraitsType::difference_type _DifferenceType;
 342
 343       _GLIBCXX_CALL(__end - __begin)
 344
 345       _RAIter __split;
 346       _RandomNumber __rng;
 347
 348       _DifferenceType __minimum_length =
 349         std::max<_DifferenceType>(2, _Settings::get().partition_minimal_n);
 350
 351       // Break if input range to small.
 352       while (static_cast<_SequenceIndex>(__end - __begin) >= __minimum_length)
 353         {
 354           _DifferenceType __n = __end - __begin;
 355
 356           _RAIter __pivot_pos = __begin +  __rng(__n);
 357
 358           // Swap __pivot_pos value to end.
 359           if (__pivot_pos != (__end - 1))
 360             std::swap(*__pivot_pos, *(__end - 1));
 361           __pivot_pos = __end - 1;
 362
 363           // _Compare must have first_value_type, second_value_type,
 364           // result_type
 365           // _Compare ==
 366           // __gnu_parallel::_Lexicographic<S, int,
 367           //                                __gnu_parallel::_Less<S, S> >
 368           // __pivot_pos == std::pair<S, int>*
 369           __gnu_parallel::binder2nd<_Compare, _ValueType, _ValueType, bool>
 370             __pred(__comp, *__pivot_pos);
 371
 372           // Divide, leave pivot unchanged in last place.
 373           _RAIter __split_pos1, __split_pos2;
 374           __split_pos1 = __begin + __parallel_partition(__begin, __end - 1,
 375                                                         __pred,
 376                                                         __get_max_threads());
 377
 378           // Left side: < __pivot_pos; __right side: >= __pivot_pos
 379
 380           // Swap pivot back to middle.
 381           if (__split_pos1 != __pivot_pos)
 382             std::swap(*__split_pos1, *__pivot_pos);
 383           __pivot_pos = __split_pos1;
 384
 385           // In case all elements are equal, __split_pos1 == 0
 386           if ((__split_pos1 + 1 - __begin) < (__n >> 7)
 387               || (__end - __split_pos1) < (__n >> 7))
 388             {
 389               // Very unequal split, one part smaller than one 128th
 390               // elements not strictly larger than the pivot.
 391               __gnu_parallel::__unary_negate<__gnu_parallel::
 392                 __binder1st<_Compare, _ValueType,
 393                             _ValueType, bool>, _ValueType>
 394                 __pred(__gnu_parallel::__binder1st<_Compare, _ValueType,
 395                        _ValueType, bool>(__comp, *__pivot_pos));
 396
 397               // Find other end of pivot-equal range.
 398               __split_pos2 = __gnu_sequential::partition(__split_pos1 + 1,
 399                                                          __end, __pred);
 400             }
 401           else
 402             // Only skip the pivot.
 403             __split_pos2 = __split_pos1 + 1;
 404
 405           // Compare iterators.
 406           if (__split_pos2 <= __nth)
 407             __begin = __split_pos2;
 408           else if (__nth < __split_pos1)
 409             __end = __split_pos1;
 410           else
 411             break;
 412         }
 413
 414       // Only at most _Settings::partition_minimal_n __elements __left.
 415       __gnu_sequential::sort(__begin, __end, __comp);
 416     }
 417
 418   /** @brief Parallel implementation of std::partial_sort().
 419   *  @param __begin Begin iterator of input sequence.
 420   *  @param __middle Sort until this position.
 421   *  @param __end End iterator of input sequence.
 422   *  @param __comp Comparator. */
 423   template<typename _RAIter, typename _Compare>
 424     void
 425     __parallel_partial_sort(_RAIter __begin,
 426                             _RAIter __middle,
 427                             _RAIter __end, _Compare __comp)
 428     {
 429       __parallel_nth_element(__begin, __middle, __end, __comp);
 430       std::sort(__begin, __middle, __comp);
 431     }
 432
 433 } //namespace __gnu_parallel
 434
 435 #undef _GLIBCXX_VOLATILE
 436
 437 #endif /* _GLIBCXX_PARALLEL_PARTITION_H */