为什么这种斐波那契的尾部调用 运行 比 Haskell 中的纯树递归更快？
Why does this kind of tail call of fibonacci run faster than pure tree recursion in Haskell?
我正在尝试理解尾调用递归。我转换纯树递归斐波那契函数：
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
尾调用版本：
fib' 0 a = a
fib' 1 a = 1 + a
fib' n a = fib' (n-1) (fib' (n-2) a)
当我尝试这两个版本时，似乎第二个版本比第一个树回避更快，即使我试图在第二个版本中使用 seq 强制严格评估！
Haskell 如何在 GHC 中处理此类尾调用？谢谢！
在 GHCi 交互式提示下测试的代码性能可能会产生误导，因此在对 GHC 代码进行基准测试时，最好在使用 ghc -O2 编译的独立可执行文件中对其进行测试。添加显式类型签名并确保 -Wall 不报告任何有关 "defaulting" 类型的警告也很有帮助。否则，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 -O2 -Wall Fib2.hs 使用 GHC 8.6.5 编译，我得到：
$ ./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 时，您可能会花费大量时间追求微小的改进。对于这个例子，当然，还有一个额外的问题，算法是完全错误的，因为算法是二次的，并且线性实现是可能的，就像通常的 "clever 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（spineless、tagless、G-machine）的程序的中间形式。它是最高级别的表示，忠实地表示程序的实际情况 运行。关于 STG 以及它如何实际转化为堆分配和栈帧的最佳文档是论文Making a fast curry: push/enter versus eval/apply for higher-order languages. When reading this paper, Figure 1 is the STG language (though the syntax differs from what GHC produces with -ddump-stg) and Figure 2's first and third panels show how STG is evaluated using an eval/apply approach (which matches current GHC-generated code). There's also an older paper Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine，它提供了更多的细节（可能太多了），但它有点过时了。
总之，要看fib和fib'的区别，我们可以看看生成的STG使用：
ghc -O2 -ddump-stg -dsuppress-all -fforce-recomp Fib2.hs
获取 STG 输出并对其进行大量清理，使其看起来更像 "regular 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'的额外参数，注意这两个实现在结构上本质上是相同的，除了[=27=中第(6)行的加法操作]和fib.
中第(14)行加法运算的case语句
要理解这两种实现的区别，首先需要明白一个函数调用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 的 return 值做一些事情，所以它编译为以下（未优化的）伪代码：
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 ,%rbp addq ,%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 ,%rbp
jmp fib_info movq %rax,%rsi
movq 8(%rbp),%rsi movq %rbx,%r14
movq %rbx,%r14 // fall through to start of fib'
addq ,%rbp
jmp plusInteger_info
这里的区别在于一些说明。由于 fib' n_minus_1 y 中的 fall-through 跳过了堆栈大小检查的开销，因此节省了更多指令。
在使用 Int 的版本中，加法和比较都是单条指令，根据我的统计，这两个程序集之间的区别是总共大约 30 条指令中的 5 条指令。由于紧密循环，这足以解释 33% 的性能差异。
所以，最重要的是 fib' 比 fib 快没有根本的结构原因，性能的小幅提升归结为少量的微优化尾调用允许的指令。
在其他情况下，重组函数以引入像这样的尾调用可能会也可能不会提高性能。这种情况可能是不寻常的，因为功能的重组对 STG 的影响非常有限，因此一些指令的净改进并没有被其他因素淹没。
我正在尝试理解尾调用递归。我转换纯树递归斐波那契函数：
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
尾调用版本：
fib' 0 a = a
fib' 1 a = 1 + a
fib' n a = fib' (n-1) (fib' (n-2) a)
当我尝试这两个版本时，似乎第二个版本比第一个树回避更快，即使我试图在第二个版本中使用 seq 强制严格评估！
Haskell 如何在 GHC 中处理此类尾调用？谢谢！
在 GHCi 交互式提示下测试的代码性能可能会产生误导，因此在对 GHC 代码进行基准测试时，最好在使用 ghc -O2 编译的独立可执行文件中对其进行测试。添加显式类型签名并确保 -Wall 不报告任何有关 "defaulting" 类型的警告也很有帮助。否则，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 -O2 -Wall Fib2.hs 使用 GHC 8.6.5 编译，我得到：
$ ./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 时，您可能会花费大量时间追求微小的改进。对于这个例子，当然，还有一个额外的问题，算法是完全错误的，因为算法是二次的，并且线性实现是可能的，就像通常的 "clever 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（spineless、tagless、G-machine）的程序的中间形式。它是最高级别的表示，忠实地表示程序的实际情况 运行。关于 STG 以及它如何实际转化为堆分配和栈帧的最佳文档是论文Making a fast curry: push/enter versus eval/apply for higher-order languages. When reading this paper, Figure 1 is the STG language (though the syntax differs from what GHC produces with -ddump-stg) and Figure 2's first and third panels show how STG is evaluated using an eval/apply approach (which matches current GHC-generated code). There's also an older paper Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine，它提供了更多的细节（可能太多了），但它有点过时了。
总之，要看fib和fib'的区别，我们可以看看生成的STG使用：
ghc -O2 -ddump-stg -dsuppress-all -fforce-recomp Fib2.hs
获取 STG 输出并对其进行大量清理，使其看起来更像 "regular 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'的额外参数，注意这两个实现在结构上本质上是相同的，除了[=27=中第(6)行的加法操作]和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 的 return 值做一些事情，所以它编译为以下（未优化的）伪代码：
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 ,%rbp addq ,%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 ,%rbp
jmp fib_info movq %rax,%rsi
movq 8(%rbp),%rsi movq %rbx,%r14
movq %rbx,%r14 // fall through to start of fib'
addq ,%rbp
jmp plusInteger_info
这里的区别在于一些说明。由于 fib' n_minus_1 y 中的 fall-through 跳过了堆栈大小检查的开销，因此节省了更多指令。
在使用 Int 的版本中，加法和比较都是单条指令，根据我的统计，这两个程序集之间的区别是总共大约 30 条指令中的 5 条指令。由于紧密循环，这足以解释 33% 的性能差异。
所以，最重要的是 fib' 比 fib 快没有根本的结构原因，性能的小幅提升归结为少量的微优化尾调用允许的指令。
在其他情况下，重组函数以引入像这样的尾调用可能会也可能不会提高性能。这种情况可能是不寻常的，因为功能的重组对 STG 的影响非常有限，因此一些指令的净改进并没有被其他因素淹没。