9
\$\begingroup\$

Just for learning purposes i wrote an implementation of quicksort algorithm.

I made some modifications to the algorithm to make it faster, that are:

  • two pivots setted to the boundaries of the middle partition(<, =, >), to avoid having two other variables counting the equal elements

  • the partitioning method checks first the presence of less(in left partition) or greater(in right partition) than pivot elements, if both are present, rather than moving the pivot twice, it just swaps them; if not behaves normally.

I benchmarked it a bit and compared the performance to std::sort; my algorithm, with random elements is faster than the STD one when there are more than 10000000, otherwise, with less elements std::sort is faster by some milliseconds(see below for actual benchmark results)

#include <algorithm>

template<class iterator>
void quickSort(iterator begin, iterator end)
{
    if (end - begin > 1)
    {
        auto lpivot = begin + (end - begin) / 2;
        auto rpivot = lpivot;

        auto pValue = *lpivot;

        auto left_it = lpivot - 1;
        auto right_it = rpivot + 1;

        auto lValue = *left_it;
        auto rValue = *right_it;

        bool isGreater = false;
        bool isLess = false;

        while (left_it != begin-1 || right_it != end)
        {
            if (lValue >= pValue)
            {
                if (lValue == pValue)
                {
                    lpivot--;
                    std::iter_swap(lpivot, left_it);
                }
                else
                    isGreater = true;
            }

            if (rValue <= pValue)
            {
                if (rValue == pValue)
                {
                    rpivot++;
                    std::iter_swap(rpivot, right_it);
                }
                else
                    isLess = true;
            }
            if (isGreater && isLess)
            {
                std::iter_swap(left_it, right_it);
            }
            else if (isGreater)
            {
                if (left_it != lpivot - 1)
                    std::iter_swap(left_it, lpivot - 1);
                std::iter_swap(rpivot - 1, lpivot - 1);
                std::iter_swap(rpivot, rpivot - 1);
                lpivot--;
                rpivot--;
            }
            else if (isLess)
            {
                if (right_it != rpivot + 1)
                    std::iter_swap(right_it, rpivot + 1);
                std::iter_swap(lpivot + 1, rpivot + 1);
                std::iter_swap(lpivot, lpivot + 1);
                lpivot++;
                rpivot++;
            }

            if (left_it != begin - 1)
                left_it--;
            if (right_it != end)
                right_it++;

            lValue = *left_it;
            rValue = *right_it;

            isGreater = false;
            isLess = false;
        }

        quickSort(begin, lpivot);
        quickSort(rpivot + 1, end);
    }
}

My algorithm benchmark

1000000  random integers --------> 80 ms
2000000  random integers --------> 165 ms
3000000  random integers --------> 247 ms
10000000 random integers --------> 780 ms

1000000  binary random integers -> 4 ms
2000000  binary random integers -> 9 ms
3000000  binary random integers -> 14 ms
10000000 binary random integers -> 49 ms

1000000  sorted integers --------> 19 ms
2000000  sorted integers --------> 43 ms
3000000  sorted integers --------> 65 ms
10000000 sorted integers --------> 232 ms

1000000  reversed integers ------> 17 ms
2000000  reversed integers ------> 37 ms
3000000  reversed integers ------> 60 ms
10000000 reversed integers ------> 216 ms

std::sort benchmark

1000000  random integers --------> 71 ms
2000000  random integers --------> 160 ms
3000000  random integers --------> 237 ms
10000000 random integers --------> 800 ms

1000000  binary random integers -> 4 ms
2000000  binary random integers -> 9 ms
3000000  binary random integers -> 13 ms
10000000 binary random integers -> 45 ms

1000000  sorted integers --------> 9 ms
2000000  sorted integers --------> 21 ms
3000000  sorted integers --------> 33 ms
10000000 sorted integers --------> 137 ms

1000000  reversed integers ------> 12 ms
2000000  reversed integers ------> 25 ms
3000000  reversed integers ------> 40 ms
10000000 reversed integers ------> 150 ms

bechmark code

int main()
{
    std::vector<int> values;

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dist(0, 1000000);
    //std::uniform_int_distribution<> dist(0, 1); //just 0s and 1s array

    std::generate_n(std::back_inserter(values), 10000000, std::bind(dist, gen)); //random

    for (int i = 0; i < 10000000; i++)
    {
        //values.push_back(i);              //sorted array
        //values.push_back(10000000 - i);   //reversed array
    }

    typedef std::chrono::high_resolution_clock Time;
    typedef std::chrono::milliseconds ms;
    typedef std::chrono::duration<float> fsec;
    auto t0 = Time::now();

    //quickSort(values.begin(), values.end());
    //std::sort(values.begin(), values.end());

    auto t1 = Time::now();
    fsec fs = t1 - t0;
    ms d = std::chrono::duration_cast<ms>(fs);
    std::cout << fs.count() << "s\n";
    std::cout << d.count() << "ms\n";

    return 0;
}

UPDATE

I tried benchmarking the same code with clang 3.8 un Ubuntu x64, and I got the same result as seen in the comments, so it is just visual studio with a slow std sort implementation

