Quicksort review

This is a discussion on Quicksort review within the C++ Programming forums, part of the General Programming Boards category; Perhaps the issue is related to both threads accessing data from the same cache line. This would become slightly less ...

  1. #16
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  2. #17
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,699
    Quote Originally Posted by Elysia View Post
    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.
    Code:
    bool fun(bool value)
    {
        return std::pow(std::exp(1), std::complex<float>(0, 1) 
        * std::complex<float>(std::atan(1)*(1 << (value + 2))))
        .real() > 0;
    }

  3. #18
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,546
    Quote Originally Posted by Sebastiani View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #19
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,699
    Quote Originally Posted by Elysia View Post
    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.

    Quote Originally Posted by Elysia View Post
    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.

    Quote Originally Posted by Elysia View Post
    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.
    Code:
    bool fun(bool value)
    {
        return std::pow(std::exp(1), std::complex<float>(0, 1) 
        * std::complex<float>(std::atan(1)*(1 << (value + 2))))
        .real() > 0;
    }

  5. #20
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,546
    Quote Originally Posted by Sebastiani View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #21
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,699
    Quote Originally Posted by Elysia View Post
    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.
    Code:
    bool fun(bool value)
    {
        return std::pow(std::exp(1), std::complex<float>(0, 1) 
        * std::complex<float>(std::atan(1)*(1 << (value + 2))))
        .real() > 0;
    }

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. problems with quicksort!
    By coni in forum C Programming
    Replies: 3
    Last Post: 10-03-2009, 02:29 AM
  2. Scalability problems with Quicksort
    By hbejkosa in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2008, 10:26 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. quicksort problem
    By spinner in forum C Programming
    Replies: 9
    Last Post: 05-04-2003, 02:02 PM
  5. Quicksort
    By Nutshell in forum C Programming
    Replies: 1
    Last Post: 01-15-2002, 08:42 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21