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)
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?
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.
> 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.
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.
http://pluto-compiler.sourceforge.net/
That thing on the link above easily does almost everything you described as unattainable for compiler and does it in automatic manner. AFAIK, it even allows your code to MPI parallelized, with optimal communication.
Which ones?
Not all of these video's are equally interesting, but there's some real gems in there, e.g. where Casey (of HH) hand-optimizes his bilinear bitmap interpolation code (somewhere between streams ~115 and ~120 if I remember correctly).
I cringe a lot about their coding style and complete disregard of architecture and basic code hygiene they appear to have, but there's still a lot of interesting things to learn from watching these streams.
[1] https://www.youtube.com/watch?v=Ee3EtYb8d1o [2] https://www.youtube.com/user/jblow888
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.
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!
http://davidad.github.io/blog/2014/02/25/overkilling-the-8-q...
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.