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

You can see how dramatically the actual data changes sort performance in e.g. this (summary of the current unstable sort in Rust, ipnsort)

https://github.com/Voultapher/sort-research-rs/blob/main/wri...

Notice how random_s95 is worse (not by much, but it's there) than fully random. random_s95 is 95% sorted data, but 5% unsorted, simulating a common "sort, do stuff, append, repeat" pattern we see in a lot of software.

In contrast the sorted cases are almost instant, and random_d20 (only 20 distinct values, chosen at random, but as a result the sorted output needs much fewer comparions) is very fast.

When Linus made that comment cmov was like a 6 cycle latency. For the last decade it has been 1 cycle, and I don't think there is any scenario where cmov is now slower than a branch.

Linus was specifically ranting about compilers inserting CMOV. These days it is actually a pain to get GCC or clang to generate a CMOV when you specifically want it.

Also, CMOV did indeed get significantly better.

Yes, that is correct.

Intel was so embarrassed by the failure of itanium they invented a Time Machine and went back and added the instruction to a 1995 CPU. Deceptive and anti-competitive!

Wouldn't the sensible lower level primitive be Clang's __builtin_unpredictable? If you standardize that then a librry can easily build your select function on top of it. I guess GCC's __builtin_expect_with_probability with probabilily 0.5 should have the same meaning.

Will we see x86 or similar CPUs replace hot instruction blocks with current-processor-specific optimized code during runtime, similar to how certain JIT VMs do?

What I mean is, say you have a similar simple "x = (cond) ? a : b;" which the compiler has not translated to a CMOV.

If this is in a hot loop then the CPU could, in theory, notice that "it's just doing a conditional move, I can do the CMOV faster" and then translate those code bytes at that memory location to a CMOV instead (ie during decoding or something like that).

Not worth the complexity? I imagine it would slow down the decoder or wherever they insert this replacement logic. Or am I hopelessly out of date and they're already doing this?

There’s a well-known in-place implementation of swap of the form:

  a ^= b
  b ^= a
  a ^= b

(Here ^ denotes bitwise XOR)

Allowing for the mask, one could do an in-place version of swap_if via

  a ^= (b & mask)
  b ^= (a & mask)
  a ^= (b & mask)

The in-place version of swap is generally discouraged because compilers are smart (https://stackoverflow.com/questions/36906/what-is-the-fastes...) but I do wonder whether the masking in swap_if obscures intent to the compiler enough to close the gap.

Assuming the mask is passed in, Godbolt puts OP’s swap_if at 26 instructions, versus the above swap_if at 17 instructions: https://godbolt.org/z/Wedco5hPv

This sort of use of turning conditionals into bitmasks and then shuffling masked values around was fairly common back in the day when writing code for SSE intrinsics.

You wouldn't want to have to check each lane individually since that would spoil the point of using SSE. So you'd write masking ops like this and keep things parallel, tThen judiciously use any() and all() type intrinsics to check whether the lanes could agree to skip certain blocks conditionally.

(This was before ISPC and before autovectorization to handle it for you.)

Use inline assembly or intrinsics. Read the code of stuff that does these things.

Resources sufficient for implementing simdjson or similar vectorized parsers: https://www.intel.com/content/www/us/en/docs/intrinsics-guid... https://lemire.me/blog/ http://0x80.pl/articles/

There are three approaches:

1) Use intrinsics, if your platform provides intrinsics for the instructions you want to use.

2) Use inline assembly (which I suppose doesn't technically count as writing C code, but is very much part of the story).

3) Write C code carefully against a chosen compiler with chosen optimization flags, and inspect the assembly. Especially for small chunks of code, a tool like godbolt.org is indispensable. Basically, you're writing the assembly you want the compiler to generate (either explicitly, or just in your head), then writing C code that seems likely to generate that sequence of instructions, then tweaking the code until the output you want is generated. If this is a super important optimization, it's also reasonable to add a build step that inspects the generated assembly and fails the build if it doesn't match the desired pattern; but in that case, writing inline assembly is usually easier.

I would say it is a moving target if the goal is to write C code that compiles to a seemingly magical cpu instruction. As other have pointed out, learning assembly and compiler explorer are useful things.

As a way to show the wonderful complexities of compilers check the TOC of https://shop.elsevier.com/books/optimizing-compilers-for-mod...

Convenience is the kind of thing a man values when he isn't pushing against any fundamental limits imposed by the universe. You have to work on computing frontiers like LLMs where people are feeling a performance crunch. Measuring things is what separates software engineering from computer programming. Computer science degenerates into social science when your computer is 100x faster than the thing you're building, since then you have no need to measure things. Without extreme self-imposed discipline, your work in that kind of environment will spiral into bloated decadence, unless you move on to the next computing frontier.

the article does mention this:

> What can we conclude from this discovery? 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.

it's true that it's not a common case, but it's probably the simplest objectively justifiable case; any particular case of the others requires more elaborate justification for privileging it. why 90% sorted instead of 80%, say? or why do we give 20% weighting to the randomized-data case and 80% weighting to the 90%-sorted case, rather than some other weighting?

and it does at least guarantee exploration of a good part of the algorithm's behavior space. i mean, bogosort is optimal on fully-sorted data, right? as long as you do the check for sortedness before the random shuffle instead of after it

it's important that your sort not explode on mostly-sorted or mostly-reverse-sorted data (myers's 'bog-standard quicksort' uses the last element as the pivot and consequently goes quadratic), but beyond that, the particular weighting of relative importance to assign to random input vs. 99% sorted vs. 90% sorted vs. 90% reverse sorted—that requires some application-specific justification

aside from the ones you mentioned, another interesting case is a large array of records that all have equal keys. median-of-three quicksort or random-pivot quicksort does fine on mostly- or fully-sorted data, but still sucks when everything is equal!

True. You would think it's maybe not that hard to find a real dataset to sort somewhere.

Belatedly changed from http://cantrip.org/sortfast.html. Thanks!

From the article - "This radix sort would be easy to make even faster. Instead, let us make one that is slower"

The radix sort was used to provide an estimate for how much better the quicksort could improve.

Which of course makes it ironic that it says "We ought to be able to sort pretty fast, by now, using a Standard Library sort."

The C++ standard promised (since 1998) that the provided sorts are O(n log n).

But in fact popular C++ implementations ignored this and shipped quicksort - after all it's "pretty fast" but unfortunately this means if bad guys can choose your input (or you get unlucky) you get O(n squared)

Gradually they fixed this, libc++ updated to Introsort (last century's best attempt to do this) in 2021. In response to a ticket opened by Orson Peters.

These days you're also starting to see a trend towards the Rust-style "fast sort which implements a wide contract" design even in C++ implementations. Rust's sort doesn't actually promise this wide contract arrangement, but it does promise safety and the wide contract turns out to be the simplest way to do that.

What I mean there by "wide contract" is that these sorts don't blow up if your ordering rule is nonsense. They can't "sort" successfully because your ordering rule is nonsense, if A > B && B > A then too bad, we can't sort A and B. But they can and do gracefully give up, while many older C++ stdlibs just cause uncontrolled mayhem in this case.