4 ms·
The number of comparisons needed to sort a shuffled array: qsort vs. std:sort
- unwind 4y agoVery 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 https://godbolt.org/z/dc7nMEY3n
- benmmurphy 4y agois 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.
- unwind 4y agoCasting 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 https://godbolt.org/z/PGTb8abP8
- ksherlock 4y agoSwitching 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.
- mattarm 4y ago> 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-aliasing-rule 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 https://en.cppreference.com/w/cpp/numeric/bit_cast
- benmmurphy 4y agoI 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.
- unwind 4y agoNo, 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.
- scaredginger 4y agoYes, 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
- mattarm 4y agoCasting 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-aliasing-rule 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 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 https://godbolt.org/z/xY6W9ja69*
- Teckla 4y agoCasting from any T* to void* back to T* is always safe. Are you sure this also applies to function pointers?
- mort96 4y agoI'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.
- _ZeD_ 4y agofrom 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???
- cryo 4y agoMaybe 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.
- strager 4y agoThat would imply that the input array given to qsort was misaligned. I don't think alignment is an issue in the comparator.
- scaredginger 4y agoYeah, I'm pretty sure you're right, the author might just be cargo culting here
- gpderetta 4y agoIt 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
- cochne 4y agoYep, this works just fine: int compare(const void *a, const void *b) { return *(double*)a - *(double*)b; }
- jokabrink 4y agoIs 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
- im3w1l 4y agoIf 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.
- Quekid5 4y agoNot that std::sort can take advantage of it (AFAIK), but a three-way comparison (spaceship) operator <=> was added to C++20.
- secondcoming 4y agoWas 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
- barbegal 4y agostd::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 https://en.wikipedia.org/wiki/Introsort
- lsbehe 4y agoWorth noting that the author, Daniel Lemire, wrote the great and incredible fast libraries simdjson and simdutf.
- bugfix-66 4y agoRadix sorting with no key comparisons: https://bugfix-66.com/834f0677c85b23c0bf1047d3654ab7c27ff05482195908116d49cca52bb593df https://bugfix-66.com/834f0677c85b23c0bf1047d3654ab7c27ff054...
- ncmncm 4y agoJust 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.