(I know those arrows suck, they are there just for clarity)

\$\endgroup\$
  • \$\begingroup\$ It might help if you provide the benchmark code too (the absolute numbers won't be comparable anywhere else, but improvements relative to the baseline might be applicable). \$\endgroup\$ – Toby Speight Mar 6 '17 at 16:48
  • 1
    \$\begingroup\$ Timing is hard. Running it only once is bad idea. Run the sort 10,000 times in main() and average the numbers after. Then run the application 3 times to make sure the numbers are similar. \$\endgroup\$ – Martin York Mar 6 '17 at 18:28
  • \$\begingroup\$ I ran your benchmark in random distribution mode with 10,000,000 elements and got: yours = 985 ms, std::sort = 674 ms. Smaller and larger numbers of elements were about the same ratio. Not sure why my numbers are so different than yours. \$\endgroup\$ – JS1 Mar 6 '17 at 20:00
  • \$\begingroup\$ @JS1, may be you got "unlucky" with the input? :) \$\endgroup\$ – Incomputable Mar 8 '17 at 17:39
  • \$\begingroup\$ @Incomputable The input is random and I ran it several times, so I don't think so. It's probably some difference in the compiler, OS, or CPU. I'm hoping other people will report their numbers so we can tell whose numbers are more realistic. \$\endgroup\$ – JS1 Mar 8 '17 at 18:00
5
\$\begingroup\$

Please note that the images in the post are under license of MatPlotLib, since I've used the modules to draw the plots.

I've finally run the benchmarks. Although they were pretty synthetic, I believe I nuked things that could affect the benchmark to the best of my abilities.

System setup: intel core i7 2600, 8GB ram 1333MHz, Ubuntu 16.04 LTS with latest updates, clang++-5.0-trunk, no performance flags except the ones passed with cmake's release mode, libc++-trunk (I believe latest version).

enter image description here

The image above is for elements in range [0; 100], generator: std::random_device (hardware, since intel cpu and libc++)

