23

私はこのhaskellファイルを持っており、ghc -O2（ghc 7.4.1）でコンパイルされており、私のマシンでは1.65秒かかります

import Data.Bits
main = do
    print $ length $ filter (\i -> i .&. (shift 1 (i `mod` 4)) /= 0) [0..123456789]

（gcc 4.6.3）でコンパイルされたCの同じアルゴリズムはgcc -O2、0.18秒で実行されます。

#include <stdio.h>
void main() {
    int count = 0;
    const int max = 123456789;
    int i;
    for (i = 0; i < max; ++i)
        if ((i & (1 << i % 4)) != 0)
            ++count;
    printf("count: %d\n", count);
}

アップデートData.Bitsが遅く なるのではないかと思ったのですが、意外とシフトを外してストレートmodにすると、実際には5.6秒で遅くなります！？！

import Data.Bits
main = do
    print $ length $ filter (\i -> (i `mod` 4) /= 0) [0..123456789]

一方、同等のCは0.16秒でわずかに速く実行されます。

#include <stdio.h>
void main() {
    int count = 0;
    const int max = 123456789;
    int i;
    for (i = 0; i < max; ++i)
        if ((i % 4) != 0)
            ++count;
    printf("count: %d\n", count);
}
4

4 に答える 4

24

2つのコードは非常に異なることをします。

import Data.Bits
main = do
    print $ length $ filter (\i -> i .&. (shift 1 (i `mod` 4)) /= 0) [0..123456789]

123456790のリストをInteger（怠惰に）作成し、それぞれの剰余を4を法として取ります（最初に、Integerが生のマシンの整数をラップするのに十分小さいかどうかのチェックを含み、次に除算の後に符号チェックを行います。これは、mod非負の結果のみを返すためです- ghc-7.6.1にはそのためのプリモップがあるので、mod以前ほど使用するブレーキではありません）、1を適切なビット数だけ左にシフトしIntegerます。これには、「ビッグ」への変換が含まれますInteger。 GMPへの呼び出しは、ビット単位で、iさらにGMPへの呼び出しを行い、結果が0であるかどうかをチェックします。これにより、GMPへの別の呼び出しまたは小整数への変換が発生しますが、GHCがここで何を行うかはわかりません。次に、結果がゼロ以外の場合、新しいリストセルが作成されます。Integer入れられ、によって消費されlengthます。これは多くの作業が行われ、不特定の数値タイプがデフォルトでに設定されているため、そのほとんどが不必要に複雑になっていIntegerます。

Cコード

#include <stdio.h>
int main(void) {
    int count = 0;
    const int max = 123456789;
    int i;
    for (i = 0; i < max; ++i)
        if ((i & (1 << i % 4)) != 0)
            ++count;
    printf("count: %d\n", count);
    return 0;
}

（私はのリターンタイプを修正する自由を取りましたmain）、はるかに少ないです。それはを取り、intそれを別のものと比較し、小さい場合はビット単位で、最初のint3 （1）intを取り、1を適切なビット数で左にシフトし、ビット単位でそれと最初のを取り、intゼロ以外の場合別intのをインクリメントし、次に最初をインクリメントします。これらはすべてマシン操作であり、生のマシンタイプで動作します。

そのコードをHaskellに翻訳すると、

module Main (main) where

import Data.Bits

maxNum :: Int
maxNum = 123456789

loop :: Int -> Int -> Int
loop acc i
    | i < maxNum = loop (if i .&. (1 `shiftL` (i .&. 3)) /= 0 then acc + 1 else acc) (i+1)
    | otherwise  = acc

main :: IO ()
main = print $ loop 0 0

より近い結果が得られます。

C, gcc -O3:
count: 30864196

real    0m0.180s
user    0m0.178s
sys     0m0.001s

Haskell, ghc -O2:
30864196

real    0m0.247s
user    0m0.243s
sys     0m0.003s

Haskell, ghc -O2 -fllvm:
30864196

real    0m0.144s
user    0m0.140s
sys     0m0.003s

GHCのネイティブコードジェネレーターは特に優れたループオプティマイザーではないため、llvmバックエンドを使用すると、ここで大きな違いが生じますが、ネイティブコードジェネレーターでさえそれほど悪くはありません。

