The computation is the same, but apparently, this tiny change prevents SimplifyCFGPass from turning the code into the branchless version later on. I'm not sure why this happens, perhaps because it messes something up in the pattern recognition of the pass?

So yeah, as you say, compilers can be very sensitive to this, and in the past (although more than 10 years ago now, so might not be relevant now), ICC often used to generate better (faster executing) code when using "val += 1" vs "++val".

  *lwr = x; lwr++;

  block
    statement (assignment)
      expression
        operator (dereference)
          variable
      expression
        variable
    statement
      expression
        operator (post-increment)
          variable

  *lwr++ = x

  block
    statement (assignment)
      expression
        operator (post-increment)
          operator (dereference)
            variable
      expression
        variable
 

As for why the second form is faster (or rather, why the compiler can generate faster code): There is likely an optimisation pass somewhere in llvm that recognises a pattern that this fits into, which allows it to generate branchless instructions. For instance, in the second form, there is a pattern of:

  operator (post-increment)
    operator (dereference)

Finding which pass that is can be non-trivial, as it's more than a matter of enabling individual passes until one works. It might be that an earlier pass does some code reshaping that allows the relevant pass to work. My suggestion would be to dump the llvm ir at the end, and find the rough pattern that you're looking for, then re-run the compilation with `-mllvm -print-after-all` to see what the IR looks like after each pass, and then manually "look back" until you can't see the pattern any more.

Edit: not saying they are different just that it is harder for the compiler to see the safety of the transform when they are quite different.

You can ask the compiler to dump its intermediate representations, so it might not be too hard to answer the question.

Why restrict the optimisation unnecessarily like this? It's never the intention to artificially restrict optimisations, but they are difficult to test and debug as they can interact with other optimisations, and applying an optimisation too broadly leads to horrible correctness bugs. So if you cannot be certain that you understand all possible interactions now and in the future, it makes some sense to be conservative in applying them.

    else{
        *rwr--=x;
    }

Both versions sort the same data using the same algorithm. Just a tiny change in the source code caused Clang to generate different machine code.

Using different seed values - (srand(1), srand(2), srand(time(NULL))) essentially leads to the same result. With a good choice of pivot, Quicksort is very close to O(n log n) in practice, so that’s not the key factor here.

The interesting thing is that the generated machine code changes significantly.

Most software introduces a large number of unnecessary stalls where one part of the hardware is waiting on or bottlenecked by a different piece of hardware. Optimization is often about removing or minimizing these stalls to the extent possible. But to do this you need to understand why specific code choices cause the hardware to stall in the first place. The most basic form of this is CPU cache locality but there are many levels.

Compilers are great at localized micro-optimizations, except for SIMD. Most idiomatic code can be detected and transformed by the compiler into something that takes advantage of the hardware design. You don't need to do tricky bit-twiddling stuff, the compiler is better at it than you are in most cases (this wasn't always true). I always recommend people interested in optimization experiment running snippets of code through the compiler using godbolt with optimization turned on. You can learn a lot about how the compiler sees and understands your code by studying this. It is also a good way to became familiar with assembly.

Leveraging SIMD and vector ISAs is a mess. Different hardware architectures rely on different idioms and compilers cannot auto-vectorize most code that can be vectorized. You need to learn the idioms of each vector ISA and how to write them using intrinsics. A great way to learn this is reading other peoples' SIMD code. Modern SIMD code is wide in that you need to memorize a lot of things but conceptually pretty shallow. It mostly comes down to learning the idiomatic tricks and gadgets for an ISA -- code is composed from these conceptual primitives.

Personally I actually haven't read too many books on optimizations, I just absorbed information over years one thing at a time, but something like Computer Organization and Design is a pretty good intro to the low-level picture. If you want to drown in extremely dense technical topics that will give you a lot of jumping off points to search, read Agner Fog's microarchicture optimization guide (https://www.agner.org/optimize/). It won't tell you what LLVM is doing, but it'll tell you why it's doing it. Fair warning, it's dense and pretty dry.

Then it depends how interested you are in doing low-level nonsense. If you spend a lot of time writing performance oriented systems code, you'll come to use profiling tools that show you the assembly. If you stare at it long enough, you sometimes start to question why the compiler wrote it this way. And you're naturally led as you try to optimize your code to wonder how LLVM is coming up with this ASM that it spits out and why it sometimes gets it wrong.

There's nothing magical or that requires innate talent. You can learn all of this very naturally if you work close to the metal and take the time to question how the abstraction layer below you actually works. If you keep doing this, you eventually find out it's not that deep, it's just a lot of stuff accumulated over time, but none of it particularly difficult or inaccessible.

In this specific instance, at the hardware level it helps to understand how the branch predictor works and why quicksort in particular is essentially the worst case for the branch predictor, and then you'll understand why the cmov/csel optimization is such a big win.

In general, you must expect to try ten things and then one of them will help you; fewer if your ideas are bad. :-) Occasionally, you learn new things (either about your machine or your language or your code base) and then you can try that elsewhere in the code (but don't go overboard, every technique has its limits).

DO NOT FALL PREY TO SUPERSTITION. Always measure in one way or the other. Don't do stuff blindly just because someone on the Internet told you (there's a _lot_ of bad performance advice out there).

1. If you write CRUD apps, make sure that the database does the heavy lifting.

2. Take note of algorithm complexities, use hashtables as appropriate, and write good hash functions when you start using hashtables/dictionaries.

3. Avoid pointer-heavy datastructures. In high level languages like Java, an object reference is a pointer dereference that can stall the CPU waiting for memory. This is sometimes optimized, but you can’t depend on it. The true zealots call this “data oriented design”.

4. If you write C/C++,rust, or the like, you might want to learn to read assembly. Godbolt.com is a fun way to learn. Note that not all instructions are equally fast: Long division and trigonomic functions are slower than integer adds, even when they are both a single instruction.

5. The next level is probably going for vectorized instructions: SIMD (ARM Neon, AVX). The most original applications can be found at lemire.me: a professor exploring optimizing things like JSON parsing using the latest processor features.

Second step is to actually make it faster.

And I would say 99% of the time you can make applications faster without going down so deep on this low-level (which is still not easy) but sometimes you can only get faster via low-level optimizations.

https://www.grc.com/inspectre.htm