# Making a faster parallel quicksort

I'm trying to take my existing parallel Quicksort and make it execute faster. Below is what I have but half the time the optimized version doesn't give me a faster time.

I use them to compare big arrays whose sizes are 10,000 or more. Any advice on what I should change? Nthreads is declared in the main function and set to 4.

void quickSort_parallel_omp(int arr[], int low, int high)
{
int pi;
if (low < high)
{
pi = partition(arr, low, high);
omp_set_nested(1);
#pragma omp parallel sections
{
#pragma omp section
quickSort_parallel_omp(arr, low, pi - 1);
#pragma omp section
quickSort_parallel_omp(arr, pi + 1, high);
}
}
}

void quickSort_Optparallel_omp(int arr[], int low, int high)   //optimized version
{
int pi;
if (low < high)
{
pi = partition(arr, low, high);
omp_set_nested(1);
{
#pragma omp section
quickSort_Optparallel_omp(arr, low, pi - 1);
#pragma omp section
quickSort_Optparallel_omp(arr, pi + 1, high);
}
}
}

• Out of curiosity, have you tried benchmarking these against std::sort with a parallel execution policy? – Frank Nov 28 '17 at 0:15
• I can't really run tests right now, but I would guess that breaking out of the parallel algorithm when high-lo < threshold would probably help. I would expect the task bookeeping overhead to overtake your paralelism gains at some point. – Frank Nov 28 '17 at 2:01
• It would be nice to see the partition() function as that can affect the running time of quick sort. – user1118321 Nov 28 '17 at 3:19
• It's not at all clear you're parallelizing your quicksort the right way. You should think about the danger of cache thrashing and memory bandwidth saturation. In fact, I would not be so sure that quicksort is the best choice for parallelization. – einpoklum Nov 28 '17 at 10:41
• This code spawns two new threads on every call. Thus the number of threads spawned will approximate the size of the input. If arr[] has 4096 elements, it spawns around 4096 threads. Did you intend to spawn at most Nthreads? I pointed this out on StackOverflow in one of the several duplicate questions you have posted, but radio silence.... Hunter - Do you copy? Calling @Hunter Davis... – Jive Dadson Nov 30 '17 at 7:50

Nested parallelism is expensive. It was designed for around 1 nesting level when the first level is not parallel enough, and loop slicing. This kind of recursive problems are much better handled by tasks.

void quickSort_tasks(int arr[], int low, int high)
{
int pi;
if (low < high)
{
pi = partition(arr, low, high);
quickSort_Optparallel_omp(arr, low, pi - 1);
quickSort_Optparallel_omp(arr, pi + 1, high);
}
}

void quickSort_omp(int arr[], int low, int high) {
#pragma omp parallel
#pragma omp single
// implicit synchronization at the end of parallel section
// otherwise use
}


Other sorting algorithms may offer higher performance or more efficient parallelization, although being algorithmically more complex. I'm thinking about radix, pigeonhole and merge sorting.