This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[PATCH][libstdc++-v3 parallel mode] Fix partition and improve nth_element
- From: Johannes Singler <singler at kit dot edu>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>, gcc-patches at gcc dot gnu dot org
- Date: Thu, 19 Nov 2009 16:05:31 +0100
- Subject: [PATCH][libstdc++-v3 parallel mode] Fix partition and improve nth_element
Tested x86_64-unknown-linux-gnu: No regressions.
Please approve for mainline and gcc-4_4-branch.
2009-11-20 Johannes Singler <singler@kit.edu>
* include/parallel/partition.h (parallel_partition): Correctly
initialize chunk size.
(parallel_nth_element): Respect nth_element_minimal_n. Use
sequential nth_element as base case instead of sort.
Johannes
Index: include/parallel/partition.h
===================================================================
--- include/parallel/partition.h (revision 154250)
+++ include/parallel/partition.h (working copy)
@@ -72,7 +72,7 @@
bool* reserved_left = NULL, * reserved_right = NULL;
- difference_type chunk_size;
+ difference_type chunk_size = __s.partition_chunk_size;
omp_lock_t result_lock;
omp_init_lock(&result_lock);
@@ -339,15 +339,16 @@
RandomAccessIterator split;
random_number rng;
- difference_type minimum_length =
- std::max<difference_type>(2, _Settings::get().partition_minimal_n);
+ const _Settings& __s = _Settings::get();
+ difference_type minimum_length = std::max<difference_type>(2,
+ std::max(__s.nth_element_minimal_n, __s.partition_minimal_n));
// Break if input range to small.
while (static_cast<sequence_index_t>(end - begin) >= minimum_length)
{
difference_type n = end - begin;
- RandomAccessIterator pivot_pos = begin + rng(n);
+ RandomAccessIterator pivot_pos = begin + rng(n);
// Swap pivot_pos value to end.
if (pivot_pos != (end - 1))
@@ -404,7 +405,7 @@
}
// Only at most _Settings::partition_minimal_n elements left.
- __gnu_sequential::sort(begin, end, comp);
+ __gnu_sequential::nth_element(begin, nth, end, comp);
}
/** @brief Parallel implementation of std::partial_sort().
Index: partition.h
===================================================================
--- partition.h (revision 154060)
+++ partition.h (working copy)
@@ -73,7 +73,7 @@
bool* __reserved_left = NULL, * __reserved_right = NULL;
- _DifferenceType __chunk_size;
+ _DifferenceType __chunk_size = __s.partition_chunk_size;
omp_lock_t __result_lock;
omp_init_lock(&__result_lock);
@@ -345,15 +345,16 @@
_RAIter __split;
_RandomNumber __rng;
- _DifferenceType __minimum_length =
- std::max<_DifferenceType>(2, _Settings::get().partition_minimal_n);
+ 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);
+ _RAIter __pivot_pos = __begin + __rng(__n);
// Swap __pivot_pos value to end.
if (__pivot_pos != (__end - 1))
@@ -412,7 +413,7 @@
}
// Only at most _Settings::partition_minimal_n __elements __left.
- __gnu_sequential::sort(__begin, __end, __comp);
+ __gnu_sequential::nth_element(__begin, __nth, __end, __comp);
}
/** @brief Parallel implementation of std::partial_sort().