さて、私はモジュラス計算をビット単位の2の累乗モジュラスに置き換える最適化を行いましたが、GHCのネイティブコードジェネレーターは（まだ）それを行いません。したがって、 ``` rem 4`` instead of。＆。3`、ネイティブコードジェネレーターは（ここでは）実行に1.42秒かかるコードを生成しますが、llvmバックエンドはその最適化を行い、手作りの最適化と同じコードを生成します。

それでは、 gsprの質問に移りましょう。

LLVMは元のコードに大きな影響を与えませんでしたが、実際には変更されたコードに影響を及ぼしました（理由を知りたいです...）。

さて、使用された元のコードInteger砂リストでは、llvmはこれらをどう処理するかをよく知らないため、そのコードをループに変換することはできません。変更されたコードはIntsを使用し、vectorパッケージはコードをループに書き換えるので、llvmはそれを適切に最適化する方法を知っています。

（1）通常のバイナリコンピュータを想定しています。divこの最適化は、命令がシフトよりも高速である非常にまれなプラットフォームを除いて、最適化フラグがなくても通常のCコンパイラによって実行されます。

于 2012-10-04T18:17:04.547 に答える
15

厳密なアキュムレータを使用して手書きのループに勝るものはほとんどありません。

{-# LANGUAGE BangPatterns #-}

import Data.Bits

f :: Int -> Int
f n = g 0 0
  where g !i !s | i <= n    = g (i+1) (if i .&. (unsafeShiftL 1 (i `rem` 4)) /= 0 then s+1 else s)
                | otherwise = s

main = print $ f 123456789

これまでに述べたトリックに加えて、これは引数をチェックしない、にも置き換えshiftられます。unsafeShiftL

とでコンパイルする-O2と-fllvm、これは私のマシンの元のマシンよりも約13倍高速です。

注：iのビットが設定されているかどうかのテストxは、としてより明確に記述できますx `testBit` i。これにより、上記と同じアセンブリが生成されます。

于 2012-10-04T17:50:11.680 に答える
12

リストの代わりにベクトル、フィルターと長さの代わりに折りたたむ

ボックス化されていないベクトルをリストに置き換え、フォールドをフィルターと長さに置き換える（つまり、カウンターをインクリメントする）と、時間が大幅に改善されます。これが私が使用したものです：

import qualified Data.Vector.Unboxed as UV
import Data.Bits

foo :: Int
foo = UV.foldl (\s i -> if i .&. (shift 1 (i `rem` 4)) /= 0 then s+1 else s) 0 (UV.enumFromN 0 123456789)

main = print foo

元のコード（ただし、コメントで提案されているように、および回避するために署名にを追加するrem代わりに、2つの変更があります）は次のようになりました。modIntInteger

$ time ./orig 
30864196

real    0m2.159s
user    0m2.144s
sys     0m0.008s

上記の変更されたコードは次のようになりました。

$ time ./new 
30864196

real    0m1.450s
user    0m1.440s
sys     0m0.004s

LLVM

LLVMは元のコードに大きな影響を与えませんでしたが、実際には変更されたコードに影響を及ぼしました（理由を知りたいです...）。

オリジナル（LLVM）：

$ time ./orig-llvm 
30864196

real    0m2.047s
user    0m2.036s
sys     0m0.008s

変更済み（LLVM）：

$ time ./new-llvm 
30864196

real    0m0.233s
user    0m0.228s
sys     0m0.004s

比較のために、OPの元のCコードは私のシステムの0m0.152sユーザーにあります。

これはすべてGHC7.4.1、GCC 4.6.3、およびベクトル0.9.1です。LLVMは2.9または3.0のいずれかです。私は両方を持っていますが、どちらのGHCが実際に使用しているかを理解できないようです。

于 2012-10-04T16:29:58.660 に答える
0

これを試して：

import Data.Bits
main = do
    print $ length $ filter (\i -> i .&. (shift 1 (i `rem` 4)) /= 0) [0..123456789::Int]

がない::Int場合、タイプはデフォルトで。になり::Integerます。 正の値の場合と同じようremに動作し、Cの場合と同じです。一方、負の値の場合は数学的に正しいですが、速度は遅くなります。mod%mod

  • intCでは32ビットです
  • IntlongHaskellでは、Cのように32ビットまたは64ビット幅です。
  • Integerは任意のビット整数であり、最小/最大値はなく、メモリサイズはその値に依存します（文字列と同様）。
于 2012-10-16T16:54:49.917 に答える