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.