How to convince Lisp SBCL to do inline fixnum arithmetic?

3
votes

I've found some techniques in other SO answers, but apparently I've been unable to convince SBCL to do inline fixnum arithmetic:

(declaim (optimize (speed 2) (safety 1)))

(declaim (ftype (function (fixnum fixnum) double-float) fixnumtest) (inline fixnumtest))
(defun fixnumtest (i j)
  (declare (type fixnum i j))
  (let* ((n (the fixnum (+ i j)))
         (n+1 (the fixnum (1+ n))))
    (declare (type fixnum n n+1))
    (/ 1.0d0 (the fixnum (* n n+1)) )
  )
)

(defun main () 
  (format t "~11,9F~%" (fixnumtest 2 3))
)

:results in forced to do GENERIC-* (cost 30)

What else should I try?

$ sbcl --eval '(load (compile-file "play.lisp"))'
This is SBCL 1.5.1,
…
; compiling file "/opt/tmp/play.lisp" (written 16 OCT 2019 08:03:15 PM):
; compiling (DECLAIM (OPTIMIZE # ...))
; compiling (DECLAIM (FTYPE # ...) ...)
; compiling (DEFUN FIXNUMTEST ...)
; file: /opt/tmp/play.lisp
; in: DEFUN FIXNUMTEST
;     (* N N+1)
; 
; note: forced to do GENERIC-* (cost 30)
;       unable to do inline fixnum arithmetic (cost 4) because:
;       The result is a (VALUES
;                        (INTEGER -21267647932558653961849226946058125312
;                         21267647932558653961849226946058125312)
;                        &OPTIONAL), not a (VALUES FIXNUM &REST T).
;       unable to do inline (signed-byte 64) arithmetic (cost 5) because:
;       The result is a (VALUES
;                        (INTEGER -21267647932558653961849226946058125312
;                         21267647932558653961849226946058125312)
;                        &OPTIONAL), not a (VALUES (SIGNED-BYTE 64) &REST T).
;       etc.

Also, am I correct to think that doing float to pointer coercion (cost 13) is the ordinary consequence of returning a float from a function?

;     (DEFUN FIXNUMTEST (I J)
;       (DECLARE (TYPE FIXNUM I J))
;       (LET* ((N (THE FIXNUM #)) (N+1 (THE FIXNUM #)))
;         (DECLARE (TYPE FIXNUM N N+1))
;         (/ 1.0d0 (THE FIXNUM (* N N+1)))))
; --> PROGN SB-IMPL::%DEFUN SB-IMPL::%DEFUN SB-INT:NAMED-LAMBDA 
; ==>
;   #'(SB-INT:NAMED-LAMBDA FIXNUMTEST
;         (I J)
;       (DECLARE (SB-C::TOP-LEVEL-FORM))
;       (DECLARE (TYPE FIXNUM I J))
;       (BLOCK FIXNUMTEST
;         (LET* ((N #) (N+1 #))
;           (DECLARE (TYPE FIXNUM N N+1))
;           (/ 1.0d0 (THE FIXNUM #)))))
; 
; note: doing float to pointer coercion (cost 13) to "<return value>"
3
optimizationlispcommon-lispsbclfixnum
What should happen on overflow for sufficiently large N? Instead of fixnums which is implementation-dependant, it usually helps to specify the range of allowed values (in practice a subset of fixnum) and either saturate or wrap any overflow. Also, you are overdoing it with "the" when the variable is already declared a type. (the minimal portable size is 16bits for fixnums but if you declare types finely it is usually for a particular impl) – coredump
>>What should happen<< Currently don't care. afaict SBCL should be convinced to do inline fixnmum arithmetic in that code snippet. I'm just trying to understand why "forced to do GENERIC-*". >>overdoing it with "the"<< But still not convincing SBCL to do inline fixnum arithmetic. – igouy

3 Answers

4
votes

Well, the compiler is telling you the answer, perhaps in a slightly unhelpful way. If you have two fixnums then it is not the case that, for instance, adding them results in a fixnum: the type fixnum is not closed under arithmetic operations (not even under +, - and *, disregarding /).

From the SBCL manual:

The SBCL compiler treats type declarations differently from most other Lisp compilers. Under default compilation policy the compiler doesn’t blindly believe type declarations, but considers them assertions about the program that should be checked: all type declarations that have not been proven to always hold are asserted at runtime.

What you need to do if you want to compile machine arithmetic is to tell the compiler that the types it is using are good enough that it can know that the result types are good enough that they can be represented immediately.

Given the arithmetic you have in the function, and assuming a 64-bit implementation, then a good type is (signed-byte 31): it's tempting to use (signed-byte 32) but this fails, because you end up with something that is bigger than a (signed-byte 64).

So this code does not warn except for consing the final double float on return:

(deftype smallish-integer (&optional (bits 31))
  `(signed-byte ,bits))


(declaim (ftype (function (smallish-integer smallish-integer) double-float)
                fixnumtest)
         (inline fixnumtest))

(defun fixnumtest (i j)
  (declare (optimize (speed 2)))
  (declare (type smallish-integer i j))
  (let* ((n (+ i j))
         (n+1 (1+ n)))
    (/ 1.0d0 (* n n+1))))

It's worth noting that a (signed-byte 64) is quite a lot larger than a fixnum: this is OK, because within a function the compiler can cope with numbers which fit in registers even though they are bigger than fixnums.

I am not familiar enough with x64 assembler to check that all the arithmetic is compiled as machine instructions, but it looks like it is.

It may be possible to persuade the SBCL compiler that you don't care about getting the correct answer and that it should just do machine arithmetic even though it knows it may overflow. I have no idea how to do that.

1
votes

Seems that the answer tfb provided allows the code snippet to be reduced a little more:

(declaim (optimize (speed 2)))

(deftype smallish-integer (&optional (bits 31))
  `(signed-byte ,bits))

(declaim (inline smallishtest))
(defun smallishtest (i j)
  (declare (type smallish-integer i j))
  (/ 1.0d0 (* (+ i j) (+ i j 1))))

(defun main () 
  (format t "~11,9F~%" (smallishtest 2 3))
)

:and still give only one compilation note:

; note: doing float to pointer coercion (cost 13) to "<return value>"

Then reduced just a little more:

(deftype smallish-integer (&optional (bits 31))
  `(signed-byte ,bits))

(declaim (inline smallishtest))
(defun smallishtest (i j)
  (declare (type smallish-integer i j))
  (/ 1.0d0 (* (+ i j) (+ i j 1))))

(defun main () 
  (format t "~11,9F~%" (smallishtest 2 3))
)
1
votes

I found a good answer in the paper Efficient Hardware Arithmetic in Common Lisp. The key problem is well described by @tfb. The arithmetic operations may go out of range.

Ok Way

The first way to resolve this is to declare the resulting type is still a fixnum. However, it if overflows the result is undefined:

(defun add-e (x y)
  (declare (type (unsigned-byte 32) x y))
  (the (unsigned-byte 32) (+ x y)))

Better Way

A better way is to use bitwise operations on the result:

(defun add-d (x y)
  (declare (type (unsigned-byte 32) x y))
  (logand (+ x y) #xffffffff))

Even if it overflows, the result is still what you would expect.

Modern compilers will optimize this away to seeing that the result lies within an acceptable range to use hardware representations.

The paper is worth reading in more detail.