Lisp fun; can it run faster than C?

A common misconception about Lisp is that it is “slow”. I wrote misconception because this is not necessarily true. Most of the time that the “slowness” argument is brought up, it eventually turns out, after talking a while with the supporter of the argument, that it is either based on hearsay or that it stems from older experience with short tests.

Writing an actual test isn’t very hard though. Using Slime and SBCL from within an Emacs session, I started writing a small “benchmark” to check how fast Lisp would be when initializing a simple vector. For the tests I used:

  • GNU Emacs 23.0.60.1 (i386-unknown-freebsd8.0, GTK+ Version 2.12.11) of 2008-09-07
  • Slime (a CVS snapshot that works with Emacs 23.0.60.1)
  • SBCL 1.0.19
  • FreeBSD 8.0-CURRENT (a snapshot from Mon Sep 8 09:55:57 EEST 2008)
  • A laptop with:
    • An Intel Core(TM)2 Duo CPU T8100 @ 2.10GHz
    • 2 GB of physical memory

The Lisp function that I wrote to initialize a simple vector of fixed-width numbers looks like this:

CL-USER> (declaim (optimize (speed 3) (space 0) (safety 0)))
; No value
CL-USER> (defun assign (vec value)
           (declare (type (simple-array fixnum (*)) vec))
           (declare (type fixnum value))
           (let ((size (array-dimension vec 0)))
             (dotimes (i size)
               (setf (aref vec i) value))))
ASSIGN
CL-USER>

Now, after having typed this into your Lisp reader, there are a few interesting questions that would be nice to seek answers for:

  • How much does it take to initialize a vector of 512 small integers using the (assign) function we just wrote?
  • Does it make a difference if we run the test one or 10 million times?

It turns out that on a relatively modern processor, running the (assign) function once takes too little time to draw any significant conclusions:

CL-USER> (let ((image (make-array '(512) :element-type 'fixnum)))
           (time (assign image 0)))

;Evaluation took:
;  0.000 seconds of real time
;  0.000030 seconds of total run time (0.000029 user, 0.000001 system)
;  100.00% CPU
;  12,432 processor cycles
;  0 bytes consed
NIL
CL-USER>

Running the same test a million times yields a wee bit more instructive results:

CL-USER> (let ((image (make-array '(512) :element-type 'fixnum)))
          (time (dotimes (i (expt 10 6))
                  (assign image 0))))

;Evaluation took:
;  1.202 seconds of real time
;  1.177157 seconds of total run time (1.177157 user, 0.000000 system)
;  97.92% CPU
;  2,517,358,872 processor cycles
;  0 bytes consed
NIL
CL-USER>

Now this is interesting. Lisp managed to initialize a vector of 512 small numbers, setting all of them to zero, and it repeated the same a million times, in slightly more than 1.2 seconds!

Running this in a workstation doing all sorts of things is bound to give different results when it runs continuously though. Background "noise" from other processes or even CPU caching effects may kick in. So let's run the million-initialization test a few dozen times in a row.

I've trimmed the "Evaluation took" messages this time, to include only the "total run time" lines, and numbered the output lines:

CL-USER> (dotimes (iter 30)
           (let ((image (make-array '(512) :element-type 'fixnum)))
             (time (dotimes (i (expt 10 6))
                     (assign image 0)))))

     1  ;  0.946381 seconds of total run time (0.946381 user, 0.000000 system)
     2  ;  0.638546 seconds of total run time (0.638546 user, 0.000000 system)
     3  ;  0.516505 seconds of total run time (0.516478 user, 0.000027 system)
     4  ;  0.506060 seconds of total run time (0.506033 user, 0.000027 system)
     5  ;  0.505158 seconds of total run time (0.505158 user, 0.000000 system)
     6  ;  0.505522 seconds of total run time (0.505522 user, 0.000000 system)
     7  ;  0.505339 seconds of total run time (0.505339 user, 0.000000 system)
     8  ;  0.504879 seconds of total run time (0.504879 user, 0.000000 system)
     9  ;  0.505535 seconds of total run time (0.505535 user, 0.000000 system)
    10  ;  0.505343 seconds of total run time (0.505343 user, 0.000000 system)
    11  ;  0.505566 seconds of total run time (0.505566 user, 0.000000 system)
    12  ;  0.505231 seconds of total run time (0.505231 user, 0.000000 system)
    13  ;  0.506214 seconds of total run time (0.506214 user, 0.000000 system)
    14  ;  0.505010 seconds of total run time (0.505010 user, 0.000000 system)
    15  ;  0.504606 seconds of total run time (0.504606 user, 0.000000 system)
    16  ;  0.504877 seconds of total run time (0.504877 user, 0.000000 system)
    17  ;  0.504904 seconds of total run time (0.504904 user, 0.000000 system)
    18  ;  0.505216 seconds of total run time (0.505170 user, 0.000046 system)
    19  ;  0.505654 seconds of total run time (0.505654 user, 0.000000 system)
    20  ;  0.504487 seconds of total run time (0.504487 user, 0.000000 system)
    21  ;  0.504815 seconds of total run time (0.504815 user, 0.000000 system)
    22  ;  0.505080 seconds of total run time (0.505080 user, 0.000000 system)
    23  ;  0.504889 seconds of total run time (0.504889 user, 0.000000 system)
    24  ;  0.505227 seconds of total run time (0.505227 user, 0.000000 system)
    25  ;  0.504862 seconds of total run time (0.504862 user, 0.000000 system)
    26  ;  0.504890 seconds of total run time (0.504834 user, 0.000056 system)
    27  ;  0.505231 seconds of total run time (0.505221 user, 0.000010 system)
    28  ;  0.505175 seconds of total run time (0.505175 user, 0.000000 system)
    29  ;  0.504781 seconds of total run time (0.504781 user, 0.000000 system)
    30  ;  0.505415 seconds of total run time (0.505415 user, 0.000000 system)
NIL
CL-USER>

Well, now things start getting really interesting and amusing. If the same piece of tight loop code runs again and again, dozens of millions of times, Lisp seems to stabilize after a couple of runs at approximately 0.504-0.506 seconds for one million assignments. Not very bad for a "slow" language :-)

This is, of course, just a tiny microbenchmark of one particular sort of vector initialization, but I think it's quite intriguing to see Lisp run this fast.

The next part of this test would be to write a similar C program and see how fast it runs without and with optimizations. Comparing the two might be even more interesting that the Lisp-only results I have managed to collect so far.

About these ads
This entry was posted in Computers, Free software, Lisp, Open source, Programming, Software and tagged , , , , , , . Bookmark the permalink.

3 Responses to Lisp fun; can it run faster than C?

  1. keramida says:

    Ah, nice page. A rounder wheel too :)

  2. michaelw says:

    I wrote up my experience on the topic some time ago: http://www.foldr.org/~michaelw/log/programming/lisp/reverse-complement-benchmark

    I also mention two other papers on the comparison of Lisp versus C.

Comments are closed.