SBCL: Fixnum 优化

Question

我正在尝试通过使用优化和Fixnums来提高一个小二次求解器的速度。以下是我的代码：

 1: (defun solve-x (d)
 2:   (declare (optimize (speed 3))
 3:               (type fixnum d))
 4:   (let ((x 1) (y 1))
 5:     (declare (type fixnum x y))
 6:     (loop while (/= (- (* x x) (* d y y)) 1) do
 7:       (if (> (- (* x x) (* d y y)) 1)
 8:         (incf y)
 9:         (incf x)))
10:     (list x y)))

SBCL编译器似乎在正确优化第6行和第7行的代码时遇到了问题。我收到了很多类似这样的警告：

forced to do GENERIC-- (cost 10)
      unable to do inline fixnum arithmetic (cost 2) because:
      The first argument is a (INTEGER 1 21267647932558653957237540927630737409), not a FIXNUM.
      The second argument is a (INTEGER
                                -98079714615416886892398913872502479823289163909206900736
                                98079714615416886871131265939943825866051622981576163327), not a FIXNUM.
      The result is a (VALUES
                       (INTEGER
                        -98079714615416886871131265939943825866051622981576163326
                        98079714615416886913666561805061133780526704836837638145)
                       &OPTIONAL), not a (VALUES FIXNUM &REST T).
      unable to do inline (signed-byte 64) arithmetic (cost 5) because:
      The first argument is a (INTEGER 1 21267647932558653957237540927630737409), not a (SIGNED-BYTE
                                                                                         64).
      The second argument is a (INTEGER
                                -98079714615416886892398913872502479823289163909206900736
                                98079714615416886871131265939943825866051622981576163327), not a (SIGNED-BYTE
                                                                                                  64).
      The result is a (VALUES
                       (INTEGER
                        -98079714615416886871131265939943825866051622981576163326
                        98079714615416886913666561805061133780526704836837638145)
                       &OPTIONAL), not a (VALUES (SIGNED-BYTE 64) &REST T).
      etc.

不知道该从哪里继续。我已经尝试在乘法、除法和减法周围插入“the fixnum”，但情况只会变得更糟。

有什么办法可以让这个更快吗？

- Hennes

---

我发现了另一种方法，通过对结果进行位运算来实现。请参考类似的问题：https://dev59.com/Y7bna4cB1Zd3GeqPjvPs - Justin Meiners

Answer 1

如果你确定数字不会在任何时候溢出，你可以在优化中添加(SAFETY 0)。此外，在计算周围添加(THE FIXNUM ...)，告诉SBCL您希望将结果视为fixnum。应该将三参数*分成两个单独的调用。 你的代码目前在循环中两次计算(- (* x x) (* d y y))。你应该将其赋值给一个变量。还要注意，由于只有X或Y在循环中更改，因此无需重新计算另一部分（我不知道这些计算是什么，所以我只称它们为FOO、BAR和QUUX）。

(defun solve-x (d)
  (declare (optimize (speed 3) (safety 0) (debug 0))
           (type fixnum d))
  (let ((x 1) (y 1))
    (declare (type fixnum x y))
    (loop with foo of-type fixnum = (* x x)
          with bar of-type fixnum = (* (the fixnum (* d y)) y)
          for quux of-type fixnum = (- foo bar)
          while (/= quux 1)
          do (if (> quux 1)
                 (setf y (1+ y)
                       bar (* (the fixnum (* d y)) y))
                 (setf x (1+ x)
                       foo (* x x))))
    (list x y)))

为了避免重复编写公式，您可以使用#n=读取器宏。将X和Y作为&AUX变量移动到参数列表中，以消除LET和第二个DECLARE。

(defun solve-x (d &aux (x 1) (y 1))
  (declare (optimize (speed 3) (safety 0) (debug 0))
           (type fixnum d x y))
  (loop with foo of-type fixnum = #1=(* x x)
        with bar of-type fixnum = #2=(* d (the fixnum (* y y)))
        for quux of-type fixnum = (- foo bar)
        while (/= quux 1)
        do (if (> quux 1)
               (setf y (1+ y)
                     bar #2#)
               (setf x (1+ x)
                     foo #1#)))
  (list x y))

由于X和Y总是增加一个，你可以通过递增上一个值来避免一些乘法计算。

(defun solve-x (d &aux (x 1) (y 1))
  (declare (optimize (speed 3) (safety 0) (debug 0))
           (type fixnum d x y))
  (loop with foo of-type fixnum = 1
        with bar of-type fixnum = d
        for quux of-type fixnum = (- foo bar)
        while (/= quux 1)
        do (if (> quux 1)
               (setf bar (+ bar (the fixnum (* d y)))
                     y (1+ y)
                     bar (+ bar (the fixnum (* d y))))
               (setf foo (+ foo x)
                     x (1+ x)
                     foo (+ foo x))))
  (list x y))

- jkiiski

Answer 2

问题在于fixnum不是一个非常有用的类型。特别地，如果a和b是fixnum，那么(* a b)很可能不是fixnum：考虑(* most-positive-fixnum most-positive-fixnum)：这不是一个fixnum。

因此，您需要声明参数具有良好的类型：特别是比fixnum小得足以使算术运算不会溢出到bignum中。假设您正在使用64位平台，这相当容易。

- user5920214

Answer 3

我不知道您的应用程序中这些数字有多大，但将它们声明为（signed-byte 31）可以带来另外约25％的速度提升。

(deftype int31 (&optional (bits 31)) `(signed-byte ,bits))
(defun solve-x (d &aux (x 1) (y 1))
  (declare (optimize (speed 3) (safety 0) (debug 0))
           (type int31 d x y))
  (loop with foo of-type int31 = 1
        with bar of-type int31 = d
        for quux of-type int31 = (- foo bar)
        while (/= quux 1)
        do (if (> quux 1)
               (setf bar (+ bar (the int31 (* d y)))
                     y (1+ y)
                     bar (+ bar (the int31 (* d y))))
               (setf foo (+ foo x)
                     x (1+ x)
                     foo (+ foo x))))
  (list x y))

- bpecsek