Thread: Quicksort review

Perhaps the issue is related to both threads accessing data from the same cache line. This would become slightly less of an issue as the objects themselves are larger.
Also, when the time taken for a comparisons or asignments/swaps is larger, then multithreading will help more.
So both the size and speed of comparison make sorting an array of ints very slanted towards single-threading being best. Sorting a structure containing a string, and several other non-key fields, might just as easily show the threaded approach to be far superrior.

Lastly, I don't know what the overhead of creating a second thread is, but it is probably much more than I had guessed and the cutoff I arbitrarily picked may be much too low. Threads aren't really meant to be created and destroyed so rapidly. Some things maintain a thread-pool for this reason.


I'm very thorough with converting recursive code to iterative code, whenever it doesn't involve maintaining an explicit stack. All you have to do is modify the input variables to the state they should be for the recursive call and then loop instead. Usually you don't need to change all of the input variables either, as in the case here where either begin or end stays the same.

Originally Posted by Elysia

I currently have a custom written Quicksort algorithm. But I thought I'd ask for someone to look over it, because there is at least one thing I am unsure of.
The code passes all the tests I have for it, but I cannot say if it's right or not.
The question is: which of these checks are required and which ones are not? I have commented out a great deal, and like I mentioned, it passes all my tests, but that doesn't mean it will always pass all tests, so...

Another thing is that I tried to parallellize the algorithm, but it turned out to be slower. Not quite sure why. Perhaps someone has some suggestions or ideas...

Code:

template<template<typename> class PivotType, typename RandomIt>
void _Quicksort(RandomIt begin, RandomIt end, int Threads)
{
    if (end - begin <= 1)
        return;

    RandomIt pivot = PivotType<RandomIt>::GetPivot(begin, end); // Gets the pivot
    RandomIt left = begin, right = end - 2;
    std::iter_swap(pivot, end - 1); // Swaps the two values pointed by the two iterators
    pivot = end - 1;

    //while (/*left <= right && *//*right >= begin && *//*left < end*/1)
    for (;;)
    {
        while (*left < *pivot /*&& *//*left <= right && *//*left < end*/) ++left;
        while (*right > *pivot /*&& right >= left && */&& right > begin) --right;
        if (left > right) break;
        std::iter_swap(left, right);
        if (right == begin || left == end - 1) break;
        /*if (left < end) */++left;
        /*if (right > begin) */--right;
    }

    std::iter_swap(left, pivot);

    //boost::thread* pThreads[2] = { NULL, NULL };
    //if (Threads-- > 0)
        //pThreads[0] = new boost::thread(boost::bind(&_Quicksort<PivotType, RandomIt>, begin, left, 0));
    //else
        Quicksort<PivotType>(begin, left);
    //if (Threads-- > 0)
        //pThreads[1] = new boost::thread(boost::bind(&_Quicksort<PivotType, RandomIt>, left + 1, end, 0));
    //else
        Quicksort<PivotType>(left + 1, end);
    //if (pThreads[0]) pThreads[0]->join();
    //if (pThreads[1]) pThreads[1]->join();

    //Quicksort<PivotType>(begin, left);
    //Quicksort<PivotType>(left + 1, end);
}

Of course, before the advent of multicore systems, the sole purpose of a thread was to prevent blocking. For these systems, thread creation overhead has always been a major concern, and except for the most trivial applications, thread pools are almost always used (and for good reason).

Moreover, I think that your design, unfortunately, doesn't accomplish encapsulation of functionality too well. If you really want to implement threading capability, just supply it as a template parameter (ei: ThreadSpawningPolicy or what have you); mixing the "raw" threading code with sorting logic just makes it harder to generalize things, anyway.

Besides, instead of reinventing the wheel, you could have simply used std::sort (courtesy of a specialized iterator). And that doesn't just cover quicksort (which can't be used on linked lists, for example), but whatever is most appropriate for that particular iterator type.

Originally Posted by Sebastiani

Of course, before the advent of multicore systems, the sole purpose of a thread was to prevent blocking. For these systems, thread creation overhead has always been a major concern, and except for the most trivial applications, thread pools are almost always used (and for good reason).

I know, and I took that into account. While operator new and thread creation takes some time, it should be negligible to the rest of the sort since I made sure it was only done once.

Moreover, I think that your design, unfortunately, doesn't accomplish encapsulation of functionality too well. If you really want to implement threading capability, just supply it as a template parameter (ei: ThreadSpawningPolicy or what have you); mixing the "raw" threading code with sorting logic just makes it harder to generalize things, anyway.

I know, but as I said, it was a test to see if I could gain any benefit from it first before implementing a full system for such a thing.

Besides, instead of reinventing the wheel, you could have simply used std::sort (courtesy of a specialized iterator). And that doesn't just cover quicksort (which can't be used on linked lists, for example), but whatever is most appropriate for that particular iterator type.

I am aware of std::sort, but I was feeling adventurous. Dealing with different sorts on my course, I took the liberty of implementing Quicksort, Heapsort and Mergesort.

Originally Posted by Elysia

I know, and I took that into account. While operator new and thread creation takes some time, it should be negligible to the rest of the sort since I made sure it was only done once.

From what I can see, it spawns however many threads are requested. Anyway, thread pools should be used exclusively, normally.

Originally Posted by Elysia

I know, but as I said, it was a test to see if I could gain any benefit from it first before implementing a full system for such a thing.

Oh, okay. Benchmarking.

Originally Posted by Elysia

I am aware of std::sort, but I was feeling adventurous. Dealing with different sorts on my course, I took the liberty of implementing Quicksort, Heapsort and Mergesort.

Sure, that's great practice. And when your done, try doing it via the iterator interface. Much more challenging.

Originally Posted by Sebastiani

From what I can see, it spawns however many threads are requested. Anyway, thread pools should be used exclusively, normally.

Yes, but if I set that to 2, it would spawn only two. And from my previous, you should be able to see I did another test, where I split the Quicksort into two functions, one where it spawned two threads after the first partition and calling a recursive Quicksort.
It was the same result.

Originally Posted by Elysia

Yes, but if I set that to 2, it would spawn only two. And from my previous, you should be able to see I did another test, where I split the Quicksort into two functions, one where it spawned two threads after the first partition and calling a recursive Quicksort.
It was the same result.

Ah, I see now - '_Quicksort' isn't being called recursively. Sorry, I overlooked that.