为什么在Haskell中，这种斐波那契的尾递归运行速度比纯树递归要快？
这篇文章探讨了为什么在Haskell中，这种尾递归的斐波那契函数运行速度比纯树递归的函数快。文章首先介绍了在测试GHC代码性能时，使用GHCi交互式提示的结果可能会非常误导人，因此建议在使用ghc -O2编译的独立可执行文件中进行测试。此外，文章还建议添加显式的类型签名，并确保-Wall没有报告任何关于“默认类型”的警告，否则GHC可能会选择你不打算使用的默认数值类型。最后，建议使用criterion基准测试库，因为它能够生成可靠且可重复的计时结果。
文章接着介绍了通过使用Criterion库对两个斐波那契函数版本进行基准测试。测试的源代码如下所示：
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编译这段代码，测试结果如下：
$ ./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类型后，性能得到了显著提升。
文章接着介绍了GHC编译器生成的中间形式——STG（Spineless, Tagless, G-machine）。通过对生成的STG进行分析，文章发现fib和fib'之间的差异在于尾调用的使用。尾调用的优化可以减少指令数目，从而提高性能。
文章最后总结道，在其他情况下，重新组织函数以引入尾调用可能会或多或少地提高性能。本例中，函数的重新组织对STG的影响非常有限，所以尾调用带来的几条指令的改进并没有被其他因素淹没。
文章解释了为什么fib'版本比fib版本快，这主要是因为尾调用带来的微小性能提升。文章还提到了测试代码性能时应该注意的一些技巧，如使用ghc -O2编译、添加显式的类型签名等。