Fast quicksort implementation

Question

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)

Answer 1

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).

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.

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.

Answer 2

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 (!(...))