The number of comparisons needed to sort a shuffled array: qsort vs. std:sort | Hacker News Reader

The number of comparisons needed to sort a shuffled array: qsort vs. std:sort

lemire.me

27 pointsingve26 comments

Very interesting! Cool that the C library holds its own, heh.

One very minor quibble is that the C function contains the "counter++;" statement to increment the benchmarking counter, but the corresponding C++ function does not. Mildly confusing but probably just a sign that the code in the article is not necessarily the code that ran for the tests.

Also, very good to showcase the slightly non-intuitive use of memcpy() here. It is compiled out [1] but a very "safe" way to grab data across types. Now if only he omitted the parentheses for non-type name arguments to sizeof ... :)

[1]: https://godbolt.org/z/dc7nMEY3n

I'm guessing that even though std::sort calls compare slightly more, it'll be faster, since the compiler has available the sort function, the comparison function and the types. In C, the call to qsort is just a normal function call; and likewise, from within qsort, the call to the compare function is just a normal function call, and the indexing operations have to use the size value that's only known at runtime.

is casting to (double*) unsafe in this case and are there platforms where using memcpy would be slower because the compiler doesn't know the data is correctly aligned? i see in x86-64 its using movsd which allows for both aligned and unaligned access, with unaligned access just being slower.

Casting from any T* to void* back to T* is always safe. That is one of the few safe things you can do with a void*, and kinda the whole point. :-)

I think casting from void* back to double* is the better option here. memcpy() is overkill here since that idiom is mainly for reinterpreting data with a different type without triggering undefined behavior: https://stackoverflow.com/questions/98650/what-is-the-strict.... We're not changing the type, so why confused people with an overly powerful idiom? That said, the memcpy() idiom is common and useful enough that C++ added a specific API for it: https://en.cppreference.com/w/cpp/numeric/bit_cast.

Casting and the memcpy() idiom compile down to the same code https://godbolt.org/z/xY6W9ja69*

Casting from any T* to void* back to T* is always safe.

Are you sure this also applies to function pointers?

Casting should be safe as far as I know, the point of void pointers is the ability to point at any kind of data.

Not sure about the platform question, I tried building it for a Cortex-M3 (32-bit "small" ARM) but that still doesn't issue the memcpy() call. Instead it just loads pairs of words from memory then moves those into the FPU for comparison. The loads are marked with "@unaligned" but not sure what that actually means and didn't spend the time to research it now.

[1]: https://godbolt.org/z/PGTb8abP8

> Casting should be safe as far as I know

I assume you're talking about this:

    long x = <whatever>
    double y = *(double*)&x;

Nope, it is undefined behavior, with few exceptions, even if sizeof double == sizeof long. See https://stackoverflow.com/questions/98650/what-is-the-strict...

If you got rid of this rule a huge number of optimizations would be lost, since the compiler would have to assume that any memory, of any type, could change if anything at all is modified through a pointer. You'd be surprised how slow everything would be. You'd also be surprised how much code violates this and gets away with it. Time bombs waiting to happen. ;-)

memcpy(), and more generally accessing bytes through char*, are how you avoid this kind of undefined behavior. It comes up so often that C++20 added std::bit_cast for this same use: https://en.cppreference.com/w/cpp/numeric/bit_cast

I think he's referring to the cast: (double*)->(void*)->(double*) which should be fine. I'm guessing the original article author prefers using memcpy because there doesn't seem to be any performance cost and its correct in other situations where the alignment is wrong, or there is type aliasing. The advantage would be if you always use a safe method in a code base then you don't have to worry about proving that possibly unsafe methods are safe.

No, in this context (a qsort() comparison callback) I'm talking about using casts to access the values to compare.

Here's how I would have written it, without memcpy():

    static int cmp_double(const void *va, const void *vb)
    {
       const double a = *(const double *) va, b = *(const double *) vb;
       return a < b ? -1 : a > b;
    }

I know you can't "jump types", but this doesn't, since qsort() is passing pointers to doubles and we're just getting them back.

Edit: missed const:s in function body oops.

