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’m assuming he measured time by averaging on 100s of instances, or he maintained the exact same input for both versions of code. Would be a big oversight if not!
I ran 10k test locally on 2e5 and I'm seeing 4 orders of magnitude instability, but very high local stability (i.e. runs within specific second are very stable, showing almost no deviation, runs couple second later are the same, but results are within 1 OoM of the prior results (smaller batches, 500 tests).
I'm not saying that optimization isn't valid, what I'm saying is that Quicksort shouldn't be optimized over randomized per run data set.
It's a good rule of thumb that can be quite useful without additional analysis. It's not always the right way to do performance tuning, but I can't count the number of times I've changed an O(n^3) to an O(n) and seen massive performance gains as a result.
Yeah it helps make awful code decent, and some algorithms are better than others, but in terms of high performance code, locality, vectorization, and branching often matter much more big O.
You don't need randomized pivoting for this, there are deterministic ones like median of median that will also result in a O(nlogn) worst case.
Also note that with a randomized pivoting you _might_ hit a O(n^2) worst case, it's just that it's incredibly rare and cannot be forced by an attacker controlling your input, so for most practical purposes can be ignored.
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.
A large part of optimization is understanding the hardware architecture in detail and then making your software architecture mirror that hardware architecture as closely as possible. A compiler can't do this for you. Much of "performance engineering" is applying your understanding of how the hardware components work and are connected to the software design.
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.
You could read compiler books, but I would actually recommend reading about CPUs and computer architecture directly. If you understand how the hardware works, then the optimizations are all very natural and fit into the picture perfectly, instead of being some arcane compiler magic that you have to take as a disconnected fact.
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.
I also agree that computer architecture is more important - it grounds your understanding of how to write efficient code regardless of platform since most machines today share very similar ideas (OOO execution, caches, NUMA etc).
How ever, I will disagree slightly that all the optimizations compilers do are about optimizing for a given architecture; some transformations are just weird algorithmic black magic about optimizing the underlying code itself. Knowing how to make sure the compiler sees through a given construct to give you the low level expression you want is too much art and randomness; we need better ways to express optimization expectations so that if the compiler fails to match expectations it becomes a loud compiler error.
Right. You won't learn from a computer architecture book or a uarch guide about SSA form, or LICM, or other famous compiler principle like the central role of inlining decisions ("the mother of all optimizations"). I don't have a good resource to recommend here, this is where my lack of formal training bites. "Go read a hundred blog articles by compiler experts" doesn't feel like very useful advice.
>Knowing how to make sure the compiler sees through a given construct to give you the low level expression you want is too much art and randomness; we need better ways to express optimization expectations so that if the compiler fails to match expectations it becomes a loud compiler error.
There's a parallel with hardware there. Verilog is a kind of hardware language designed for an abstract simulator, in the same way than C is designed for a standard abstract machine for the sake of portability. You end up with an idea of the assembly/RTL you want the compiler/synthetizer to generate in your head, and then it's a game of writing the right pattern that will be recognized and generate the output you want.
I think this is partially unavoidable, because we're inherently asking the compiler to generate a non-portable target-specific output in what is supposed to be a portable high-level language. If you start injecting compiler hints or requirements in your "portable" code, it all becomes a bit of a mess. Part of the problem is also that the high-level languages we're using were designed at a time were many questions were still unsettled. Things like signed integers being two's complements is a recent change in C and C++. But I think some of it is intrinsic impedance mismatch between high-level code and machine code.
I'm not sure I would like a proliferation of annotations that direct exactly how the compiler should optimize (like "must use cmov/csel here"), because if internal optimizer choices become public API, people will rely on internals in their large legacy codebases. I expect this would be a force that ossifies the compiler and prevent optimizations from improving. The "register" and "inline" keywords in C used to mean something to the compiler. But they were misused, having them be a requirement would have held back performance more than anything.
Then again I accepted the same justification against Postgres planner hints, and now that the idea has been recast as a plan stability feature I'm actually very happy with that idea. I'm uncomfortable with letting old calcified codebases hold back compiler internal, but at the same time once you find a way to have the compiler generate what you want, there's a real need to not have it break silently when you upgrade.
I'm not sure it's a "technique" but the general insight worth taking away from this is that compiler authors often write optimizers to recognize specific patterns so writing your code in a more idiomatic form increases the odds an optimizer will be able to optimize it.
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.
About that kind of 'technique', I guess I should make it a habit to dig into the compiler, which is still a black box to me. I should study a few techniques myself. Have a good day
While the article is interesting, it's the case of a missed optimization by the compiler and (possibly) something that a future version of the compiler will catch.
This sort of optimization is one that'd I'd not spend too much time trying to fix or catch, unless you are doing it for fun or you have a specific piece of code in a hot path that needs to go fast.
Where I'd spend time if I were trying to write very fast code which a compiler is unlikely to get right is SIMD optimizations. Specifically with floating point values.
One thing compilers can't and won't do is reorganize floating point optimizations (well, unless you explicitly give them permission to do that). That means the way you write your floating point code can really nerf performance and exclude you from much faster assembly.
The sure fire way to actually make such code faster is learning and using SIMD expressions. The compilers can sometimes get this right, but it's quite fragile.
I did Nand2Tetris and then I understod why I need to vectorize. You get a view from nand-gate to software and get to see all the interfaces. Its a wonderful course.
Got to my first job out of college and they gave me core dumps and had me debug the kernel for a year. Not my kind of fun, but definitely got me skilled in the art of low level.
Expose yourself to lower level technologies (compilers and optimization techniques, hardware history and design) and let curiosity guide you. Learn how to profile and analyze program performance.
it's arguably more of a cpu bug than a computer bug. The problem is that predictable data determined whether a cmov or a branch is faster. cmov is only faster than if when the branch is unpredictable. Summer the compiler doesn't know what values your program will be called with, it can only pick and hope. To fix this, cpus could have an instruction like cmov but that learns whether speculation would be profitable and converts to treat it like a branch if better.
tbh, I'm not sure if we need "more clever" CPUs since they cause more and more unpredictable performance outcome -- and more pressing issues like Spectre.
Besides, looking at the evolution of technology tells us that performance increases mainly comes from parallelism, like multicore and GPUs. Which doesn't apply to "annoyingly not parallel" problems of course. But besides "gambling" approaches like branch prediction, there's not much you can do about them in the general case.
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’m assuming he measured time by averaging on 100s of instances, or he maintained the exact same input for both versions of code. Would be a big oversight if not!
Looking at big-O isn't very informative. We have plenty of statistical tools for telling whether there is an effect even with noisy data.
I ran 10k test locally on 2e5 and I'm seeing 4 orders of magnitude instability, but very high local stability (i.e. runs within specific second are very stable, showing almost no deviation, runs couple second later are the same, but results are within 1 OoM of the prior results (smaller batches, 500 tests).
I'm not saying that optimization isn't valid, what I'm saying is that Quicksort shouldn't be optimized over randomized per run data set.
You don't happen to be running `srand(time(0))`?
> I'm not saying that optimization isn't valid, what I'm saying is that Quicksort shouldn't be optimized over randomized per run data set.
But yeah, this is correct. When optimizing, we want to pin every variable other than the change, as much as possible.
It's a good rule of thumb that can be quite useful without additional analysis. It's not always the right way to do performance tuning, but I can't count the number of times I've changed an O(n^3) to an O(n) and seen massive performance gains as a result.
Yeah it helps make awful code decent, and some algorithms are better than others, but in terms of high performance code, locality, vectorization, and branching often matter much more big O.
I hope the test data is the same when comparing the different runs. So the big o notation should be the same across different runs.
if you have decent (randomized) pivoting, you never hit the worst case or anything like it
You don't need randomized pivoting for this, there are deterministic ones like median of median that will also result in a O(nlogn) worst case.
Also note that with a randomized pivoting you _might_ hit a O(n^2) worst case, it's just that it's incredibly rare and cannot be forced by an attacker controlling your input, so for most practical purposes can be ignored.
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.
A large part of optimization is understanding the hardware architecture in detail and then making your software architecture mirror that hardware architecture as closely as possible. A compiler can't do this for you. Much of "performance engineering" is applying your understanding of how the hardware components work and are connected to the software design.
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.
You could read compiler books, but I would actually recommend reading about CPUs and computer architecture directly. If you understand how the hardware works, then the optimizations are all very natural and fit into the picture perfectly, instead of being some arcane compiler magic that you have to take as a disconnected fact.
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.
I also agree that computer architecture is more important - it grounds your understanding of how to write efficient code regardless of platform since most machines today share very similar ideas (OOO execution, caches, NUMA etc).
How ever, I will disagree slightly that all the optimizations compilers do are about optimizing for a given architecture; some transformations are just weird algorithmic black magic about optimizing the underlying code itself. Knowing how to make sure the compiler sees through a given construct to give you the low level expression you want is too much art and randomness; we need better ways to express optimization expectations so that if the compiler fails to match expectations it becomes a loud compiler error.
Right. You won't learn from a computer architecture book or a uarch guide about SSA form, or LICM, or other famous compiler principle like the central role of inlining decisions ("the mother of all optimizations"). I don't have a good resource to recommend here, this is where my lack of formal training bites. "Go read a hundred blog articles by compiler experts" doesn't feel like very useful advice.
>Knowing how to make sure the compiler sees through a given construct to give you the low level expression you want is too much art and randomness; we need better ways to express optimization expectations so that if the compiler fails to match expectations it becomes a loud compiler error.
There's a parallel with hardware there. Verilog is a kind of hardware language designed for an abstract simulator, in the same way than C is designed for a standard abstract machine for the sake of portability. You end up with an idea of the assembly/RTL you want the compiler/synthetizer to generate in your head, and then it's a game of writing the right pattern that will be recognized and generate the output you want.
I think this is partially unavoidable, because we're inherently asking the compiler to generate a non-portable target-specific output in what is supposed to be a portable high-level language. If you start injecting compiler hints or requirements in your "portable" code, it all becomes a bit of a mess. Part of the problem is also that the high-level languages we're using were designed at a time were many questions were still unsettled. Things like signed integers being two's complements is a recent change in C and C++. But I think some of it is intrinsic impedance mismatch between high-level code and machine code.
I'm not sure I would like a proliferation of annotations that direct exactly how the compiler should optimize (like "must use cmov/csel here"), because if internal optimizer choices become public API, people will rely on internals in their large legacy codebases. I expect this would be a force that ossifies the compiler and prevent optimizations from improving. The "register" and "inline" keywords in C used to mean something to the compiler. But they were misused, having them be a requirement would have held back performance more than anything.
Then again I accepted the same justification against Postgres planner hints, and now that the idea has been recast as a plan stability feature I'm actually very happy with that idea. I'm uncomfortable with letting old calcified codebases hold back compiler internal, but at the same time once you find a way to have the compiler generate what you want, there's a real need to not have it break silently when you upgrade.
I'm not sure it's a "technique" but the general insight worth taking away from this is that compiler authors often write optimizers to recognize specific patterns so writing your code in a more idiomatic form increases the odds an optimizer will be able to optimize it.
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.
About that kind of 'technique', I guess I should make it a habit to dig into the compiler, which is still a black box to me. I should study a few techniques myself. Have a good day
While the article is interesting, it's the case of a missed optimization by the compiler and (possibly) something that a future version of the compiler will catch.
This sort of optimization is one that'd I'd not spend too much time trying to fix or catch, unless you are doing it for fun or you have a specific piece of code in a hot path that needs to go fast.
Where I'd spend time if I were trying to write very fast code which a compiler is unlikely to get right is SIMD optimizations. Specifically with floating point values.
One thing compilers can't and won't do is reorganize floating point optimizations (well, unless you explicitly give them permission to do that). That means the way you write your floating point code can really nerf performance and exclude you from much faster assembly.
The sure fire way to actually make such code faster is learning and using SIMD expressions. The compilers can sometimes get this right, but it's quite fragile.
Casey Muratori's https://computerenhance.com is a good resource
thanks!
I did Nand2Tetris and then I understod why I need to vectorize. You get a view from nand-gate to software and get to see all the interfaces. Its a wonderful course.
Got to my first job out of college and they gave me core dumps and had me debug the kernel for a year. Not my kind of fun, but definitely got me skilled in the art of low level.
I personally learned a lot from cpp conference videos. I would highly recommmend it.
I should study that. Thank you
Expose yourself to lower level technologies (compilers and optimization techniques, hardware history and design) and let curiosity guide you. Learn how to profile and analyze program performance.
Wow that is quite surprising. Almost seems like it could be a compiler bug tbh. Very fragile optimisation if not!
it's arguably more of a cpu bug than a computer bug. The problem is that predictable data determined whether a cmov or a branch is faster. cmov is only faster than if when the branch is unpredictable. Summer the compiler doesn't know what values your program will be called with, it can only pick and hope. To fix this, cpus could have an instruction like cmov but that learns whether speculation would be profitable and converts to treat it like a branch if better.
tbh, I'm not sure if we need "more clever" CPUs since they cause more and more unpredictable performance outcome -- and more pressing issues like Spectre. Besides, looking at the evolution of technology tells us that performance increases mainly comes from parallelism, like multicore and GPUs. Which doesn't apply to "annoyingly not parallel" problems of course. But besides "gambling" approaches like branch prediction, there's not much you can do about them in the general case.
You can, in fact, give compiler a hint wether the branch will be predictable or not. E.g. clang has __builtin_unpredictable().