Unscientific and unreliable toy benchmark game: Common Lisp, Racket, Python, C, and Fibonacci numbers

Update 2015/12/21: update the Common Lisp and C implementations and revise the article according to the new results.

Warning: take the results in this blog post with a grain of salt.

So I have been playing with Common Lisp and type declarations for a while now. With Steel Bank Common Lisp (SBCL), declaring types also result in the compiler automatically checking the declared types for any errors or inconsistencies.

This is obviously good for safety purposes. But in addition to that, SBCL also uses the type information to optimize the code and improve performance. In order to understand how type declarations help the compiler optimizes the code during compilations, we need to do a benchmark. And what better benchmark to use than everyone’s favorite toy benchmark: computing Fibonacci numbers.

I will be using the naive recursive algorithm, the one with the runtime complexity of O(2^n). Here is the algorithm implemented in Python:

I ran the above script using the time utility to measure how long it takes to compute the 40th Fibonacci number (n = 40), and this is the result with Python version 2.7.9 on my Thinkpad X230 running Debian Sid:

$ time python2.7 fib.py

102334155

real    0m32.401s
user    0m32.392s
sys     0m0.020s

Surprisingly enough, Python version 3.4.2 performed even worse than Python 2.7.9:

$ time python3 fib.py

102334155

real    0m37.492s
user    0m37.432s
sys     0m0.032s

Next is the Common Lisp version:

Using SBCL to compile the script and run the resultant binary gave us the following result:

$ time ./fib1

102334155

real    0m4.081s
user    0m4.080s
sys     0m0.000s

So Common Lisp takes about 4 seconds to compute the number, and is already 8 to 9 times faster than the Python versions. But can we do better?

Let’s go all out and declare the type of all variables (well, there is only one variable to declare anyway), as well as using all the optimization options:

Note how I specified the type of the argument, n, as a fixnum. This is because a fixnum is the most efficient type of integers in Common Lisp (more information about fixnum and its characteristics can be found here, here, and here).

Compiled and ran the above code gave us the following:

$ time ./fib2

102334155

real    0m1.183s
user    0m1.176s
sys     0m0.004s

So this version runs almost 3 seconds faster than the untyped, unoptimized Common Lisp version, and 26 to 30 times faster than both Python versions.

That’s impressive and all, but how does Common Lisp fare against its cousin, Racket?

Here is the same algorithm implemented in Racket:

Running the Racket script gave us the following numbers:

$ time racket fib1.rkt

102334155

real    0m2.055s
user    0m2.032s
sys     0m0.024s

While the Racket version is about one second slower than the properly typed Common Lisp version, its performance is still very impressive, being 2 seconds faster than the equivalent untyped Common Lisp version. This is most likely due to its sophisticated JIT compiler.

And last but not least is the C version (our baseline):

Compiled and ran the program, again using the time utility to measure how long it takes to compute the result, gave us the following:


$ time ./fib
102334155

real    0m0.882s
user    0m0.880s
sys     0m0.000s

So the C version takes about a little less than a second to find the value.

In conclusion, our little “benchmark” game did show us that declaring types does make Common Lisp code perform significantly faster than not doing so. Indeed, with a proper type declaration (which is crucial, since declaring a wrong or inappropriate type can hinder the performance), SBCL can create a very, very fast binary code, ranks second to only the C implementation in terms of the raw execution speed (and leaves other dynamic languages behind in the dust).

Again, please take the results in this blog post with a grain of salt. I’m still new to both Common Lisp and Racket, and still have a lot to learn.

C’s Designated Initializers

While working with FUSE C API, I came across the follow snippets of code which caught me eyes:

static struct fuse_operations xmp_oper = {
    .getattr  = xmp_getattr,
    .access   = xmp_access,
    .readlink = xmp_readlink,
    ...
    .fsync    = xmp_fsync,
}

Those style of struct initialization are called designated Initializers, and apparently they were introduced in ISO C99 (it is also existed as a GNU extension to C90 as well).

A thread on Hacker News has an interesting discussion on the topic (such as the fact that it is extensively used in Linux device driver code, e.g., [1]), as well as many informative links [2, 3] and even a suggestion on a book that describes new features that were introduced in C99.