13

私の最初の本格的なプログラミング体験は、Haskell でした。その場しのぎのニーズのために、習得が容易で、コーディングが迅速で、保守が簡単なツールが必要でしたが、それはうまく機能したと言えます。

しかし、ある時点で、私のタスクの規模がはるかに大きくなり、C の方が適しているのではないかと考え、そのようになりました。たぶん、私はプログラミングのスキルが十分ではなかったのかもしれませんが、適切な Haskell は C と同じようなパフォーマンスができると聞いていたにもかかわらず、Haskell を C ほど高速にすることはできませんでした。

最近、Haskell をもう一度試してみようと思ったのですが、一般的な単純な (計算の観点から) タスクには依然として優れていますが、Collat​​z 予想などの問題で C の速度に匹敵することはできないようです。読みました：

Project Euler との速度比較: C vs Python vs Erlang vs Haskell

GHC 最適化: コラッツ予想

haskell を使用した collat​​z-list の実装

しかし、私が見たところ、次のような単純な最適化方法があります。

  • Integer の代わりに Int64 のような「より厳密な」型を選択する
  • 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ましたが、コンパイラはそれをシフトとビットごとの and に置き換えます。残念ながら、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 を使用すると、同等の速度が得られます (1000000 の制限で、私のボックスでは 0.35 秒対 C の 0.32 秒)。LLVM バックエンドを使用してコンパイルする場合、% 2and/ 2をビット単位の操作に置き換える必要さえありません。LLVM がそれを行います (ただし、元の Haskell ソースに対して 0.4 秒という遅いコードが生成されます。驚くべきことに、通常、LLVM はそうではありません)。ループ最適化ではネイティブ コード ジェネレーターよりも悪い)。

32 ビット GHC では、64 ビット整数に対するプリミティブ操作が C 呼び出しによって実装されるため、匹敵する速度は得られません。それらは primops として実装されます。GHC に取り組んでいる少数の人々は、他のもっと重要なことに時間を費やしていました。

TL;DR: Haskell のコードは、計算が単純なタスクの場合にのみ、すばやく作成でき、保守も簡単で、パフォーマンスが重要な場合にこの特性を失うのでしょうか?

場合によります。どのような種類の入力から GHC が生成するコードの種類についてある程度の知識が必要であり、いくつかのパフォーマンス トラップを回避する必要があります。少し練習すれば、そのようなタスクで gcc -O3 の速度の約 2 倍以内に収めることは非常に簡単です。

于 2012-12-02T12:28:19.677 に答える