The following one is for elements in range [0; 100'000], std::mt19937_64, default constructed.

enter image description here

Do note that comparing two images doesn't make much sense due to varying setup and input range. Though the relation between speed and input range is pretty clear, especially for std::sort. The reason might be in more swaps that are to be made.

As you can see, your algorithm has algorithmic performance gain compared to libc++'s std::sort. The spikes near the end is me watching youtube videos, since the benchmark run for around 1.5 hours, and greatly slowed down at the very end. I believe the reason for slow down is not the algorithms, but the std::random_device (the overhead from it is excluded from the benchmark itself), so if anyone would want to benchmark the code in the future, don't use std::random_device to generate big data sets!

I've read somewhere on their bug tracker that their std::sort use some sophisticated quick sort. For further information I recommend having a look at this bug report.

Code Review:

I'm not great at algorithms, so I'll mention code style and some improvements for generic code.

Comments:

Yeah, this is pretty niche. But hey, I can't remember what I've written a month ago, although I'm noted as the one who has pretty tough long time memory among my peers. You could at least keep a markdown or tex/latex file around with it that explains . It is impossible to oversell code clarity.

iterator categories:

With C++17, I (believe) there are 7 categories. std::list will probably have bidirectional category, and it is probably good to fallback to merge sort. I haven't checked that myself, but my professor agrees with the post.

As a result, you could explicitly specify that you would "like" random access iterators, by changing declaration:

template<class RandomAccessIt>
void quickSort(RandomAccessIt begin, RandomAccessIt end)

it will probably fix the conformance bugs coming from the specialized version that you've probably built on the current code. From personal experience I know that it is quite hard to get full conformance to specification.

Minor things:

auto pValue = *lpivot;

That will probably increase type constraints. From what I've seen in the code, you don't modify it. So it should be:

const auto& pValue = *lpivot;

The key to understanding is that for any function of the following form:

template <typename T>
void foo(T value);

T will have references stripped of it if it is rvalue. Proof. So the code is practically copy constructing the pValue, which could be very expensive.

Benchmarking approach:

Although your benchmarking code is good to get a very rough measure of performance, I don't think it will suffise when you will start squeezing performance. Also, documenting your thoughts on every stage is going to be a very good approach. In short, all of the software engineering practices should be applied here, plus benchmarking:

  • Always have a baseline. It is usually the fastest version of the code. If you are not measuring the code against something, you're not making it faster.

  • Setup multiple situations. I don't think everyone wants to always sort ints. There might be compilation errors, undefined behavior, and whatnot.

  • Raw runtime is not the best thing. If you'll read the bug report I've linked, a user will mention that raw runtime is not portable and heavily environment dependent. My voice probably won't mean anything, but I agree with him/her. Better measures are throughput, data reads/writes. I believe all of the things can be captured by using google benchmark library.

Code used for benchmark:

Modified version of my benchmark v2.

Code in the main():

std::size_t counter = 0;
auto quicksort_bench = [&counter](std::vector<int>& v)
{
    quickSort(v.begin(), v.end());
    std::cout << v.front() << ' ' << counter++ << '\n'; //just to tell compiler to not optimize the code away
};

auto stdsort_bench = [&counter](std::vector<int>& v)
{
    std::sort(v.begin(), v.end());
    std::cout << v.front() << ' ' << counter++ << '\n'; //ditto
};

auto checked_bench = shino::benchmarker(generator{}, quicksort_bench, stdsort_bench);

for (std::size_t i = 1000; i <= 1'000'000; i += 100)
{
    checked_bench.time(i, 3); //3 means runcount for the same dataset
}

checked_bench.save_as<std::chrono::microseconds>("./benchmarks/metafile.txt",
                      {"custom quicksort.txt", "standard sort.txt"});

Generator was slightly tricky to write to not cause slow down and not run out of memory:

class generator
{
    std::unique_ptr<shino::random_int_generator<>> gen;
public:
    using input_type = std::size_t;

    generator():
            gen(std::make_unique<shino::random_int_generator<>>(0, 100)) //replaced with 0, 100'000 on second run
    {}

    generator(generator&& other):
            gen(std::move(other.gen))
    {}

    std::tuple<std::vector<int>> operator()(input_type input)
    {
        static std::vector<int> v(input);
        if (v.size() != input)
        {
            v.resize(input);
            (*gen)(v.begin(), v.end());
        }

        return v;
    }
};

Generation of the input happens outside of "critical section", so it shouldn't affect the benchmark. Also, the default is std::random_device, which is the reason why benchmark run for so long.

and a python script to draw the plots, which is I think irrelevant, since it doesn't modify the data at all.

\$\endgroup\$
  • \$\begingroup\$ I removed the links to my posts to not look like self promotional, let me know if I should put them back. Or you can just roll back the edit. \$\endgroup\$ – Incomputable Mar 22 '17 at 1:21
  • \$\begingroup\$ Are you only generating numbers in the range 0..100? \$\endgroup\$ – JS1 Mar 22 '17 at 1:59
  • \$\begingroup\$ @JS1, yes. I can add more if you want to, but I found it to be reasonable. I've changed the generator to std::mt19937_64, and I believe results will be available in a few minutes. \$\endgroup\$ – Incomputable Mar 22 '17 at 2:08
  • \$\begingroup\$ @JS1, update: it slowed down greatly. Thanks for noticing that. I'll get some sleep and post the results after the run will be finished. \$\endgroup\$ – Incomputable Mar 22 '17 at 2:16
  • \$\begingroup\$ @JS1, input range clearly affected the results, but not overall meaning of them: std::sort is still slower in those cases. I might investigate the relation later. \$\endgroup\$ – Incomputable Mar 22 '17 at 3:15
0
\$\begingroup\$

I would think this minor change will improve performance on larger datasets

Original

if (lValue >= pValue) // == is redundant changeto <
   {
    if (lValue == pValue)
       {
        lpivot--;
        std::iter_swap(lpivot, left_it);
       }
    else
       isGreater = true;
   }

   if (rValue <= pValue) // == is redundant changeto >
      {
       if (rValue == pValue)
          {
           rpivot++;
           std::iter_swap(rpivot, right_it);
          }
       else
          isLess = true;
   }

Change to

if (!(lValue < pValue)) // leaving == and >
   {
    if (lValue == pValue)
       {
        lpivot--;
        std::iter_swap(lpivot, left_it);
       }
    else
       isGreater = true;
   }

if (!(rValue > pValue)) // leaving == and <
   {
    if (rValue == pValue)
       {
        rpivot++;
        std::iter_swap(rpivot, right_it);
       }
    else
       isLess = true;
   }

I am going to look at think about how to improve your performance on sequenced data.

Edit: changed !(...) to (!(...))

\$\endgroup\$
  • \$\begingroup\$ Your code is wrong, if a value is less or greater than another, it can't equal that \$\endgroup\$ – Dan Dan Mar 8 '17 at 17:30
  • \$\begingroup\$ @EnigmaMaitreya, I believe there is std::is_sorted (not sure though). That way you can know for sure. \$\endgroup\$ – Incomputable Mar 8 '17 at 18:45
  • \$\begingroup\$ @Incomputable I assume your referencing avoiding the pitfalls of sorting sorted data, that is certainly a valid check. The more I thought about it, the less I was inclined to pursue it as the OP request no design change. \$\endgroup\$ – Enigma Maitreya Mar 8 '17 at 18:57
  • \$\begingroup\$ @EnigmaMaitreya, no, I just wanted to say that you will be able to support the claim of working code by a fact. So, merely for debugging purposes. I'll probably include your code into the benchmark as well, though it will be coming not earlier than tomorrow :) \$\endgroup\$ – Incomputable Mar 8 '17 at 18:59
  • \$\begingroup\$ @Incomputable Do you have reason to believe the code changes I suggested are flawed? If so please give me an "opportunity for improvement" (ofi's are what make the world go round) \$\endgroup\$ – Enigma Maitreya Mar 8 '17 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.