Rose::ParallelSort Namespace Reference


Algorithms for parallel sorting.

These algorithms use multiple threads to sort large arrays of values in parallel. Their usage is similar to std::sort in terms of the arguments, but they also take an additional argument to specify the number of threads. The following algorithms are implemented:


template<class RandomAccessIterator , class Compare >
void quicksort (RandomAccessIterator begin, RandomAccessIterator end, Compare compare, size_t nthreads)
 Sort values in parallel. More...

Function Documentation

template<class RandomAccessIterator , class Compare >
void Rose::ParallelSort::quicksort ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Compare  compare,
size_t  nthreads 

Sort values in parallel.

Sorts the values between begin (inclusive) and end (exclusive) according to the comparator compare using nthreads threads. Multi-threading is only used if the size of the range of values exceeds a certain threshold.

Note: using normal C++ iterators with debugging support will result in slower execution the more threads are used because the iterator dereference operators serialize some sanity checks which causes lock contention. It is best to do the sanity check once up front, then then call the sort function with pointers. For example:

std::vector<Thing> data;
// This method might get slower as nthreads increases
quicksort(data.begin(), data.end(), thingComparer, nthreads);
// But this should scale well provided data.size() is large enough.
quicksort(&data[0], &data[0]+data.size(), thingComparer, nthreads);

Definition at line 140 of file ParallelSort.h.