6 ms·
Several years ago, I happened on a blog post where someone demonstrated a very fast variant of the N-queens solution based on hand-written, SSE vectorized that
by jcranmer 9y ago
Several years ago, I happened on a blog post where someone demonstrated a very fast variant of the N-queens solution based on hand-written, SSE vectorized that was presented as very fast. I managed to write a faster, non-vectorized C solution that was recursive and that the compiler couldn't vectorize, and much easier to understand than the vectorized original it was based off of.
Turns out that main reason the vaunted "overkilled" solution was so abysmally slow was that the author happily used BSF and BTC in the hottest part of the loop... which are actually rather slow instructions, particularly when you're using them to control a branch (compare-and-jump is a fused µop in practice, but BTC-and-jump is not).
The point of this tail is that if you want to absolutely wring the last clock cycle out of a hot path, you usually need good microarchitectural knowledge about which operations are going to be faster and which are not. Sure, you can beat a compiler with hand-written, hand-optimized assembly code most of the time--but the people who have the skills to write such code are going to be the people working on the compilers.
The tools for optimizing compilers are getting better, and probably faster than we are capable of pumping out performance engineers to hand-craft the inner loops. In the past decade, we've seen polyhedral loop transformations become production-quality. Auto-vectorization is getting better, particularly when user-directed (think #pragma openmp simd); I know Intel has been pushing "outer-loop vectorization" very hard in the past few years. The other big fruit on the horizon is superoptimizers: I suspect we'll see superoptimizers shipping in production compilers within a decade or two.
- innocenat 9y agoI think it depends a lot. I have work on some hand-crafted SIMD for multimedia use before. It is fairly easy to outperform the auto-vectorization in that field IMO. I have also played around with various attempts to hand-craft inner loop (SIMD and no SIMD) for other project but most of the time I failed to outperform the compiler.
- w0utert 9y agoYes, it depends a lot. Typical signal-processing tasks you will definitely want to hand-optimize, no matter how good the compiler is, it will never be able to get close to hand-crafted SIMD code in combination with careful memory-layout, reducing the working set, eliminating dependencies, maximizing cache usage etc. There's a lot involved with that kind of optimizations that supposes semantic knowledge of the data going through the algorithm to be able to make transformations to optimize the code. For the other 99% of code it's hard (and definitely not worthwhile to try) to beat the compiler though. I sometimes watch programming streams where people go very deep into the compiler-generated code to analyze runtime behavior of their code, and it's almost scary to see the kinds of things compilers can do these days.
- mpweiher 9y ago> For the other 99% of code it's hard (and definitely not > worthwhile to try) to beat the compiler though. Bernstein's thesis is that the other 99% of the code is so cold that it's not really worth running the optimizer, and my experience (and evidence from industry) suggests that he is right about that. In fact, you might be better off with an interpreter and a really compact byte-code. Examples: Tcl used for "steering" supercomputer computations, Squeak Smalltalk doing fine for multi-media work with a simple bytecode interpreter + primitives, Objective-C, Ruby on Rails and Sinatra for a huge swathe of web-sites, the (incorrect) perception of Swift as "fast", even in Debug mode (without optimizations), Python/Numpy, etc.
- Sean1708 9y agoCertainly in my experience it's about 90-9-1; where 90% of the runtime is "cold", 9% is "warm" (optimising compiler is good enough), and 1% is "hot". I'm literally writing some code right now where -O2 pushes us from "not fast enough in the average case" to "just about fast enough in the worst case". I fully accept that things might be different in Web Development, but are optimising compilers really that common in Web Dev?
- emilecantin 9y agoThere's an impressive amount of resources poured into making Javascript faster; we often have to think about what the interpreter will do with the code we write in order to let it do some optimisations.
- Sean1708 9y agoAh yeah, that's a good point.
- tom_mellior 9y ago>> [99% of all code is cold] > in my experience it's about 90-9-1 I don't think such numbers can be meaningfully presented as representative data. They are probably true for certain specific application domains such as crypto or signal processing, if you squint at the data just the right way (i.e., by benchmarking a crypto library with a tiny driver program, not as part of a real application). I did some profiling on the SPEC CPU 2000 benchmarks some years ago. I don't have the exact numbers lying around. But I recall large variation among the different benchmarks, with anything from 90% of execution time in the top function to the top 60% of execution time spread evenly (i.e., 20% each) over the top three functions. So some things certainly follow the patterns above, and others... don't. I've also several times optimized programs until their profile was so flat that you could say that 100% of the code was lukewarm.
- gcp 9y agothe author happily used BSF and BTC in the hottest part of the loop... which are actually rather slow instructions Depends on the hardware you're running on. They used to be very fast on Intel machines. (There's an argument here that C survives architecture changes better than the ASM alternative, but BSF/BSR don't have C equivalents that the compiler can translate if appropriate, AFAIK. The best generic, widely fast implementation I know of uses multiply-shift with de Bruijn sequences and isn't automatically translated for obvious reasons)
- bluGill 9y agoThat is the point: I can spend a couple months hand optimizing a hot spot, but for what CPU? The optimizations I'd do for an intel core i7 are different and intel core i9 - and these are generations of the same architecture try to support AMD ryzen and things are very different. Now add in an ARM CPU (which?)... If I can find a better algorithm I can of course beat the compiler on all of the above. However does such an algorithm exist?
- i336_ 9y ago> ...if you want to absolutely wring the last clock cycle out of a hot path, you usually need good microarchitectural knowledge... Could starting with compiler output for a given problem be a good idea for new programmers? For example, I might take a complex problem I want to solve and then implement a series of solutions in multiple high-level(-ish) languages like C, FORTRAN, or even possibly Haskell. Once the implementations are correct, I get all languages to output assembly, and then spend a while pouring over the output, possibly doing some further iteration on the high-level source code in the process. My thinking here is that, the compiler is basically a gigantic database+graph of "use this instruction in this scenario" and a crazy complicated state machine to direct operations throughout the graph. Way too complex to read through... but I can make a compiler tell me the 90th-percentile+-most-relevant instructions to use by simply writing my program in that compiler's language. Obviously, the standard caveats about compilers producing terrible output apply - I'd never recommend treating compiler output as normative or "good for educational use", just a decent startpoint - and something to have no qualms about surpassing.
- innocenat 9y agoI would not entirely agree. Some of the current optimizations are so advanced and specific for each particular bit of code that it might not good to generalize from those output. I remember ICC generating different (but similar) code for each Intel CPU generation. I suppose it has to do with the decoder limitation (4-1-1-1, 4-2, 2-2, etc.) and exhausting execution port usage, but I never bother to confirm this. It gets very complex after a while.
- i336_ 9y agoOkay. My question was along the lines of "is this a sane default or am I wandering into a minefield," your answer is pretty much what I was looking for. > Some of the current optimizations are so advanced and specific for each particular bit of code that it might not good to generalize from those output. If only it were possible for the compiler to concisely describe its "workings-out". I imagine compilers can generate trace information, but it's probably pages long. > I remember ICC generating different (but similar) code for each Intel CPU generation. I suppose it has to do with the decoder limitation (4-1-1-1, 4-2, 2-2, etc.) and exhausting execution port usage... That's amazing. Definitely keeping that in mind, thanks!
- ruffel 9y agoWould it be this one? http://davidad.github.io/blog/2014/02/25/overkilling-the-8-queens-problem/ http://davidad.github.io/blog/2014/02/25/overkilling-the-8-q...
- jcranmer 9y agoYou are correct.