alt Hacker NewsYour code is fast – if you're lucky
Comments
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?
else *rwr-- = x;
Coincidentally a few days ago, also for a sorting algorithm, I stumbled over a situation where replacing the branchless cmov with branching instructions actually made the code 30% faster: https://github.com/graphhopper/graphhopper/pull/3380 Or at least the AI explained it this way to me, but I'm unsure if this is correct.
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.
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.
What if you wrote this in a branchless way?
bool v = BLQS_CMP(x, piv);
int* ptr = v ? lwr : rwr;
*ptr = x;
ptr += int(v) * 2 - 1;
Auto-vectorization is not a programming model!
Don't forget to disable all "spectre and friends" mitigations in your linux kernel, and some workloads will become much faster.
Can you do the same on the windows kernel or apple kernels?
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.
Wow that is quite surprising. Almost seems like it could be a compiler bug tbh. Very fragile optimisation if not!
[dead]
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
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.