42 #ifndef _GLIBCXX_PARALLEL_BALANCED_QUICKSORT_H
43 #define _GLIBCXX_PARALLEL_BALANCED_QUICKSORT_H 1
54 #if _GLIBCXX_ASSERTIONS
61 template<
typename _RAIter>
64 typedef std::iterator_traits<_RAIter> _TraitsType;
65 typedef typename _TraitsType::difference_type _DifferenceType;
98 template<
typename _RAIter,
typename _Compare>
99 typename std::iterator_traits<_RAIter>::difference_type
103 _GLIBCXX_PARALLEL_ASSERT(__num_threads > 0);
105 typedef std::iterator_traits<_RAIter> _TraitsType;
106 typedef typename _TraitsType::value_type _ValueType;
107 typedef typename _TraitsType::difference_type _DifferenceType;
109 _RAIter __pivot_pos =
113 #if defined(_GLIBCXX_ASSERTIONS)
115 _DifferenceType __n = __end - __begin;
117 _GLIBCXX_PARALLEL_ASSERT((!__comp(*__pivot_pos, *__begin)
118 && !__comp(*(__begin + __n / 2),
120 || (!__comp(*__pivot_pos, *__begin)
121 && !__comp(*(__end - 1), *__pivot_pos))
122 || (!__comp(*__pivot_pos, *(__begin + __n / 2))
123 && !__comp(*__begin, *__pivot_pos))
124 || (!__comp(*__pivot_pos, *(__begin + __n / 2))
125 && !__comp(*(__end - 1), *__pivot_pos))
126 || (!__comp(*__pivot_pos, *(__end - 1))
127 && !__comp(*__begin, *__pivot_pos))
128 || (!__comp(*__pivot_pos, *(__end - 1))
129 && !__comp(*(__begin + __n / 2),
134 if (__pivot_pos != (__end - 1))
135 std::iter_swap(__pivot_pos, __end - 1);
136 __pivot_pos = __end - 1;
139 __pred(__comp, *__pivot_pos);
147 std::iter_swap(__begin + __split_pos, __pivot_pos);
148 __pivot_pos = __begin + __split_pos;
150 #if _GLIBCXX_ASSERTIONS
152 for (__r = __begin; __r != __pivot_pos; ++__r)
153 _GLIBCXX_PARALLEL_ASSERT(__comp(*__r, *__pivot_pos));
154 for (; __r != __end; ++__r)
155 _GLIBCXX_PARALLEL_ASSERT(!__comp(*__r, *__pivot_pos));
169 template<
typename _RAIter,
typename _Compare>
172 _RAIter __begin, _RAIter __end,
177 typedef std::iterator_traits<_RAIter> _TraitsType;
178 typedef typename _TraitsType::value_type _ValueType;
179 typedef typename _TraitsType::difference_type _DifferenceType;
181 _DifferenceType __n = __end - __begin;
183 if (__num_threads <= 1 || __n <= 1)
194 _DifferenceType __split_pos =
197 #if _GLIBCXX_ASSERTIONS
198 _GLIBCXX_PARALLEL_ASSERT(0 <= __split_pos &&
199 __split_pos < (__end - __begin));
203 __num_threads_leftside = std::max<_ThreadIndex>
204 (1, std::min<_ThreadIndex>(__num_threads - 1, __split_pos
205 * __num_threads / __n));
211 # pragma omp parallel num_threads(2)
214 if(omp_get_num_threads() < 2)
217 __wait = __parent_wait;
219 # pragma omp sections
224 __iam, __num_threads_leftside, __wait);
225 __wait = __parent_wait;
230 __qsb_conquer(__tls, __begin + __split_pos + 1, __end, __comp,
231 __iam + __num_threads_leftside,
232 __num_threads - __num_threads_leftside, __wait);
233 __wait = __parent_wait;
245 template<
typename _RAIter,
typename _Compare>
251 typedef std::iterator_traits<_RAIter> _TraitsType;
252 typedef typename _TraitsType::value_type _ValueType;
253 typedef typename _TraitsType::difference_type _DifferenceType;
260 if (__base_case_n < 2)
269 _DifferenceType __elements_done = 0;
270 #if _GLIBCXX_ASSERTIONS
271 _DifferenceType __total_elements_done = 0;
277 _RAIter __begin = __current.first, __end = __current.second;
278 _DifferenceType __n = __end - __begin;
280 if (__n > __base_case_n)
283 _RAIter __pivot_pos = __begin + __rng(__n);
286 if (__pivot_pos != (__end - 1))
287 std::iter_swap(__pivot_pos, __end - 1);
288 __pivot_pos = __end - 1;
291 <_Compare, _ValueType, _ValueType,
bool>
292 __pred(__comp, *__pivot_pos);
295 _RAIter __split_pos1, __split_pos2;
296 __split_pos1 = __gnu_sequential::partition(__begin, __end - 1,
300 #if _GLIBCXX_ASSERTIONS
301 _GLIBCXX_PARALLEL_ASSERT(__begin <= __split_pos1
302 && __split_pos1 < __end);
305 if (__split_pos1 != __pivot_pos)
306 std::iter_swap(__split_pos1, __pivot_pos);
307 __pivot_pos = __split_pos1;
310 if ((__split_pos1 + 1 - __begin) < (__n >> 7)
311 || (__end - __split_pos1) < (__n >> 7))
316 <_Compare, _ValueType, _ValueType,
bool>, _ValueType>
318 <_Compare, _ValueType, _ValueType,
bool>
319 (__comp, *__pivot_pos));
322 __split_pos2 = __gnu_sequential::partition(__split_pos1 + 1,
327 __split_pos2 = __split_pos1 + 1;
330 __elements_done += (__split_pos2 - __split_pos1);
331 #if _GLIBCXX_ASSERTIONS
332 __total_elements_done += (__split_pos2 - __split_pos1);
335 if (((__split_pos1 + 1) - __begin) < (__end - (__split_pos2)))
338 if ((__split_pos2) != __end)
343 __current.second = __split_pos1;
349 if (__begin != __split_pos1)
351 (__begin, __split_pos1));
353 __current.first = __split_pos2;
360 __gnu_sequential::sort(__begin, __end, __comp);
361 __elements_done += __n;
362 #if _GLIBCXX_ASSERTIONS
363 __total_elements_done += __n;
375 #if _GLIBCXX_ASSERTIONS
376 double __search_start = omp_get_wtime();
380 bool __successfully_stolen =
false;
382 && !__successfully_stolen
385 && (omp_get_wtime() < (__search_start + 1.0))
390 __victim = __rng(__num_threads);
393 __successfully_stolen = (__victim != __iam)
394 && __tls[__victim]->_M_leftover_parts.pop_back(__current);
395 if (!__successfully_stolen)
397 #if !defined(__ICC) && !defined(__ECC)
402 #if _GLIBCXX_ASSERTIONS
403 if (omp_get_wtime() >= (__search_start + 1.0))
406 _GLIBCXX_PARALLEL_ASSERT(omp_get_wtime()
407 < (__search_start + 1.0));
410 if (!__successfully_stolen)
412 #if _GLIBCXX_ASSERTIONS
428 template<
typename _RAIter,
typename _Compare>
435 typedef std::iterator_traits<_RAIter> _TraitsType;
436 typedef typename _TraitsType::value_type _ValueType;
437 typedef typename _TraitsType::difference_type _DifferenceType;
442 _DifferenceType __n = __end - __begin;
448 if (__num_threads > __n)
452 _TLSType** __tls =
new _TLSType*[__num_threads];
453 _DifferenceType __queue_size = (__num_threads
463 volatile _DifferenceType __elements_leftover = __n;
467 __tls[__i]->_M_num_threads = __num_threads;
476 __num_threads,
true);
478 #if _GLIBCXX_ASSERTIONS
482 _GLIBCXX_PARALLEL_ASSERT(
483 !__tls[__i]->_M_leftover_parts.pop_back(__dummy));
Runtime settings and tuning parameters, heuristics to decide whether to use parallelized algorithms...
void __qsb_conquer(_QSBThreadLocal< _RAIter > **__tls, _RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __iam, _ThreadIndex __num_threads, bool __parent_wait)
Quicksort conquer step.
_ThreadIndex _M_num_threads
Number of threads involved in this algorithm.
uint16_t _ThreadIndex
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
Information local to one thread in the parallel quicksort run.
Includes the original header files concerned with iterators except for stream iterators. This file is a GNU parallel extension to the Standard C++ Library.
void __yield()
Yield control to another thread, without waiting for the end of the time slice.
Lock-free double-ended queue. This file is a GNU parallel extension to the Standard C++ Library...
_RAIter __median_of_three_iterators(_RAIter __a, _RAIter __b, _RAIter __c, _Compare __comp)
Compute the median of three referenced elements, according to __comp.
_Piece _M_global
The complete sequence to sort.
void __parallel_sort_qsb(_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
Top-level quicksort routine.
#define _GLIBCXX_ASSERTIONS
Switch on many _GLIBCXX_PARALLEL_ASSERTions in parallel code. Should be switched on only locally...
#define _GLIBCXX_CALL(__n)
Macro to produce log message when entering a function.
Similar to std::binder2nd, but giving the argument types explicitly.
Random number generator based on the Mersenne twister. This file is a GNU parallel extension to the S...
_RestrictedBoundedConcurrentQueue< _Piece > _M_leftover_parts
Work-stealing queue.
_SequenceIndex sort_qsb_base_case_maximal_n
Maximal subsequence __length to switch to unbalanced __base case. Applies to std::sort with dynamical...
Double-ended queue of bounded size, allowing lock-free atomic access. push_front() and pop_front() mu...
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Routines for checking the correctness of algorithm results. This file is a GNU parallel extension to ...
_Size __rd_log2(_Size __n)
Calculates the rounded-down logarithm of __n for base 2.
std::iterator_traits< _RAIter >::difference_type __qsb_divide(_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
Balanced quicksort divide step.
void __qsb_local_sort_with_helping(_QSBThreadLocal< _RAIter > **__tls, _Compare &__comp, _ThreadIndex __iam, bool __wait)
Quicksort step doing load-balanced local sort.
Similar to std::binder1st, but giving the argument types explicitly.
Parallel implementation of std::partition(), std::nth_element(), and std::partial_sort(). This file is a GNU parallel extension to the Standard C++ Library.
GNU parallel code for public use.
std::iterator_traits< _RAIter >::difference_type __parallel_partition(_RAIter __begin, _RAIter __end, _Predicate __pred, _ThreadIndex __num_threads)
Parallel implementation of std::partition.
Random number generator, based on the Mersenne twister.
static const _Settings & get()
Get the global settings.
_Piece _M_initial
Initial piece to work on.
volatile _DifferenceType * _M_elements_leftover
Pointer to a counter of elements left over to sort.
Similar to std::unary_negate, but giving the argument types explicitly.
std::pair< _RAIter, _RAIter > _Piece
Continuous part of the sequence, described by an iterator pair.
_QSBThreadLocal(int __queue_size)
Constructor.