4 ms·

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

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

im3w1l 4y ago
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.
Quekid5 4y ago
Not that std::sort can take advantage of it (AFAIK), but a three-way comparison (spaceship) operator <=> was added to C++20.
secondcoming 4y ago
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
- janwas 4y ago
  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.

im3w1l 4y ago

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.

Quekid5 4y ago

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

secondcoming 4y ago

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

janwas 4y ago
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.