C vs Haskell Collat​​z猜想速度比較

Question

我的第一個真正的編程經驗是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優化在
• S使用簡單的優化技術，如避免不必要的計算或簡單的功能

還是不要讓Haskell代碼甚至接近幾乎相同（在方法方面）爲真正的大號碼的C代碼。唯一能夠使它的性能與C相當（用於大規模問題）的唯一方法是使用優化方法，使代碼成爲漫長而可怕的monadic地獄，這違背了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，但是編譯器用shift和bitwise來替換它。遺憾的是，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.35S對C的0.32s我框的1000000限制）。如果使用LLVM後端進行編譯，甚至不需要用位操作替換% 2和/ 2，LLVM可以爲您執行此操作（但對於原始Haskell源代碼而言，它會產生較慢的代碼，0.4s，令人驚訝的是 - 通常是LLVM並不比在循環優化時的本地代碼生成器差）。

對於32位的GHC，你不會得到相同的速度，因爲在那些情況下，64位整數的原始操作是通過C調用實現的 - 在32位上從未有足夠的快速64位操作需求位系統爲他們被實現爲首飾;爲GHC工作的人很少花時間去做其他更重要的事情。

TL; DR：Haskell代碼是否易於編寫和維護，僅用於計算上簡單的任務，並且在性能至關重要時會丟失此特性？

這取決於。您必須瞭解GHC根據什麼類型的輸入生成的代碼類型，並且您必須避免一些性能陷阱。通過一些練習，在這種任務中獲得2倍於gcc -O3的速度是相當容易的。