Viewing file: 
multiway_mergesort.h (14.96 KB) -rw-r--r--Select action/file-type:
(
+) |
(
+) |
(
+) |
Code (
+) |
Session (
+) |
(
+) |
SDB (
+) |
(
+) |
(
+) |
(
+) |
(
+) |
(
+) |
// -*- C++ -*-
// Copyright (C) 2007, 2008, 2009, 2010 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/multiway_mergesort.h
* @brief Parallel multiway merge sort.
* This file is a GNU parallel extension to the Standard C++ Library.
*/
// Written by Johannes Singler.
#ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H
#define _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H 1
#include <vector>
#include <parallel/basic_iterator.h>
#include <bits/stl_algo.h>
#include <parallel/parallel.h>
#include <parallel/multiway_merge.h>
namespace __gnu_parallel
{
/** @brief Subsequence description. */
template<typename _DifferenceTp>
struct _Piece
{
typedef _DifferenceTp _DifferenceType;
/** @brief Begin of subsequence. */
_DifferenceType _M_begin;
/** @brief End of subsequence. */
_DifferenceType _M_end;
};
/** @brief Data accessed by all threads.
*
* PMWMS = parallel multiway mergesort */
template<typename _RAIter>
struct _PMWMSSortingData
{
typedef std::iterator_traits<_RAIter> _TraitsType;
typedef typename _TraitsType::value_type _ValueType;
typedef typename _TraitsType::difference_type _DifferenceType;
/** @brief Number of threads involved. */
_ThreadIndex _M_num_threads;
/** @brief Input __begin. */
_RAIter _M_source;
/** @brief Start indices, per thread. */
_DifferenceType* _M_starts;
/** @brief Storage in which to sort. */
_ValueType** _M_temporary;
/** @brief Samples. */
_ValueType* _M_samples;
/** @brief Offsets to add to the found positions. */
_DifferenceType* _M_offsets;
/** @brief Pieces of data to merge @c [thread][__sequence] */
std::vector<_Piece<_DifferenceType> >* _M_pieces;
};
/**
* @brief Select _M_samples from a sequence.
* @param __sd Pointer to algorithm data. _Result will be placed in
* @c __sd->_M_samples.
* @param __num_samples Number of _M_samples to select.
*/
template<typename _RAIter, typename _DifferenceTp>
void
__determine_samples(_PMWMSSortingData<_RAIter>* __sd,
_DifferenceTp __num_samples)
{
typedef std::iterator_traits<_RAIter> _TraitsType;
typedef typename _TraitsType::value_type _ValueType;
typedef _DifferenceTp _DifferenceType;
_ThreadIndex __iam = omp_get_thread_num();
_DifferenceType* __es = new _DifferenceType[__num_samples + 2];
equally_split(__sd->_M_starts[__iam + 1] - __sd->_M_starts[__iam],
__num_samples + 1, __es);
for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
::new(&(__sd->_M_samples[__iam * __num_samples + __i]))
_ValueType(__sd->_M_source[__sd->_M_starts[__iam]
+ __es[__i + 1]]);
delete[] __es;
}
/** @brief Split consistently. */
template<bool __exact, typename _RAIter,
typename _Compare, typename _SortingPlacesIterator>
struct _SplitConsistently
{ };
/** @brief Split by exact splitting. */
template<typename _RAIter, typename _Compare,
typename _SortingPlacesIterator>
struct _SplitConsistently<true, _RAIter, _Compare, _SortingPlacesIterator>
{
void
operator()(const _ThreadIndex __iam,
_PMWMSSortingData<_RAIter>* __sd,
_Compare& __comp,
const typename
std::iterator_traits<_RAIter>::difference_type
__num_samples) const
{
# pragma omp barrier
std::vector<std::pair<_SortingPlacesIterator,
_SortingPlacesIterator> >
__seqs(__sd->_M_num_threads);
for (_ThreadIndex __s = 0; __s < __sd->_M_num_threads; __s++)
__seqs[__s] = std::make_pair(__sd->_M_temporary[__s],
__sd->_M_temporary[__s]
+ (__sd->_M_starts[__s + 1]
- __sd->_M_starts[__s]));
std::vector<_SortingPlacesIterator> __offsets(__sd->_M_num_threads);
// if not last thread
if (__iam < __sd->_M_num_threads - 1)
multiseq_partition(__seqs.begin(), __seqs.end(),
__sd->_M_starts[__iam + 1], __offsets.begin(),
__comp);
for (_ThreadIndex __seq = 0; __seq < __sd->_M_num_threads; __seq++)
{
// for each sequence
if (__iam < (__sd->_M_num_threads - 1))
__sd->_M_pieces[__iam][__seq]._M_end
= __offsets[__seq] - __seqs[__seq].first;
else
// very end of this sequence
__sd->_M_pieces[__iam][__seq]._M_end =
__sd->_M_starts[__seq + 1] - __sd->_M_starts[__seq];
}
# pragma omp barrier
for (_ThreadIndex __seq = 0; __seq < __sd->_M_num_threads; __seq++)
{
// For each sequence.
if (__iam > 0)
__sd->_M_pieces[__iam][__seq]._M_begin =
__sd->_M_pieces[__iam - 1][__seq]._M_end;
else
// Absolute beginning.
__sd->_M_pieces[__iam][__seq]._M_begin = 0;
}
}
};
/** @brief Split by sampling. */
template<typename _RAIter, typename _Compare,
typename _SortingPlacesIterator>
struct _SplitConsistently<false, _RAIter, _Compare, _SortingPlacesIterator>
{
void
operator()(const _ThreadIndex __iam,
_PMWMSSortingData<_RAIter>* __sd,
_Compare& __comp,
const typename
std::iterator_traits<_RAIter>::difference_type
__num_samples) const
{
typedef std::iterator_traits<_RAIter> _TraitsType;
typedef typename _TraitsType::value_type _ValueType;
typedef typename _TraitsType::difference_type _DifferenceType;
__determine_samples(__sd, __num_samples);
# pragma omp barrier
# pragma omp single
__gnu_sequential::sort(__sd->_M_samples,
__sd->_M_samples
+ (__num_samples * __sd->_M_num_threads),
__comp);
# pragma omp barrier
for (_ThreadIndex __s = 0; __s < __sd->_M_num_threads; ++__s)
{
// For each sequence.
if (__num_samples * __iam > 0)
__sd->_M_pieces[__iam][__s]._M_begin =
std::lower_bound(__sd->_M_temporary[__s],
__sd->_M_temporary[__s]
+ (__sd->_M_starts[__s + 1]
- __sd->_M_starts[__s]),
__sd->_M_samples[__num_samples * __iam],
__comp)
- __sd->_M_temporary[__s];
else
// Absolute beginning.
__sd->_M_pieces[__iam][__s]._M_begin = 0;
if ((__num_samples * (__iam + 1)) <
(__num_samples * __sd->_M_num_threads))
__sd->_M_pieces[__iam][__s]._M_end =
std::lower_bound(__sd->_M_temporary[__s],
__sd->_M_temporary[__s]
+ (__sd->_M_starts[__s + 1]
- __sd->_M_starts[__s]),
__sd->_M_samples[__num_samples * (__iam + 1)],
__comp)
- __sd->_M_temporary[__s];
else
// Absolute end.
__sd->_M_pieces[__iam][__s]._M_end = (__sd->_M_starts[__s + 1]
- __sd->_M_starts[__s]);
}
}
};
template<bool __stable, typename _RAIter, typename _Compare>
struct __possibly_stable_sort
{ };
template<typename _RAIter, typename _Compare>
struct __possibly_stable_sort<true, _RAIter, _Compare>
{
void operator()(const _RAIter& __begin,
const _RAIter& __end, _Compare& __comp) const
{ __gnu_sequential::stable_sort(__begin, __end, __comp); }
};
template<typename _RAIter, typename _Compare>
struct __possibly_stable_sort<false, _RAIter, _Compare>
{
void operator()(const _RAIter __begin,
const _RAIter __end, _Compare& __comp) const
{ __gnu_sequential::sort(__begin, __end, __comp); }
};
template<bool __stable, typename Seq_RAIter,
typename _RAIter, typename _Compare,
typename DiffType>
struct __possibly_stable_multiway_merge
{ };
template<typename Seq_RAIter, typename _RAIter,
typename _Compare, typename _DiffType>
struct __possibly_stable_multiway_merge<true, Seq_RAIter,
_RAIter, _Compare, _DiffType>
{
void operator()(const Seq_RAIter& __seqs_begin,
const Seq_RAIter& __seqs_end,
const _RAIter& __target,
_Compare& __comp,
_DiffType __length_am) const
{ stable_multiway_merge(__seqs_begin, __seqs_end, __target,
__length_am, __comp, sequential_tag()); }
};
template<typename Seq_RAIter, typename _RAIter,
typename _Compare, typename _DiffType>
struct __possibly_stable_multiway_merge<false, Seq_RAIter,
_RAIter, _Compare, _DiffType>
{
void operator()(const Seq_RAIter& __seqs_begin,
const Seq_RAIter& __seqs_end,
const _RAIter& __target,
_Compare& __comp,
_DiffType __length_am) const
{ multiway_merge(__seqs_begin, __seqs_end, __target, __length_am,
__comp, sequential_tag()); }
};
/** @brief PMWMS code executed by each thread.
* @param __sd Pointer to algorithm data.
* @param __comp Comparator.
*/
template<bool __stable, bool __exact, typename _RAIter,
typename _Compare>
void
parallel_sort_mwms_pu(_PMWMSSortingData<_RAIter>* __sd,
_Compare& __comp)
{
typedef std::iterator_traits<_RAIter> _TraitsType;
typedef typename _TraitsType::value_type _ValueType;
typedef typename _TraitsType::difference_type _DifferenceType;
_ThreadIndex __iam = omp_get_thread_num();
// Length of this thread's chunk, before merging.
_DifferenceType __length_local =
__sd->_M_starts[__iam + 1] - __sd->_M_starts[__iam];
// Sort in temporary storage, leave space for sentinel.
typedef _ValueType* _SortingPlacesIterator;
__sd->_M_temporary[__iam] =
static_cast<_ValueType*>(::operator new(sizeof(_ValueType)
* (__length_local + 1)));
// Copy there.
std::uninitialized_copy(__sd->_M_source + __sd->_M_starts[__iam],
__sd->_M_source + __sd->_M_starts[__iam]
+ __length_local,
__sd->_M_temporary[__iam]);
__possibly_stable_sort<__stable, _SortingPlacesIterator, _Compare>()
(__sd->_M_temporary[__iam],
__sd->_M_temporary[__iam] + __length_local,
__comp);
// Invariant: locally sorted subsequence in sd->_M_temporary[__iam],
// __sd->_M_temporary[__iam] + __length_local.
// No barrier here: Synchronization is done by the splitting routine.
_DifferenceType __num_samples =
_Settings::get().sort_mwms_oversampling * __sd->_M_num_threads - 1;
_SplitConsistently<__exact, _RAIter, _Compare, _SortingPlacesIterator>()
(__iam, __sd, __comp, __num_samples);
// Offset from __target __begin, __length after merging.
_DifferenceType __offset = 0, __length_am = 0;
for (_ThreadIndex __s = 0; __s < __sd->_M_num_threads; __s++)
{
__length_am += (__sd->_M_pieces[__iam][__s]._M_end
- __sd->_M_pieces[__iam][__s]._M_begin);
__offset += __sd->_M_pieces[__iam][__s]._M_begin;
}
typedef std::vector<
std::pair<_SortingPlacesIterator, _SortingPlacesIterator> >
_SeqVector;
_SeqVector __seqs(__sd->_M_num_threads);
for (_ThreadIndex __s = 0; __s < __sd->_M_num_threads; ++__s)
{
__seqs[__s] =
std::make_pair(__sd->_M_temporary[__s]
+ __sd->_M_pieces[__iam][__s]._M_begin,
__sd->_M_temporary[__s]
+ __sd->_M_pieces[__iam][__s]._M_end);
}
__possibly_stable_multiway_merge<
__stable, typename _SeqVector::iterator,
_RAIter, _Compare, _DifferenceType>()(__seqs.begin(), __seqs.end(),
__sd->_M_source + __offset, __comp,
__length_am);
# pragma omp barrier
for (_DifferenceType __i = 0; __i < __length_local; ++__i)
__sd->_M_temporary[__iam][__i].~_ValueType();
::operator delete(__sd->_M_temporary[__iam]);
}
/** @brief PMWMS main call.
* @param __begin Begin iterator of sequence.
* @param __end End iterator of sequence.
* @param __comp Comparator.
* @param __n Length of sequence.
* @param __num_threads Number of threads to use.
*/
template<bool __stable, bool __exact, typename _RAIter,
typename _Compare>
void
parallel_sort_mwms(_RAIter __begin, _RAIter __end,
_Compare __comp,
_ThreadIndex __num_threads)
{
_GLIBCXX_CALL(__end - __begin)
typedef std::iterator_traits<_RAIter> _TraitsType;
typedef typename _TraitsType::value_type _ValueType;
typedef typename _TraitsType::difference_type _DifferenceType;
_DifferenceType __n = __end - __begin;
if (__n <= 1)
return;
// at least one element per thread
if (__num_threads > __n)
__num_threads = static_cast<_ThreadIndex>(__n);
// shared variables
_PMWMSSortingData<_RAIter> __sd;
_DifferenceType* __starts;
_DifferenceType __size;
# pragma omp parallel num_threads(__num_threads)
{
__num_threads = omp_get_num_threads(); //no more threads than requested
# pragma omp single
{
__sd._M_num_threads = __num_threads;
__sd._M_source = __begin;
__sd._M_temporary = new _ValueType*[__num_threads];
if (!__exact)
{
__size =
(_Settings::get().sort_mwms_oversampling * __num_threads - 1)
* __num_threads;
__sd._M_samples = static_cast<_ValueType*>
(::operator new(__size * sizeof(_ValueType)));
}
else
__sd._M_samples = 0;
__sd._M_offsets = new _DifferenceType[__num_threads - 1];
__sd._M_pieces
= new std::vector<_Piece<_DifferenceType> >[__num_threads];
for (_ThreadIndex __s = 0; __s < __num_threads; ++__s)
__sd._M_pieces[__s].resize(__num_threads);
__starts = __sd._M_starts = new _DifferenceType[__num_threads + 1];
_DifferenceType __chunk_length = __n / __num_threads;
_DifferenceType __split = __n % __num_threads;
_DifferenceType __pos = 0;
for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
{
__starts[__i] = __pos;
__pos += ((__i < __split)
? (__chunk_length + 1) : __chunk_length);
}
__starts[__num_threads] = __pos;
} //single
// Now sort in parallel.
parallel_sort_mwms_pu<__stable, __exact>(&__sd, __comp);
} //parallel
delete[] __starts;
delete[] __sd._M_temporary;
if (!__exact)
{
for (_DifferenceType __i = 0; __i < __size; ++__i)
__sd._M_samples[__i].~_ValueType();
::operator delete(__sd._M_samples);
}
delete[] __sd._M_offsets;
delete[] __sd._M_pieces;
}
} //namespace __gnu_parallel
#endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H */
