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.
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.
else *rwr-- = x;
No. Make that obvious and the PR can pass. Argue, and you're off the project.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.
bool v = BLQS_CMP(x, piv);
int* ptr = v ? lwr : rwr;
*ptr = x;
ptr += int(v) * 2 - 1;
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.
Can you do the same on the windows kernel or apple kernels?