Just for fun—recursion benchmark Link to heading

I was curious how different programming languages and their compilers optimize heavily recursive calls. So today, let’s compare how long it takes to calculate 40th Fibonacci number using naive recursive implementation on gcc, clang, zig cc, go, ghc, java, dotnet, dart, cpython, pypy, node, and bun!

Our program will simply read an integer n from the argument and calculate the nth Fibonacci number and print. For our benchmark, we will use the naive recursive approach. Below is the baseline implementation in C. We will test with gcc, clang, and zig cc at various optimization levels.

// fibo.c
#include <stdio.h>
#include <stdlib.h>

int fibo(int n) {
    if (n <= 1) return n;
    return fibo(n - 2) + fibo(n - 1);
}

int main(int argc, const char **argv) {
    double n = atoi(argv[1]);
    printf("%d\n", fibo(n));
    return 0;
}

I will skip C++ since this shall be practically identical to C. Next would be in Rust 🦀. We will test with various optimization levels.

// fibo.rs
fn main() {
    let n: i32 = std::env::args().nth(1).unwrap().parse().unwrap();
    println!("{}", fibo(n));
}

fn fibo(n: i32) -> i32 {
    if n <= 1 {
        n
    } else {
        fibo(n - 2) + fibo(n - 1)
    }
}

Next, we will write in Go.

// fibo.go
package main

import (
    "fmt"
    "os"
    "strconv"
)

func fibo(n int) int {
    if n <= 1 {
        return n
    }
    return fibo(n-2) + fibo(n-1)
}

func main() {
    arg := os.Args[1]
    n, err := strconv.Atoi(arg)
    if err != nil {
        fmt.Println("Error:", err)
        return
    }

    fmt.Println(fibo(n))
}

Finally, we let’s do Haskell as well.

-- fibo.hs
import System.Environment (getArgs)

fibo :: Int -> Int
fibo n
  | n <= 1    = n
  | otherwise = fibo (n - 2) + fibo (n - 1)

main :: IO ()
main = do
  args <- getArgs
  let n = read (head args) :: Int
  print (fibo n)

These are the programming languages that compile to the native machine code. Next up we have languages that run in a virtual machine (VM). Let’s start with Java:

// Fibo.java
public class Fibo {
    public static int fibo(int n) {
        if (n <= 1) return n;
        return fibo(n - 2) + fibo(n - 1);
    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        System.out.printf("%d\n", fibo(n));
    }
}

Then we have C#. Personally, I think dotnet sdk-tool is a pain in the a** because it refuses to build/run a single .cs file without setting up a project. One could use csc from mono, but we’ll stick to the official dotnet tool for the best performance in this experiment.

// Fibo.cs
using System;

class Program
{
    static int Foo(int n)
    {
        if (n <= 1) return n;
        return Foo(n - 2) + Foo(n - 1);
    }

    static void Main(string[] args)
    {
        if (int.TryParse(args[0], out int n))
        {
            Console.WriteLine(Foo(n));
        }
        else
        {
            Console.WriteLine("Invalid number format.");
        }
    }
}

Next up is Dart. This is what drives Flutter under the hood.

// fibo.dart
import 'dart:io';

int fibo(int n) {
  if (n <= 1) return n;
  return fibo(n - 2) + fibo(n - 1);
}

void main(List<String> args) {
  int n;
  try {
    n = int.parse(args[0]);
  } catch (e) {
    print('Invalid number format.');
    return;
  }

  print(fibo(n));
}

Next up is Python. We will run it with both CPython and Pypy.

# fibo.py
import sys

def fibo(n):
    if n <= 1:
        return n
    return fibo(n - 2) + fibo(n - 1)

if __name__ == "__main__":
    n = int(sys.argv[1])
    print(fibo(n))

Finally, Javascript. We will test with both Node and Bun.

// fibo.js
const fibo = (n) => {
  if (n <= 1) return n;
  return fibo(n - 2) + fibo(n - 1);
};

const main = () => {
  const n = parseInt(process.argv[2], 10);
  console.log(fibo(n));
};

main();

Overall Link to heading

OK, below shows the summary of the results run on my x64 Linux system with the legend for naming

{gcc,clang,zig}{0,1,2,3}: C source code compiled by {gcc,clang,zig} with optimization level {0,1,2,3}
ghc{0,1,2}: haskell source code compiled by ghc with optimization level {0,1,2}
go: go
rust{0,1,2,3}: rust source code compiled by rustc with optimization level {0,1,2,3}
java: open-jdk
dotnet-{Debug,Release}: c# source code compiled and run by dotnet with {Debug,Release} config
dart: dart
{cpython,pypy}: python source code run by {cpython,pypy}
{node,bun}: javascript source code run by {node,bun}

As always, CPython is the slowest by a large margin, followed by unoptimized binary by GHC Haskell. Of interesting note is that Bun is definitely faster than node. Because of these very slow outliers (thank you CPython) it is hard to compare other data points, so below I selected the fastest among its category and re-plotted below.

Native compiled Link to heading

The bars in the blue color show those programs compiled ahead of time (AOT) and run natively on the system. They are typically the fasted, as there is minimal overhead. What is surprising to me is that the binary produced by gcc is almost 2x faster than that produced by clang!

Go and Haskell run much slower because they offer automatic memory management, i.e., they are garbage-collected languages. They sacrifice performance for memory safety. The only exception would be Rust, which offers memory safety without performance hit via its unique ownership model. Personally, I believe the Rust way is the right direction for future languages 🦀.

Statically-typed VM Link to heading

The next group is in the green color. They are statically-typed programming languages that run on VM. Among these, Java runs the fastest, while dotnet runs the slowest. It could be because dotnet is not optimized for non-Windows platforms, but even so the performance gap is larger than I expected. This is especially surprising given that Java is tested with open-jdk and not oracle-jdk. Given the larger user base and longer history of C#/.NET compared to Dart, I always assumed dotnet would run much faster than Dart.

Believe it or not, once upon a time Java was considered too slow. Well, I guess people can’t say that anymore, as it runs faster than even Go!

Dynamically-typed VM Link to heading

Lastly we have the dynamically-typed languages in the yellow color. They offer the lowest hurdles for the novice developers but at the same time are most prone to runtime errors due to lack of type-check at compile time. Also, they are the slowest because it is much more difficult to optimize given that the type is only known at runtime. What is still surprising to me is that bun runs really fast, even beating statically-typed VMs like dotnet and dart by a large margin. This must imply that the bun VM is extremely well optimized — by the way, bun is implemented in zig language.

Python, once again, run the slowest. Its most popular implementation CPython is about 100x slower than gcc , while its faster cousin pypy manages to be 25x slower. This makes me really wonder if there is some intrinsic limitation with Python language design that makes it so much more difficult to optimize compared to Javascript — which I doubt. If anyone knows the reason, please help me understand why CPython/pypy can’t run as fast as Node/Bun. Probably it is just that the Python community hasn’t spent as much effort in optimizing for performance just yet.

Alright, hopefully this was a fun exercise, and I hope to do another test soon. As always with program benchmark, this is just a single data-point and shall be taken with a grain of salt. It is not the language itself that matters most of the time — it is really the implementation of the compiler/runtime that matters.