为什么这种简化使我的功能变慢？

Question

下面的函数计算由尾递归和平方斐波纳契数列：

(defun fib1 (n &optional (a 1) (b 0) (p 0) (q 1)) 
    (cond ((zerop n) b) 
    ((evenp n) 
    (fib1 (/ n 2) 
      a 
      b 
      (+ (* p p) (* q q)) 
      (+ (* q q) (* 2 p q)))) 
    (t 
    (fib1 (1- n) 
      (+ (* b q) (* a (+ p q))) 
      (+ (* b p) (* a q)) 
      p 
      q)))) 

基本上它每个奇数输入减小到甚至一个，并且减少了一半每个偶数输入。例如，

F(21) 
    = F(21 1 0 0 1) 
    = F(20 1 1 0 1) 
    = F(10 1 1 1 1) 
    = F(5 1 1 2 3) 
    = F(4 8 5 2 3) 
    = F(2 8 5 13 21) 
    = F(1 8 5 610 987) 
    = F(0 17711 10946 610 987) 
    = 10946 

当我看到这个我想这可能是更好的偶数和奇数的情况结合起来（因为奇减一=偶数），所以我写了

(defun fib2 (n &optional (a 1) (b 0) (p 0) (q 1)) 
    (if (zerop n) b 
    (fib2 (ash n -1) 
      (if (evenp n) a (+ (* b q) (* a (+ p q)))) 
      (if (evenp n) b (+ (* b p) (* a q))) 
      (+ (* p p) (* q q)) 
      (+ (* q q) (* 2 p q))))) 

，并希望这将使其更快，如上述现在方程变为

F(21) 
    = F(21 1 0 0 1) 
    = F(10 1 1 1 1) 
    = F(5 1 1 2 3) 
    = F(2 8 5 13 21) 
    = F(1 8 5 610 987) 
    = F(0 17711 10946 1346269 2178309) 
    = 10946 

但是，它变成了要慢得多（需要更多的约50％的时间在例如Clozure CL，CLISP和Lispworks）当我检查需要F上的时间IB（1000000）由下面的代码（忽略progn这个，我只是不想让我的屏幕上写满数字。）

(time (progn (fib1 1000000)())) 
(time (progn (fib2 1000000)())) 

我只能看到FIB2可以做的比FIB1更evenp，所以那为什么慢得多？

编辑：我想下午。做对了，我编辑了第二组公式。例如。在上面F（21）的例子中，fib2实际上计算了p和q中的F（31）和F（32），这是从未使用过的。所以在F（1000000）中，fib2计算F（1048575）和F（1048576）。

懒惰的评价岩石，这是一个很好的观点。我猜在Common Lisp中，只有一些像“and”和“or”这样的宏被懒惰地评估了吗？

以下改性FIB2（对于n定义> 0）实际上运行速度更快：

(defun fib2 (n &optional (a 1) (b 0) (p 0) (q 1)) 
    (if (= n 1) (+ (* b p) (* a q)) 
    (fib2 (ash n -1) 
      (if (evenp n) a (+ (* b q) (* a (+ p q)))) 
      (if (evenp n) b (+ (* b p) (* a q))) 
      (+ (* p p) (* q q)) 
      (+ (* q q) (* 2 p q))))) 

Answer 1

插入打印中间结果。在计算结束时请注意p和q。

您会注意到fib2在最后一步计算了p和q的很大的值。这两个值说明了所有的性能差异。

具有讽刺意味的是，这些昂贵的价值是未使用的。这就是为什么Haskell不会遇到这个性能问题：未使用的值实际上没有计算。

Answer 2

如果没有别的，FIB2具有更多的条件句（而计算的参数）。这可能会改变代码流的完成方式。条件意味着跳跃，意味着管道延迟。

查看生成的代码可能很有意义（尝试(disassemble #'fib1)和(disassemble #'fib2)并查看是否存在明显差异）。改变优化设置可能也是值得的，通常只有很少的优化没有完成，除非你要求对速度进行大量优化。