Hacker News Reader

Comment by jokabrink | Hacker News Reader

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

View on HN

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.

Reply on news.ycombinator.com