为什么这段 Haskell 代码比 C 慢那么多

Stack Overflow 是个神奇的网站，大神调教出了一个比 C 更快的 Haskell 版本，还很优雅，连尾递归都（几乎）没用！

本回答转自 Stack Overflow，原作者 András Kovács，回答的英文原始地址请戳这里。

这段代码的性能取决于好几个因素。搞定其中的每一个，这段代码的性能能达到 C 版本的水平。这些因素分别是：

一、使用正确的整数类型
题目中给出的 C 代码并非最佳：它在所有架构上均使用 32 位整数（主流 C 实现中，只有 long 在 64 位机器上为八个字节），而 Haskell 的 Int 在 64 位机器上是 64 位整数。比较要想准确，我们就应该在两段代码里使用相同的整数类型。此外，如非必要，我们都应当在 Haskell 代码里使用原生的整数类型，即在 64 位机器上使用 64 位数字，而不是 Int32 或者 Word32 之流，因为 GHC 对非原生整数类型的操作往往是通过调用外部 C 函数来实现的，这很慢。

二、collatzNext 中的除法操作
对 Int 来说，div 比 quot 慢很多，这是因为 div 对负数有特殊处理。用 Word 之所以会让程序变快，是因为对 Word 来说，div 和 quot 是一样的。但这还是比 C 要慢一些。除以二可以通过右移一位来实现。因为种种原因，即使 LLVM 也没有实现这一特定优化，所以我们最好手工实现它，将 quot n 2 换成 shiftR n 1。

三、奇偶检查
最快的检查奇偶的方式莫过于看最后一二进制位的值了。LLVM 可以对 even 函数做此优化，而 GHC 默认的后段则不可以。因此，如果我们要使用默认的后端，我们可以把 even n 换成 n .&. 1 == 0，这对性能有着不错的提示。

然而，我发现 GHC 7.10 有一个小性能 bug：它没有为 Word 类型内联 even 函数，这对性能影响很大（一次额外的函数调用，Word 是 box 类型因而分配在堆上，even 函数位于代码最「活跃」的路径上）。因此，我们应该使用 rem n 2 == 0 或者 n .&. 1 == 0 而不是 even 函数。不过 GHC 对 Int 类型还是会内联 even 的。