marisa-build のメモリ消費はどのくらい？

以前から「調べなきゃー」と思いつつ忘れていた内容です．marisa-build を使って辞書を構築するときのメモリ消費（ピーク）を /usr/bin/time -v により計測してみました．

# /usr/bin/time -v の Maximum resident set size (kbytes) を確認したわけですが，get_rusage() で得られる値の 4 倍になるという不思議現象が確認されたため，1/4 にした値を示しています．

実験では，英語 Wikipedia のタイトル一覧を入力として，キー数を変更しつつ，入力サイズとメモリ消費を比較してみました．結果は以下のとおりです．

キー数 [K]	入力サイズ [KB]	メモリ消費 [KB]	比率
8,472	171,336	930,184	5.429
8,000	162,530	728,472	4.482
7,000	141,395	638,964	4.519
6,000	121,713	572,360	4.703
5,000	101,728	512,228	5.035
4,000	80,478	358,296	4.452
3,000	61,101	287,032	4.698
2,000	41,251	181,388	4.397
1,000	21,180	92,524	4.368

入力サイズに対して，メモリ消費は 5 倍前後となりました．キー数によって比率が上下している理由は，領域の拡張に倍々戦略を採用しているからです．入力キー集合の保存については倍々戦略を採用していないこともあり，それほど極端な差は出ていません．とはいえ，25% くらいの誤差はあるので，試験的に測定した結果が手元にあっても多少の余裕を持って運用した方がよさそうです．

今回のデータでは 5 倍前後という比率になったわけですが，基本的には，短いキーが多ければ比率が高くなり，長いキーが多ければ比率が低くなりやすいという特徴があります．ちなみに，英語 Wikipedia のタイトル一覧は平均長が 20 bytes 前後です．また，平均長が 50 bytes 強の URL 一覧を入力にしたときは，比率が 2.877 になりました．

# ただし，極端に短いキーばっかりだと，1 byte のラベルばっかりになって，逆に比率が低くなる可能性もあります．

後，辞書サイズは入力サイズの 1/4 程度になりました．