Switching among godbolt compilers (at optimization 0) ... gcc on less common architectures (like esp32, risc32 or msp430), icc, and msvc don't optimize out the memcpy.

Yes, you're right in that casting an arbitrary void * to double and dereferencing would be unsafe, but in this case, the void pointers point to doubles by construction, so they must be aligned

Is this even comparable? I mean, for C you have a three-way comparison and for C++ there is only a two-way comparison.

If you run the code by yourself you end up that C (while calling the compare() less often than C++) needs more comparisons (i.e. more '<' and '==') kinda defeating the argument of costly comparisons:

  N = 2**16:
  qsort comparison calls 14.735568
  qsort comparisons 22.103386
  std::sort comparisons 19.294233

If you sort primitives then three-way maybe just two two-way comparisons. But when you use lexicographic ordering of strings or of multiple fields, then two-way will need to use three-way comparisons internally to know whether it is done or needs to move on to the next field/character. In this case three-way and two-way comparisons have almost the same cost.

Edit: For primitives we can also consider what happens in the processor. A comparison consists of two parts. First loading the operands and comparing them (loading is the expensive part here), and then a conditional branch instruction. A three-way comparison only loads the operands once and so has the same memory pressure but it does put more stress on the branch predictor. Not quite twice though, because the second branch instruction will only be encountered about half the time, and it will usually take the same path as elements are usually not equal.

Was about to post the same sentiment:

C++ compare function:

    compare(double, double):     # @compare(double, double)
        ucomisd xmm1, xmm0
        seta    al
        ret

C compare function:

    compare:           # @compare
        movsd   xmm0, qword ptr [rdi]           # xmm0 = mem[0],zero
        movsd   xmm1, qword ptr [rsi]           # xmm1 = mem[0],zero
        movapd  xmm2, xmm0
        cmpneqsd        xmm2, xmm1
        movq    rcx, xmm2
        and     ecx, 1
        ucomisd xmm1, xmm0
        mov     eax, -1
        cmovbe  eax, ecx
        ret

Nice data point. This is also relevant beyond qsort vs std::sort. Some implementations of Quicksort use a 3-way partition to save work for skewed inputs (if the pivot occurs often, no need to recurse for all those values).

We have found that in the SIMD context, those two comparisons are expensive enough to make this no longer worthwhile. We instead special-case subarrays with one and two unique values, which can be about 4x as fast on real data vs uniform-random data.

Not that std::sort can take advantage of it (AFAIK), but a three-way comparison (spaceship) operator <=> was added to C++20.

from TFA

>>> compare is a function which returns an integer less than, equal to, or greater than zero if the first argument is less than, equal to, or greater than the second. Because it is a C function, it takes in void pointers which we must convert back to actual values. One safe way to achieve such a conversion is through the memcpy function.

wait, what? why do you need to copy the memory??? can't you just cast to (double*) and deference???

It might be an hypercorrection. memcpy is a safe way to do type punning, but no punning is necessary here as the pointee was originally a double so the cast back and dereference should be perfectly safe.

edit s/pointer/pointee

Yep, this works just fine:

int compare(const void *a, const void *b) { return *(double*)a - *(double*)b; }

Maybe due alignment, on ARM unaligned dereference would crash if I remember correctly. So it's safe to copy the value first and use that aligned memory for the comparison.

That would imply that the input array given to qsort was misaligned. I don't think alignment is an issue in the comparator.

Yeah, I'm pretty sure you're right, the author might just be cargo culting here

Worth noting that the author, Daniel Lemire, wrote the great and incredible fast libraries simdjson and simdutf.

Radix sorting with no key comparisons:

https://bugfix-66.com/834f0677c85b23c0bf1047d3654ab7c27ff054...

std::sort is implemented using introsort [1] which trades off average case complexity for worst case complexity. If you are really chasing performance gains then these are the things you need to look into.

[1] https://en.wikipedia.org/wiki/Introsort

Just goes to show that counting comparisons doesn't tell you all you need to know about a sort.

There are of course faster sorts than std::sort, such a pdqsort, if you are really pinched. Usually you are not.

Reply on news.ycombinator.com