Multithreaded QuickSort taking longer than normal QuickSort

Question

I have implemented quicksort using multithreading, it is sorting the array of integers correctly but however it is taking longer than a normal quicksort to execute. For e.g to sort 10000 integers Multithreading: 6856 ms Normal: 1 ms

I do not know what is wrong in my code.

public void run()
{
    quickSort1(this.Array,this.low,this.high);
}
int partition(int[]A,int l,int r)
  {
    int v = A[r];
    int i = l;
    int j = r;

    while(i<j)
    {
        while(A[i]<v)
        {
            i++;
        }

        while((i<j)&&(A[j]>=v))
        {
            j--;
        }

        if(i<j)
        {
            int C = A[i];


            A[i] = A[j];
            A[j] = C;
        }

        else
        {
            int D = A[i];

            A[i] = A[r];
            A[r] = D;
        }
    }


    return i;
}



void quickSort1(int[] A,int l,int r)
{
    int i;
    if(r>l)
    {
        i = partition(A,l,r);

        quickSort sort1 = new quickSort(A,l,i-1);
        Thread t1 = new Thread(sort1);


        quickSort sort2 = new quickSort(A,i+1,r);
        Thread t2 = new Thread(sort2);
        t1.start();
        t2.start();

        try
        {
            t1.join();
            t2.join();
        }catch(Exception e){}



    }
}

void normal_quickSort(int[] A,int l,int r)
{

    int i;
    if(r>l)
    {
        i = partition(A,l,r);

        normal_quickSort(A,l,i-1);
        normal_quickSort(A,i+1,r);
    }
}

I'm going to say that the overhead required to create threads is greater than what it takes to do the computation in a single one. — Robert Moskal, Mar 09 '16 at 16:30
@BitExodus by the looks of it - twice the number of array elements minus 1. — Andy Turner, Mar 09 '16 at 16:32
@BitExodus Each time it partitions the array into two I have two threads which handles the sub arrays. — KMB, Mar 09 '16 at 16:34
I do not understand by what you are trying to say by "too much". Am I creating too much threads? — KMB, Mar 09 '16 at 16:37
@KMB I think so, as Robert Moskal said in his comment. Take a look at this about threads: http://stackoverflow.com/questions/5483047/why-is-creating-a-thread-said-to-be-expensive — BitExodus, Mar 09 '16 at 16:42
@BitExodus it's because I don't have the overhead of thread creation ;) — Andy Turner, Mar 09 '16 at 16:43

score 4 · Answer 1 · answered Mar 09 '16 at 16:58

Two problems,

(1) You are creating too many threads. Creating threads is expensive. For a compute-bound task, it's probably a mistake if the total number of threads that you create is greater than the number of CPUs in your platform.

The trick is to pool the threads. (e.g., create a java.util.concurrent.ThreadPoolExecutor, and give it tasks to perform).

(2) You are breaking the work up into too-small tasks. Synchronizing threads and passing data between threads is expensive too. Not nearly as expensive as creating and destroying threads, but there's still a limit to how many times you want to do it.

Your algorithm potentially divides the work up to where you're giving a thread a list of one element, and asking the thread to "sort" it. That's a ridiculously small task for multi-threading.

To implement quicksort, you have to keep splitting the array into smaller and smaller chunks, but you don't have to give each chunk to a different thread, and after they get small enough, you shouldn't. I don't know how small is small enough (100? 1000? 10,000?), but you could easily experiment to find out.

Thanks for the detailed answer. I will try to implement it. – KMB Mar 09 '16 at 17:48 — KMB, Mar 09 '16 at 17:48

Multithreaded QuickSort taking longer than normal QuickSort

1 Answers1