From 36fc59580b92ea18a02ef2e1623b96103608f774 Mon Sep 17 00:00:00 2001 From: Johannes Singler Date: Fri, 16 May 2008 07:10:26 +0000 Subject: [PATCH] parallel_mode.xml: Documented the new choices, factoring out common tags. 2008-05-16 Johannes Singler * doc/xml/manual/parallel_mode.xml: Documented the new choices, factoring out common tags. * include/parallel/multiway_merge.h: Place comparison functor at the end, to comply with established convention. (parallel_multiway_merge) Pass number of threads explicitly. Introduce new compile-time variants, make exact splitting the default. * include/parallel/tags.h: Extend exact_tag, introduce sampling_tag. * include/parallel/merge.h: (parallel_merge_advance) Adapt to changed interface. * include/parallel/multiway_mergesort.h: Likewise. From-SVN: r135411 --- libstdc++-v3/doc/xml/manual/parallel_mode.xml | 36 +- libstdc++-v3/include/parallel/merge.h | 4 +- .../include/parallel/multiway_merge.h | 509 +++++++++++------- .../include/parallel/multiway_mergesort.h | 8 +- libstdc++-v3/include/parallel/tags.h | 22 +- 5 files changed, 371 insertions(+), 208 deletions(-) diff --git a/libstdc++-v3/doc/xml/manual/parallel_mode.xml b/libstdc++-v3/doc/xml/manual/parallel_mode.xml index fb439062fea..faea5a9e7f6 100644 --- a/libstdc++-v3/doc/xml/manual/parallel_mode.xml +++ b/libstdc++-v3/doc/xml/manual/parallel_mode.xml @@ -575,24 +575,36 @@ This means that the actual parallelization strategy is chosen at run-time. (Choosing the variants at compile-time will come soon.) + +For the following algorithms in general, we have +__gnu_parallel::parallel_tag and +__gnu_parallel::default_parallel_tag, in addition to +__gnu_parallel::sequential_tag. +__gnu_parallel::default_parallel_tag chooses the default +algorithm at compiletime, as does omitting the tag. +__gnu_parallel::parallel_tag postpones the decision to runtime +(see next section). +For all tags, the number of threads desired for this call can optionally be +passed to the respective tag's constructor. + + + +The multiway_merge algorithm comes with the additional choices, +__gnu_parallel::exact_tag and +__gnu_parallel::sampling_tag. +Exact and sampling are the two available splitting strategies. + + For the sort and stable_sort algorithms, there are -several possible choices, -__gnu_parallel::parallel_tag, -__gnu_parallel::default_parallel_tag, +several additional choices, namely __gnu_parallel::multiway_mergesort_tag, __gnu_parallel::multiway_mergesort_exact_tag, __gnu_parallel::multiway_mergesort_sampling_tag, -__gnu_parallel::quicksort_tag, +__gnu_parallel::quicksort_tag, and __gnu_parallel::balanced_quicksort_tag. -Multiway mergesort comes with two splitting strategies for merging, therefore -the extra choice. If non is chosen, the default splitting strategy is selected. -__gnu_parallel::default_parallel_tag chooses the default parallel -sorting algorithm at runtime. __gnu_parallel::parallel_tag -postpones the decision to runtime (see next section). -The quicksort options cannot be used for stable_sort. -For all tags, the number of threads desired for this call can optionally be -passed to the tag's constructor. +Multiway mergesort comes with the two splitting strategies for multi-way +merging. The quicksort options cannot be used for stable_sort. diff --git a/libstdc++-v3/include/parallel/merge.h b/libstdc++-v3/include/parallel/merge.h index cabd5bd4de2..580b1479329 100644 --- a/libstdc++-v3/include/parallel/merge.h +++ b/libstdc++-v3/include/parallel/merge.h @@ -254,11 +254,11 @@ namespace __gnu_parallel RandomAccessIterator3 target_end = parallel_multiway_merge < /* stable = */ true, /* sentinels = */ false>( - seqs, seqs + 2, target, comp, + seqs, seqs + 2, target, multiway_merge_exact_splitting < /* stable = */ true, iterator_pair*, Comparator, difference_type1>, - max_length); + max_length, comp, omp_get_max_threads()); return target_end; } diff --git a/libstdc++-v3/include/parallel/multiway_merge.h b/libstdc++-v3/include/parallel/multiway_merge.h index 37e99cdeb6a..3c75c70f3c4 100644 --- a/libstdc++-v3/include/parallel/multiway_merge.h +++ b/libstdc++-v3/include/parallel/multiway_merge.h @@ -297,7 +297,7 @@ template class iterator, RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, - Comparator comp, _DifferenceTp length) + _DifferenceTp length, Comparator comp) { _GLIBCXX_CALL(length); @@ -416,7 +416,7 @@ template class iterator, multiway_merge_4_variant(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, - Comparator comp, _DifferenceTp length) + _DifferenceTp length, Comparator comp) { _GLIBCXX_CALL(length); typedef _DifferenceTp difference_type; @@ -540,8 +540,7 @@ template::value_type::first_type>::value_type& sentinel, - Comparator comp, - _DifferenceTp length) + _DifferenceTp length, + Comparator comp) { _GLIBCXX_CALL(length) typedef _DifferenceTp difference_type; @@ -716,8 +715,8 @@ template< const typename std::iterator_traits::value_type::first_type>::value_type& sentinel, - Comparator comp, - _DifferenceTp length) + _DifferenceTp length, + Comparator comp) { _GLIBCXX_CALL(length) @@ -740,7 +739,7 @@ template< target_end = multiway_merge_loser_tree_unguarded - (seqs_begin, seqs_end, target, sentinel, comp, length); + (seqs_begin, seqs_end, target, sentinel, length, comp); #if _GLIBCXX_ASSERTIONS _GLIBCXX_PARALLEL_ASSERT(target_end == target + length); @@ -808,10 +807,10 @@ struct multiway_merge_3_variant_sentinel_switch RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, - Comparator comp, _DifferenceTp length) + _DifferenceTp length, Comparator comp) { return multiway_merge_3_variant( - seqs_begin, seqs_end, target, comp, length); + seqs_begin, seqs_end, target, length, comp); } }; @@ -833,10 +832,10 @@ struct multiway_merge_3_variant_sentinel_switch RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, - Comparator comp, _DifferenceTp length) + _DifferenceTp length, Comparator comp) { return multiway_merge_3_variant( - seqs_begin, seqs_end, target, comp, length); + seqs_begin, seqs_end, target, length, comp); } }; @@ -857,10 +856,10 @@ struct multiway_merge_4_variant_sentinel_switch RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, - Comparator comp, _DifferenceTp length) + _DifferenceTp length, Comparator comp) { return multiway_merge_4_variant( - seqs_begin, seqs_end, target, comp, length); + seqs_begin, seqs_end, target, length, comp); } }; @@ -882,10 +881,10 @@ struct multiway_merge_4_variant_sentinel_switch RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, - Comparator comp, _DifferenceTp length) + _DifferenceTp length, Comparator comp) { return multiway_merge_4_variant( - seqs_begin, seqs_end, target, comp, length); + seqs_begin, seqs_end, target, length, comp); } }; @@ -908,7 +907,7 @@ struct multiway_merge_k_variant_sentinel_switch const typename std::iterator_traits::value_type::first_type>::value_type& sentinel, - Comparator comp, _DifferenceTp length) + _DifferenceTp length, Comparator comp) { typedef typename std::iterator_traits ::value_type::first_type @@ -921,7 +920,7 @@ struct multiway_merge_k_variant_sentinel_switch loser_tree_traits::use_pointer , LoserTreePointerUnguarded , LoserTreeUnguarded - >::__type>(seqs_begin, seqs_end, target, sentinel, comp, length); + >::__type>(seqs_begin, seqs_end, target, sentinel, length, comp); } }; @@ -945,7 +944,7 @@ struct multiway_merge_k_variant_sentinel_switch const typename std::iterator_traits::value_type::first_type>::value_type& sentinel, - Comparator comp, _DifferenceTp length) + _DifferenceTp length, Comparator comp) { typedef typename std::iterator_traits ::value_type::first_type @@ -958,7 +957,7 @@ struct multiway_merge_k_variant_sentinel_switch loser_tree_traits::use_pointer , LoserTreePointer , LoserTree - >::__type >(seqs_begin, seqs_end, target, comp, length); + >::__type >(seqs_begin, seqs_end, target, length, comp); } }; @@ -990,7 +989,7 @@ template< const typename std::iterator_traits::value_type::first_type>::value_type& sentinel, - Comparator comp, _DifferenceTp length) + _DifferenceTp length, Comparator comp) { _GLIBCXX_CALL(length) @@ -1043,7 +1042,7 @@ template< , RandomAccessIteratorIterator , RandomAccessIterator3 , _DifferenceTp - , Comparator>()(seqs_begin, seqs_end, target, comp, length); + , Comparator>()(seqs_begin, seqs_end, target, length, comp); break; case 4: return_target = multiway_merge_4_variant_sentinel_switch< @@ -1051,7 +1050,7 @@ template< , RandomAccessIteratorIterator , RandomAccessIterator3 , _DifferenceTp - , Comparator>()(seqs_begin, seqs_end, target, comp, length); + , Comparator>()(seqs_begin, seqs_end, target, length, comp); break; default: return_target = multiway_merge_k_variant_sentinel_switch< @@ -1060,8 +1059,7 @@ template< , RandomAccessIteratorIterator , RandomAccessIterator3 , _DifferenceTp - , Comparator>() - (seqs_begin, seqs_end, target, sentinel, comp, length); + , Comparator>()(seqs_begin, seqs_end, target, sentinel, length, comp); break; } #if _GLIBCXX_ASSERTIONS @@ -1108,8 +1106,7 @@ template< void multiway_merge_sampling_splitting( RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, - Comparator comp, difference_type length, - difference_type total_length, + difference_type length, difference_type total_length, Comparator comp, std::vector > *pieces) { typedef typename std::iterator_traits @@ -1190,9 +1187,7 @@ template< void multiway_merge_exact_splitting( RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, - Comparator comp, - difference_type length, - difference_type total_length, + difference_type length, difference_type total_length, Comparator comp, std::vector > *pieces) { typedef typename std::iterator_traits @@ -1297,9 +1292,10 @@ template< parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, - Comparator comp, Splitter splitter, - _DifferenceTp length) + _DifferenceTp length, + Comparator comp, + thread_index_t num_threads) { #if _GLIBCXX_ASSERTIONS _GLIBCXX_PARALLEL_ASSERT(seqs_end - seqs_begin > 1); @@ -1347,8 +1343,8 @@ template< std::vector >* pieces; - thread_index_t num_threads = static_cast - (std::min(get_max_threads(), total_length)); + num_threads = static_cast + (std::min(num_threads, total_length)); # pragma omp parallel num_threads (num_threads) { @@ -1365,8 +1361,8 @@ template< __gnu_parallel::_Settings::get().merge_oversampling * num_threads; - splitter(ne_seqs, ne_seqs + k, comp, length, total_length, - pieces); + splitter(ne_seqs, ne_seqs + k, length, total_length, + comp, pieces); } //single thread_index_t iam = omp_get_thread_num(); @@ -1389,7 +1385,7 @@ template< if(length > target_position) sequential_multiway_merge( chunks, chunks + k, target + target_position, - *(seqs_begin->second), comp, length - target_position); + *(seqs_begin->second), length - target_position, comp); delete[] chunks; } // parallel @@ -1481,6 +1477,7 @@ template< * * @return end iterator of output sequence */ +// multiway_merge // public interface template< typename RandomAccessIteratorPairIterator @@ -1491,49 +1488,7 @@ RandomAccessIteratorOut multiway_merge(RandomAccessIteratorPairIterator seqs_begin , RandomAccessIteratorPairIterator seqs_end , RandomAccessIteratorOut target - , Comparator comp, _DifferenceTp length) -{ - typedef _DifferenceTp difference_type; - _GLIBCXX_CALL(seqs_end - seqs_begin) - - // catch special case: no sequences - if (seqs_begin == seqs_end) - return target; - - // Execute merge; maybe parallel, depending on the number of merged - // elements and the number of sequences and global thresholds in - // Settings. - if ((seqs_end - seqs_begin > 1) && - _GLIBCXX_PARALLEL_CONDITION( - ((seqs_end - seqs_begin) >= - __gnu_parallel::_Settings::get().multiway_merge_minimal_k) - && ((sequence_index_t)length >= - __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) - return parallel_multiway_merge - - (seqs_begin, seqs_end, target, comp, - multiway_merge_sampling_splitting - ::value_type*, Comparator, _DifferenceTp>, - static_cast(length)); - else - return sequential_multiway_merge - ( - seqs_begin, seqs_end, - target, *(seqs_begin->second), comp, length); -} - -// public interface -template< - typename RandomAccessIteratorPairIterator - , typename RandomAccessIteratorOut - , typename _DifferenceTp - , typename Comparator> -RandomAccessIteratorOut -multiway_merge(RandomAccessIteratorPairIterator seqs_begin - , RandomAccessIteratorPairIterator seqs_end - , RandomAccessIteratorOut target - , Comparator comp, _DifferenceTp length + , _DifferenceTp length, Comparator comp , __gnu_parallel::sequential_tag) { typedef _DifferenceTp difference_type; @@ -1546,10 +1501,10 @@ multiway_merge(RandomAccessIteratorPairIterator seqs_begin // Execute multiway merge *sequentially*. return sequential_multiway_merge - (seqs_begin, seqs_end, target, *(seqs_begin->second), comp, length); + (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp); } -//public interface +// public interface template< typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut @@ -1559,8 +1514,8 @@ RandomAccessIteratorOut multiway_merge(RandomAccessIteratorPairIterator seqs_begin , RandomAccessIteratorPairIterator seqs_end , RandomAccessIteratorOut target - , Comparator comp, _DifferenceTp length - , __gnu_parallel::exact_tag) + , _DifferenceTp length, Comparator comp + , __gnu_parallel::exact_tag tag) { typedef _DifferenceTp difference_type; _GLIBCXX_CALL(seqs_end - seqs_begin) @@ -1580,17 +1535,15 @@ multiway_merge(RandomAccessIteratorPairIterator seqs_begin __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) return parallel_multiway_merge ( - seqs_begin, seqs_end, - target, comp, + seqs_begin, seqs_end, target, multiway_merge_exact_splitting ::value_type*, Comparator, _DifferenceTp>, - static_cast(length)); + static_cast(length), comp, tag.get_num_threads()); else return sequential_multiway_merge ( - seqs_begin, seqs_end, - target, *(seqs_begin->second), comp, length); + seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp); } // public interface @@ -1600,10 +1553,11 @@ template< , typename _DifferenceTp , typename Comparator> RandomAccessIteratorOut -stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin +multiway_merge(RandomAccessIteratorPairIterator seqs_begin , RandomAccessIteratorPairIterator seqs_end , RandomAccessIteratorOut target - , Comparator comp, _DifferenceTp length) + , _DifferenceTp length, Comparator comp + , __gnu_parallel::sampling_tag tag) { typedef _DifferenceTp difference_type; _GLIBCXX_CALL(seqs_end - seqs_begin) @@ -1618,24 +1572,59 @@ stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin if ((seqs_end - seqs_begin > 1) && _GLIBCXX_PARALLEL_CONDITION( ((seqs_end - seqs_begin) >= - __gnu_parallel::_Settings::get().multiway_merge_minimal_k) + __gnu_parallel::_Settings::get().multiway_merge_minimal_k) && ((sequence_index_t)length >= __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) return parallel_multiway_merge - ( + ( seqs_begin, seqs_end, - target, comp, - multiway_merge_sampling_splitting ::value_type*, Comparator, _DifferenceTp>, - static_cast(length)); + static_cast(length), comp, tag.get_num_threads()); else return sequential_multiway_merge - ( + ( seqs_begin, seqs_end, - target, *(seqs_begin->second), comp, length); + target, *(seqs_begin->second), length, comp); } +// public interface +template< + typename RandomAccessIteratorPairIterator + , typename RandomAccessIteratorOut + , typename _DifferenceTp + , typename Comparator> +RandomAccessIteratorOut +multiway_merge(RandomAccessIteratorPairIterator seqs_begin + , RandomAccessIteratorPairIterator seqs_end + , RandomAccessIteratorOut target + , _DifferenceTp length, Comparator comp + , parallel_tag tag = parallel_tag(0)) +{ + return multiway_merge(seqs_begin, seqs_end, target, length, comp, + exact_tag(tag.get_num_threads())); +} + +// public interface +template< + typename RandomAccessIteratorPairIterator + , typename RandomAccessIteratorOut + , typename _DifferenceTp + , typename Comparator> +RandomAccessIteratorOut +multiway_merge(RandomAccessIteratorPairIterator seqs_begin + , RandomAccessIteratorPairIterator seqs_end + , RandomAccessIteratorOut target + , _DifferenceTp length, Comparator comp + , default_parallel_tag tag) +{ + return multiway_merge(seqs_begin, seqs_end, target, length, comp, + exact_tag(tag.get_num_threads())); +} + +// stable_multiway_merge // public interface template< typename RandomAccessIteratorPairIterator @@ -1646,7 +1635,7 @@ RandomAccessIteratorOut stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin , RandomAccessIteratorPairIterator seqs_end , RandomAccessIteratorOut target - , Comparator comp, _DifferenceTp length + , _DifferenceTp length, Comparator comp , __gnu_parallel::sequential_tag) { typedef _DifferenceTp difference_type; @@ -1659,7 +1648,7 @@ stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin // Execute multiway merge *sequentially*. return sequential_multiway_merge - (seqs_begin, seqs_end, target, *(seqs_begin->second), comp, length); + (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp); } // public interface @@ -1672,8 +1661,8 @@ RandomAccessIteratorOut stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin , RandomAccessIteratorPairIterator seqs_end , RandomAccessIteratorOut target - , Comparator comp, _DifferenceTp length - , __gnu_parallel::exact_tag) + , _DifferenceTp length, Comparator comp + , __gnu_parallel::exact_tag tag) { typedef _DifferenceTp difference_type; _GLIBCXX_CALL(seqs_end - seqs_begin) @@ -1694,17 +1683,95 @@ stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin return parallel_multiway_merge ( seqs_begin, seqs_end, - target, comp, - multiway_merge_exact_splitting - - ::value_type*, Comparator, _DifferenceTp>, - static_cast(length)); + target, + multiway_merge_exact_splitting + ::value_type*, Comparator, _DifferenceTp>, + static_cast(length), comp, tag.get_num_threads()); else return sequential_multiway_merge( seqs_begin, seqs_end, - target, *(seqs_begin->second), comp, length); + target, *(seqs_begin->second), length, comp); +} + +// public interface +template< + typename RandomAccessIteratorPairIterator + , typename RandomAccessIteratorOut + , typename _DifferenceTp + , typename Comparator> +RandomAccessIteratorOut +stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin + , RandomAccessIteratorPairIterator seqs_end + , RandomAccessIteratorOut target + , _DifferenceTp length, Comparator comp + , sampling_tag tag) +{ + typedef _DifferenceTp difference_type; + _GLIBCXX_CALL(seqs_end - seqs_begin) + + // catch special case: no sequences + if (seqs_begin == seqs_end) + return target; + + // Execute merge; maybe parallel, depending on the number of merged + // elements and the number of sequences and global thresholds in + // Settings. + if ((seqs_end - seqs_begin > 1) && + _GLIBCXX_PARALLEL_CONDITION( + ((seqs_end - seqs_begin) >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_k) + && ((sequence_index_t)length >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) + return parallel_multiway_merge + ( + seqs_begin, seqs_end, + target, + multiway_merge_sampling_splitting + ::value_type*, Comparator, _DifferenceTp>, + static_cast(length), comp, tag.get_num_threads()); + else + return sequential_multiway_merge + ( + seqs_begin, seqs_end, + target, *(seqs_begin->second), length, comp); +} + + +// public interface +template< + typename RandomAccessIteratorPairIterator + , typename RandomAccessIteratorOut + , typename _DifferenceTp + , typename Comparator> +RandomAccessIteratorOut +stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin + , RandomAccessIteratorPairIterator seqs_end + , RandomAccessIteratorOut target + , _DifferenceTp length, Comparator comp + , parallel_tag tag = parallel_tag(0)) +{ + return stable_multiway_merge(seqs_begin, seqs_end, target, length, comp, + exact_tag(tag.get_num_threads())); +} + +// public interface +template< + typename RandomAccessIteratorPairIterator + , typename RandomAccessIteratorOut + , typename _DifferenceTp + , typename Comparator> +RandomAccessIteratorOut +stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin + , RandomAccessIteratorPairIterator seqs_end + , RandomAccessIteratorOut target + , _DifferenceTp length, Comparator comp + , default_parallel_tag tag) +{ + return stable_multiway_merge(seqs_begin, seqs_end, target, length, comp, + exact_tag(tag.get_num_threads())); } /** @@ -1782,6 +1849,7 @@ stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin * * @return end iterator of output sequence */ +// multiway_merge_sentinels // public interface template< typename RandomAccessIteratorPairIterator @@ -1792,50 +1860,7 @@ RandomAccessIteratorOut multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin , RandomAccessIteratorPairIterator seqs_end , RandomAccessIteratorOut target - , Comparator comp, _DifferenceTp length) -{ - typedef _DifferenceTp difference_type; - _GLIBCXX_CALL(seqs_end - seqs_begin) - - // catch special case: no sequences - if (seqs_begin == seqs_end) - return target; - - // Execute merge; maybe parallel, depending on the number of merged - // elements and the number of sequences and global thresholds in - // Settings. - if ((seqs_end - seqs_begin > 1) && - _GLIBCXX_PARALLEL_CONDITION( - ((seqs_end - seqs_begin) >= - __gnu_parallel::_Settings::get().multiway_merge_minimal_k) - && ((sequence_index_t)length >= - __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) - return parallel_multiway_merge - - (seqs_begin, seqs_end, target, comp, - multiway_merge_sampling_splitting - - ::value_type*, Comparator, _DifferenceTp>, - static_cast(length)); - else - return sequential_multiway_merge - ( - seqs_begin, seqs_end, - target, *(seqs_begin->second), comp, length); -} - -//public interface -template< - typename RandomAccessIteratorPairIterator - , typename RandomAccessIteratorOut - , typename _DifferenceTp - , typename Comparator> -RandomAccessIteratorOut -multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin - , RandomAccessIteratorPairIterator seqs_end - , RandomAccessIteratorOut target - , Comparator comp, _DifferenceTp length + , _DifferenceTp length, Comparator comp , __gnu_parallel::sequential_tag) { typedef _DifferenceTp difference_type; @@ -1848,7 +1873,8 @@ multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin // Execute multiway merge *sequentially*. return sequential_multiway_merge - (seqs_begin, seqs_end, target, *(seqs_begin->second), comp, length); + (seqs_begin, seqs_end, + target, *(seqs_begin->second), length, comp); } // public interface @@ -1861,8 +1887,8 @@ RandomAccessIteratorOut multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin , RandomAccessIteratorPairIterator seqs_end , RandomAccessIteratorOut target - , Comparator comp, _DifferenceTp length - , __gnu_parallel::exact_tag) + , _DifferenceTp length, Comparator comp + , __gnu_parallel::exact_tag tag) { typedef _DifferenceTp difference_type; _GLIBCXX_CALL(seqs_end - seqs_begin) @@ -1883,17 +1909,16 @@ multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin return parallel_multiway_merge ( seqs_begin, seqs_end, - target, comp, - multiway_merge_exact_splitting - - ::value_type*, Comparator, _DifferenceTp>, - static_cast(length)); + target, + multiway_merge_exact_splitting + ::value_type*, Comparator, _DifferenceTp>, + static_cast(length), comp, tag.get_num_threads()); else return sequential_multiway_merge ( seqs_begin, seqs_end, - target, *(seqs_begin->second), comp, length); + target, *(seqs_begin->second), length, comp); } // public interface @@ -1903,10 +1928,11 @@ template< , typename _DifferenceTp , typename Comparator> RandomAccessIteratorOut -stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin +multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin , RandomAccessIteratorPairIterator seqs_end , RandomAccessIteratorOut target - , Comparator comp, _DifferenceTp length) + , _DifferenceTp length, Comparator comp + , sampling_tag tag) { typedef _DifferenceTp difference_type; _GLIBCXX_CALL(seqs_end - seqs_begin) @@ -1925,21 +1951,54 @@ stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin && ((sequence_index_t)length >= __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) return parallel_multiway_merge - ( - seqs_begin, seqs_end, - target, comp, - multiway_merge_sampling_splitting - - ::value_type*, Comparator, _DifferenceTp>, - static_cast(length)); + + (seqs_begin, seqs_end, target, + multiway_merge_sampling_splitting + ::value_type*, Comparator, _DifferenceTp>, + static_cast(length), comp, tag.get_num_threads()); else return sequential_multiway_merge - ( + ( seqs_begin, seqs_end, - target, *(seqs_begin->second), comp, length); + target, *(seqs_begin->second), length, comp); +} + +// public interface +template< + typename RandomAccessIteratorPairIterator + , typename RandomAccessIteratorOut + , typename _DifferenceTp + , typename Comparator> +RandomAccessIteratorOut +multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin + , RandomAccessIteratorPairIterator seqs_end + , RandomAccessIteratorOut target + , _DifferenceTp length, Comparator comp + , parallel_tag tag = parallel_tag(0)) +{ + return multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp, + exact_tag(tag.get_num_threads())); +} + +// public interface +template< + typename RandomAccessIteratorPairIterator + , typename RandomAccessIteratorOut + , typename _DifferenceTp + , typename Comparator> +RandomAccessIteratorOut +multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin + , RandomAccessIteratorPairIterator seqs_end + , RandomAccessIteratorOut target + , _DifferenceTp length, Comparator comp + , default_parallel_tag tag) +{ + return multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp, + exact_tag(tag.get_num_threads())); } +// stable_multiway_merge_sentinels // public interface template< typename RandomAccessIteratorPairIterator @@ -1950,7 +2009,7 @@ RandomAccessIteratorOut stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin , RandomAccessIteratorPairIterator seqs_end , RandomAccessIteratorOut target - , Comparator comp, _DifferenceTp length + , _DifferenceTp length, Comparator comp , __gnu_parallel::sequential_tag) { typedef _DifferenceTp difference_type; @@ -1963,7 +2022,7 @@ stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin // Execute multiway merge *sequentially*. return sequential_multiway_merge - (seqs_begin, seqs_end, target, *(seqs_begin->second), comp, length); + (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp); } // public interface @@ -1976,8 +2035,8 @@ RandomAccessIteratorOut stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin , RandomAccessIteratorPairIterator seqs_end , RandomAccessIteratorOut target - , Comparator comp, _DifferenceTp length - , __gnu_parallel::exact_tag) + , _DifferenceTp length, Comparator comp + , __gnu_parallel::exact_tag tag) { typedef _DifferenceTp difference_type; _GLIBCXX_CALL(seqs_end - seqs_begin) @@ -1998,17 +2057,93 @@ stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin return parallel_multiway_merge ( seqs_begin, seqs_end, - target, comp, - multiway_merge_exact_splitting - - ::value_type*, Comparator, _DifferenceTp>, - static_cast(length)); + target, + multiway_merge_exact_splitting + ::value_type*, Comparator, _DifferenceTp>, + static_cast(length), comp, tag.get_num_threads()); else return sequential_multiway_merge + ( + seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp); +} + +// public interface +template< + typename RandomAccessIteratorPairIterator + , typename RandomAccessIteratorOut + , typename _DifferenceTp + , typename Comparator> +RandomAccessIteratorOut +stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin + , RandomAccessIteratorPairIterator seqs_end + , RandomAccessIteratorOut target + , _DifferenceTp length, Comparator comp + , sampling_tag tag) +{ + typedef _DifferenceTp difference_type; + _GLIBCXX_CALL(seqs_end - seqs_begin) + + // catch special case: no sequences + if (seqs_begin == seqs_end) + return target; + + // Execute merge; maybe parallel, depending on the number of merged + // elements and the number of sequences and global thresholds in + // Settings. + if ((seqs_end - seqs_begin > 1) && + _GLIBCXX_PARALLEL_CONDITION( + ((seqs_end - seqs_begin) >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_k) + && ((sequence_index_t)length >= + __gnu_parallel::_Settings::get().multiway_merge_minimal_n))) + return parallel_multiway_merge ( seqs_begin, seqs_end, - target, *(seqs_begin->second), comp, length); + target, + multiway_merge_sampling_splitting + ::value_type*, Comparator, _DifferenceTp>, + static_cast(length), comp, tag.get_num_threads()); + else + return sequential_multiway_merge + ( + seqs_begin, seqs_end, + target, *(seqs_begin->second), length, comp); +} + +// public interface +template< + typename RandomAccessIteratorPairIterator + , typename RandomAccessIteratorOut + , typename _DifferenceTp + , typename Comparator> +RandomAccessIteratorOut +stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin + , RandomAccessIteratorPairIterator seqs_end + , RandomAccessIteratorOut target + , _DifferenceTp length, Comparator comp + , parallel_tag tag = parallel_tag(0)) +{ + return stable_multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp, + exact_tag(tag.get_num_threads())); +} + +// public interface +template< + typename RandomAccessIteratorPairIterator + , typename RandomAccessIteratorOut + , typename _DifferenceTp + , typename Comparator> +RandomAccessIteratorOut +stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin + , RandomAccessIteratorPairIterator seqs_end + , RandomAccessIteratorOut target + , _DifferenceTp length, Comparator comp + , default_parallel_tag tag) +{ + return stable_multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp, + exact_tag(tag.get_num_threads())); } }; // namespace __gnu_parallel diff --git a/libstdc++-v3/include/parallel/multiway_mergesort.h b/libstdc++-v3/include/parallel/multiway_mergesort.h index 3791a144d53..9d9733ad05f 100644 --- a/libstdc++-v3/include/parallel/multiway_mergesort.h +++ b/libstdc++-v3/include/parallel/multiway_mergesort.h @@ -289,8 +289,8 @@ template