I'm actually surprised that gcc doesn't do this! If there's one thing compilers do well is pattern match on code patterns and replace with more efficient ones; just try pasting things from Hacker's Delight and watch it always canonicalise it to the equivalent, fastest machine code.
I'm once again surprised at GCC being slower than clang. I would have thought that GCC, which had a 20? year head start would've made faster code. And yet, occasionally I look into the assembly and go "what are you doing?" And the same flags + source into clang is better optimized or uses better instructions or whatever. One time it was bit extraction using shifts. Clang did it in 2 steps: shift left, shift right. GCC did it in 3 I think? I think it maybe shifted right first or maybe did a logical instead of arithmetic and then sign extended. Point is, it was just slower.
I'm not. GCC started out as a work of idealistic licensing purists and was deliberately "obfuscated" to make it hard to extend and embed. That stance has since been softened considerably, but the code generator is still far more complex than it needs to be, and I think that has made it harder to modify for efficiency. Clang is far less ideology-focused and its structure makes implementing optimisations easier.
On the other hand, I find MSVC and especially ICC output to be quite decent, although I have never seen their source code.
Having inspected the output of compilers for several decades, it's rather easy to tell them apart.
I will admit I was initially surprised Matt was not already familiar with this behavior given his reputation. I remember discovering it while playing with llvm intermediate representation 10 years ago in college. I would never have considered myself very knowledgeable about modern compilers, and have never done any serious performance work. In that case it had solved a recursion to a simple multiplication, which completely surprised me. The fact that Matt did not know this makes me think this pass may only work on relatively trivial problems that he would never have written in the first place, and therefore never have witnessed the optimization.
These sorts of things are fun and interesting. Compiler optimizations fall into two categories:
1. organized data flow analysis
2. recognizing a pattern and replacing it with a faster version
The first is very effective over a wide range of programs and styles, and is the bulk of the actual transformations. The second is a never-ending accumulation of patterns, where one reaches diminishing returns fairly quickly.
The example in the linked article is very clever and fun, but not really of much value (I've never written a loop like that in 45 years). As mentioned elsewhere "Everyone knows the Gauss Summation formula for sum of n integers i.e. n(n+1)/2" and since everyone knows it why not just write that instead of the loop!
Of course one could say that for any pattern, like replacing i*2 with i<<1, but those pattern replacements are very valuable because they are generated by high level generic coding.
And you could say I'm just being grumpy about this because my optimizer does not do this particular optimization. Fair enough!
The point is not really that the compiler is able to spot the Gaussian sum. It uses a general infrastructure to turn many "math loops" that sum/multiply numbers into closed-form solutions. This handles Gauss but is much more general. In turn it allows you to write simple code that still does the right thing, instead of a complicated-looking large multiplication with a bunch of random-seeming constants.
A hard problem in optimization today is trying to fit code into the things complex SSE-type instructions can do. Someone recently posted an example where they'd coded a loop to count the number of one bits in a word, and the compiler generated a "popcount" instruction. That's impressive.
What's actually way cooler about this is that it's generic. Anybody could pattern match the "sum of a finite integer sequence" but the fact that it's general purpose is really awesome.
This is really bluring the line between implementation and specification. You may think you're writing the implementation but it is really a proxy for the specification. In other words, the compiler creating an illusion of an imperative machine.
25 comments
[ 5.1 ms ] story [ 51.1 ms ] threadThis kind of optimization, complete loop removal and computing the final value for simple math loops, is at least 10 years old.
https://github.com/llvm/llvm-project/blob/release/21.x/llvm/...
https://github.com/llvm/llvm-project/blob/release/21.x/llvm/...
https://en.wikipedia.org/wiki/Wilf%E2%80%93Zeilberger_pair
On the other hand, I find MSVC and especially ICC output to be quite decent, although I have never seen their source code.
Having inspected the output of compilers for several decades, it's rather easy to tell them apart.
1. organized data flow analysis
2. recognizing a pattern and replacing it with a faster version
The first is very effective over a wide range of programs and styles, and is the bulk of the actual transformations. The second is a never-ending accumulation of patterns, where one reaches diminishing returns fairly quickly.
The example in the linked article is very clever and fun, but not really of much value (I've never written a loop like that in 45 years). As mentioned elsewhere "Everyone knows the Gauss Summation formula for sum of n integers i.e. n(n+1)/2" and since everyone knows it why not just write that instead of the loop!
Of course one could say that for any pattern, like replacing i*2 with i<<1, but those pattern replacements are very valuable because they are generated by high level generic coding.
And you could say I'm just being grumpy about this because my optimizer does not do this particular optimization. Fair enough!
A hard problem in optimization today is trying to fit code into the things complex SSE-type instructions can do. Someone recently posted an example where they'd coded a loop to count the number of one bits in a word, and the compiler generated a "popcount" instruction. That's impressive.