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&#x27;t vectorize, and much easier to understand than the vectorized original it was based off of.<p>Turns out that main reason the vaunted &quot;overkilled&quot; 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&#x27;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&#x27;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 &quot;outer-loop vectorization&quot; very hard in the past few years. The other big fruit on the horizon is superoptimizers: I suspect we&#x27;ll see superoptimizers shipping in production compilers within a decade or two.