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. 

不知道，在哪里可以继续。我已经试图在乘法，除法和减法之间插入'fixnum'，但它只是变得更糟。

任何想法，如何使这个快？

Answer 1

如果您确定这些数字在任何时候都不会溢出，您可以将(SAFETY 0)添加到优化中。还要在计算周围添加(THE FIXNUM ...)以告诉SBCL您希望将结果作为修正号处理。三个参数*应该分成两个独立的调用。

您的代码目前正在循环中计算两次(- (* 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)) 

Answer 2

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

因此，您需要做的是声明具有良好类型的参数：特别是小于fixnum的算术不会溢出到bignum s的类型。假设你使用的是64位平台，这相当容易。