This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[PATCH][libstdc++-v3 parallel mode] Compile-time parallelism variant choice for multi-way merge
- From: Johannes Singler <singler at ira dot uka dot de>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>, gcc-patches at gcc dot gnu dot org
- Date: Thu, 15 May 2008 15:04:14 +0200
- Subject: [PATCH][libstdc++-v3 parallel mode] Compile-time parallelism variant choice for multi-way merge
This patch enables the compile-time choice of the parallelism variant,
for multi-way merging, this time, i. e. follows up onto the work on
sorting, so the arguments are pretty much the same.
This can reduce compilation time and object code size significantly.
Also, the user can propose the number of threads to use for a specific
call, without having to set it globally via omp_set_num_threads(). This
is important for the upcoming OpenMP-in-pthread nesting. The algorithms
still work correct even if not enough threads are alloted by the OpenMP
runtime. The default behavior is unchanged, conforming to OpenMP
conventions concerning the number of threads.
Tested x86_64-unknown-linux-gnu: No regressions.
Please approve for mainline.
2008-05-15 Johannes Singler <singler@ira.uka.de>
* 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.
Johannes
Index: doc/xml/manual/parallel_mode.xml
===================================================================
--- doc/xml/manual/parallel_mode.xml (revision 135328)
+++ doc/xml/manual/parallel_mode.xml (working copy)
@@ -576,23 +576,35 @@
</para>
<para>
+For the following algorithms in general, we have
+<code>__gnu_parallel::parallel_tag</code> and
+<code>__gnu_parallel::default_parallel_tag</code>, in addition to
+<code>__gnu_parallel::sequential_tag</code>.
+<code>__gnu_parallel::default_parallel_tag</code> chooses the default
+algorithm at compiletime, as does omitting the tag.
+<code>__gnu_parallel::parallel_tag</code> 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.
+</para>
+
+<para>
+The <code>multiway_merge</code> algorithm comes with the additional choices,
+<code>__gnu_parallel::exact_tag</code> and
+<code>__gnu_parallel::sampling_tag</code>.
+Exact and sampling are the two available splitting strategies.
+</para>
+
+<para>
For the <code>sort</code> and <code>stable_sort</code> algorithms, there are
-several possible choices,
-<code>__gnu_parallel::parallel_tag</code>,
-<code>__gnu_parallel::default_parallel_tag</code>,
+several additional choices, namely
<code>__gnu_parallel::multiway_mergesort_tag</code>,
<code>__gnu_parallel::multiway_mergesort_exact_tag</code>,
<code>__gnu_parallel::multiway_mergesort_sampling_tag</code>,
-<code>__gnu_parallel::quicksort_tag</code>,
+<code>__gnu_parallel::quicksort_tag</code>, and
<code>__gnu_parallel::balanced_quicksort_tag</code>.
-Multiway mergesort comes with two splitting strategies for merging, therefore
-the extra choice. If non is chosen, the default splitting strategy is selected.
-<code>__gnu_parallel::default_parallel_tag</code> chooses the default parallel
-sorting algorithm at runtime. <code>__gnu_parallel::parallel_tag</code>
-postpones the decision to runtime (see next section).
-The quicksort options cannot be used for <code>stable_sort</code>.
-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 <code>stable_sort</code>.
</para>
</sect3>
Index: include/parallel/multiway_merge.h
===================================================================
--- include/parallel/multiway_merge.h (revision 135328)
+++ include/parallel/multiway_merge.h (working copy)
@@ -297,7 +297,7 @@
RandomAccessIteratorIterator seqs_begin,
RandomAccessIteratorIterator seqs_end,
RandomAccessIterator3 target,
- Comparator comp, _DifferenceTp length)
+ _DifferenceTp length, Comparator comp)
{
_GLIBCXX_CALL(length);
@@ -416,7 +416,7 @@
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 @@
multiway_merge_loser_tree(RandomAccessIteratorIterator seqs_begin,
RandomAccessIteratorIterator seqs_end,
RandomAccessIterator3 target,
- Comparator comp,
- _DifferenceTp length)
+ _DifferenceTp length, Comparator comp)
{
_GLIBCXX_CALL(length)
@@ -626,8 +625,8 @@
const typename std::iterator_traits<typename std::iterator_traits<
RandomAccessIteratorIterator>::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 @@
const typename std::iterator_traits<typename std::iterator_traits<
RandomAccessIteratorIterator>::value_type::first_type>::value_type&
sentinel,
- Comparator comp,
- _DifferenceTp length)
+ _DifferenceTp length,
+ Comparator comp)
{
_GLIBCXX_CALL(length)
@@ -740,7 +739,7 @@
target_end = multiway_merge_loser_tree_unguarded
<UnguardedLoserTree>
- (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 @@
RandomAccessIteratorIterator seqs_begin,
RandomAccessIteratorIterator seqs_end,
RandomAccessIterator3 target,
- Comparator comp, _DifferenceTp length)
+ _DifferenceTp length, Comparator comp)
{
return multiway_merge_3_variant<guarded_iterator>(
- seqs_begin, seqs_end, target, comp, length);
+ seqs_begin, seqs_end, target, length, comp);
}
};
@@ -833,10 +832,10 @@
RandomAccessIteratorIterator seqs_begin,
RandomAccessIteratorIterator seqs_end,
RandomAccessIterator3 target,
- Comparator comp, _DifferenceTp length)
+ _DifferenceTp length, Comparator comp)
{
return multiway_merge_3_variant<unguarded_iterator>(
- seqs_begin, seqs_end, target, comp, length);
+ seqs_begin, seqs_end, target, length, comp);
}
};
@@ -857,10 +856,10 @@
RandomAccessIteratorIterator seqs_begin,
RandomAccessIteratorIterator seqs_end,
RandomAccessIterator3 target,
- Comparator comp, _DifferenceTp length)
+ _DifferenceTp length, Comparator comp)
{
return multiway_merge_4_variant<guarded_iterator>(
- seqs_begin, seqs_end, target, comp, length);
+ seqs_begin, seqs_end, target, length, comp);
}
};
@@ -882,10 +881,10 @@
RandomAccessIteratorIterator seqs_begin,
RandomAccessIteratorIterator seqs_end,
RandomAccessIterator3 target,
- Comparator comp, _DifferenceTp length)
+ _DifferenceTp length, Comparator comp)
{
return multiway_merge_4_variant<unguarded_iterator>(
- seqs_begin, seqs_end, target, comp, length);
+ seqs_begin, seqs_end, target, length, comp);
}
};
@@ -908,7 +907,7 @@
const typename std::iterator_traits<typename std::iterator_traits<
RandomAccessIteratorIterator>::value_type::first_type>::value_type&
sentinel,
- Comparator comp, _DifferenceTp length)
+ _DifferenceTp length, Comparator comp)
{
typedef typename std::iterator_traits<RandomAccessIteratorIterator>
::value_type::first_type
@@ -921,7 +920,7 @@
loser_tree_traits<value_type>::use_pointer
, LoserTreePointerUnguarded<stable, value_type, Comparator>
, LoserTreeUnguarded<stable, value_type, Comparator>
- >::__type>(seqs_begin, seqs_end, target, sentinel, comp, length);
+ >::__type>(seqs_begin, seqs_end, target, sentinel, length, comp);
}
};
@@ -945,7 +944,7 @@
const typename std::iterator_traits<typename std::iterator_traits<
RandomAccessIteratorIterator>::value_type::first_type>::value_type&
sentinel,
- Comparator comp, _DifferenceTp length)
+ _DifferenceTp length, Comparator comp)
{
typedef typename std::iterator_traits<RandomAccessIteratorIterator>
::value_type::first_type
@@ -958,7 +957,7 @@
loser_tree_traits<value_type>::use_pointer
, LoserTreePointer<stable, value_type, Comparator>
, LoserTree<stable, value_type, Comparator>
- >::__type >(seqs_begin, seqs_end, target, comp, length);
+ >::__type >(seqs_begin, seqs_end, target, length, comp);
}
};
@@ -990,7 +989,7 @@
const typename std::iterator_traits<typename std::iterator_traits<
RandomAccessIteratorIterator>::value_type::first_type>::value_type&
sentinel,
- Comparator comp, _DifferenceTp length)
+ _DifferenceTp length, Comparator comp)
{
_GLIBCXX_CALL(length)
@@ -1043,7 +1042,7 @@
, 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 @@
, 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 @@
, 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 @@
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<std::pair<difference_type, difference_type> > *pieces)
{
typedef typename std::iterator_traits<RandomAccessIteratorIterator>
@@ -1190,9 +1187,7 @@
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<std::pair<difference_type, difference_type> > *pieces)
{
typedef typename std::iterator_traits<RandomAccessIteratorIterator>
@@ -1297,9 +1292,10 @@
parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin,
RandomAccessIteratorIterator seqs_end,
RandomAccessIterator3 target,
+ Splitter splitter,
+ _DifferenceTp length,
Comparator comp,
- Splitter splitter,
- _DifferenceTp length)
+ thread_index_t num_threads)
{
#if _GLIBCXX_ASSERTIONS
_GLIBCXX_PARALLEL_ASSERT(seqs_end - seqs_begin > 1);
@@ -1347,8 +1343,8 @@
std::vector<std::pair<difference_type, difference_type> >* pieces;
- thread_index_t num_threads = static_cast<thread_index_t>
- (std::min<difference_type>(get_max_threads(), total_length));
+ num_threads = static_cast<thread_index_t>
+ (std::min<difference_type>(num_threads, total_length));
# pragma omp parallel num_threads (num_threads)
{
@@ -1365,8 +1361,8 @@
__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 @@
if(length > target_position)
sequential_multiway_merge<stable, sentinels>(
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 @@
*
* @return end iterator of output sequence
*/
+// multiway_merge
// public interface
template<
typename RandomAccessIteratorPairIterator
@@ -1491,49 +1488,7 @@
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
- </* stable = */ false, /* sentinels = */ false>
- (seqs_begin, seqs_end, target, comp,
- multiway_merge_sampling_splitting</* stable = */ false,
- typename std::iterator_traits<RandomAccessIteratorPairIterator>
- ::value_type*, Comparator, _DifferenceTp>,
- static_cast<difference_type>(length));
- else
- return sequential_multiway_merge
- </* stable = */false, /* sentinels = */ false>(
- 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 @@
// Execute multiway merge *sequentially*.
return sequential_multiway_merge
</* stable = */ false, /* sentinels = */ false>
- (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 @@
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 @@
__gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
return parallel_multiway_merge
</* stable = */ false, /* sentinels = */ false>(
- seqs_begin, seqs_end,
- target, comp,
+ seqs_begin, seqs_end, target,
multiway_merge_exact_splitting</* stable = */ false,
typename std::iterator_traits<RandomAccessIteratorPairIterator>
::value_type*, Comparator, _DifferenceTp>,
- static_cast<difference_type>(length));
+ static_cast<difference_type>(length), comp, tag.get_num_threads());
else
return sequential_multiway_merge
</* stable = */ false, /* sentinels = */ false>(
- 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 @@
, 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,22 +1572,22 @@
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
- </* stable = */ true, /* sentinels = */ false>(
+ </* stable = */ false, /* sentinels = */ false>(
seqs_begin, seqs_end,
- target, comp,
- multiway_merge_sampling_splitting</* stable = */ true,
+ target,
+ multiway_merge_exact_splitting</* stable = */ false,
typename std::iterator_traits<RandomAccessIteratorPairIterator>
::value_type*, Comparator, _DifferenceTp>,
- static_cast<difference_type>(length));
+ static_cast<difference_type>(length), comp, tag.get_num_threads());
else
return sequential_multiway_merge
- </* stable = */ true, /* sentinels = */ false>(
+ </* stable = */ false, /* sentinels = */ false>(
seqs_begin, seqs_end,
- target, *(seqs_begin->second), comp, length);
+ target, *(seqs_begin->second), length, comp);
}
// public interface
@@ -1643,10 +1597,45 @@
, 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
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+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 @@
// Execute multiway merge *sequentially*.
return sequential_multiway_merge
</* stable = */ true, /* sentinels = */ false>
- (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 @@
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,19 +1683,97 @@
return parallel_multiway_merge
</* stable = */ true, /* sentinels = */ false>(
seqs_begin, seqs_end,
- target, comp,
- multiway_merge_exact_splitting
- </* stable = */ true,
- typename std::iterator_traits<RandomAccessIteratorPairIterator>
- ::value_type*, Comparator, _DifferenceTp>,
- static_cast<difference_type>(length));
+ target,
+ multiway_merge_exact_splitting</* stable = */ true,
+ typename std::iterator_traits<RandomAccessIteratorPairIterator>
+ ::value_type*, Comparator, _DifferenceTp>,
+ static_cast<difference_type>(length), comp, tag.get_num_threads());
else
return sequential_multiway_merge</* stable = */ true,
/* sentinels = */ false>(
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
+ </* stable = */ true, /* sentinels = */ false>(
+ seqs_begin, seqs_end,
+ target,
+ multiway_merge_sampling_splitting</* stable = */ true,
+ typename std::iterator_traits<RandomAccessIteratorPairIterator>
+ ::value_type*, Comparator, _DifferenceTp>,
+ static_cast<difference_type>(length), comp, tag.get_num_threads());
+ else
+ return sequential_multiway_merge
+ </* stable = */ true, /* sentinels = */ false>(
+ 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()));
+}
+
/**
* @brief Multiway Merge Frontend.
*
@@ -1782,6 +1849,7 @@
*
* @return end iterator of output sequence
*/
+// multiway_merge_sentinels
// public interface
template<
typename RandomAccessIteratorPairIterator
@@ -1792,50 +1860,7 @@
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
- </* stable = */ false, /* sentinels = */ true>
- (seqs_begin, seqs_end, target, comp,
- multiway_merge_sampling_splitting
- </* stable = */ false,
- typename std::iterator_traits<RandomAccessIteratorPairIterator>
- ::value_type*, Comparator, _DifferenceTp>,
- static_cast<difference_type>(length));
- else
- return sequential_multiway_merge
- </* stable = */false, /* sentinels = */ true>(
- 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 @@
// Execute multiway merge *sequentially*.
return sequential_multiway_merge
</* stable = */ false, /* sentinels = */ true>
- (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 @@
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 @@
return parallel_multiway_merge
</* stable = */ false, /* sentinels = */ true>(
seqs_begin, seqs_end,
- target, comp,
- multiway_merge_exact_splitting
- </* stable = */ false,
- typename std::iterator_traits<RandomAccessIteratorPairIterator>
- ::value_type*, Comparator, _DifferenceTp>,
- static_cast<difference_type>(length));
+ target,
+ multiway_merge_exact_splitting</* stable = */ false,
+ typename std::iterator_traits<RandomAccessIteratorPairIterator>
+ ::value_type*, Comparator, _DifferenceTp>,
+ static_cast<difference_type>(length), comp, tag.get_num_threads());
else
return sequential_multiway_merge
</* stable = */ false, /* sentinels = */ true>(
seqs_begin, seqs_end,
- target, *(seqs_begin->second), comp, length);
+ target, *(seqs_begin->second), length, comp);
}
// public interface
@@ -1903,10 +1928,11 @@
, 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,19 +1951,17 @@
&& ((sequence_index_t)length >=
__gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
return parallel_multiway_merge
- </* stable = */ true, /* sentinels = */ true>(
- seqs_begin, seqs_end,
- target, comp,
- multiway_merge_sampling_splitting
- </* stable = */ true,
- typename std::iterator_traits<RandomAccessIteratorPairIterator>
- ::value_type*, Comparator, _DifferenceTp>,
- static_cast<difference_type>(length));
+ </* stable = */ false, /* sentinels = */ true>
+ (seqs_begin, seqs_end, target,
+ multiway_merge_sampling_splitting</* stable = */ false,
+ typename std::iterator_traits<RandomAccessIteratorPairIterator>
+ ::value_type*, Comparator, _DifferenceTp>,
+ static_cast<difference_type>(length), comp, tag.get_num_threads());
else
return sequential_multiway_merge
- </* stable = */ true, /* sentinels = */ true>(
+ </* stable = */false, /* sentinels = */ true>(
seqs_begin, seqs_end,
- target, *(seqs_begin->second), comp, length);
+ target, *(seqs_begin->second), length, comp);
}
// public interface
@@ -1947,10 +1971,45 @@
, 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
+ , typename RandomAccessIteratorOut
+ , typename _DifferenceTp
+ , typename Comparator>
+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 @@
// Execute multiway merge *sequentially*.
return sequential_multiway_merge
</* stable = */ true, /* sentinels = */ true>
- (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 @@
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,19 +2057,95 @@
return parallel_multiway_merge
</* stable = */ true, /* sentinels = */ true>(
seqs_begin, seqs_end,
- target, comp,
- multiway_merge_exact_splitting
- </* stable = */ true,
- typename std::iterator_traits<RandomAccessIteratorPairIterator>
- ::value_type*, Comparator, _DifferenceTp>,
- static_cast<difference_type>(length));
+ target,
+ multiway_merge_exact_splitting</* stable = */ true,
+ typename std::iterator_traits<RandomAccessIteratorPairIterator>
+ ::value_type*, Comparator, _DifferenceTp>,
+ static_cast<difference_type>(length), comp, tag.get_num_threads());
else
return sequential_multiway_merge
</* stable = */ true, /* sentinels = */ true>(
+ 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
+ </* stable = */ true, /* sentinels = */ true>(
seqs_begin, seqs_end,
- target, *(seqs_begin->second), comp, length);
+ target,
+ multiway_merge_sampling_splitting</* stable = */ true,
+ typename std::iterator_traits<RandomAccessIteratorPairIterator>
+ ::value_type*, Comparator, _DifferenceTp>,
+ static_cast<difference_type>(length), comp, tag.get_num_threads());
+ else
+ return sequential_multiway_merge
+ </* stable = */ true, /* sentinels = */ true>(
+ 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
#endif
Index: include/parallel/tags.h
===================================================================
--- include/parallel/tags.h (revision 135328)
+++ include/parallel/tags.h (working copy)
@@ -47,9 +47,6 @@
/** @brief Forces sequential execution at compile time. */
struct sequential_tag { };
- /** @brief Forces exact splitting in multiway merge at compile time. */
- struct exact_tag { };
-
/** @brief Recommends parallel execution at compile time,
* optionally using a user-specified number of threads. */
struct parallel_tag
@@ -119,6 +116,25 @@
struct find_tag { };
+ /** @brief Forces parallel merging
+ * with exact splitting, at compile time. */
+ struct exact_tag : public parallel_tag
+ {
+ exact_tag() { }
+ exact_tag(thread_index_t num_threads)
+ : parallel_tag(num_threads) { }
+ };
+
+ /** @brief Forces parallel merging
+ * with exact splitting, at compile time. */
+ struct sampling_tag : public parallel_tag
+ {
+ sampling_tag() { }
+ sampling_tag(thread_index_t num_threads)
+ : parallel_tag(num_threads) { }
+ };
+
+
/** @brief Forces parallel sorting using multiway mergesort
* at compile time. */
struct multiway_mergesort_tag : public parallel_tag
Index: include/parallel/merge.h
===================================================================
--- include/parallel/merge.h (revision 135328)
+++ include/parallel/merge.h (working copy)
@@ -254,11 +254,11 @@
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;
}
Index: include/parallel/multiway_mergesort.h
===================================================================
--- include/parallel/multiway_mergesort.h (revision 135328)
+++ include/parallel/multiway_mergesort.h (working copy)
@@ -289,8 +289,8 @@
Comparator& comp,
DiffType length_am) const
{
- stable_multiway_merge(seqs_begin, seqs_end, target, comp,
- length_am, sequential_tag());
+ stable_multiway_merge(seqs_begin, seqs_end, target, length_am, comp,
+ sequential_tag());
}
};
@@ -306,8 +306,8 @@
Comparator& comp,
DiffType length_am) const
{
- multiway_merge(seqs_begin, seqs_end, target, comp,
- length_am, sequential_tag());
+ multiway_merge(seqs_begin, seqs_end, target, length_am, comp,
+ sequential_tag());
}
};