7

質問

次のようなシーケンスを記述するプログラムが必要です。

1
...
10000000

ファイルに。まともなパフォーマンスが得られる最も簡単なコードは何ですか? 私の直感は、バッファリング不足の問題があるということです。私の C コードは 100 MB/s で実行されますが、参考までに、Linux コマンド ライン ユーティリティddは9 GB/s 3 GB/s で実行されます (不正確で申し訳ありません。コメントを参照してください。全体像にもっと興味があります。 -大きさですが）。

これは今では解決された問題だと思うかもしれません...つまり、最新のコンパイラーは、適度にうまく機能するようなプログラムをすぐに書くことができます...

Cコード

#include <stdio.h>

int main(int argc, char **argv) {
    int len = 10000000;
    for (int a = 1; a <= len; a++) {
        printf ("%d\n", a);
    }
    return 0;
}

でコンパイルしていclang -O3ます。8 回コールするパフォーマンス スケルトンputchar('\n')は、同等のパフォーマンスを取得します。

Haskell コード

単純な Haskell 実装は 13 MiB/秒で実行され、ghc -O2 -optc-O3 -optc-ffast-math -fllvm -fforce-recomp -funbox-strict-fields. (ライブラリを-fllvmで再コンパイルしていません。おそらく再コンパイルする必要があります。) コード:

import Control.Monad
main = forM [1..10000000 :: Int] $ \j -> putStrLn (show j)

私の Haskell での最高のスタブは、さらに遅く、17 MiB/秒です。Vector問題は、 を に変換する良い方法が見つからないことですByteString(おそらく iteratees を使用した解決策がありますか?)。

import qualified Data.Vector.Unboxed as V
import Data.Vector.Unboxed (Vector, Unbox, (!))

writeVector :: (Unbox a, Show a) => Vector a -> IO ()
writeVector v = V.mapM_ (System.IO.putStrLn . show) v

main = writeVector (V.generate 10000000 id)

このコードで示されているように、 の書き込みByteStringは高速のようで、同等の文字数を書き込み、

import Data.ByteString.Char8 as B
main = B.putStrLn (B.replicate 76000000 '\n')

これは 1.3 GB/s で、 ほど高速ではありませんddが、明らかにはるかに優れています。

4

3 に答える 3

7

最初にいくつかの完全に非科学的なベンチマーク:

すべてのプログラムは、デフォルトの最適化レベル (gcc では -O3、GHC では -O2) でコンパイルされ、

time ./prog > outfile

ベースラインとして、C プログラムは約 76MB (78888897 バイト) のファイルを生成するのに 1.07 秒かかり、およそ 70MB/秒のスループットでした。

  1. 「素朴な」Haskell プログラム ( forM [1 .. 10000000] $ \j -> putStrLn (show j)) は 8.64 秒、約 8.8MB/秒かかりました。
  2. forM_代わりにforM5.64 秒、約 13.5MB/秒かかりました。
  3. ByteStringdflemstr の回答のバージョンは 9.13 秒、約 8.3MB/秒かかりました。
  4. dflemstr の回答のTextバージョンは 5.64 秒、約 13.5MB/秒かかりました。
  5. 質問のVectorバージョンは 5.54 秒、約 13.7MB/秒かかりました。
  6. main = mapM_ (C.putStrLn . C.pack . show) $ [1 :: Int .. 10000000]、ここCでData.ByteString.Char8、 は 4.25 秒、約 17.9MB/秒かかりました。
  7. putStr . unlines . map show $ [1 :: Int .. 10000000]3.06 秒、約 24.8MB/秒かかりました。

  8. 手動ループ、

    main = putStr $ go 1
  where
    go :: Int -> String
    go i
        | i > 10000000 = ""
        | otherwise = shows i . showChar '\n' $ go (i+1)

    2.32 秒、約 32.75MB/秒かかりました。

  9. main = putStrLn $ replicate 78888896 'a'1.15 秒、約 66MB/秒かかりました。
  10. main = C.putStrLn $ C.replicate 78888896 'a'ここCでData.ByteString.Char8、0.143 秒、約 530MB/秒かかりました。これは、lazyByteStringの場合とほぼ同じ数値です。

そこから何を学べるでしょうか。

まず、本当に結果を収集したい場合を除き、 forMorを使用しないでください。mapMパフォーマンスに関しては、それはひどいです。

その後、ByteString出力は非常に高速になりますが (10.)、ByteStringto 出力の構築が遅い場合 (3.)、単純なString出力よりもコードが遅くなります。

3.の何がそんなにひどいの？さて、関連するすべてのStrings は非常に短いです。だからあなたはのリストを取得します

Chunk "1234567" Empty

そのような 2 つの間に aChunk "\n" Emptyが配置され、結果のリストが連結されます。つまり、これらEmptyの s はすべて、 a... (Chunk "1234567" (Chunk "\n" (Chunk "1234568" (...))))が構築されるときに破棄されます。これは、多くの無駄な構築 - 解体 - 再構築が行われていることです。Textおよび固定された「ナイーブ」Stringバージョンに匹敵する速度は、packstrict に ing をByteString使用してfromChunks(およびData.List.intersperse改行に対して) 使用することで実現できます。コストのかかるシングルトンを削除することで、6.よりわずかに優れたパフォーマンスを得ることができます。の代わりにStringを使用して改行を s に接着する場合、連結はわずかに長いs の半分を処理する必要があり、これは報われます。\k -> shows k "\n"showByteString

テキストまたはベクターの内部構造については、観測されたパフォーマンスの理由について半知識に基づく推測以上のものを提供できるほど詳しくないので、省略します。固定された単純なバージョンと比較して、パフォーマンスの向上はせいぜいわずかであると言えば十分Stringです。

ここで、6. はByteStringoutput が output よりも高速であることを示してStringおり、この場合は ing の追加作業がpack相殺される以上のものです。ただし、常にそうであると信じることにだまされないでください。圧縮する が長い場合、出力Stringよりも圧縮に時間がかかることがあります。String

しかし、それが であろうとバージョンでputStrLnあろうと、の 1000 万回の呼び出しには多くの時間がかかります。一度だけ取得して、非 IO コードで出力を構築する方が高速です。すでにうまくいっていますが、まだ list の構築に苦しんでいます。残念ながら、コンパイラはそれを取り除くことができませんでした (しかし、それはすでにかなり良いことです)。それでは、自分でやってみましょう。8 になります。それほどひどいものではありませんが、それでも C プログラムの 2 倍以上の時間がかかります。StringByteStringstdout HandleStringunlinesmap show [1 .. 10^7][1 .. 10^7]

を経由せずに低レベルでByteStrings を直接埋めることで、より高速な Haskell プログラムを作成できますが、C の速度に到達できるかどうかはわかりません。とにかく、その低レベルのコードはあまりきれいではないので、私が持っているものは割愛しますが、速度が重要な場合は手を汚さなければならないことがあります.Stringshow

于 2012-04-10T03:08:15.337 に答える
3

レイジーバイト文字列を使用すると、文字列が即座に書き込まれ、必要なときにのみより多くの数値が生成されるため、バッファリングが可能になります。このコードは基本的な考え方を示しています (いくつかの最適化が行われる可能性があります)。

import qualified Data.ByteString.Lazy.Char8 as ByteString

main =
  ByteString.putStrLn .
  ByteString.intercalate (ByteString.singleton '\n') .
  map (ByteString.pack . show) $
  ([1..10000000] :: [Int])

ここでも数値に s を使用Stringしているため、速度が大幅に低下します。textライブラリの代わりにライブラリに切り替えると、bytestringint の "ネイティブ" 表示関数にアクセスできるようになり、次のことが可能になります。

import Data.Monoid
import Data.List
import Data.Text.Lazy.IO as Text
import Data.Text.Lazy.Builder as Text
import Data.Text.Lazy.Builder.Int as Text

main :: IO ()
main =
  Text.putStrLn .
  Text.toLazyText .
  mconcat .
  intersperse (Text.singleton '\n') .
  map Text.decimal $
  ([1..10000000] :: [Int])

これらのプログラムの「速度」を (ツールを使用して) どのように測定しているかはわかりませんがpv、これらの手順の 1 つが、取得できる最も簡単なプログラムの中で最も速いものになると思います。

于 2012-04-09T22:01:15.183 に答える
3

パフォーマンスを最大化する場合は、全体像を把握することが役立ちます。[Int]つまり、メモリのチャンクをファイルに書き込む一連のシステム コールから にマップする関数を書きたいとします。

遅延バイト文字列は、メモリのチャンクのシーケンスを表すのに適しています。怠惰なバイト文字列を、メモリのチャンクを書き込む一連のシステム コールにマッピングすることL.hPutが行われています ( import qualified Data.ByteString.Lazy as L. したがって、対応する遅延バイト文字列を効率的に構築する手段が必要です。これは、怠惰なバイト文字列ビルダーが得意とするところです。新しい bytestring ビルダー ( API ドキュメントはこちら) を使用すると、次のコードがその役割を果たします。

import qualified Data.ByteString.Lazy          as L
import           Data.ByteString.Lazy.Builder       (toLazyByteString, charUtf8)
import           Data.ByteString.Lazy.Builder.ASCII (intDec)
import           Data.Foldable                      (foldMap)
import           Data.Monoid                        (mappend)
import           System.IO                          (openFile, IOMode(..))

main :: IO ()
main = do
    h <- openFile "/dev/null" WriteMode
    L.hPut h $ toLazyByteString $
        foldMap ((charUtf8 '\n' `mappend`) . intDec) [1..10000000]

/dev/nullディスクドライバーによる干渉を避けるために出力することに注意してください。データを OS に移動する手間は変わりません。私のマシンでは、上記のコードは 0.45 秒で実行されます。これは、元のコードの 5.4 秒よりも 12 倍高速です。これは、168 MB/秒のスループットを意味します。制限付きエンコーディングを使用して、さらに 30% の速度 (220 MB/秒) を絞り出すことができます]。

import qualified Data.ByteString.Lazy.Builder.BasicEncoding as E

L.hPut h $ toLazyByteString $
    E.encodeListWithB 
        ((\x -> (x, '\n')) E.>$< E.intDec `E.pairB` E.charUtf8) 
        [1..10000000]

a は、コンパイル時に制限を計算できるように、BoundedEncoding aタイプの Haskell 値を制限付き長さのバイト シーケンスに変換することを指定するため、これらの構文は少し風変わりに見えます。これにより、実際のバッファの充填を実装するためにいくつかの追加の最適化を実行するなどの関数が可能になります。詳細については、上記の API ドキュメントへのリンクのドキュメントを参照してください (新規ユーザー向けのばかげたハイパーリンク制限)。aE.encodeListWithBData.ByteString.Lazy.Builder.BasicEncoding

これが私のすべてのベンチマークのソースです。

結論として、実装のコスト モデルを理解し、適切なデータ構造を使用すれば、宣言型ソリューションから非常に優れたパフォーマンスを得ることができます。パックされた値のシーケンス (たとえば、バイト文字列として表されるバイトのシーケンス) を構築するときはいつでも、使用する正しいデータ構造はバイト文字列Builderです。

于 2012-04-25T07:52:57.470 に答える