Your Code Is Fast Only If You Are Lucky: A Quicksort Lesson
Your code is fast – if you're lucky
I discovered that modern compilers like Clang only generate optimal branch-free code if you write in a very specific style. My initial Quicksort implementation was surprisingly slow compared to C++ std::sort, but rewriting simple pointer logic into a more idiomatic C form unlocked massive performance gains. This experience proves that code speed often depends on luck and stylistic choices rather than just algorithmic efficiency.
Modern compilers optimize loops using fast, branch-free instructions - provided you use the right programming style.
- fsmv
But it's not exactly a cosmetic change. x++ is semantically different from x; x++; I wonder if clang would make it branchless if you instead write
if (BLQS_CMP(x, piv)) { *lwr = x; ++lwr; }
else { *rwr = x; --rwr; }
The difference is post-increment has strange semantics. While the compiler should be able to understand that the value wasn't used and post increment and pre increment are the same I wouldn't be surprised if it tracks that it was post increment and misses some optimizations because it's trying to garuntee post increment semantics.
Although it's true compilers can be very sensitive to exact phrasing triggering specific optimization passes. So it still might not give the branchless version by changing it to pre increment (which is the same as a normal +=1).
The only way to really know is to dig into what optimization passes clang took in both cases and analyze the difference.
- jdw64
I really envy programmers who are so skilled at this kind of low-level optimization.
The same meaning, but different performance based on notation—it's ultimately about entering LLVM's optimization pass, which likely comes down to differences in the internal IR pattern. It almost feels like a difference in innate talent...
I feel like I can build CRUD applications well enough, but I still seem to be weak at low-level processing.
Where can I learn these kinds of techniques? I'd appreciate any book recommendations.
- jimaway123
Does anyone know exactly what is going on here to cause this difference? I am extremely puzzled that the "beginner friendly" code is not at some point in the compilation pipeline in EXACTLY the same representation as the non-"beginner friendly" code. I would imagine they'd be in the same form very early on, perhaps even at the point of generating an initial syntax tree. And once they take on the same form in the compilation pipeline, the resulting compiler output should be identical. So what is really going on here?
- xlii
Is it only me..?
Quicksort is supposed to be an algorithm that has O(n) to O(n²) performance and O(n log n) being only an average performance case. Test was made on random data coming from different archs (so I doubt it's characteristic would be remotely identical).
Given input size of 50M it means that performance could be between 50M (5e7) up to 2.5e15. That's like performance instability of 8 orders of magnitude.
I'm not sure here if we can't write instead that "Your code is fast if you picked fast case for it" especially since fix of 6 OOM is smaller than algorithm's performance range.
- shevy-java
My code is not fast. Writing efficient code takes a lot
of brain power. My brain is of the lazy type - it wants
the computer (but not AI) to solve things. I only write
code so I can be lazier lateron.
I think with this approach, we will only win if a language
allows for:
1) ease of writing, and
2) fastness
Right now languages don't really combine both. We have
ease of writing e. g. ruby or python, but they are slower
than C, our godfather language. So far all languages that
try to solve both problems, become mega-verbose and tend
to gravitate more towards one than the other - usually
e. g. "let's write a replacement for C". I wonder if
combining both 1) and 2) is possible, kind of like select
on your own what to combine, so if my time is precious,
I write a quick prototype. If this must become faster,
I write it with more details. That's still not really
a language that combines 1) and 2) genuinely but perhaps
it is an acceptable trade-off. Right now we kind of mix
two languages here, say, ruby+java or python+C or any
other similar combination.