Execution time of recursive Fibonacci function is slower in C than equivalent Nim and Pascal code

Question

At this link there is a benchmark about a recursive Fibonacci function written in various languages. I tried some examples(specifically Nim and Pascal) and verified that the execution time was about the same as on that page. Then I tried the C version below (which I was interested in, since I am learning C and C++) and I was baffled to see that on my machine (an old i5 desktop) the time was ~17 seconds whereas on the benchmark page is ~7 seconds!! I used the same compiler flags as stated on that page (namely -O3 and release target of course) but got much slower execution time. I am on Microsoft Windows and I am using Mingw64 with code::blocks.

I cannot believe that Nim and Pascal are faster. After all, if I am not mistaken, Nim compiles to C!

So what am I doing wrong here?

The code is:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

static uint64_t fib(uint64_t n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    time_t t1 = time(NULL);
    uint64_t res = fib(47);
    time_t t2 = time(NULL);
    printf("%llu seconds\n", t2 - t1);
    return 0;
}

Answer 1

You are not doing anything wrong, your system happens to have a slower CPU than the benchmark machine. Running the examples in other languages on your PC would probably produce even longer times. The same code runs in about 8 seconds on my M2 Macbook.

This naive recursive Fibonacci implementation is a classic to measure function call performance. As you can see in the README file, performance is very similar across statically typed compiled languages. None of the compilers tested match the pattern in the fib function to produce code for an alternative algorithm that would run in less than a microsecond.

Here is a modified version that outputs the result in addition to a more precise timing and accepts command line arguments:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <time.h>

static uint64_t fib(uint64_t n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

static double time_microseconds(void) {
#ifdef TIME_UTC
    struct timespec ts;
    timespec_get(&ts, TIME_UTC);
    return ts.tv_sec * 1000000.0 + ts.tv_nsec / 1000;
#elif 1
    return clock() * 1000000.0 / CLOCKS_PER_SEC;
#else
    return time(NULL) * 1000000.0;
#endif
}

static void test_fib(uint64_t n) {
    double t1 = time_microseconds();
    uint64_t res = fib(n);
    double t2 = time_microseconds();
    printf("fib(%"PRIu64") = %"PRIu64"  %g seconds\n", n, res, (t2 - t1) / 1000000.0);
}

int main(int argc, char *argv[]) {
    if (argc > 1) {
        for (int i = 1; i < argc; i++)
            test_fib(strtoul(argv[i], NULL, 0));
    } else {
        test_fib(47);
    }
    return 0;
}

Output on my M2 laptop:

chqrlie@macbook ~/dev/stackoverflow > ./230704-fib 10 20 30 {40..47}
fib(10) = 55  1e-06 seconds
fib(20) = 6765  4.5e-05 seconds
fib(30) = 832040  0.00471 seconds
fib(40) = 102334155  0.29385 seconds
fib(41) = 165580141  0.453271 seconds
fib(42) = 267914296  0.728588 seconds
fib(43) = 433494437  1.18065 seconds
fib(44) = 701408733  1.91074 seconds
fib(45) = 1134903170  3.08946 seconds
fib(46) = 1836311903  5.02768 seconds
fib(47) = 2971215073  8.17137 seconds

The faster version below produces the same results in less than a microsecond for all values tested, but so would it if implemented this way in other languages:

static uint64_t fib_fast(uint64_t n) {
    uint64_t a = 0, b = 1, c = n;
    while (n --> 1) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

Answer 2

I cannot believe that Nim and Pascal are faster. After all, if I am not mistaken, Nim compiles to C!

Regarding this specific question, you can find the explanation in the issues area of drujensen's github repository: The fastest languages are cheating #119