When benchmarking, we need programs and inputs that run long enough for us to measure the running time accurately.

For micro-benchmarks, the running time is likely to be too small to measure accurately unless the inputs are large or the algorithm's running time is polynomial of high degree, exponential, or worse.

We can measure the running time of a fast program more accurately by running it many times, but we have to be careful lest the overhead of that loop dominates the running time we are trying to measure.

That explains why ridiculously inefficient algorithms, such as the obvious doubly recursive computation of Fibonacci numbers, are often used in micro-benchmarks or test programs.

A doubly recursive computation of Fibonacci numbers runs in exponential time. Exponential time is much faster than the running time needed for Ackermann's function, which was the first example ever discovered of a mathematical function that is not primitive recursive.

The C program shown below is one of the Kernighan and Van Wyk micro-benchmarks. It computes Ackermann's function.

      #include <stdio.h>
      
      int ack(int m, int n) {
          if (m == 0)
              return n+1;
          else if (n == 0)
              return ack(m-1, 1);
          else
              return ack(m-1, ack(m, n-1));
      }
      
      int main(int argc, char **argv)
      {
          int m = 3, n = 9;
      
          if (argc > 1)
              m = atoi(argv[1]);
          if (argc > 2)
              n = atoi(argv[2]);
          printf("%d\n", ack(m, n));
          return 0;
      }