Do low-level optimizations matter? Faster quicksort with cmov (2020)

A correction to the history mentioned in the article: CMOV has not been added by AMD around 2000.

CMOV has been added by Intel in 1995, to Pentium Pro. It was the most important addition to the x86 ISA added by Pentium Pro. So CMOV was supported by Pentium Pro and its successors, like Pentium 2 or Pentium III, but it was not supported by Pentium, Pentium with MMX or AMD K6 CPUs. AMD has added CMOV starting with Athlon, in 1999.

Pentium Pro was the first Intel CPU with out-of-order execution and it did much more speculative execution than its predecessors. Therefore it had the need for CMOV to limit the performance loss caused by branch mispredictions.

The most important bit of this is in the conclusion:

  Before we conclude anything, we should remind ourselves of its limitations. The tests run were on completely random data. Truly random data seldom occurs in real life.

Linus famously ranted about CMOV in https://yarchive.net/comp/linux/cmov.html (2007, so potentially more modern architectures are better at some of this) and he says:

  if you KNOW the branch is totally unpredictable, cmov is often good for
  performance. But a compiler almost never knows that.

As usual with optimizations like this you have to benchmark and even then if your sample isn't representative it might not mean much.

> Back in 2000, AMD included cmov in its 64-bit x86 ISA extensions. Then, Intel had to adopt them when Itanium flopped.

Wasn't "cmov" one of the things added for the pentium pro? So it wasn't instruction compatible - hence the "i686" prefix to a lot of compiler triples?

Rather than std::swap_if which is rather niche, I would prefer to see std::select(cond, if_true, if_false), with the guarantee that unlike the ternary operator it eagerly evaluates both arguments and selects between them branchlessly if possible.

Something similar is coming to Rust as well: https://doc.rust-lang.org/nightly/core/intrinsics/fn.select_...

I would expect eliminating branches in a busy inner loop to matter.

The interesting part is how that was done:

> A New Primitive, swap_if

> How can we use this method in our sort? First, let us make a swap_if:

  inline bool swap_if(bool c, int& a, int& b) {
    int ta = a, mask = -c;  // false -> 0, true -> 111..111
    a = (b & mask) | (ta & ~mask);
    b = (ta & mask) | (b & ~mask);
    return c;
  }

> In our partition function, then, we can transform

    if (*right <= pivot) {
      int tmp = *left; *left = *right, *right = tmp;
      ++left;
    }

> into just

    left += swap_if(*right <= pivot, *left, *right);

> I call this bog-standard, but the quicksorts most easily found online are always oddly pessimized, both more complicated and slower. This one uses the “Lomuto partition”, which is simpler than Hoare’s.

The Lomuto partitioning is a naive vandalism of Hoare's original, which causes quicksort to have quadratic behavior on sorted input.

Fascinating! How does one learn to write C code that will make use of specific asm instructions?

SIMDjson is another example that comes to mind. The conceit of C is that you do t have control over the underlying machine instructions without inlining it yourself. So how do people write C code with cpu optimizations like this?

Heh, nice! This article reminded me of a great talk I recently noticed:

Rethinking Binary Search: Improving on a Classic with AI Assistance: https://www.youtube.com/watch?v=FAGf5Xr8HZU

The gist is rather simple: Assuming that a substiantial amount of your searches results in no result, you can bias the binary search to jump farther then just half, improving runtime noticeably.

Matter to whom?

If your primary audience is other developers then it absolutely does not matter. In fact it’s a way to expose deep anger. All that matters is convenience and measurements just piss people off, because measuring anything is just too hard.

If your primary audience is business, especially transactional finance, then absolutely yes. Squeeze absolutely every millisecond out, measure absolutely everything in terms of transaction quantity, focus on concurrent operations.

Note that random data is not a common case for sorting algorithms. It'd be interesting to see how the numbers change on partially-, mostly-, and fully-sorted data.

It’s weird to admit that this is an arbitrary dataset that doesn’t mimic real-world use cases, then admit that radix sort is far faster for this situation, then conclude that low-level optimizations are important and a cmov-wrapper should be added to the standard library to make programs faster. It’s a great post I just disagree with the conclusion.

Here's the article linked as https; I'll email the mods.

https://cantrip.org/sortfast.html

The radix sort implementation is not optimal. Instead of sorting 1 digit at a time, it should be sorting 11 digits at a time to saturate the cache lines.

So the baseline radix sort can be even faster.

(2020)