Compiler Optimizations are Awesome
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.<p>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).<p>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.<p>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.