parallel quicksort in c

Question

After a lot of searching for an implementation of parallel quicksort in c, I'm about to dive in and code it myself. (I need to sort an array of about 1 million text strings.) It seems that all the implementations I have found divide the work inside the qsort function itself, which creates a huge amount of overhead in partitioning the relatively small amount of work per thread.

Would it not be much faster to divide the 1 million strings by the number of threads (in my case, 24 threads), and have them each work on a section, and then do a mergesort? Granted, this has the theoretical disadvantage that it is not an in-place sort, but with gobs of memory available it is not a problem. The machine this runs on has 12 (very fast) physical/24 logical cores and 192 GB (yes, gigabytes) of memory. Currently, even on this machine, the sort takes almost 8 minutes!

Solution 1

Would it not be much faster to divide the 1 million strings by the number of threads (in my case, 24 threads), and have them each work on a section, and then do a mergesort?

Its a good idea.

But you can make some observation by writing toy programs for quick-sort and merge-sort and take advantages of their algorithmic-/run-time-behavior.

For example. quick-sort sorts while dividing process (pivot element will be put in its final place at the end of that iteration) and merge-sort sorts while merging (sorting is done after the whole working-set is broken down (divided) into very granular-units where it can be directly compared with other granular-units (== or strcmp()).

Mixing up algorithms based on the nature of the working set is a good idea.

With respect to the parallel sorting, here is my parallel merge-sort for you to get started.

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>

#define NOTHREADS 2

/*

gcc -ggdb -lpthread parallel-mergesort.c 


NOTE: 
The mergesort boils downs to this.. 
Given two sorted array's how do we merge this?

We need a new array to hold the result of merging
otherwise it is not possible to do it using array, 
so we may need a linked list

*/

int a[] = {10, 8, 5, 2, 3, 6, 7, 1, 4, 9};

typedef struct node {
int i;
int j;
} NODE;

void merge(int i, int j)
{
        int mid = (i+j)/2;
        int ai = i;
        int bi = mid+1;

        int newa[j-i+1], newai = 0;

        while(ai <= mid && bi <= j) {
                if (a[ai] > a[bi])
                        newa[newai++] = a[bi++];
                else                    
                        newa[newai++] = a[ai++];
        }

        while(ai <= mid) {
                newa[newai++] = a[ai++];
        }

        while(bi <= j) {
                newa[newai++] = a[bi++];
        }

        for (ai = 0; ai < (j-i+1) ; ai++)
                a[i+ai] = newa[ai];

}

void * mergesort(void *a)
{
                NODE *p = (NODE *)a;
                NODE n1, n2;
                int mid = (p->i+p->j)/2;
                pthread_t tid1, tid2;
                int ret;

                n1.i = p->i;
                n1.j = mid;

                n2.i = mid+1;
                n2.j = p->j;

                if (p->i >= p->j) return;

                ret = pthread_create(&tid1, NULL, mergesort, &n1);
                if (ret) {
                        printf("%d %s - unable to create thread - ret - %d\n", __LINE__, __FUNCTION__, ret);    
                        exit(1);
                }


                ret = pthread_create(&tid2, NULL, mergesort, &n2);
                if (ret) {
                        printf("%d %s - unable to create thread - ret - %d\n", __LINE__, __FUNCTION__, ret);    
                        exit(1);
                }

                pthread_join(tid1, NULL);
                pthread_join(tid2, NULL);

                merge(p->i, p->j);
                pthread_exit(NULL);
}


int main()
{
                int i;
                NODE m;
                m.i = 0;
                m.j = 9;
                pthread_t tid;

                int ret; 

                ret=pthread_create(&tid, NULL, mergesort, &m);
                if (ret) {
                        printf("%d %s - unable to create thread - ret - %d\n", __LINE__, __FUNCTION__, ret);    
                        exit(1);
                }

                pthread_join(tid, NULL);

                for (i = 0; i < 10; i++)
                                printf ("%d ", a[i]);

                printf ("\n");

                // pthread_exit(NULL);
                return 0;
}

Good luck!

Solution 2

Quicksort involves an initial pass over a list, which sorts the list into sections that are higher and lower than the pivot.

Why not do that in one thread, and then spawn another thread and delegate it to one half while the extant thread takes the other half, and so on and so forth?

Solution 3

Have you considered using a sorting algorithm specifically designed to sort strings? It seems like it might be a better idea than trying to implement a custom quicksort. The specific choice of algorithms probably depends on the length of the strings and how different they are but a radix sort probably isn't a bad bet.

A quick google search turned up an article about sorting strings. I haven't read it but Sedgewick and Bentley really know their stuff. According to the abstract, their algorithm is an amalgam of Quicksort and radix sort.

Another possible solution is to wrap a parallel sorting algorithm from C++. GNU's STL implementation has a parallel mode, which contains a parallel quicksort implementation. This is probably the easiest solution.

Comments

[PaeneInsula]

That is a great link. It seems that the algo they use for sorting strings is at least 2x as fast as qsort. Looks a little hairy for making parallel, so that will be a future project.