3 ms·
The compiler has determined that the second call `fib(n - 2)` is "almost" tail-recursive (there is probably a better term for this), and so was able to convert
by BeeOnRope 8y ago
The compiler has determined that the second call `fib(n - 2)` is "almost" tail-recursive (there is probably a better term for this), and so was able to convert that call into the loop you see at 10081 to 10095. This loop repeatedly calls the `fib(n - 1)` part.
In other words, the function was transformed from:
uint64_t fib(uint64_t n) {
if (n <= 1) return 1;
return fib(n - 1) + fib(n - 2);
}
into the equivalent of:
uint64_t fib2(uint64_t n) {
if (n <= 1) return 1;
uint64_t sum = 1;
for (; n > 1; n -= 2) {
sum += fib2(n - 1);
}
return sum;
}
Unfortunately, the result isn't too great as the initial part of the function is pretty heavy, and this bottlenecks computation. It would be better to inline some copies of fib into itself which might even allow some small amount of CSE, but importantly would reduce the number of calls.
The alignment you show is "special" (fast) because it's the point at which the top of the main loop (10081) is near the start of a 32-byte region, which allows multiple uops to be efficiently dispatched after jumping there.