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

by fanf2 • 2 years ago

174 75 2 years ago

mbroncano• 2 years ago

(2020)

tialaramex6• 2 years ago

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.

gpderetta9• 2 years ago

I'm pretty sure that introsort was already implemented in the original STL last century.

In fact the standard didn't require O(log n) untill C++11 as all implementations were already using introsort, so allowing the previous more permissive O(n^2) bound was no longer necessary.

karmakaze• 2 years ago

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);

magicalhippo3• 2 years ago

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?

akira2501• 2 years ago

I think it could only do that in spans of code where interrupts are disabled and purely between values already in registers. CPU state feels like it's in your control, but it's not at all in your control, and even if it was, multiple processes might exist and memory is never in your control.

saagarjha• 2 years ago

Whether to use a branch or a conditional move isn’t really dependent on what the source is doing but how likely the branch is and its dependencies. Simplifying a bit, an explicit cmov is basically telling the computer that the condition is not easy to predict and to not bother. Modern processors will typically do the same analysis themselves and perform similarly on a branch with a slight overhead.

jeffbee• 2 years ago

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?

Wasn't that one of Transmeta's things?

gpderetta9• 2 years ago

Look for "idiom detection". Macro uop fusion is a limited form of this.

As a relevant example, POWER CPUs can convert some non diverging branches into conditional execution if not well predictable.

Many RISC CPUs can convert well known LL/SC code patterns into locked atomic operations to guarantee forward progress.

kevinventullo2• 2 years ago

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

ack_complete• 2 years ago

You have the optimizer disabled and the functions are no-ops. Additionally, masking that way makes the XOR no longer a no-op, so only one masking operation is necessary -- but it seems that GCC already knows this trick:

https://godbolt.org/z/qxMvcbrc8

Someone• 2 years ago

The in-place version of swap is generally discouraged because compilers are smart

Isn’t that more because CPUs slow down when there are dependencies between instructions?

Compilers could (and may even do) fairly easily detect that pattern (like they do with some versions of popcnt. See for example https://langdev.stackexchange.com/questions/3942/what-are-th..., discussed here in https://news.ycombinator.com/item?id=40987123) and compile it to whatever is fastest on the target CPU/in the given context (in some contexts, it can be compiled to nothing, just changing the mapping between local variables and the registers they’re stored in)

a_e_k2• 2 years ago

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.)

djmips2• 2 years ago

Does ISPC + auto vectorization truly remove the need to attend to these details in the most optimized code?

memset• 2 years ago

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?

anonymoushn• 2 years ago

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/

addaon2• 2 years ago

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.

vlovich123• 2 years ago

Option 4 is sometimes compiler annotations like __builtin_expect_with_probability which you could use to assign a branch a value of 50% which should coerce it to pick cmov (same risk as 3 though in that you need to inspect compiler output).

adelpozo• 2 years ago

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...

kimixa• 2 years ago

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?

pbsd• 2 years ago

Yes, that is correct.

tedunangst• 2 years ago

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!

basementcat• 2 years ago

Intel failed to predict the timeline branch in which i686 arch had cmov so they had to roll back and replay it.

dgl• 2 years ago

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.

tialaramex6• 2 years ago

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.

jnordwick3• 2 years ago

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.

haberman• 2 years ago

The problem is not the 1 cycle latency, but the data dependency on both values. A correctly-predicted branch cuts the dependency on the value that is not used.

I've definitely measured scenarios where cmov/branchless is slower than a branch for a given algorithm. Especially if the branchless version is doing a bit more work to avoid the branch.

clausecker2• 2 years ago

Are you sure? I recall cmov always having single cycle latency.

mgaunard3• 2 years ago

a cmov-based approach is necessarily slower than a branch-based approach that was correctly predicted, since cmov requires computing both branches then selecting the result at the end.

gpderetta9• 2 years ago

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.

pcwalton• 2 years ago

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.

kragen• 2 years ago

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!

xiaodai2• 2 years ago

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.

djmips2• 2 years ago

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.

xiaodai2• 2 years ago

but why make a slower one? when a faster one is around? none of the x-times analysis make any sense now.

orlp2• 2 years ago

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_...

account423• 2 years ago

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.

gpderetta9• 2 years ago

I guess GCC's __builtin_expect_with_probability with probabilily 0.5 should have the same meaning.

But it doesn't! the sequence 1010101010... has probability 50% that it assumes one or the other value, yet is completely predictable.

adrian_b• 2 years ago

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.

lynx23• 2 years ago

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.

austin-cheney• 2 years ago

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.

jart• 2 years ago

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.

pronoiac• 2 years ago

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

https://cantrip.org/sortfast.html

dang• 2 years ago

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

MatthiasPortzel• 2 years ago

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.

snek_case• 2 years ago

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

kazinator• 2 years ago

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.

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

Related Stories