It looks like gcc is going backwards on this one (at least in performance, the gcc-8 code is smaller): gcc-8, which generates the compact code you show, is the

It looks like gcc is going backwards on this one (at least in performance, the gcc-8 code is smaller): gcc-8, which generates the compact code you show, is the slowest of all the versions I tested (at -O3). Here's what I got: gcc 4.8: 4.1 s gcc 4.9: 4.3 s gcc 5.5: 4.3 s gcc 7.3: 4.8 s gcc 8.1: 6.6 s The difference between the compilers isn't just alignment: gcc-8 is generating very different code than the others, which are generally generating a large fib function with several calls of fib inlined into it, so there are many fewer calls (around 300k calls for gcc 4.8 through 7, but around 3 million for gcc 8).