qsort vs. std::sort

When you have an array with some data structure that you would like to sort, you are looking for a sorting algorithm in the standard library.

In C, you have the qsort function which has a pretty cumbersome declaration:

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

So you have to pass a pointer to your container, pass the number of elements in the container, pass the size of each element and a comparator function.

Bjarne Stroustrup asked the questions which seem natural when you are used to C++ in a talk about C++11:

• Why doesn't the container know its size?
• Why doesn't the container know the size of its elements?
• Why don't the elements know their order, the way to compare them to each other?

Additionally, the void * in the comparator function mean that type safety cannot be enforced by the compiler, which is bad.

Since the function is passed as a pointer, and the elements are passed as pointers as well, it means that each comparison costs three indirections and a function call. In C++, the std::sort is a template algorithm, so that it can be compiled once for each type. The operator< of the type is usually baked into the sort algorithm as well (inlining), reducing the cost of the comparison significantly.

As Stroustrup pointed out in his talk, people sometimes think that qsort must be faster, since it is C, which is supposed to be the fastest language you can get. The fact that the declaration of qsort is cumbersome tells those people that it is even faster.

Test programs

I want to sort a container of simple floating points numbers. That way, the actual comparison is a really fast operation and the overhead will be seen dramatically.

In C, this is implemented using a dynamic array, a comparison function and the qsort function. I only show the relevant parts here, you can find the full code for this example on GitHub.

int compare(void const *this, void const *other) {
    double const a = *((const double *)this);
    double const b = *((const double *)other);
    if (a < b)
        return -1;
    else if (a == b)
        return 0;
    else
        return 1;
}

The sorting is then done using the qsort function:

qsort(data, size, sizeof(*data), compare);

I have generated files with random numbers in them such that the sorting would have some actual work to do.

You can see that the information regarding the container and its contents are split across several blocks. You have the size, the data and the compare function.

In C++, I use that there exists an operator< for int and the std::sort function. So we only need to actually use it:

std::sort(std::begin(data), std::end(data));

I find that the C++ version is very clear on intent. This is a thing where I prefer C++ over C.

This is compiled with a sufficiently new standard as well as full optimization:

-Wall -Wpedantic -O3 -march=native

Results

The sorting is repeated from 10 numbers to 10 million numbers. The C and C++ programs translated with the GCC and LLVM compilers scale like the following:

It is very curious to see that for small lengths, the GCC versions are faster then the LLVM versions; the language makes the smaller difference! For more items, the C++ version is faster with both compilers.

Taking the appropriate ratios, one can compare GCC with LLVM and also C with C++ here:

For small data sets, one cannot really say anything, the statistical fluctuations are just too large. For large data sets, there is not much of a difference between GCC and LLVM. There is, however, a difference of a factor 1.9 between C and C++, the C version is slower than the C++ version.

Conclusion

The main point is that the C++ version is way faster than the C version, although the C++ version is more elegant. With C++, you can express your intentions more clearly, helping the compiler to optimize your program. Trust your optimizer!