問題タブ [unordered-containers]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
performance - Haskell: Data.HashSet (unordered-container から) 大きなセットのパフォーマンス
データ
まず、いくつかの入力を生成して、具体的なデータについて説明しましょう。
input.txtこれにより、0 から 3999999 までの数字をそれぞれの行に含むファイルが生成されます。つまり、4,000,000 行のファイルが必要で、合計すると 30,888,890 バイト、約 29 MiB になります。
すべてをリストとして
では、すべてを次のようにメモリにロードしましょう[Text]。
そしてそれを実行します：
1.4 秒で実行され、533 MB のメモリが必要です。Haskell Wiki の Memory Footprint の時点で、4MTextインスタンスは 6 ワード + 2N バイトのメモリを必要とします。私は64ビットなので、1ワードは8バイトです。つまり、(6 * 8 バイト * 4000000) + (2*26888890) バイト = 234 MiB になります。input.txt(26888890 は、改行文字ではないすべてのバイトです)。それらすべてを保持するリストには、(1 + 3N) ワード + N * sizeof(v) の追加メモリが必要です。sizeof(v) は へのポインターになるため、8 にする必要がありますText。リストは (1 + 3 * 4000000) * 8 バイト + 4000000 * 8 バイト = 122MiB を使用する必要があります。したがって、合計 (リスト + 文字列) で 356 MiB のメモリが使用されると予想されます。メモリの 177 MiB (50%) の違いがどこに行ったのかはわかりませんが、今は無視しておきましょう。
大きなハッシュセット
最後に、私が実際に興味を持っているユースケースに行きます: すべての単語を大きなData.HashSet. そのために、プログラムをごくわずかに変更しました
それをもう一度実行すると
かなり悪いです: 13 秒と 1094MiB のメモリが使用されました。メモリ フットプリント ページには、ハッシュ セットの 4.5N ワード + N * sizeof(v) がリストされており、(4.5 * 4000000 * 8 バイト) + (4000000 * 8 バイト) = 167 MiB になります。スティング用のストレージ (234 MiB) を追加すると、 2 倍以上の 401 MiB が予想されますが、その上かなり遅く感じます :(.
思考実験: メモリを手動で管理する
思考実験として: メモリ レイアウトを手動で制御し、 Open アドレッシングで HashSet を実装できる言語を使用すると、次のサイズになると予想されます。公平を期すために、文字列は引き続き UTF-16 であると想定します (つまり、Data.Textします）。合計で 26888890 文字 (改行なし) であるとすると、UTF-16 の文字列はおよそ 53777780 バイト (2 * 26888890) = 51 MiB になります。すべての文字列の長さを保存する必要があります。これは 8 バイト * 4000000 = 30 MiB になります。また、ハッシュ セット (4000000 * 8 バイト) 用のスペースが必要です。これも 30 MiB です。通常、ハッシュ セットが指数関数的に増加することを考えると、最悪の場合は 32 MiB または 64 MiB になると予想されます。最悪のケースを見てみましょう: テーブルの 64 MiB + 文字列の長さの 30 MiB + 実際の文字列データの 51 MiB、合計 145 MiB です。
文字列を格納するための特別な実装ではないことを考えるとData.HashSet、計算された 401 MiB はそれほど悪くはありませんが、実際に使用された 1094 MiB は少し無駄に思えます。
最後に質問:)
それで、ついにそこにたどり着きました：
- 計算のどこが間違っていますか?
- 私の実装に何か問題がありますか、それとも 1094 MiB が本当に最高でしょうか?
バージョンなど
- アスキー文字しか必要ないので、おそらく
ByteString代わりに s を使用する必要がありますText - 私はGHC 7.10.1を使用しています
unordered-containers-0.2.5.1
比較のために: 4,000,000Int秒:
見栄えが良くありません：
これは、4M Ints でほぼ 800 MiB です!
haskell - M.Map 突然予想される型エラー
約1か月ほど前まで、すべてがうまく機能していました...
突然私は得ています
コードから：
それが何を伝えているのか、正確に解読するのを手伝ってくれませんか？私の側にある種の構文エラーがあるようですが、何が変更されたのか、なぜ以前のようにコンパイルされないのか理解できませんか?
参照: https://github.com/berkson/berkson.github.io/blob/source/source/blog.hs#L330
haskell - 一連の挿入時に HashMap が通常の形式にならないのはなぜですか?
私は ghc-heap-view パッケージとそれが提供するユーティリティを使用して、Haskell プログラムのメモリ内モデルの厳密性を確保しようとしてきましたHashMap。 . ヒープ ツリーを印刷してみましたが、実際にいくつかのサンクが表示されます。次に、要素を挿入する別の方法 ( unionandを使用singleton) を試しましたが、今回は厳密になります。
誰かがなぜそうなのかを説明insertし、他の方法と同じように動作させるために私にできることがあるかどうかアドバイスしてもらえますか?
ここに私のテストコードがあります:
出力は次のとおりです。