How to lie with benchmarks | Richard Cocks

Richard Cocks

7 August 2026

How to lie with benchmarks

Naive double-recursion

A recent hacker news post1 alerted me to the idea of testing the speed of function calls in different languages by implementing naive recursive fibonacci.

You know, the kind you get by implementing:

int fib(int n) {<br>if (n

This is the sort of algorithm you might implement on day one of a programming course, with no regards to optimisation.

In fact, it’s so unoptimised, we can calculate how many function calls are required. I’ll leave the maths for another day, but it’s a fibonacci sequence too, and ends up at 2·fib(n+1) − 1.

For fib(32) which we’ll be benchmarking with, that’s 7,049,155 function calls.

This is of course a slow algorithm, but now we have a slow algorithm, we can run our naive algorithm in different languages, to give ourselves a list of top performing languages.

fib(32), best of 15 timed runs after 15 warm-up runs (click to expand results table)

Runtime<br>best<br>mean

AOT<br>C / gcc 12.2 -O2<br>3.58 ms<br>3.67 ms

Rust 1.97.1 -O<br>6.64 ms<br>6.96 ms

C / clang 14.0 -O2<br>6.84 ms<br>6.92 ms

Java 25 (GraalVM native-image)<br>9.53 ms<br>9.83 ms

Go 1.26.5<br>10.42 ms<br>10.59 ms

C# / .NET NativeAOT<br>10.62 ms<br>10.69 ms

JIT<br>F# / .NET 10<br>7.11 ms<br>7.22 ms

C# / .NET 10<br>7.15 ms<br>7.40 ms

Java 25 (HotSpot C2)<br>11.32 ms<br>11.78 ms

Julia 1.12.6<br>11.42 ms<br>12.03 ms

Gleam 1.18 (Erlang OTP 25)<br>19.74 ms<br>19.96 ms

Gleam 1.18 (Node / V8)<br>20.87 ms<br>21.30 ms

Node 26.5.1 / V8 14.6<br>22.13 ms<br>23.37 ms

LuaJIT 2.1<br>25.95 ms<br>26.24 ms

PyPy 3.9.16<br>26.68 ms<br>31.81 ms

Interpreted<br>LuaJIT -joff<br>100.62 ms<br>101.49 ms

Lua 5.4<br>156.66 ms<br>160.97 ms

Lua 5.1<br>239.58 ms<br>244.23 ms

CPython 3.11<br>294.85 ms<br>303.02 ms

These results have a few surprises:

Gcc beating Clang by some distance.

C# / .NET JIT beating Ahead of Time (AOT) compilation.

Java beating Go.

The devil is of course in the details, to understand what these benchmarks tell us we have to understand what we’re comparing.

We deliberately implemented a naive algorithm, with double-recursion and one unsuitable for tail call optimisation, but the compilers have no reason to respect that.

Clang for instance, compiles our algorithm down to a single recursive function:

int fib(int n) {<br>int acc = 0;<br>while (n >= 2) {<br>acc += fib(n - 1); // the only real recursive call left<br>n -= 2;<br>return acc + n; // n has decayed to 1 or 0, i.e. fib(1) or fib(0)

Now gcc goes further than clang by inlining and nesting function calls, so that instead of a single recursion each n, it only has to recurse in batches of 8:

function fib(n)<br>if n 2 do<br>n1 ← n − 1<br>acc1 ← 0<br>while n1 > 2 do<br>n2 ← n1 − 1<br>acc2 ← 0<br>while n2 > 2 do<br>n3 ← n2 − 1<br>acc3 ← 0<br>while n3 > 2 do<br>n4 ← n3 − 1<br>acc4 ← 0<br>while n4 > 2 do<br>n5 ← n4 − 1<br>acc5 ← 0<br>while n5 > 2 do<br>n6 ← n5 − 1<br>acc6 ← 0<br>while n6 > 2 do<br>n7 ← n6 − 1<br>acc7 ← 0<br>while n7 > 2 do<br>n8 ← n7 − 1<br>acc8 ← 0<br>while n8 > 1 do<br>acc8 ← acc8 + fib(n8 − 1)<br>n8 ← n8 − 2<br>acc7 ← acc7 + acc8 + n8<br>n7 ← n7 − 2<br>acc6 ← acc6 + acc7 + 1<br>n6 ← n6 − 2<br>acc5 ← acc5 + acc6 + 1<br>n5 ← n5 − 2<br>acc4 ← acc4 + acc5 + 1<br>n4 ← n4 − 2<br>acc3 ← acc3 + acc4 + 1<br>n3 ← n3 − 2<br>acc2 ← acc2 + acc3 + 1<br>n2 ← n2 − 2<br>acc1 ← acc1 + acc2 + 1<br>n1 ← n1 − 2<br>acc0 ← acc0 + acc1 + 1<br>n ← n − 2<br>return acc0 + 1

This still explodes into a tree of recursion, but it takes us down from over 7M function calls to ~300k.

If we hand this implementation over to C# and LuaJIT, then we see a speed-up there too:

C# naive recursive mean 7.23 ms ± 0.19 ms<br>C# gcc-shaped mean 2.70 ms ± 0.10 ms<br>LuaJIT gcc-shaped mean 3.39 ms ± 0.25 ms

In fact the “gcc-shaped” code ends up faster than gcc. This doesn’t mean much, as we’ll see later.

Iteration

We’re not done. Let’s not use recursion to do something we can do in a single loop.

function fib(n) {<br>if (n == 0) return 0;<br>a = 0, b = 1;<br>while (--n) { t = a + b; a = b; b = t; }<br>return b;

There’s another algorithm that’s even quicker, because you can jump your index by a factor of two each time, using the identities:

fib(2k) = fib(k) · (2·fib(k+1) − fib(k))<br>fib(2k+1) = fib(k)² + fib(k+1)²

This takes us from microbenchmarking to nanobenchmarking, so to get accurate measurements we have to use a real benchmarking harness such as Criterion or BenchmarkDotNet.

Calculated iteratively, we find:

implementation<br>time

iterative loop — C, clang 14<br>4.30 ns

fast doubling — C# / .NET 10<br>5.49 ns

fast doubling — C, gcc 12.2<br>6.39 ns

fast doubling — C, clang 14<br>8.17 ns

iterative loop — C, gcc 12.2<br>9.58 ns

iterative loop — C# / .NET 10<br>13.37 ns

naive recursive — C, gcc ( best case, from the previous table )<br>3,580,000 ns

So we find ourselves almost a million times quicker. The interesting thing here is that this time Clang optimises the iterative loop better than gcc does, but that it even optimises the iterative loop to be faster than the “fast doubling” approach, this time due to loop unrolling by clang:

The tight loop becomes:

add %esi,%edx ; b += a → (a,b) advance one step<br>add %edx,%esi ; a += b → another step<br>add...