performance - C vs Haskell Collat​​z 猜想速度对比

Question

就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持，但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the help center寻求指导。




9年前关闭。




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

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

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

Speed comparison with Project Euler: C vs Python vs Erlang vs Haskell

GHC Optimization: Collatz conjecture

collatz-list implementation using haskell

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

选择“更严格”的类型，例如 Int64 而不是 Integer

开启 GHC 优化

使用简单的优化技术，例如避免不必要的计算或更简单的函数

仍然没有使 Haskell 代码甚至接近于几乎相同(就方法而言)非常大的数字的 C 代码。唯一使它的性能可以与 C 相媲美的 [对于大规模问题] 是使用优化方法，使代码变成一个漫长而可怕的单子(monad) hell ，这违背了 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 代码是否仅针对计算简单的任务编写快速且易于维护，并且在性能至关重要时失去了这一特性？

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.4 秒 - 通常，LLVM 在循环优化时并不比 native 代码生成器差)。

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

TL;DR: Is Haskell code quick to write and simple to maintain only for computationally simple tasks and loses this characteristic when performance is crucial?

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