From: bc@freeuk.com

On 30/09/2025 17:12, Kaz Kylheku wrote:
> On 2025-09-30, Janis Papanagnou  wrote:
>> In another newsgroup the question came up to what degree the
>> GNU "C" compilers can handle optimization of recursions like
>> fib() or ack(), i.e. cascading ones. Somebody here may know?
>
> What exactly are you talking about? The ability to unroll one or more
> levels of recursion by inlining cases of a function into itself
> to create a larger functon that makes fewer calls?
>
> The common way fib is written recursively doesn't lend to
> tail call optimization; it has to be refactored for that.
>
> The usual way Ackermann is written, it has some tail calls
> and a non-tail call, since one of its cases returns
> a call to ack, which has an argument computed by calling ack.
>
>> Can we expect that (with the higher optimization levels) the
>> exponential complexity from cascaded recursion gets linearized?
>
> I'm reasonably sure that GCC is not going to recognize and linearize
> "return fib(n - 1) + fib(n - 2)" recursion. You have to do it yourself
> with explicit memoization or iterative rewrite.
>

Take a Fib() function using 'if (n<3) return 1; else...' (since there
are a few different ways of doing it).

In that form, evaluating Fib(N) requires 2N-1 nested calls, which is
what makes it a good benchmark. Or it would be if gcc didn't try to cheat.

Compiled with -O3, gcc implements Fib(N) with only 5% of the necessary
number of calls. (This makes doesn't make it 20x faster, more like 3x as
fast, as there's still a lot going on.)

You can only find out it's 5% by inserting counting code, which can only
be done in the generated assembly, otherwise gcc will ensure the count
has the expected result.

What is normally 25 lines of assembly ends up at over 250 lines. It's a
lot of effort to expend on on 6-line function, which makes you wonder if
it recognises this benchmark and gives it special treatment.

--- SoupGate-Win32 v1.05
 * Origin: you cannot sedate... all the things you hate (1:229/2)