39

テキストファイルを処理してMap（数百万の要素を含む）を構築するHaskellプログラムがあります。全体で 2 ～ 3 分実行できます。-H オプションと -A オプションを微調整すると、実行時間に大きな違いが生じることがわかりました。

RTS のこの機能に関するドキュメントがありますが、GC 理論のアルゴリズムと用語を知らないので、私には読みにくいです。Haskell/GHC に固有の、より技術的な説明を探しています。これらのオプションに適切な値を選択することについての参照はありますか?

編集：それがコードです。指定された単語のリストに対してトライを構築します。

buildTrie :: [B.ByteString] -> MyDFA 
buildTrie l = fst3 $ foldl' step (emptyDFA, B.empty, 1) $ sort $ map B.reverse l where
    step :: (MyDFA , B.ByteString, Int) -> B.ByteString -> (MyDFA , B.ByteString, Int)
    step (dfa, lastWord, newIndex) newWord = (insertNewStates, newWord, newIndex + B.length newSuffix) where            
        (pref, lastSuffix, newSuffix) = splitPrefix lastWord newWord
        branchPoint = transStar dfa pref

        --new state labels for the newSuffix path
        newStates = [newIndex .. newIndex + B.length newSuffix - 1]
        --insert newStates
        insertNewStates = (foldl' (flip insertTransition) dfa $ zip3 (branchPoint:init newStates) (B.unpack newSuffix) newStates)
4

2 に答える 2

72

一般的に言えば、ガベージ コレクションは空間と時間のトレードオフです。GC により多くのスペースを与えると、時間が短縮されます。他にも (多くの) 要因、特にキャッシュがありますが、空間と時間のトレードオフが最も重要です。

トレードオフは次のように機能します。プログラムは、(GC の自動チューニング パラメーターによって、または RTS オプションによって明示的に決定される) 制限に達するまでメモリを割り当てます。制限に達すると、GC はプログラムが現在使用しているすべてのデータをトレースし、不要になったデータによって使用されているすべてのメモリを再利用します。このプロセスを遅らせれば遅らせるほど、その間により多くのデータが到達不能 (「デッド」) になるため、GC はそのデータのトレースを回避します。GC を遅らせる唯一の方法は、割り当てるメモリを増やすことです。したがって、より多くのメモリはより少ない GC に等しく、より低い GC オーバーヘッドに等しくなります。大まかに言えば、GHC の -H オプションを使用すると、GC が使用するメモリ量の下限を設定できるため、GC のオーバーヘッドを下げることができます。

GHC は世代別 GCを使用します。これは、ヒープが 2 つ以上の世代に分割される基本スキームの最適化です。オブジェクトは「若い」世代に割り当てられ、十分に長く存続するオブジェクトは「古い」世代に昇格します (2 世代の設定)。若い世代は古い世代よりもはるかに頻繁に収集されます。「ほとんどのオブジェクトは若くして死ぬ」という考えがあるため、若い世代のコレクションは安価ですが (あまりデータを追跡しません)、多くのメモリを再利用します。大まかに言えば、 -A オプションは、若い世代のサイズ、つまり、若い世代が収集される前に割り当てられるメモリの量を設定します。

-A のデフォルトは 512k です。若い世代を L2 キャッシュより小さく保つことをお勧めします。L2 キャッシュ サイズを超えると、一般にパフォーマンスが低下します。しかし、GC のスペースと時間のトレードオフは反対の方向に働きます。非常に大きな若い世代のサイズを使用すると、GC が実行する必要のある作業量が減り、キャッシュのメリットを上回る可能性があります。これは常に発生するとは限りません。アプリケーションのダイナミクスに依存するため、GC が自動的に調整するのが難しくなります。-H オプションも若い世代のサイズを大きくするため、キャッシュの使用に悪影響を与える可能性があります。

肝心なのは、オプションをいじってみて、何が機能するかを確認することです。メモリに余裕がある場合は、-A または -H を使用してパフォーマンスを向上できる可能性がありますが、必ずしもそうとは限りません。

于 2010-07-03T19:56:00.140 に答える
8

何が起こっているのかを簡単に確認できる、より小さなデータ セットで問題を再現できる可能性があります。特に、プロファイリングにある程度慣れることをお勧めします。

次に、表示されるメモリ プロファイルが期待どおりかどうかを確認します (有用なグラフを取得するために、すべてのプロファイル オプションについて知る必要はありません)。アキュムレータとしての厳密なタプルと非厳密なタプルの組み合わせは、foldl'私が最初に見たいものです。タプルのコンポーネントが強制されていない場合、その再帰は未評価の式を構築しています。

ところで、非常に小さなデータセットについてコードを手作業で評価しようとすることで、そのようなことについての優れた直感を構築できます。アプリケーションに適した方法で式が評価されるか、評価されないままになるかを確認するには、数回の反復で十分です。

于 2010-07-03T21:47:58.193 に答える