For the C++ programmer wondering whether to try his hand at Lisp, one thing that make come up is the question of code efficiency. The Gnu Compiler Collection produces good, fast code. Can a program compiled in Lisp do as well?
Well, there are tricks to improve Lisp code. SBCL will even produce output showing what expressions it could not optimize, generally because the compiler could not infer the type of some object. Using this output, the programmer can speed up the hot spots in the code by providing compiler hints, basically promises that a certain object has a certain type.
Here’s an example of how one might do this in SBCL. We’ll write a simple program that computes the average and standard deviation of a list of numbers.
(declaim (optimize (debug 0) (safety 0) (speed 3))) (defun get-stats (list-of-numbers) (let ((sum-x 0.0d0) (sum-x2 0.0d0) (num-pts 0) avg stddev) (dolist (num list-of-numbers) (incf sum-x num) (incf sum-x2 (* num num)) (incf num-pts)) (when (> num-pts 0) (setf avg (/ sum-x num-pts)) (when (> num-pts 1) (setf stddev (sqrt (/ (- (* num-pts sum-x2) (* sum-x sum-x)) (* num-pts (1- num-pts))))))) (values avg stddev)))
Now, when this is compiled in SBCL, we get the following optimizer output:
; compiling (DECLAIM (OPTIMIZE # ...))
; compiling (DEFUN GET-STATS ...)
; file: /home/neufeld/programming/lisp/blogging/optimizing.lisp
; in: DEFUN GET-STATS
; (/ SUM-X NUM-PTS)
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a FLOAT.
;
; note: unable to
; convert x/2^k to shift
; due to type uncertainty:
; The first argument is a NUMBER, not a INTEGER.
; (* NUM-PTS SUM-X2)
;
; note: unable to
; optimize
; due to type uncertainty:
; The second argument is a NUMBER, not a FLOAT.
;
; note: unable to
; convert x*2^k to shift
; due to type uncertainty:
; The second argument is a NUMBER, not a INTEGER.
; (* SUM-X SUM-X)
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a RATIONAL.
; The second argument is a NUMBER, not a FLOAT.
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a FLOAT.
; The second argument is a NUMBER, not a RATIONAL.
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a SINGLE-FLOAT.
; The second argument is a NUMBER, not a DOUBLE-FLOAT.
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a DOUBLE-FLOAT.
; The second argument is a NUMBER, not a SINGLE-FLOAT.
;
; note: unable to
; convert x*2^k to shift
; due to type uncertainty:
; The first argument is a NUMBER, not a INTEGER.
; The second argument is a NUMBER, not a INTEGER.
; (- (* NUM-PTS SUM-X2) (* SUM-X SUM-X))
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a RATIONAL.
; The second argument is a NUMBER, not a FLOAT.
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a FLOAT.
; The second argument is a NUMBER, not a RATIONAL.
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a SINGLE-FLOAT.
; The second argument is a NUMBER, not a DOUBLE-FLOAT.
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a DOUBLE-FLOAT.
; The second argument is a NUMBER, not a SINGLE-FLOAT.
; (/ (- (* NUM-PTS SUM-X2) (* SUM-X SUM-X)) (* NUM-PTS (1- NUM-PTS)))
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a FLOAT.
;
; note: unable to
; convert x/2^k to shift
; due to type uncertainty:
; The first argument is a NUMBER, not a INTEGER.
; (SQRT (/ (- (* NUM-PTS SUM-X2) (* SUM-X SUM-X)) (* NUM-PTS (1- NUM-PTS))))
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a SINGLE-FLOAT.
; The result is a (VALUES
; (OR (MEMBER 0.0 0.0d0) (DOUBLE-FLOAT (0.0d0))
; (SINGLE-FLOAT (0.0)) (COMPLEX SINGLE-FLOAT)
; (COMPLEX DOUBLE-FLOAT))
; &OPTIONAL), not a (VALUES FLOAT &REST T).
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a DOUBLE-FLOAT.
; The result is a (VALUES
; (OR (MEMBER 0.0 0.0d0) (DOUBLE-FLOAT (0.0d0))
; (SINGLE-FLOAT (0.0)) (COMPLEX SINGLE-FLOAT)
; (COMPLEX DOUBLE-FLOAT))
; &OPTIONAL), not a (VALUES FLOAT &REST T).
; (INCF SUM-X NUM)
; --> LET*
; ==>
; (+ SUM-X #:G3)
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a RATIONAL.
; The second argument is a NUMBER, not a FLOAT.
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a FLOAT.
; The second argument is a NUMBER, not a RATIONAL.
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a SINGLE-FLOAT.
; The second argument is a NUMBER, not a DOUBLE-FLOAT.
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a DOUBLE-FLOAT.
; The second argument is a NUMBER, not a SINGLE-FLOAT.
; (* NUM NUM)
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a RATIONAL.
; The second argument is a NUMBER, not a FLOAT.
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a FLOAT.
; The second argument is a NUMBER, not a RATIONAL.
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a SINGLE-FLOAT.
; The second argument is a NUMBER, not a DOUBLE-FLOAT.
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a DOUBLE-FLOAT.
; The second argument is a NUMBER, not a SINGLE-FLOAT.
;
; note: unable to
; convert x*2^k to shift
; due to type uncertainty:
; The first argument is a NUMBER, not a INTEGER.
; The second argument is a NUMBER, not a INTEGER.
; (INCF SUM-X2 (* NUM NUM))
; --> LET*
; ==>
; (+ SUM-X2 #:G5)
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a RATIONAL.
; The second argument is a NUMBER, not a FLOAT.
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a FLOAT.
; The second argument is a NUMBER, not a RATIONAL.
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a SINGLE-FLOAT.
; The second argument is a NUMBER, not a DOUBLE-FLOAT.
;
; note: unable to
; optimize
; due to type uncertainty:
; The first argument is a NUMBER, not a DOUBLE-FLOAT.
; The second argument is a NUMBER, not a SINGLE-FLOAT.
; (INCF SUM-X NUM)
; --> LET*
; ==>
; (+ SUM-X #:G3)
;
; note: forced to do GENERIC-+ (cost 10)
; unable to do inline float arithmetic (cost 2) because:
; The first argument is a NUMBER, not a DOUBLE-FLOAT.
; The second argument is a NUMBER, not a DOUBLE-FLOAT.
; The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES DOUBLE-FLOAT
; &REST T).
; unable to do inline float arithmetic (cost 2) because:
; The first argument is a NUMBER, not a SINGLE-FLOAT.
; The second argument is a NUMBER, not a SINGLE-FLOAT.
; The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES SINGLE-FLOAT
; &REST T).
; etc.
; (* NUM NUM)
;
; note: forced to do GENERIC-* (cost 30)
; unable to do inline float arithmetic (cost 4) because:
; The first argument is a NUMBER, not a (COMPLEX SINGLE-FLOAT).
; The second argument is a NUMBER, not a SINGLE-FLOAT.
; The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES
; (COMPLEX SINGLE-FLOAT)
; &REST T).
; unable to do inline float arithmetic (cost 4) because:
; The first argument is a NUMBER, not a SINGLE-FLOAT.
; The second argument is a NUMBER, not a SINGLE-FLOAT.
; The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES SINGLE-FLOAT
; &REST T).
; etc.
; (INCF SUM-X2 (* NUM NUM))
; --> LET*
; ==>
; (+ SUM-X2 #:G5)
;
; note: forced to do GENERIC-+ (cost 10)
; unable to do inline float arithmetic (cost 2) because:
; The first argument is a NUMBER, not a DOUBLE-FLOAT.
; The second argument is a NUMBER, not a DOUBLE-FLOAT.
; The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES DOUBLE-FLOAT
; &REST T).
; unable to do inline float arithmetic (cost 2) because:
; The first argument is a NUMBER, not a SINGLE-FLOAT.
; The second argument is a NUMBER, not a SINGLE-FLOAT.
; The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES SINGLE-FLOAT
; &REST T).
; etc.
; (INCF NUM-PTS)
; --> LET*
; ==>
; (+ NUM-PTS #:G7)
;
; note: forced to do GENERIC-+ (cost 10)
; unable to do inline fixnum arithmetic (cost 1) because:
; The first argument is a UNSIGNED-BYTE, not a FIXNUM.
; The result is a (VALUES (INTEGER 1) &OPTIONAL), not a (VALUES FIXNUM
; &REST T).
; unable to do inline fixnum arithmetic (cost 2) because:
; The first argument is a UNSIGNED-BYTE, not a FIXNUM.
; The result is a (VALUES (INTEGER 1) &OPTIONAL), not a (VALUES FIXNUM
; &REST T).
; etc.
; (> NUM-PTS 0)
;
; note: forced to do GENERIC-> (cost 10)
; unable to do inline fixnum comparison (cost 3) because:
; The first argument is a UNSIGNED-BYTE, not a FIXNUM.
; unable to do inline fixnum comparison (cost 4) because:
; The first argument is a UNSIGNED-BYTE, not a FIXNUM.
; etc.
; (> NUM-PTS 1)
;
; note: forced to do GENERIC-> (cost 10)
; unable to do inline fixnum comparison (cost 3) because:
; The first argument is a (INTEGER 1), not a FIXNUM.
; unable to do inline fixnum comparison (cost 4) because:
; The first argument is a (INTEGER 1), not a FIXNUM.
; etc.
; (* NUM-PTS SUM-X2)
;
; note: forced to do GENERIC-* (cost 30)
; unable to do inline fixnum arithmetic (cost 4) because:
; The first argument is a (INTEGER 2), not a FIXNUM.
; The second argument is a NUMBER, not a FIXNUM.
; The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES FIXNUM &REST T).
; unable to do inline (signed-byte 64) arithmetic (cost 5) because:
; The first argument is a (INTEGER 2), not a (SIGNED-BYTE 64).
; The second argument is a NUMBER, not a (SIGNED-BYTE 64).
; The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES (SIGNED-BYTE 64)
; &REST T).
; etc.
; (* SUM-X SUM-X)
;
; note: forced to do GENERIC-* (cost 30)
; unable to do inline float arithmetic (cost 4) because:
; The first argument is a NUMBER, not a (COMPLEX SINGLE-FLOAT).
; The second argument is a NUMBER, not a SINGLE-FLOAT.
; The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES
; (COMPLEX SINGLE-FLOAT)
; &REST T).
; unable to do inline float arithmetic (cost 4) because:
; The first argument is a NUMBER, not a SINGLE-FLOAT.
; The second argument is a NUMBER, not a SINGLE-FLOAT.
; The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES SINGLE-FLOAT
; &REST T).
; etc.
; (- (* NUM-PTS SUM-X2) (* SUM-X SUM-X))
;
; note: forced to do GENERIC-- (cost 10)
; unable to do inline float arithmetic (cost 2) because:
; The first argument is a NUMBER, not a DOUBLE-FLOAT.
; The second argument is a NUMBER, not a DOUBLE-FLOAT.
; The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES DOUBLE-FLOAT
; &REST T).
; unable to do inline float arithmetic (cost 2) because:
; The first argument is a NUMBER, not a SINGLE-FLOAT.
; The second argument is a NUMBER, not a SINGLE-FLOAT.
; The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES SINGLE-FLOAT
; &REST T).
; etc.
; (1- NUM-PTS)
; ==>
; (- NUM-PTS 1)
;
; note: forced to do GENERIC-- (cost 10)
; unable to do inline fixnum arithmetic (cost 1) because:
; The first argument is a (INTEGER 2), not a FIXNUM.
; The result is a (VALUES (INTEGER 1) &OPTIONAL), not a (VALUES FIXNUM
; &REST T).
; unable to do inline fixnum arithmetic (cost 2) because:
; The first argument is a (INTEGER 2), not a FIXNUM.
; The result is a (VALUES (INTEGER 1) &OPTIONAL), not a (VALUES FIXNUM
; &REST T).
; etc.
; (* NUM-PTS (1- NUM-PTS))
;
; note: forced to do GENERIC-* (cost 30)
; unable to do inline fixnum arithmetic (cost 4) because:
; The first argument is a (INTEGER 2), not a FIXNUM.
; The second argument is a (INTEGER 1), not a FIXNUM.
; The result is a (VALUES (INTEGER 2) &OPTIONAL), not a (VALUES FIXNUM
; &REST T).
; unable to do inline (signed-byte 64) arithmetic (cost 5) because:
; The first argument is a (INTEGER 2), not a (SIGNED-BYTE 64).
; The second argument is a (INTEGER 1), not a (SIGNED-BYTE 64).
; The result is a (VALUES (INTEGER 2) &OPTIONAL), not a (VALUES
; (SIGNED-BYTE 64)
; &REST T).
; etc.
;
; compilation unit finished
; printed 41 notes
So, let’s look at the output of the optimizer. The first complaint is about the division to obtain the average. The optimizer knows that sum-x is a number, but doesn’t know whether it’s a float, integer, double. It also notes that, if it knows the first number is an integer and the second is a power of two, that it can perform the division by bit-shifting. This will not be the case, so we’ll modify the code to inform it of the true restrictions.
The second complaint is about a multiplication. Again, it has to produce general multiplication code, instead of producing code optimized for a particular numeric type. You see more warnings of this type through all of the output. So, it’s time to modify the code to help the optimizer.
We point out certain types to the compiler, and we ensure that, in one spot where it needs to use a number several times, that the number has been pre-converted to a double-precision float. The new code looks like this:
(declaim (optimize (debug 0) (safety 0) (speed 3))) (defun get-stats2 (list-of-numbers) (let ((sum-x 0.0d0) (sum-x2 0.0d0) (num-pts 0) (avg 0.0d0) (stddev 0.0d0)) (declare (double-float sum-x)) (declare (double-float sum-x2)) (declare (double-float avg)) (declare (double-float stddev)) (declare (fixnum num-pts)) (dolist (num list-of-numbers) (let ((num-double (coerce num 'double-float))) (incf sum-x num-double) (incf sum-x2 (* num-double num-double)) (incf num-pts))) (when (> num-pts 0) (setf avg (/ sum-x num-pts)) (when (> num-pts 1) (setf stddev (sqrt (/ (- (* num-pts sum-x2) (* sum-x sum-x)) (* num-pts (1- num-pts))))))) (values avg stddev)))
What does this do to performance? Testing the unoptimized and optimized versions:
CL-USER> (progn (time (let ((mylist (list 2. 2. 1. 3. 2.))) (dotimes (i 10000000) (get-stats mylist)))) (time (let ((mylist (list 2. 2. 1. 3. 2.))) (dotimes (i 10000000) (get-stats2 mylist))))) Evaluation took: 2.514 seconds of real time 2.516157 seconds of total run time (2.500156 user, 0.016001 system) [ Run times consist of 0.044 seconds GC time, and 2.473 seconds non-GC time. ] 100.08% CPU 8,575,512,723 processor cycles 3,520,004,080 bytes consed Evaluation took: 0.598 seconds of real time 0.596037 seconds of total run time (0.596037 user, 0.000000 system) [ Run times consist of 0.016 seconds GC time, and 0.581 seconds non-GC time. ] 99.67% CPU 2,040,223,555 processor cycles 1,280,003,632 bytes consed
We see that the optimizations resulted in a better than four-fold improvement in runtime.
The interested programmer can even ask to see the generated code, by issuing the command (disassemble ‘get-stats).
So, after all this, how fast is Lisp-generated code? Well, a good resource to get answers to that is to look in the Computer Language Benchmarks Game. This is a page where people can submit their solutions to some specific computational problems in the programming language of their choice, and the solutions are built, executed, and compared on a reference system to produce statistics on the relative efficiency of the different solutions to the same problem. A benchmark comparison of some SBCL vs. g++ code can be found here.