25 #ifndef __TPIE_PARALLEL_SORT_H__
26 #define __TPIE_PARALLEL_SORT_H__
30 #include <boost/iterator/iterator_traits.hpp>
38 #include <tpie/config.h>
50 template <
typename iterator_type,
typename comp_type,
bool Progress,
51 size_t min_size=1024*1024*8/
sizeof(
typename boost::iterator_value<iterator_type>::type)>
61 std::uint64_t work_estimate;
62 std::uint64_t total_work_estimate;
63 std::condition_variable cond;
68 typedef typename boost::iterator_value<iterator_type>::type value_type;
73 static inline std::uint64_t sortWork(std::uint64_t n) {
77 return static_cast<uint64_t
>(log(static_cast<double>(n)) *
static_cast<double>(n) * 1.8
78 / log(static_cast<double>(2)));
87 template <
typename comp_t>
88 static inline iterator_type unguarded_partition(iterator_type first,
92 iterator_type pivot = first;
95 while (comp(*pivot, *last));
98 if (first == last)
break;
100 }
while (comp(*first, *pivot));
102 if (first == last)
break;
104 std::iter_swap(first, last);
106 std::iter_swap(last, pivot);
117 static inline iterator_type median(iterator_type a, iterator_type b, iterator_type c, comp_type & comp) {
119 if (comp(*b, *c))
return b;
120 else if (comp(*a, *c))
return c;
123 if (comp(*a, *c))
return a;
124 else if (comp(*b, *c))
return c;
137 static inline iterator_type pick_pivot(iterator_type a, iterator_type b, comp_type & comp) {
138 if (a == b)
return a;
144 size_t step = (b-a)/8;
146 return median(median(a+0, a+step, a+step*2, comp),
147 median(a+step*3, a+step*4, a+step*5, comp),
148 median(a+step*6, a+step*7, b-1, comp), comp);
157 static inline iterator_type partition(iterator_type a, iterator_type b, comp_type & comp) {
158 iterator_type pivot = pick_pivot(a, b, comp);
160 std::iter_swap(pivot, a);
161 iterator_type l = unguarded_partition(a, b, comp);
178 : a(a), b(b), comp(comp), parent(parent), progress(p) {
184 for (
size_t i = 0; i < children.size(); ++i) {
197 while (static_cast<size_t>(b - a) >= min_size) {
198 iterator_type pivot = partition(a, b, comp);
203 children.push_back(j);
207 add_progress(sortWork(b - a));
217 std::lock_guard<std::mutex> lock(progress.mutex);
218 progress.work_estimate = progress.total_work_estimate;
219 progress.cond.notify_one();
228 progress_t & progress;
230 std::vector<qsort_job *> children;
232 void add_progress(uint64_t amount) {
233 std::lock_guard<std::mutex> lock(progress.mutex);
234 progress.work_estimate += amount;
235 progress.cond.notify_one();
239 parallel_sort_impl(
typename P::base * p) {
248 void operator()(iterator_type a, iterator_type b, comp_type comp=std::less<value_type>() ) {
249 progress.work_estimate = 0;
250 progress.total_work_estimate = sortWork(b-a);
251 if (progress.pi) progress.pi->init(progress.total_work_estimate);
253 if (static_cast<size_t>(b - a) < min_size) {
255 if (progress.pi) progress.pi->done();
262 std::uint64_t prev_work_estimate = 0;
263 std::unique_lock<std::mutex> lock(progress.mutex);
264 while (progress.work_estimate < progress.total_work_estimate) {
265 if (progress.pi && progress.work_estimate > prev_work_estimate) progress.pi->step(progress.work_estimate - prev_work_estimate);
266 prev_work_estimate = progress.work_estimate;
267 progress.cond.wait(lock);
273 if (progress.pi) progress.pi->done();
276 static const size_t max_job_count=256;
281 std::pair<iterator_type, iterator_type> jobs[max_job_count];
293 template <
bool Progress,
typename iterator_type,
typename comp_type>
297 comp_type comp=std::less<
typename boost::iterator_value<iterator_type>::type>()) {
298 #ifdef TPIE_PARALLEL_SORT
315 template <
typename iterator_type,
typename comp_type>
318 comp_type comp=std::less<
typename boost::iterator_value<iterator_type>::type>()) {
319 #ifdef TPIE_PARALLEL_SORT
329 #endif //__TPIE_PARALLEL_SORT_H__
void sort(uncompressed_stream< T > &instream, uncompressed_stream< T > &outstream, Compare comp, progress_indicator_base &indicator)
Sort elements of a stream using the given STL-style comparator object.
The base class for indicating the progress of some task.
void parallel_sort(iterator_type a, iterator_type b, typename tpie::progress_types< Progress >::base &pi, comp_type comp=std::less< typename boost::iterator_value< iterator_type >::type >())
Sort items in the range [a,b) using a parallel quick sort.
void operator()(iterator_type a, iterator_type b, comp_type comp=std::less< value_type >())
Perform a parallel sort of the items in the interval [a,b).
virtual void done()
Advance the indicator to the end.
virtual void on_done() override
Called when this job and all subjobs are done.
Generic internal queue with known memory requirements.
A simple parallel sort implementation with progress tracking.
Represents quick sort work at a given level.
void join()
Wait for this job and its subjobs to complete.
Job class for job manager.
qsort_job(iterator_type a, iterator_type b, comp_type comp, qsort_job *parent, progress_t &p)
Construct a qsort_job.
For applications where you wish to disable progress indicators via a template parameter, refer to progress_types members names sub, fp and base.
void enqueue(job *parent=0)
Add this job to the job pool.
virtual void operator()() override
Running a job with iterators a and b will repeatedly partition [a,b), spawn a job on the left part an...
Progress indicator concept in an efficient non-inheritance way.
virtual void init(stream_size_type range=0)
Initialize progress indicator.