6

次のようなモジュールがあるとします。

module Explosion where

import Pipes.Parse (foldAll, Parser, Producer)
import Pipes.ByteString (ByteString, fromLazy)
import Pipes.Aeson (DecodingError)
import Pipes.Aeson.Unchecked (decoded)
import Data.List (intercalate)
import Data.ByteString.Lazy.Char8 (pack)
import Lens.Family (view)
import Lens.Family.State.Strict (zoom)

produceString :: Producer ByteString IO ()
produceString = fromLazy $ pack $ intercalate " " $ map show [1..1000000]

produceInts :: 
    Producer Int IO (Either (DecodingError, Producer ByteString IO ()) ())
produceInts = view decoded produceString

produceInts' :: Producer Int IO ()
produceInts' = produceInts >> return ()

parseBiggest :: Parser ByteString IO Int
parseBiggest = zoom decoded (foldAll max 0 id)

「produceString」関数はバイト文字列プロデューサーであり、解析を折りたたんで何らかの結果を生成することに関心があります。

次の 2 つのプログラムは、バイト文字列を一連の JSON int として解析することにより、バイト文字列の最大値を見つけるという問題に取り組むさまざまな方法を示しています。

プログラム 1:

module Main where

import Explosion (produceInts')
import Pipes.Prelude (fold)

main :: IO ()
main = do
    biggest <- fold max 0 id produceInts'
    print $ show biggest

プログラム 2:

module Main where

import Explosion (parseBiggest, produceString)
import Pipes.Parse (evalStateT)

main :: IO ()
main = do
    biggest <- evalStateT parseBiggest produceString
    print $ show biggest

残念なことに、両方のプログラムをプロファイリングすると、合計で約 200MB のメモリを消費します。この問題は、ストリーミング パーサーを使用することで解決できると期待していました。最初のプログラムは、ほとんどの時間とメモリ (> 70%) をLens.Family(^.)から使用します。使用グラフは以下。どちらのプログラムも、時間の約 70% をガベージ コレクションに費やしています。fmapzoom

私は何か間違ったことをしていますか？Prelude 関数maxは十分に厳密ではありませんか? ライブラリ関数が悪いのか、それともライブラリの使い方が間違っているのかわかりません! （多分後者です。）

完全を期すために、私が話していることを直接確認したい場合は、複製して実行できるgit リポジトリを次に示します。2 つのプログラムのメモリ使用量は次のとおりです。cabal install

プログラム 1 のメモリ使用量 プログラム 2 のメモリ使用量

4

1 に答える 1

5

厳密なバイト文字列を単一でラップしても、yield遅延は発生しません。ストリーミング動作を取得するには、より小さなチャンクを生成する必要があります。

編集：エラーが見つかりました。 次のように定義された関数pipes-aesonを内部的に使用します。consecutively

consecutively parser = step where
    step p0 = do
      (mr, p1) <- lift $
         S.runStateT atEndOfBytes (p0 >-> PB.dropWhile B.isSpaceWord8)
      case mr of
         Just r  -> return (Right r)
         Nothing -> do
            (ea, p2) <- lift (S.runStateT parser p1)
            case ea of
               Left  e -> return (Left (e, p2))
               Right a -> yield a >> step p2

問題のある行はPB.dropWhile. これにより、解析された要素の数に比例する 2 次爆発が追加されます。

何が起こるかというと、この計算に通されたパイプは、cat各解析後に下流に新しいパイプを蓄積します。したがって、N 回の解析の後、N 個catのパイプが取得され、解析された各要素に O(N) のオーバーヘッドが追加されます。

これを修正する ために Github の問題を作成しました。pipes-aesonは Renzo によって保守されており、彼は以前にこの問題を修正しています。

編集: 2 つ目の問題を修正するためにプル リクエストintercalateを送信しました (遅延バイト文字列には を使用する必要がありました)。これで、プログラムは両方のバージョンで 5 KB の定数スペースで実行されます。

ここに画像の説明を入力

ここに画像の説明を入力

于 2014-05-19T21:04:37.060 に答える