haskell - 为什么这种斐波那契的尾调用比 Haskell 中的纯树递归运行得更快？

在 GHCi 交互式提示符下测试的代码性能可能会产生误导，因此在对 GHC 代码进行基准测试时，最好在使用ghc -O2. 添加显式类型签名并确保-Wall不报告任何有关“默认”类型的警告也很有帮助。否则，GHC 可能会选择您不希望的默认数字类型。最后，使用criterion基准测试库也是一个好主意，因为它可以很好地生成可靠且可重现的时序结果。

fib使用程序以这种方式对您的两个版本进行基准测试：

import Criterion.Main

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

fib' :: Integer -> Integer -> Integer
fib' 0 a = a
fib' 1 a = 1 + a
fib' n a = fib' (n-1) (fib' (n-2) a)

main :: IO ()
main = defaultMain
  [ bench "fib" $ whnf fib 30
  , bench "fib'" $ whnf (fib' 30) 0
  ]

使用 GHC 8.6.5 编译ghc -O2 -Wall Fib2.hs，我得到：

$ ./Fib2
benchmarking fib
time                 40.22 ms   (39.91 ms .. 40.45 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 39.91 ms   (39.51 ms .. 40.11 ms)
std dev              581.2 μs   (319.5 μs .. 906.9 μs)

benchmarking fib'
time                 38.88 ms   (38.69 ms .. 39.06 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 38.57 ms   (38.49 ms .. 38.67 ms)
std dev              188.7 μs   (139.6 μs .. 268.3 μs)

这里的差异很小，但可以始终如一地复制。该fib'版本比该fib版本快约 3-5%。

在这一点上，可能值得指出我的类型签名使用了Integer. 这也是 GHC 在没有显式类型签名的情况下选择的默认值。将这些替换Int为可带来巨大的性能提升：

benchmarking fib
time                 4.877 ms   (4.850 ms .. 4.908 ms)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 4.766 ms   (4.730 ms .. 4.808 ms)
std dev              122.2 μs   (98.16 μs .. 162.4 μs)

benchmarking fib'
time                 3.295 ms   (3.260 ms .. 3.332 ms)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 3.218 ms   (3.202 ms .. 3.240 ms)
std dev              62.51 μs   (44.57 μs .. 88.39 μs)

这就是为什么我建议包含显式类型签名并确保没有关于默认类型的警告。Integer否则，当真正的问题是在本来可以使用时使用的循环索引时，您可能会花费大量时间来追求微小的改进Int。对于这个例子，当然，还有一个额外的问题是算法都是错误的，因为算法是二次的，并且线性实现是可能的，就像通常的“聪明的 Haskell”解决方案一样：

-- fib'' 30 runs about 100 times faster than fib 30
fib'' :: Int -> Int
fib'' n = fibs !! n
  where fibs = scanl (+) 0 (1:fibs)

无论如何，让我们切换回fib并fib'使用Integer这个答案的其余部分......

GHC 编译器生成称为 STG（无脊椎、无标记、G 机器）的程序的中间形式。它是最高级别的表示，忠实地表示程序将如何实际运行。STG 的最佳文档以及它如何实际转换为堆分配和堆栈帧是论文制作快速咖喱：push/enter vs eval/apply for high-order languages。阅读本文时，图 1 是 STG 语言（尽管语法与 GHC 生成的不同-ddump-stg），图 2 的第一个和第三个面板显示了如何使用 eval/apply 方法评估 STG（与当前 GHC 生成的代码匹配）。还有一篇较旧的论文在股票硬件上实现惰性函数式语言：Spineless Tagless G-machine这提供了更多细节（可能太多），但它有点过时了。

无论如何，要查看和之间的区别fib，fib'我们可以使用以下命令查看生成的 STG：

ghc -O2 -ddump-stg -dsuppress-all -fforce-recomp Fib2.hs

采用 STG 输出并对其进行大量清理以使其看起来更像“常规 Haskell”，我得到以下定义：

fib = \n ->                          fib' = \n a ->
  case (==) n 0 of                     case (==) n 0 of
    True -> 0                            True -> a;
    _ ->                                 _ ->
      case (==) n 1 of                     case (==) n 1 of
        True -> 1                            True -> (+) 1 a;                 -- (6)
        _ ->                                 _ ->
          case (-) n 2 of                      case (-) n 2 of
            n_minus_2 ->                         n_minus_2 ->
              case fib n_minus_2 of                case fib' n_minus_2 a of
                y ->                                 y ->
                  case (-) n 1 of                      case (-) n 1 of
                    n_minus_1 ->                         n_minus_1 ->
                      case fib n_minus_1 of                fib' n_minus_1 y   -- (14)
                        x -> (+) x y

在这里，严格性分析已经使整个计算变得严格。这里没有创建 thunk。（在 STG 中，只有let块创建 thunk，而这个 STG 中没有let块。）因此，这两种实现之间的（最小）性能差异与严格与懒惰无关。

忽略的额外参数fib'，请注意这两个实现在结构上基本相同，除了第 (6) 行中的fib'加法运算和第 (14) 行中的加法运算的 case 语句fib。

要了解这两种实现的区别，首先需要了解一个函数调用f a b是编译成伪代码的：

lbl_f:  load args a,b
        jump to f_entry

请注意，所有函数调用，无论它们是否是尾调用，都被编译为这样的跳转。当代码f_entry完成时，它将跳转到堆栈顶部的任何延续帧，所以如果调用者想要对函数调用的结果做一些事情，它应该在跳转之前推送一个延续帧。

例如，代码块：

case f a b of
    True -> body1
    _    -> body2

想要对的返回值做一些事情f a b，所以它编译为以下（未优化的）伪代码：

        push 16-byte case continuation frame <lbl0,copy_of_arg1> onto the stack
lbl_f:  -- code block for f a b, as above:
        load args a,b
        jump to f_entry   -- f_entry will jump to lbl0 when done
lbl0:   restore copy_of_arg1, pop case continuation frame
        if return_value == True jump to lbl2 else lbl1
lbl1:   block for body1
lbl2:   block for body2

知道了这一点，第 (6) 行的两个实现之间的区别是伪代码：

-- True -> 1                              -- True -> (+) 1 a
load 1 as return value                    load args 1,a
jump to next continuation                 jump to "+"
                                          -- Note: "+" will jump to next contination

两种实现在第 (14) 行的区别是：

-- case fib n_minus_1 of ...              -- fib' n_minus_1 y
        push case continuation <lbl_a>    load args n_minus_1,y
        load arg n_minus_1                jump to fib'
        jump to fib
lbl_a:  pop case continuation
        load args returned_val,y
        jump to "+"

一旦它们被优化，它们之间实际上几乎没有任何性能差异。为这些块生成的汇编代码是：

-- True -> 1                              -- True -> (+) 1 a
                                          movq 16(%rbp),%rsi
movl $lvl_r83q_closure+1,%ebx             movl $lvl_r83q_closure+1,%r14d
addq $16,%rbp                             addq $24,%rbp
jmp *(%rbp)                               jmp plusInteger_info

-- case fib n_minus_1 of ...              -- fib' n_minus_1 y
movq $block_c89A_info,(%rbp)              movq 8(%rbp),%rax
movq %rbx,%r14                            addq $16,%rbp
jmp fib_info                              movq %rax,%rsi
movq 8(%rbp),%rsi                         movq %rbx,%r14
movq %rbx,%r14                            // fall through to start of fib'
addq $16,%rbp
jmp plusInteger_info

这里的区别是一些说明。保存了更多指令，因为直通fib' n_minus_1 y跳过了堆栈大小检查的开销。

在 using 的版本中Int，加法和比较都是单条指令，两个程序集之间的区别是——据我统计——总共大约 30 条指令中有 5 条指令。由于紧密的循环，这足以解释 33% 的性能差异。

因此，底线是没有fib'比更快的基本结构原因fib，并且小的性能改进归结为尾调用允许的少量指令顺序的微优化。

在其他情况下，重新组织函数以引入这样的尾调用可能会也可能不会提高性能。这种情况可能很不寻常，因为函数的重组对 STG 的影响非常有限，因此一些指令的净改进并没有被其他因素所淹没。

haskell - 为什么这种斐波那契的尾调用比 Haskell 中的纯树递归运行得更快？

问题描述

解决方案

推荐阅读