I wrote the same naive recursive Fibonacci in Python, Go, C and x86-64 assembly to see how far apart they are. The interesting part was not "C is fast". It was that C is only fast because clang rewrites my code, and assembly is only fast if I write it with the same trick clang uses.
The function
static int fib(const int n) {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}Exponential on purpose. fib(30) makes 2,692,537 calls, so this is a benchmark of function calls, not of math.
How it started
On my Linux x86-64 box I had fib.c, fib.go and fib.py, all computing fib(30). The first C version looked like this, timed with clock():
static int fib (const int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return fib (n - 1) + fib (n - 2);
}I built it the lazy way, clang fib.c, no flags:
$ clang fib.c && ./a.out
In C Fibonacci function took 0.005658 seconds to execute
$ go run fib.go
In Go Fibonacci function took 0.003153 seconds to execute
$ python3.13 fib.py
In Python Fibonacci function took 0.05898761749267578 seconds to executeGo beat C. Almost 2x. Not what "C is the fastest" promises. The only thing I changed next was one flag:
$ clang -O2 fib.c && ./a.out
In C Fibonacci function took 0.003675 seconds to execute
$ go run fib.go
In Go Fibonacci function took 0.003179 seconds to executeClose to Go now, still not ahead. Then I cleaned up the code: if (n < 2) return n; as the base case, clock_gettime(CLOCK_MONOTONIC) instead of clock(), printing the result so nothing can be thrown away, and a run-all.sh that builds everything the same way:
fib(30) = 832040
In Python Fibonacci function took 0.058293 seconds to execute
fib(30) = 832040
In C Fibonacci function took 0.001640 seconds to execute
fib(30) = 832040
In Go Fibonacci function took 0.003153 seconds to execute(It took a couple of tries: go build fib.go -o fib-go fails with named files must be .go files: -o, flags go before the file: go build -o fib-go fib.go.)
Now C at -O2 is 2x faster than Go. But careful: the cleanup itself did not make fib faster. I compiled the early version with -O2 and read the assembly. The n == 0 / n == 1 checks become one n < 2 compare and clang emits the same loop as for the clean version (shown below). The call is not removed either, even though the early version ignores the result. The 0.0037 s vs 0.0016 s gap is measurement noise: at fib(30) the whole run is a few milliseconds, so CPU clock ramp-up and scheduling are a big part of the number.
Then I wrote the same function in x86-64 assembly. The first version was the simple approach: plain recursion, two calls per frame, just like the C source:
fib(30) = 832040
In Python Fibonacci function took 0.057940 seconds to execute
fib(30) = 832040
In C Fibonacci function took 0.001678 seconds to execute
fib(30) = 832040
In Go Fibonacci function took 0.003210 seconds to execute
fib(30) = 832040
In Assembly Fibonacci function took 0.002506 seconds to executeHand-written assembly lost to C. 0.0025 s vs 0.0017 s. So I looked at what clang -O2 emits, rewrote my assembly with the same trick (more on that below), and ran again:
fib(30) = 832040
In Python Fibonacci function took 0.058673 seconds to execute
fib(30) = 832040
In C Fibonacci function took 0.001619 seconds to execute
fib(30) = 832040
In Go Fibonacci function took 0.003156 seconds to execute
fib(30) = 832040
In Assembly Fibonacci function took 0.001174 seconds to executeSteady 0.001174 s on every run, now faster than C. Summary, fib(30):
Python 3.13 0.058 s
C clang (-O0) 0.0057 s
Go 0.0032 s
Assembly simple recursion 0.0025 s
C clang -O2 0.0016 s
Assembly clang-style 0.0012 sSame C source sits both below Go and above it, depending on one compiler flag. Same for assembly: the simple version is slower than C, the clang-style one is faster. So I wanted to know what exactly clang does.
C without optimization
clang fib.c with no flags means -O0. Here is what it produces for fib:
fib:
pushq %rbp
movq %rsp, %rbp
subq $16, %rsp
movl %edi, -8(%rbp) # n goes to the stack
cmpl $2, -8(%rbp) # and is read back from memory
jge .LBB1_2
movl -8(%rbp), %eax
movl %eax, -4(%rbp)
jmp .LBB1_3
.LBB1_2:
movl -8(%rbp), %edi
subl $1, %edi
callq fib # fib(n - 1)
movl %eax, -12(%rbp) # spill result
movl -8(%rbp), %edi
subl $2, %edi
callq fib # fib(n - 2)
movl %eax, %ecx
movl -12(%rbp), %eax # reload
addl %ecx, %eax
movl %eax, -4(%rbp)
.LBB1_3:
movl -4(%rbp), %eax
addq $16, %rsp
popq %rbp
retqA literal translation: every variable lives in memory, every use is a load, and there are two calls per frame. That is the C that lost to Go.
What -O2 does
This is fib from my -O2 binary (Debian clang 19.1.7), disassembled:
fib:
pushq %r14
pushq %rbx
pushq %rax
movl %edi, %r14d # n in a register
xorl %ebx, %ebx # acc = 0
cmpl $2, %edi
jge .LBB1_2
movl %r14d, %ecx
jmp .LBB1_4
.LBB1_2:
xorl %ebx, %ebx
.LBB1_3: # loop
leal -1(%r14), %edi
callq fib # acc += fib(n - 1)
leal -2(%r14), %ecx
addl %eax, %ebx
cmpl $3, %r14d
movl %ecx, %r14d # n -= 2
ja .LBB1_3
.LBB1_4:
addl %ecx, %ebx # acc + base case
movl %ebx, %eax
addq $8, %rsp
popq %rbx
popq %r14
retqRegisters instead of stack slots, and no frame pointer, are the small wins. The big one: **there is only one call**. Clang turned the second recursive call into a loop with an accumulator. In C it would look like:
int fib(int n) {
int acc = 0;
while (n >= 2) {
acc += fib(n - 1);
n -= 2;
}
return acc + n;
}fib(n - 2) is no longer a call, it is the next loop iteration. LLVM can do this because + is associative, so the last call can be folded into an accumulator (tail-call elimination with accumulator recursion).
Does assembly save you?
If assembly is "the fastest", hand-written assembly with plain recursion should beat C. It did not: 0.0025 s vs 0.0017 s.
My first approach was the obvious translation. Registers only, no stack spills, no frame pointer, but still two calls per frame:
fib_asm:
cmpq $2, %rdi
jl 1f
pushq %rbx
pushq %r12
subq $8, %rsp # keep stack 16-byte aligned
movq %rdi, %rbx
leaq -1(%rdi), %rdi
call fib_asm # fib(n - 1)
movq %rax, %r12
leaq -2(%rbx), %rdi
call fib_asm # fib(n - 2)
addq %r12, %rax
addq $8, %rsp
popq %r12
popq %rbx
ret
1:
movq %rdi, %rax
retThe second version uses the same loop + accumulator idea as -O2, plus one extra step: when the next call would be fib(1), it just adds 1 instead of calling.
fib_asm:
cmpq $2, %rdi
jl 1f
pushq %rbx
pushq %r12
pushq %rax
movq %rdi, %rbx # n
xorl %r12d, %r12d # acc = 0
2:
leaq -1(%rbx), %rdi
cmpq $2, %rdi
jl 3f # fib(1) = 1, skip the call
call fib_asm
addq %rax, %r12 # acc += fib(n - 1)
subq $2, %rbx # n -= 2
cmpq $2, %rbx
jge 2b
leaq (%r12,%rbx), %rax # acc + n
jmp 4f
3:
leaq 1(%r12), %rax # acc + 1
4:
popq %rcx
popq %r12
popq %rbx
ret
1:
movq %rdi, %rax
retCounting calls
This benchmark is all function calls, so the number of calls explains the results. For fib(30):
naive recursion (C -O0, simple asm) 2,692,537 calls
clang -O2 1,346,269 calls
clang-style asm 832,040 calls- Unoptimized C is slow. Two calls per frame, and every variable goes through memory. It lost even to Go.
- Simple assembly is still slow. Perfect register use, but the same 2.7 million calls, twice as many as
-O2C. Writing in assembly does not remove work, the algorithm decides how much work there is. - **
-O2C halves the calls.** Exactly half, becausefib(n - 2)became a loop iteration. That is what made C beat Go. - Assembly wins only with the same idea. With clang's loop + accumulator, plus skipping the
fib(1)calls, it makes 38% fewer calls than-O2C. That is why it ended up the fastest of all.
Running it
clang fib.c -o fib-c && ./fib-c # -O0
clang -O2 fib.c -o fib-c && ./fib-c
clang -O2 -S fib.c -o - # read what clang did
clang -O2 fib_asm_main.c fib_asm.S -o fib-asm && ./fib-asm
go build -o fib-go fib.go && ./fib-go
python3.13 fib.pyTakeaway
The speed of "C" in language benchmarks is mostly the optimizer. The optimizer is not just picking better instructions, it changes the shape of the program, here halving the number of calls. Assembly gives control, not speed. And the real fix is still an O(n) loop, which makes fib(30) take nanoseconds in every one of these languages.
Disclaimer: all the code and experiments in this post are my own work. I used a Claude agent to help write the blog post itself.
Comments