Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: A thought of C Date: Tue, 21 Apr 2026 21:24:29 -0700 Organization: A noiseless patient Spider Lines: 109 Message-ID: <86a4uv62rm.fsf@linuxsc.com> References: <3a3462bdd72c4ed9d392a78b7d369a7b5ccc3b04.camel@gmail.com> <10rtnud$2jfm5$1@dont-email.me> <10s01e1$384ct$1@dont-email.me> <10s06q2$39rhn$1@dont-email.me> <10s2a2u$3t0f5$1@dont-email.me> <10s2fhc$3ug5h$1@dont-email.me> <10s2h5f$3uctl$1@dont-email.me> <10s2oq0$19am$1@dont-email.me> <10s2tfe$2lvm$1@dont-email.me> <10s34f6$542f$1@dont-email.me> <10s3akj$7ajg$1@dont-email.me> <10s3otn$bk6v$1@dont-email.me> <10s4gtb$grfo$1@dont-email.me> <10s53k2$mlh7$1@dont-email.me> <10s5ou0$tq3a$1@kst.eternal-september.org> <10s61e6$vu54$2@dont-email.me> <10s7asn$1b41l$1@dont-email.me> <10s7m2s$1epfv$1@dont-email.me> <20260421155535.00007852@yahoo.com> <10s7va5$1h3vn$1@dont-email.me> <20260421184458.000068de@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Wed, 22 Apr 2026 04:24:30 +0000 (UTC) Injection-Info: dont-email.me; posting-host="99049ae40d76034458eb7791fd827e8a"; logging-data="2085314"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+a3x74KjPulQBQ7Y91JDUtgCIn8D44XTU=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:mgNqJwtMiF9z/W53WxO7vmVTXEk= sha1:/EUNE04Xi6CCDvt2a6USLv5BwhA= Xref: csiph.com comp.lang.c:397779 Michael S writes: > On Tue, 21 Apr 2026 14:49:58 +0100 > Bart wrote: > >> On 21/04/2026 13:55, Michael S wrote: >> >>> On Tue, 21 Apr 2026 12:12:28 +0100 >>> Bart wrote: >>> >>>> Note 2: I believe these figures are suspect because the requisite >>>> number of calls are not done. >>> >>> I don't see anything suspect in the -O1 code generated by gcc 14.2.0 >>> >>> Source: >>> unsigned long long fib(unsigned long long n) >>> { >>> if (n < 2) >>> return 1; >>> return fib(n-1)+fib(n-2); >>> } >>> >>> $ gcc -S -O1 -Wall -Wextra -fno-asynchronous-unwind-tables >>> ref0_fib.c $ cat ref0_fib.s >>> .file "ref0_fib.c" >>> .text >>> .globl fib >>> .def fib; .scl 2; .type 32; .endef >>> fib: >>> movl $1, %eax >>> cmpq $1, %rcx >>> jbe .L5 >>> pushq %rsi >>> pushq %rbx >>> subq $40, %rsp >>> movq %rcx, %rbx >>> leaq -1(%rcx), %rcx >>> call fib >>> movq %rax, %rsi >>> leaq -2(%rbx), %rcx >>> call fib >>> addq %rsi, %rax >>> addq $40, %rsp >>> popq %rbx >>> popq %rsi >>> ret >>> .L5: >>> ret >>> .ident "GCC: (Rev2, Built by MSYS2 project) 14.2.0" >>> >>> Measured with n=43 on my very old home desktop it gave: >>> 1402817465/2.646 s = 530165330.7 calls/sec >> >> You're right. It was either a different version or I was mistaken. >> >> But it seems that Clang -O1 will generate a version with only a >> single fib call. This is the godbolt code for the Fib() version using >> "if (n < 3) return 1": >> >> fib: >> pushq %r14 >> pushq %rbx >> pushq %rax >> movl %edi, %r14d >> xorl %ebx, %ebx >> cmpl $3, %r14d >> jl .LBB0_3 >> .LBB0_2: >> leal -1(%r14), %edi >> callq fib >> addl %eax, %ebx >> addl $-2, %r14d >> cmpl $3, %r14d >> jge .LBB0_2 >> .LBB0_3: >> incl %ebx >> movl %ebx, %eax >> addq $8, %rsp >> popq %rbx >> popq %r14 >> retq >> >> If I inject an increment to a global counter just after than callq >> fib, then it shows only half the expected value. >> >> (This fib version is one-based, so that fib(10) is 55, while yours I >> think has it as 89. Google tells me that Fibonacci(10) is 55.) > > That looks like tail call elimination. I.e. compiler turned the code > into: > unsigned long long fib(unsigned long long n) > { > unsigned long long res = 0; > while (n >= 3) { > res += fib(n-1); > n -= 2; > } > return res + 1;; > } > > gcc generates similar code with -O -foptimize-sibling-calls > For certain styles of coding, e.g. one often preferred by Tim Rentsch, > this optimization is extremely important. Please don't misrepresent me. The code transformation shown above is not important to the functional recursive style that I often employ. Neither of the two recursive calls to fib() in the C code function shown at the top are tail calls.