0,0 → 1,434 |
// -*- C++ -*- |
|
// Copyright (C) 2007-2015 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 3, or (at your option) any later |
// version. |
|
// This library is distributed in the hope that it will be useful, but |
// WITHOUT ANY WARRANTY; without even the implied warranty of |
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
// General Public License for more details. |
|
// 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/partition.h |
* @brief Parallel implementation of std::partition(), |
* std::nth_element(), and std::partial_sort(). |
* This file is a GNU parallel extension to the Standard C++ Library. |
*/ |
|
// Written by Johannes Singler and Felix Putze. |
|
#ifndef _GLIBCXX_PARALLEL_PARTITION_H |
#define _GLIBCXX_PARALLEL_PARTITION_H 1 |
|
#include <parallel/basic_iterator.h> |
#include <parallel/sort.h> |
#include <parallel/random_number.h> |
#include <bits/stl_algo.h> |
#include <parallel/parallel.h> |
|
/** @brief Decide whether to declare certain variables volatile. */ |
#define _GLIBCXX_VOLATILE volatile |
|
namespace __gnu_parallel |
{ |
/** @brief Parallel implementation of std::partition. |
* @param __begin Begin iterator of input sequence to split. |
* @param __end End iterator of input sequence to split. |
* @param __pred Partition predicate, possibly including some kind |
* of pivot. |
* @param __num_threads Maximum number of threads to use for this task. |
* @return Number of elements not fulfilling the predicate. */ |
template<typename _RAIter, typename _Predicate> |
typename std::iterator_traits<_RAIter>::difference_type |
__parallel_partition(_RAIter __begin, _RAIter __end, |
_Predicate __pred, _ThreadIndex __num_threads) |
{ |
typedef std::iterator_traits<_RAIter> _TraitsType; |
typedef typename _TraitsType::value_type _ValueType; |
typedef typename _TraitsType::difference_type _DifferenceType; |
|
_DifferenceType __n = __end - __begin; |
|
_GLIBCXX_CALL(__n) |
|
const _Settings& __s = _Settings::get(); |
|
// shared |
_GLIBCXX_VOLATILE _DifferenceType __left = 0, __right = __n - 1, |
__dist = __n, |
__leftover_left, __leftover_right, |
__leftnew, __rightnew; |
|
// just 0 or 1, but int to allow atomic operations |
int* __reserved_left = 0, * __reserved_right = 0; |
|
_DifferenceType __chunk_size = __s.partition_chunk_size; |
|
//at least two chunks per thread |
if (__dist >= 2 * __num_threads * __chunk_size) |
# pragma omp parallel num_threads(__num_threads) |
{ |
# pragma omp single |
{ |
__num_threads = omp_get_num_threads(); |
__reserved_left = new int[__num_threads]; |
__reserved_right = new int[__num_threads]; |
|
if (__s.partition_chunk_share > 0.0) |
__chunk_size = std::max<_DifferenceType> |
(__s.partition_chunk_size, (double)__n |
* __s.partition_chunk_share / (double)__num_threads); |
else |
__chunk_size = __s.partition_chunk_size; |
} |
|
while (__dist >= 2 * __num_threads * __chunk_size) |
{ |
# pragma omp single |
{ |
_DifferenceType __num_chunks = __dist / __chunk_size; |
|
for (_ThreadIndex __r = 0; __r < __num_threads; ++__r) |
{ |
__reserved_left [__r] = 0; // false |
__reserved_right[__r] = 0; // false |
} |
__leftover_left = 0; |
__leftover_right = 0; |
} //implicit barrier |
|
// Private. |
_DifferenceType __thread_left, __thread_left_border, |
__thread_right, __thread_right_border; |
|
__thread_left = __left + 1; |
// Just to satisfy the condition below. |
__thread_left_border = __thread_left - 1; |
|
__thread_right = __n - 1; |
// Just to satisfy the condition below. |
__thread_right_border = __thread_right + 1; |
|
bool __iam_finished = false; |
while (!__iam_finished) |
{ |
if (__thread_left > __thread_left_border) |
{ |
_DifferenceType __former_dist = |
__fetch_and_add(&__dist, -__chunk_size); |
if (__former_dist < __chunk_size) |
{ |
__fetch_and_add(&__dist, __chunk_size); |
__iam_finished = true; |
break; |
} |
else |
{ |
__thread_left = |
__fetch_and_add(&__left, __chunk_size); |
__thread_left_border = |
__thread_left + (__chunk_size - 1); |
} |
} |
|
if (__thread_right < __thread_right_border) |
{ |
_DifferenceType __former_dist = |
__fetch_and_add(&__dist, -__chunk_size); |
if (__former_dist < __chunk_size) |
{ |
__fetch_and_add(&__dist, __chunk_size); |
__iam_finished = true; |
break; |
} |
else |
{ |
__thread_right = |
__fetch_and_add(&__right, -__chunk_size); |
__thread_right_border = |
__thread_right - (__chunk_size - 1); |
} |
} |
|
// Swap as usual. |
while (__thread_left < __thread_right) |
{ |
while (__pred(__begin[__thread_left]) |
&& __thread_left <= __thread_left_border) |
++__thread_left; |
while (!__pred(__begin[__thread_right]) |
&& __thread_right >= __thread_right_border) |
--__thread_right; |
|
if (__thread_left > __thread_left_border |
|| __thread_right < __thread_right_border) |
// Fetch new chunk(__s). |
break; |
|
std::iter_swap(__begin + __thread_left, |
__begin + __thread_right); |
++__thread_left; |
--__thread_right; |
} |
} |
|
// Now swap the leftover chunks to the right places. |
if (__thread_left <= __thread_left_border) |
# pragma omp atomic |
++__leftover_left; |
if (__thread_right >= __thread_right_border) |
# pragma omp atomic |
++__leftover_right; |
|
# pragma omp barrier |
|
_DifferenceType |
__leftold = __left, |
__leftnew = __left - __leftover_left * __chunk_size, |
__rightold = __right, |
__rightnew = __right + __leftover_right * __chunk_size; |
|
// <=> __thread_left_border + (__chunk_size - 1) >= __leftnew |
if (__thread_left <= __thread_left_border |
&& __thread_left_border >= __leftnew) |
{ |
// Chunk already in place, reserve spot. |
__reserved_left[(__left - (__thread_left_border + 1)) |
/ __chunk_size] = 1; |
} |
|
// <=> __thread_right_border - (__chunk_size - 1) <= __rightnew |
if (__thread_right >= __thread_right_border |
&& __thread_right_border <= __rightnew) |
{ |
// Chunk already in place, reserve spot. |
__reserved_right[((__thread_right_border - 1) - __right) |
/ __chunk_size] = 1; |
} |
|
# pragma omp barrier |
|
if (__thread_left <= __thread_left_border |
&& __thread_left_border < __leftnew) |
{ |
// Find spot and swap. |
_DifferenceType __swapstart = -1; |
for (int __r = 0; __r < __leftover_left; ++__r) |
if (__reserved_left[__r] == 0 |
&& __compare_and_swap(&(__reserved_left[__r]), 0, 1)) |
{ |
__swapstart = __leftold - (__r + 1) * __chunk_size; |
break; |
} |
|
#if _GLIBCXX_ASSERTIONS |
_GLIBCXX_PARALLEL_ASSERT(__swapstart != -1); |
#endif |
|
std::swap_ranges(__begin + __thread_left_border |
- (__chunk_size - 1), |
__begin + __thread_left_border + 1, |
__begin + __swapstart); |
} |
|
if (__thread_right >= __thread_right_border |
&& __thread_right_border > __rightnew) |
{ |
// Find spot and swap |
_DifferenceType __swapstart = -1; |
for (int __r = 0; __r < __leftover_right; ++__r) |
if (__reserved_right[__r] == 0 |
&& __compare_and_swap(&(__reserved_right[__r]), 0, 1)) |
{ |
__swapstart = __rightold + __r * __chunk_size + 1; |
break; |
} |
|
#if _GLIBCXX_ASSERTIONS |
_GLIBCXX_PARALLEL_ASSERT(__swapstart != -1); |
#endif |
|
std::swap_ranges(__begin + __thread_right_border, |
__begin + __thread_right_border |
+ __chunk_size, __begin + __swapstart); |
} |
#if _GLIBCXX_ASSERTIONS |
# pragma omp barrier |
|
# pragma omp single |
{ |
for (_DifferenceType __r = 0; __r < __leftover_left; ++__r) |
_GLIBCXX_PARALLEL_ASSERT(__reserved_left[__r] == 1); |
for (_DifferenceType __r = 0; __r < __leftover_right; ++__r) |
_GLIBCXX_PARALLEL_ASSERT(__reserved_right[__r] == 1); |
} |
#endif |
|
__left = __leftnew; |
__right = __rightnew; |
__dist = __right - __left + 1; |
} |
|
# pragma omp flush(__left, __right) |
} // end "recursion" //parallel |
|
_DifferenceType __final_left = __left, __final_right = __right; |
|
while (__final_left < __final_right) |
{ |
// Go right until key is geq than pivot. |
while (__pred(__begin[__final_left]) |
&& __final_left < __final_right) |
++__final_left; |
|
// Go left until key is less than pivot. |
while (!__pred(__begin[__final_right]) |
&& __final_left < __final_right) |
--__final_right; |
|
if (__final_left == __final_right) |
break; |
std::iter_swap(__begin + __final_left, __begin + __final_right); |
++__final_left; |
--__final_right; |
} |
|
// All elements on the left side are < piv, all elements on the |
// right are >= piv |
delete[] __reserved_left; |
delete[] __reserved_right; |
|
// Element "between" __final_left and __final_right might not have |
// been regarded yet |
if (__final_left < __n && !__pred(__begin[__final_left])) |
// Really swapped. |
return __final_left; |
else |
return __final_left + 1; |
} |
|
/** |
* @brief Parallel implementation of std::nth_element(). |
* @param __begin Begin iterator of input sequence. |
* @param __nth _Iterator of element that must be in position afterwards. |
* @param __end End iterator of input sequence. |
* @param __comp Comparator. |
*/ |
template<typename _RAIter, typename _Compare> |
void |
__parallel_nth_element(_RAIter __begin, _RAIter __nth, |
_RAIter __end, _Compare __comp) |
{ |
typedef std::iterator_traits<_RAIter> _TraitsType; |
typedef typename _TraitsType::value_type _ValueType; |
typedef typename _TraitsType::difference_type _DifferenceType; |
|
_GLIBCXX_CALL(__end - __begin) |
|
_RAIter __split; |
_RandomNumber __rng; |
|
const _Settings& __s = _Settings::get(); |
_DifferenceType __minimum_length = std::max<_DifferenceType>(2, |
std::max(__s.nth_element_minimal_n, __s.partition_minimal_n)); |
|
// Break if input range to small. |
while (static_cast<_SequenceIndex>(__end - __begin) >= __minimum_length) |
{ |
_DifferenceType __n = __end - __begin; |
|
_RAIter __pivot_pos = __begin + __rng(__n); |
|
// Swap __pivot_pos value to end. |
if (__pivot_pos != (__end - 1)) |
std::iter_swap(__pivot_pos, __end - 1); |
__pivot_pos = __end - 1; |
|
// _Compare must have first_value_type, second_value_type, |
// result_type |
// _Compare == |
// __gnu_parallel::_Lexicographic<S, int, |
// __gnu_parallel::_Less<S, S> > |
// __pivot_pos == std::pair<S, int>* |
__gnu_parallel::__binder2nd<_Compare, _ValueType, _ValueType, bool> |
__pred(__comp, *__pivot_pos); |
|
// Divide, leave pivot unchanged in last place. |
_RAIter __split_pos1, __split_pos2; |
__split_pos1 = __begin + __parallel_partition(__begin, __end - 1, |
__pred, |
__get_max_threads()); |
|
// Left side: < __pivot_pos; __right side: >= __pivot_pos |
|
// Swap pivot back to middle. |
if (__split_pos1 != __pivot_pos) |
std::iter_swap(__split_pos1, __pivot_pos); |
__pivot_pos = __split_pos1; |
|
// In case all elements are equal, __split_pos1 == 0 |
if ((__split_pos1 + 1 - __begin) < (__n >> 7) |
|| (__end - __split_pos1) < (__n >> 7)) |
{ |
// Very unequal split, one part smaller than one 128th |
// elements not strictly larger than the pivot. |
__gnu_parallel::__unary_negate<__gnu_parallel:: |
__binder1st<_Compare, _ValueType, |
_ValueType, bool>, _ValueType> |
__pred(__gnu_parallel::__binder1st<_Compare, _ValueType, |
_ValueType, bool>(__comp, *__pivot_pos)); |
|
// Find other end of pivot-equal range. |
__split_pos2 = __gnu_sequential::partition(__split_pos1 + 1, |
__end, __pred); |
} |
else |
// Only skip the pivot. |
__split_pos2 = __split_pos1 + 1; |
|
// Compare iterators. |
if (__split_pos2 <= __nth) |
__begin = __split_pos2; |
else if (__nth < __split_pos1) |
__end = __split_pos1; |
else |
break; |
} |
|
// Only at most _Settings::partition_minimal_n __elements __left. |
__gnu_sequential::nth_element(__begin, __nth, __end, __comp); |
} |
|
/** @brief Parallel implementation of std::partial_sort(). |
* @param __begin Begin iterator of input sequence. |
* @param __middle Sort until this position. |
* @param __end End iterator of input sequence. |
* @param __comp Comparator. */ |
template<typename _RAIter, typename _Compare> |
void |
__parallel_partial_sort(_RAIter __begin, |
_RAIter __middle, |
_RAIter __end, _Compare __comp) |
{ |
__parallel_nth_element(__begin, __middle, __end, __comp); |
std::sort(__begin, __middle, __comp); |
} |
|
} //namespace __gnu_parallel |
|
#undef _GLIBCXX_VOLATILE |
|
#endif /* _GLIBCXX_PARALLEL_PARTITION_H */ |