32 #ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H
33 #define _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H 1
46 template<
typename _DifferenceTp>
49 typedef _DifferenceTp difference_type;
61 template<
typename RandomAccessIterator>
65 typedef typename traits_type::value_type value_type;
66 typedef typename traits_type::difference_type difference_type;
96 template<
typename RandomAccessIterator,
typename _DifferenceTp>
99 _DifferenceTp num_samples)
102 typedef typename traits_type::value_type value_type;
103 typedef _DifferenceTp difference_type;
107 difference_type* es =
new difference_type[num_samples + 2];
110 num_samples + 1, es);
112 for (difference_type i = 0; i < num_samples; ++i)
113 ::
new(&(sd->
samples[iam * num_samples + i]))
120 template<
bool exact,
typename RandomAccessIterator,
121 typename Comparator,
typename SortingPlacesIterator>
127 template<
typename RandomAccessIterator,
typename Comparator,
128 typename SortingPlacesIterator>
130 <true, RandomAccessIterator, Comparator, SortingPlacesIterator>
137 std::iterator_traits<RandomAccessIterator>::difference_type
146 seqs[s] = std::make_pair(sd->
temporary[s],
153 if (iam < sd->num_threads - 1)
161 sd->
pieces[iam][seq].end = offsets[seq] - seqs[seq].first;
164 sd->
pieces[iam][seq].end =
174 sd->
pieces[iam][seq].begin = sd->
pieces[iam - 1][seq].end;
177 sd->
pieces[iam][seq].begin = 0;
183 template<
typename RandomAccessIterator,
typename Comparator,
184 typename SortingPlacesIterator>
186 SortingPlacesIterator>
193 std::iterator_traits<RandomAccessIterator>::difference_type
198 typedef typename traits_type::value_type value_type;
199 typedef typename traits_type::difference_type difference_type;
206 __gnu_sequential::sort(sd->
samples,
215 if (num_samples * iam > 0)
216 sd->
pieces[iam][s].begin =
220 sd->
samples[num_samples * iam],
225 sd->
pieces[iam][s].begin = 0;
227 if ((num_samples * (iam + 1)) < (num_samples * sd->
num_threads))
232 sd->
samples[num_samples * (iam + 1)],
242 template<
bool stable,
typename RandomAccessIterator,
typename Comparator>
243 struct possibly_stable_sort
247 template<
typename RandomAccessIterator,
typename Comparator>
248 struct possibly_stable_sort<true, RandomAccessIterator, Comparator>
250 void operator()(
const RandomAccessIterator& begin,
251 const RandomAccessIterator& end, Comparator& comp)
const
253 __gnu_sequential::stable_sort(begin, end, comp);
257 template<
typename RandomAccessIterator,
typename Comparator>
258 struct possibly_stable_sort<false, RandomAccessIterator, Comparator>
260 void operator()(
const RandomAccessIterator begin,
261 const RandomAccessIterator end, Comparator& comp)
const
263 __gnu_sequential::sort(begin, end, comp);
267 template<
bool stable,
typename SeqRandomAccessIterator,
268 typename RandomAccessIterator,
typename Comparator,
270 struct possibly_stable_multiway_merge
274 template<
typename SeqRandomAccessIterator,
typename RandomAccessIterator,
275 typename Comparator,
typename DiffType>
276 struct possibly_stable_multiway_merge
277 <true, SeqRandomAccessIterator, RandomAccessIterator, Comparator,
280 void operator()(
const SeqRandomAccessIterator& seqs_begin,
281 const SeqRandomAccessIterator& seqs_end,
282 const RandomAccessIterator& target,
284 DiffType length_am)
const
286 stable_multiway_merge(seqs_begin, seqs_end, target, length_am, comp,
291 template<
typename SeqRandomAccessIterator,
typename RandomAccessIterator,
292 typename Comparator,
typename DiffType>
293 struct possibly_stable_multiway_merge
294 <false, SeqRandomAccessIterator, RandomAccessIterator, Comparator,
297 void operator()(
const SeqRandomAccessIterator& seqs_begin,
298 const SeqRandomAccessIterator& seqs_end,
299 const RandomAccessIterator& target,
301 DiffType length_am)
const
312 template<
bool stable,
bool exact,
typename RandomAccessIterator,
319 typedef typename traits_type::value_type value_type;
320 typedef typename traits_type::difference_type difference_type;
325 difference_type length_local = sd->
starts[iam + 1] - sd->
starts[iam];
329 typedef value_type* SortingPlacesIterator;
332 static_cast<value_type*
>(
333 ::operator
new(
sizeof(value_type) * (length_local + 1)));
340 possibly_stable_sort<stable, SortingPlacesIterator, Comparator>()
348 difference_type num_samples =
351 <exact, RandomAccessIterator, Comparator, SortingPlacesIterator>()
352 (iam, sd, comp, num_samples);
355 difference_type offset = 0, length_am = 0;
358 length_am += sd->
pieces[iam][s].end - sd->
pieces[iam][s].begin;
359 offset += sd->
pieces[iam][s].begin;
374 possibly_stable_multiway_merge<
376 typename seq_vector_type::iterator,
377 RandomAccessIterator,
378 Comparator, difference_type>()
379 (seqs.begin(), seqs.end(),
380 sd->
source + offset, comp,
395 template<
bool stable,
bool exact,
typename RandomAccessIterator,
405 typedef typename traits_type::value_type value_type;
406 typedef typename traits_type::difference_type difference_type;
408 difference_type n = end - begin;
419 difference_type* starts;
421 # pragma omp parallel num_threads(num_threads)
423 num_threads = omp_get_num_threads();
430 sd.
temporary =
new value_type*[num_threads];
434 difference_type size =
437 sd.
samples =
static_cast<value_type*
>(
438 ::operator
new(size *
sizeof(value_type)));
443 sd.
offsets =
new difference_type[num_threads - 1];
445 for (
int s = 0; s < num_threads; ++s)
446 sd.
pieces[s].resize(num_threads);
447 starts = sd.
starts =
new difference_type[num_threads + 1];
449 difference_type chunk_length = n / num_threads;
450 difference_type split = n % num_threads;
451 difference_type pos = 0;
452 for (
int i = 0; i < num_threads; ++i)
455 pos += (i < split) ? (chunk_length + 1) : chunk_length;
457 starts[num_threads] = pos;
461 parallel_sort_mwms_pu<stable, exact>(&sd, comp);
#define _GLIBCXX_CALL(n)
Macro to produce log message when entering a function.
value_type * samples
Samples.
void multiseq_partition(RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank, RankIterator begin_offsets, Comparator comp=std::less< typename std::iterator_traits< typename std::iterator_traits< RanSeqs >::value_type::first_type >::value_type >())
Splits several sorted sequences at a certain global rank, resulting in a splitting point for each seq...
difference_type * starts
Start indices, per thread.
void determine_samples(PMWMSSortingData< RandomAccessIterator > *sd, _DifferenceTp num_samples)
Select samples from a sequence.
void parallel_sort_mwms_pu(PMWMSSortingData< RandomAccessIterator > *sd, Comparator &comp)
PMWMS code executed by each thread.
GNU parallel code for public use.
pair holds two objects of arbitrary type.
static const _Settings & get()
Get the global settings.
void parallel_sort_mwms(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads)
PMWMS main call.
A standard container which offers fixed time access to individual elements in any order...
RandomAccessIteratorOut multiway_merge(RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, __gnu_parallel::sequential_tag)
Multiway Merge Frontend.
thread_index_t num_threads
Number of threads involved.
RandomAccessIterator source
Input begin.
value_type ** temporary
Storage in which to sort.
uint16 thread_index_t
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
Includes the original header files concerned with iterators except for stream iterators. This file is a GNU parallel extension to the Standard C++ Library.
Data accessed by all threads.
difference_type begin
Begin of subsequence.
difference_type * offsets
Offsets to add to the found positions.
unsigned int sort_mwms_oversampling
Oversampling factor for parallel std::sort (MWMS).
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
difference_type end
End of subsequence.
_ForwardIterator uninitialized_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result)
Copies the range [first,last) into result.
OutputIterator equally_split(difference_type n, thread_index_t num_threads, OutputIterator s)
Function to split a sequence into parts of almost equal size.
Implementation of sequential and parallel multiway merge.
std::vector< Piece< difference_type > > * pieces
Pieces of data to merge [thread][sequence].