C与Haskell-Collatz猜想的速度比较

Question

我第一次真正的编程经历是使用Haskell。对于我的特殊需求，我需要一个易于学习、快速编码和易于维护的工具，我可以说它做得很好。

然而，有一次我的任务规模变得更大了，我认为C可能更适合他们，事实确实如此。也许我在编程方面不够熟练，但我没能让Haskell像C一样高效，尽管我听说合适的Haskell也能有类似的性能。

最近，我想我会再次尝试一些Haskell，虽然它对于一般的简单任务(就计算而言)仍然很好，但它似乎无法将C的速度与Collatz猜想等问题相匹配。我读过：

与Project Euler的速度比较：C与Python与Erlang与Haskell

GHC优化：Collatz猜想

使用haskell 实现collatz列表

但据我所见，简单的优化方法，包括：

• 选择"更紧密"的类型，如Int64而不是Integer
• 打开GHC优化
• 使用简单的优化技术，如避免不必要的计算或更简单的函数

仍然不能使Haskell代码对于真正大的数字甚至接近于几乎相同的(在方法方面)C代码。唯一能使其性能与C(针对大规模问题)相媲美的是使用优化方法，使代码成为一个漫长而可怕的一元地狱，这违背了Haskell(和我)非常重视的原则。

这是C版本：

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int32_t col(int64_t n);
int main(int argc, char **argv)
{
int64_t n = atoi(argv[1]), i;
int32_t s, max;
for(i = 2, max = 0; i <= n; ++i)
{
s = col(i);
if(s > max) max = s;
}
printf("%dn", max);
return 0;
}
int32_t col(int64_t n)
{
int32_t s;
for(s = 0; ; ++s)
{
if(n == 1) break;
n = n % 2 ? 3 * n + 1 : n / 2;
}
return s;
}

和Haskell版本：

module Main where
import System.Environment (getArgs)
import Data.Int (Int32, Int64)
main :: IO ()
main = do
arg <- getArgs
print $ maxCol 0 (read (head arg) :: Int64)
col :: Int64 -> Int32
col x = col' x 0
col' :: Int64 -> Int32 -> Int32
col' 1 n            = n
col' x n
| rem x 2 == 0  = col' (quot x 2) (n + 1)
| otherwise     = col' (3 * x + 1) (n + 1)
maxCol :: Int32 -> Int64 -> Int32
maxCol maxS 2   = maxS
maxCol maxS n
| s > maxS  = maxCol s (n - 1)
| otherwise = maxCol maxS (n - 1)
where s = col n

TL；DR：Haskell代码是否只针对计算简单的任务编写快速、维护简单，并且在性能至关重要时会失去这一特性？

Answer 1

Haskell代码的最大问题是您正在划分，而在C版本中没有。

是的，您编写了n % 2和n / 2，但编译器将其替换为移位和逐位和。不幸的是，GHC还没有被教导这样做。

如果你自己做替换

module Main where
import System.Environment (getArgs)
import Data.Int (Int32, Int64)
import Data.Bits
main :: IO ()
main = do
arg <- getArgs
print $ maxCol 0 (read (head arg) :: Int64)
col :: Int64 -> Int32
col x = col' x 0
col' :: Int64 -> Int32 -> Int32
col' 1 n            = n
col' x n
| x .&. 1 == 0  = col' (x `shiftR` 1) (n + 1)
| otherwise     = col' (3 * x + 1) (n + 1)
maxCol :: Int32 -> Int64 -> Int32
maxCol maxS 2   = maxS
maxCol maxS n
| s > maxS  = maxCol s (n - 1)
| otherwise = maxCol maxS (n - 1)
where s = col n

使用64位GHC，您可以获得相当的速度(0.35秒与我的盒子上的C的0.32秒，限制为1000000)。如果您使用LLVM后端进行编译，您甚至不需要用逐位操作替换% 2和/ 2，LLVM就可以做到这一点(但它为您的原始Haskell源代码生成的代码较慢，为0.4s，令人惊讶-通常，LLVM在循环优化方面并不比本机代码生成器差)。

使用32位GHC，您将无法获得类似的速度，因为使用这些GHC，64位整数上的基元运算是通过C调用实现的——对于32位系统上的快速64位运算，从未有足够的需求将其实现为基元运算；为数不多的GHC工作人员把时间花在了其他更重要的事情上。

TL；DR：Haskell代码是否只针对计算简单的任务编写快速、维护简单，并且在性能至关重要时会失去这一特性？

这取决于情况。您必须知道GHC从什么类型的输入中生成什么类型的代码，并且必须避免一些性能陷阱。经过一点实践，很容易达到2倍于gcc-O3的速度。