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.
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.
The Big-O for sorting algorithms is typically on the number of comparisons. The problem with that is that a comparison takes 1 cycle and you can do 4 per cycle in scalar code or much more in SIMD. Obviously comparisons of doubles are going to be a bit more expensive. Memory reads, on the other hand, take 4 cycles from L1, 10 from L2, and it goes up from there. If you have a predictable memory access pattern, the CPU can preload everything into cache for you, and if you have a deep enough pipeline you can cover up memory reads. Memory access is often completely ignored when analyzing sorting algorithms.
Heapsort has the minimum number of comparisons. Search up "An optimal algorithm for deleting the root of a heap" by Svante Carlsson. Notice how Heapsort is commonly used only as a fallback sort? That's because minimizing comparisons isn't the most important.
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?
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.
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.
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.
14 comments
[ 2.9 ms ] story [ 31.7 ms ] threadThe 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.
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.
Heapsort has the minimum number of comparisons. Search up "An optimal algorithm for deleting the root of a heap" by Svante Carlsson. Notice how Heapsort is commonly used only as a fallback sort? That's because minimizing comparisons isn't the most important.
Can you do the same on the windows kernel or apple kernels?
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.
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.