Common Lisp: Optimizing functions in SBCL

Question

For 2D graphics I need to optimize my functions, but in SBCL I get lots of comments about SBCL not being able to inline arithmetic operations. I tried all sorts of declarations but it doesn't seem to make the compiler happy. Here is a simple example:

(defun test-floor (x div)
  (declare (type single-float x)
           (type (signed-byte 64) div)
           (optimize (speed 3)))
  (floor x div))

gives the following 4 notes below. I'm completely lost as #'floor is a builtin function. I tried to find information/tutorials on how to properly give the compiler hints in SBCL and didn't find the right information, so any info would be very appreciated! Unfortunately optimization in Common Lisp is quite unknown territory for me. I'm using SBCL 1.3.20 on a Linux machine.

; file: /tmp/file595dqU
; in: defun test-floor
;     (FLOOR CL-FLOCKS::X CL-FLOCKS::DIV)
; --> MULTIPLE-VALUE-BIND MULTIPLE-VALUE-CALL TRUNCATE LET* 
; ==>
;   (SB-KERNEL:%UNARY-TRUNCATE/SINGLE-FLOAT (/ SB-C::X SB-C::F))
; 
; note: forced to do full call
;       unable to do inline float truncate (cost 5) because:
;       The result is a (values integer &optional), not a (values
;                                                          (signed-byte 64) &rest
;                                                          t).

; --> MULTIPLE-VALUE-BIND MULTIPLE-VALUE-CALL TRUNCATE LET* VALUES - * 
; ==>
;   (SB-KERNEL:%SINGLE-FLOAT SB-C::RES)
; 
; note: forced to do full call
;       unable to do inline float coercion (cost 5) because:
;       The first argument is a integer, not a (signed-byte 64).

; --> MULTIPLE-VALUE-BIND MULTIPLE-VALUE-CALL FUNCTION IF VALUES 1- 
; ==>
;   (- SB-C::TRU 1)
; 
; note: forced to do generic-- (cost 10)
;       unable to do inline fixnum arithmetic (cost 1) because:
;       The first argument is a integer, not a fixnum.
;       The result is a (values integer &optional), not a (values fixnum &rest t).
;       unable to do inline fixnum arithmetic (cost 2) because:
;       The first argument is a integer, not a fixnum.
;       The result is a (values integer &optional), not a (values fixnum &rest t).
;       etc.

; --> MULTIPLE-VALUE-BIND MULTIPLE-VALUE-CALL FUNCTION IF VALUES 
; ==>
;   (+ REM SB-C::DIVISOR)
; 
; note: doing signed word to integer coercion (cost 20) from div, for:
;       the second argument of generic-+
; 
; compilation unit finished
;   printed 4 notes

CL-USER>

coredump coredump · Accepted Answer · 2017-12-04T14:10:45

When you call floor, you have to deal with different subtypes of numbers: the code divides a float by an integer (that may involve coercing the integer as a float), and then have to coerce the result back to an integer. This is the amount of work that must be done, correctly, and you are unlikely to bypass it if you don't restrict your input types.

If instead you use ffloor, then the primary result is a float (you can still round it to an integer later, when you really need it (e.g. convert to pixels coordinates)). The following code does not give compilation notes:

(defun test-floor (x div)
  (declare (type single-float x)
           (type fixnum div)
           (optimize (speed 3)))
  (ffloor x div))

You may even declare div as being a float, which would push the responsibility of providing appropriately typed values (and performing runtime checks) to the callers.

Note also that you should probably (declaim (inline test-floor)) before you define the function; that helps because then the compiler can put shortcuts in the code to avoid checking input parameter types and boxing results.

Edit:

The range of a float cover a large possible domain (due to the exponent): more densely packed near zero, more spaced towards infinity. Integer values are linearly spaced, but cover a smaller range with the same number of bits. So if you want to guarantee your output fits in a fixnum, you have to make sure the float in your inputs does not go outside the range of fixnum, too. I tried the following:

(defun test-round (x)
  (declare (type (single-float #.(float most-negative-fixnum 0f0)
                               #.(float (/ most-positive-fixnum 2) 0f0)) x)
           (optimize (speed 3)))
  (round x))

I had to half the upper range of the floats because when you test:

(typep (round (coerce most-positive-fixnum 'single-float)) 'fixnum)

... it returns NIL. I don't have much time to see why this happens, but this depends on your implementation and architecture. Taking half the most positive fixnum ensures the value is low enough to be converted as a fixnum. Now, I have no more compilation notes.

(the same goes for (signed-byte 64)))

NB. Unlike in the above example, you should use deftype and avoid repeating the same declarations everywhere.

Common Lisp: Optimizing functions in SBCL

3 Answers