SBCL is Fast!

I just read an article comparing the performance of Clojure, Java, Ruby, and Scala. As I read the article, I wondered how Common Lisp compares to the languages covered in the article. So I fired up Emacs, started Slime, and wrote some quicksort code for SBCL.

I'm guessing I did something wrong, because I wrote a couple of basic quicksort functions with no type-hints or any other kind of optimization, and the functions were able to sort 180,000 elements in about 0.5 seconds, which is better than twice as fast as the Java version in the article.

Here's the code:

        (defun quicksort1 (list)
          (if (< (length list) 2) list
              (let* ((pivot (nth (random (length list)) list))
                     (less (remove-if-not (lambda (x) (< x pivot)) list))
                     (p (remove-if-not (lambda (x) (= x pivot)) list))
                     (more (remove-if-not (lambda (x) (> x pivot)) list)))
                (append (quicksort1 less) p (quicksort1 more)))))
        (defun quicksort2 (list)
          (if (< (length list) 2) list
              (let ((p (nth (random (length list)) list)))
                (append (quicksort2 (remove-if-not (lambda (x) (< x p)) list))
                        (remove-if-not (lambda (x) (= x p)) list)
                        (quicksort2 (remove-if-not (lambda (x) (> x p)) list))))))

        (defun test (function n)
          (let ((list (loop for a from 1 to n collect (random n))))
            (time (funcall function list))

And here are the tests that use those functions:

        CL-USER> (test #'quicksort1 180000)
        Evaluation took:
          0.513 seconds of real time
          0.508032 seconds of total run time (0.456029 user, 0.052003 system)
          [ Run times consist of 0.172 seconds GC time, and 0.337 seconds non-GC time. ]
          99.03% CPU
          1,159,623,975 processor cycles
          100,363,056 bytes consed

        CL-USER> (test #'quicksort2 180000)
        Evaluation took:
          0.551 seconds of real time
          0.524033 seconds of total run time (0.476030 user, 0.048003 system)
          [ Run times consist of 0.156 seconds GC time, and 0.369 seconds non-GC time. ]
          95.10% CPU
          1,245,664,978 processor cycles
          104,055,744 bytes consed

What we have here is functional, recursive, and theoretically slow code, just they way I first expressed the functions. This code is my understanding of the quicksort function and I'm sure that the speed could be improved dramatically with better coding and some optimization (type hints, for example, which I've never used).

I ran this on a typical Core 2 Duo laptop (Dell Latitude E6400), so I don't think my hardware makes that much of a difference.

Every time look at any aspect of Common Lisp, I come away amazed.