13

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

然而，在某一时刻，我的任务规模变得更大，我认为 C 可能更适合他们，而且确实如此。也许我在 [任何] 编程方面不够熟练，但我无法使 Haskell 像 C 一样具有速度效率，即使我听说适当的 Haskell 能够提供类似的性能。

最近，我想我会再次尝试一些 Haskell，虽然它对于通用的简单（在计算方面）任务仍然很棒，但它似乎无法将 C 的速度与 Collat​​z 猜想等问题相提并论。我读过了：

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

GHC 优化：Collat​​z 猜想

使用haskell的collat​​z-list实现

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

  • 选择“更严格”的类型，比如 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("%d\n", 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 代码是否仅针对计算简单的任务编写快速且易于维护，并且在性能至关重要时失去了这一特性？

4

1 回答 1

20

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

是的，您编写了n % 2and 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 后端进行编译，您甚至不需要将% 2and替换为/ 2按位操作，LLVM 会为您做到这一点（但它会为您的原始 Haskell 源代码生成更慢的代码，0.4 秒，令人惊讶的是 - 通常，LLVM 不是比循环优化的本机代码生成器差）。

使用 32 位 GHC，您将无法获得可比的速度，因为使用这些，对 64 位整数的原始操作是通过 C 调用实现的——在 32 位系统上对快速 64 位操作的需求永远不够它们将作为primops实施；少数从事 GHC 工作的人把时间花在了其他更重要的事情上。

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

那要看。您必须对 GHC 从何种输入生成何种代码有所了解，并且必须避免一些性能陷阱。通过一些练习，对于此类任务，很容易达到 gcc -O3 的 2 倍速度。

于 2012-12-02T12:28:19.677 回答