1 // -*- C++ -*- 2 3 // Copyright (C) 2007, 2008, 2009, 2010 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 = __s.partition_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::iter_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::iter_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 const _Settings& __s = _Settings::get(); 349 _DifferenceType __minimum_length = std::max<_DifferenceType>(2, 350 std::max(__s.nth_element_minimal_n, __s.partition_minimal_n)); 351 352 // Break if input range to small. 353 while (static_cast<_SequenceIndex>(__end - __begin) >= __minimum_length) 354 { 355 _DifferenceType __n = __end - __begin; 356 357 _RAIter __pivot_pos = __begin + __rng(__n); 358 359 // Swap __pivot_pos value to end. 360 if (__pivot_pos != (__end - 1)) 361 std::iter_swap(__pivot_pos, __end - 1); 362 __pivot_pos = __end - 1; 363 364 // _Compare must have first_value_type, second_value_type, 365 // result_type 366 // _Compare == 367 // __gnu_parallel::_Lexicographic<S, int, 368 // __gnu_parallel::_Less<S, S> > 369 // __pivot_pos == std::pair<S, int>* 370 __gnu_parallel::__binder2nd<_Compare, _ValueType, _ValueType, bool> 371 __pred(__comp, *__pivot_pos); 372 373 // Divide, leave pivot unchanged in last place. 374 _RAIter __split_pos1, __split_pos2; 375 __split_pos1 = __begin + __parallel_partition(__begin, __end - 1, 376 __pred, 377 __get_max_threads()); 378 379 // Left side: < __pivot_pos; __right side: >= __pivot_pos 380 381 // Swap pivot back to middle. 382 if (__split_pos1 != __pivot_pos) 383 std::iter_swap(__split_pos1, __pivot_pos); 384 __pivot_pos = __split_pos1; 385 386 // In case all elements are equal, __split_pos1 == 0 387 if ((__split_pos1 + 1 - __begin) < (__n >> 7) 388 || (__end - __split_pos1) < (__n >> 7)) 389 { 390 // Very unequal split, one part smaller than one 128th 391 // elements not strictly larger than the pivot. 392 __gnu_parallel::__unary_negate<__gnu_parallel:: 393 __binder1st<_Compare, _ValueType, 394 _ValueType, bool>, _ValueType> 395 __pred(__gnu_parallel::__binder1st<_Compare, _ValueType, 396 _ValueType, bool>(__comp, *__pivot_pos)); 397 398 // Find other end of pivot-equal range. 399 __split_pos2 = __gnu_sequential::partition(__split_pos1 + 1, 400 __end, __pred); 401 } 402 else 403 // Only skip the pivot. 404 __split_pos2 = __split_pos1 + 1; 405 406 // Compare iterators. 407 if (__split_pos2 <= __nth) 408 __begin = __split_pos2; 409 else if (__nth < __split_pos1) 410 __end = __split_pos1; 411 else 412 break; 413 } 414 415 // Only at most _Settings::partition_minimal_n __elements __left. 416 __gnu_sequential::nth_element(__begin, __nth, __end, __comp); 417 } 418 419 /** @brief Parallel implementation of std::partial_sort(). 420 * @param __begin Begin iterator of input sequence. 421 * @param __middle Sort until this position. 422 * @param __end End iterator of input sequence. 423 * @param __comp Comparator. */ 424 template<typename _RAIter, typename _Compare> 425 void 426 __parallel_partial_sort(_RAIter __begin, 427 _RAIter __middle, 428 _RAIter __end, _Compare __comp) 429 { 430 __parallel_nth_element(__begin, __middle, __end, __comp); 431 std::sort(__begin, __middle, __comp); 432 } 433 434 } //namespace __gnu_parallel 435 436 #undef _GLIBCXX_VOLATILE 437 438 #endif /* _GLIBCXX_PARALLEL_PARTITION_H */ 439