データ
まず、いくつかの入力を生成して、具体的なデータについて説明しましょう。
python -c 'for f in xrange(4000000): print f' > input.txt
input.txtこれにより、0 から 3999999 までの数字をそれぞれの行に含むファイルが生成されます。つまり、4,000,000 行のファイルが必要で、合計すると 30,888,890 バイト、約 29 MiB になります。
すべてをリストとして
では、すべてを次のようにメモリにロードしましょう[Text]。
import Data.Conduit
import Data.Text (Text)
import Control.Monad.Trans.Resource (runResourceT)
import qualified Data.Conduit.Binary as CB
import qualified Data.Conduit.Text as CT
import qualified Data.Conduit.List as CL
main :: IO ()
main = do
hs <- (runResourceT
$ CB.sourceFile "input.txt"
$$ CT.decode CT.utf8
=$ CT.lines
=$ CL.fold (\b a -> a `seq` b `seq` a:b) [])
print $ head hs
そしてそれを実行します：
[1 of 1] Compiling Main ( Test.hs, Test.o )
Linking Test ...
"3999999"
2,425,996,328 bytes allocated in the heap
972,945,088 bytes copied during GC
280,665,656 bytes maximum residency (13 sample(s))
5,120,528 bytes maximum slop
533 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 4378 colls, 0 par 0.296s 0.309s 0.0001s 0.0009s
Gen 1 13 colls, 0 par 0.452s 0.661s 0.0508s 0.2511s
INIT time 0.000s ( 0.000s elapsed)
MUT time 0.460s ( 0.465s elapsed)
GC time 0.748s ( 0.970s elapsed)
EXIT time 0.002s ( 0.034s elapsed)
Total time 1.212s ( 1.469s elapsed)
%GC time 61.7% (66.0% elapsed)
Alloc rate 5,271,326,694 bytes per MUT second
Productivity 38.3% of total user, 31.6% of total elapsed
real 0m1.481s
user 0m1.212s
sys 0m0.232s
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. そのために、プログラムをごくわずかに変更しました
import Data.Conduit
import Data.Text (Text)
import Control.Monad.Trans.Resource (runResourceT)
import qualified Data.Conduit.Binary as CB
import qualified Data.Conduit.Text as CT
import qualified Data.Conduit.List as CL
import qualified Data.HashSet as HS
main :: IO ()
main = do
hs <- (runResourceT
$ CB.sourceFile "input.txt"
$$ CT.decode CT.utf8
=$ CT.lines
=$ CL.fold (\b a -> a `seq` b `seq` HS.insert a b) HS.empty)
print $ HS.size hs
それをもう一度実行すると
$ ghc -fforce-recomp -O3 -rtsopts Test.hs && time ./Test +RTS -sstderr
[1 of 1] Compiling Main ( Test.hs, Test.o )
Linking Test ...
4000000
6,544,900,208 bytes allocated in the heap
6,314,477,464 bytes copied during GC
442,295,792 bytes maximum residency (26 sample(s))
8,868,304 bytes maximum slop
1094 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 12420 colls, 0 par 5.756s 5.869s 0.0005s 0.0034s
Gen 1 26 colls, 0 par 3.068s 3.633s 0.1397s 0.6409s
INIT time 0.000s ( 0.000s elapsed)
MUT time 3.567s ( 3.592s elapsed)
GC time 8.823s ( 9.502s elapsed)
EXIT time 0.008s ( 0.097s elapsed)
Total time 12.399s ( 13.192s elapsed)
%GC time 71.2% (72.0% elapsed)
Alloc rate 1,835,018,578 bytes per MUT second
Productivity 28.8% of total user, 27.1% of total elapsed
real 0m13.208s
user 0m12.399s
sys 0m0.646s
かなり悪いです: 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秒:
import Data.List (foldl')
import qualified Data.HashSet as HS
main = do
let hs = foldl' (\b a -> a `seq` b `seq` HS.insert a b) (HS.empty :: HS.HashSet Int) [1..4000000]
print $ HS.size hs
見栄えが良くありません：
[...]
798 MB total memory in use (0 MB lost due to fragmentation)
[...]
real 0m9.956s
これは、4M Ints でほぼ 800 MiB です!