Rose::ParallelSort Namespace Reference

Description

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:

• quicksort()

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

Function Documentation

quicksort()

template<class RandomAccessIterator , class Compare >

void Rose::ParallelSort::quicksort	(	RandomAccessIterator	begin,
		RandomAccessIterator	end,
		size_t	nThreads,
		Compare	compare
	)

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 141 of file ParallelSort.h.