如何说服 Lisp SBCL 进行内联 fixnum 运算？

Question

我在其他 SO 答案中找到了一些技巧，但显然我一直无法说服 SBCL 进行内联 fixnum 算术：

(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))
)

：结果为 forced to do GENERIC-* (cost 30)

我还应该尝试什么？

$ 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.

此外，我认为 doing float to pointer coercion (cost 13) 是从函数返回浮点数的普通结果是否正确？

;     (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>"

Answer 1

好吧，编译器正在告诉你答案，也许是以一种有点无用的方式。如果你有两个 fixnums 那么情况就不是这样，例如，将它们相加会得到一个 fixnum：类型 fixnum 在算术运算下不闭合（甚至在 +、[=13= 下也不闭合） ] 和 *，忽略 /)。

来自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.

如果你想编译机器算法，你需要做的是告诉编译器它正在使用的类型足够好，它可以知道结果类型足够好，可以立即表示它们。

鉴于函数中的算法，并假设是 64 位实现，那么一个好的类型是 (signed-byte 31)：使用 (signed-byte 32) 很诱人，但这失败了，因为你最终比 (signed-byte 64).

大的东西

所以除了在 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))))

值得注意的是 (signed-byte 64) 比 fixnum 大很多：这没关系，因为在一个函数中，编译器可以处理适合寄存器的数字，即使它们是大于 fixnums。

我对 x64 汇编程序不够熟悉，无法检查所有算术是否都编译为机器指令，但看起来确实如此。

可能会说服 SBCL 编译器您不关心获得正确答案，它应该只执行机器算术，即使它知道它可能会溢出。我不知道该怎么做。

Answer 2

似乎提供的答案tfb允许代码片段再减少一点：

(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))
)

:还是只给一个编译笔记：

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

然后再减少一点：

(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))
)

Answer 3

我在论文Efficient Hardware Arithmetic in Common Lisp中找到了一个很好的答案。 @tfb 很好地描述了关键问题。算术运算可能超出范围。

好的

解决这个问题的第一种方法是声明结果类型仍然是 fixnum。但是，如果溢出，结果是未定义的：

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

更好的方式

更好的方法是对结果使用按位运算：

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

即使溢出了，结果还是如你所愿

现代编译器会对此进行优化，以确保结果在使用硬件表示的可接受范围内。

这篇论文值得更详细地阅读。

如何说服 Lisp SBCL 进行内联 fixnum 运算？

How to convince Lisp SBCL to do inline fixnum arithmetic?

lisp

optimization

sbcl

common-lisp

fixnum