トライ（ダブル配列，簡潔データ構造）と STL コンテナ

研究

以前実装した構築速度重視の動的ダブル配列 (表中 dda) の構築速度を Darts, darts-clone (0.32g beta5, 0.32e5), DASTrie (1.0), doar (0.0.10)，簡潔データ構造を利用したトライ (tx 0.16) ，STL コンテナ (std::map, std::tr1::unordered_map) 辺りと比べてみた．キー集合としては，中規模で疎な集合（Wikipedia 英語版記事タイトル）と小規模で密な集合（郵便番号辞書）を用いた．

======================================================================
 Wikipedia-en 記事タイトル |  Build  | Search  | Search* | Size [bytes]
======================================================================
 sorted keys
  Darts 0.32             | 13.869s |  0.529s |  6.650s |  552,547,920
  darts-clone 0.32g      |  6.499s |  0.611s |  5.792s |  258,735,104
  darts-clone 0.32g  v:1 | 16.625s |  0.748s |  6.191s |   95,080,448
 *darts-clone 0.32e5     | 11.334s |  0.902s |  5.852s |  113,360,140
 *darts-clone 0.32e5 v:1 | 10.806s |  0.829s |  5.519s |   87,122,880
  darts-clone 0.32e5 huge|  3.866s |  0.531s |  5.927s |  147,491,712
 *DASTrie 1.0 -c         |      NA |      NA |      NA |           NA
  DASTrie 1.0            |  4.090s |  0.772s |  6.140s |  157,593,742
 *doar 0.0.10 static     |  8.341s |  0.648s |  5.538s |  123,000,249
  --------------------------------------------------------------------
 *doar 0.0.10 dynamic    | +4.423s |  0.648s |  5.548s | +123,000,249
  dda                    |  3.239s |  0.603s |  6.985s |  517,091,328
 ---------------------------------------------------------------------
  map           k:char*  |  2.924s |  2.174s | 17.421s |(>163,859,393)
  map           k:string | 10.513s |  5.763s | 27.332s |(>163,859,393)
  unordered_map k:char*  |  6.048s |  1.975s |  3.574s |(>163,859,393)
  unordered_map k:string |  7.003s |  2.175s |  4.524s |(>163,859,393)
  --------------------------------------------------------------------
  tx 0.16                | 14.046s | 25.926s | 69.734s |   87,520,717
 =====================================================================
 randomized keys
  doar 0.0.10 dynamic    |+26.186s |  1.901s |  5.543s | +123,000,249
  dda                    |  9.961s |  3.619s |  8.421s |  517,091,328
  --------------------------------------------------------------------
  map           k:char*  | 16.569s |  3.603s | 21.168s |(>163,859,393)
  map           k:string | 26.542s |  8.050s | 30.219s |(>163,859,393)
  unordered_map k:char*  |  6.151s |  3.545s |  3.592s |(>163,859,393)
  unordered_map k:string |  7.100s |  4.506s |  4.583s |(>163,859,393)
  --------------------------------------------------------------------
  tx 0.16                | 35.183s | 27,029s | 69.673s |   87,520,717
======================================================================

======================================================================
 郵便番号辞書              |  Build  | Search  | Search* | Size [bytes]
======================================================================
 sorted keys
  Darts 0.32             |  0.036s |  0.003s |  0.011s |    2,156,576
  darts-clone 0.32g      |  0.037s |  0.003s |  0.010s |    1,069,056
  darts-clone 0.32g  v:1 |  0.023s |  0.003s |  0.007s |      106,496
 *darts-clone 0.32e5     |  0.164s |  0.004s |  0.012s |    1,154,676
 *darts-clone 0.32e5 v:1 |  0.157s |  0.004s |  0.011s |      650,116
  darts-clone 0.32e5 huge|  0.146s |  0.004s |  0.012s |    1,363,656
 *DASTrie 1.0 -c         |  2.396s |  0.006s |  0.015s |    1,248,609
  DASTrie 1.0            |  2.586s |  0.007s |  0.017s |    1,411,783
 *doar 0.0.10 static     |  0.061s |  0.004s |  0.012s |    1,204,561
  --------------------------------------------------------------------
 *doar 0.0.10 dynamic    | +0.097s |  0.004s |  0.012s |   +1,204,561
  dda                    |  0.024s |  0.004s |  0.012s |    2,129,920
  --------------------------------------------------------------------
  map           k:char*  |  0.043s |  0.030s |  0.074s |  (>1,425,852)
  map           k:string |  0.138s |  0.066s |  0.152s |  (>1,425,852)
  unordered_map k:char*  |  0.021s |  0.010s |  0.025s |  (>1,425,852)
  unordered_map k:string |  0.035s |  0.012s |  0.038s |  (>1,425,852)
  --------------------------------------------------------------------
  tx 0.16                |  0.079s |  0.099s |  0.134s |      222,888
 =====================================================================
 randomized keys
 *doar 0.0.10 dynamic    | +0.103s |  0.009s |  0.012s |   +1,204,561
  dda                    |  0.034s |  0.010s |  0.012s |    2,129,920
  --------------------------------------------------------------------
  map           k:char*  |  0.056s |  0.036s |  0.087s |  (>1,425,852)
  map           k:string |  0.131s |  0.088s |  0.162s |  (>1,425,852)
  unordered_map k:char*  |  0.026s |  0.022s |  0.025s |  (>1,425,852)
  unordered_map k:string |  0.043s |  0.035s |  0.038s |  (>1,425,852)
  --------------------------------------------------------------------
  tx 0.16                |  0.137s |  0.102s |  0.137s |      222,888
======================================================================
(compiled with gcc 4.5.0, -O2 -march=core2 -m64)
(3/18  00:05; 色々おかしかったので再実験)
(3/28  13:00; darts-clone 0.32g beta5 に更新)
(4/6   14:00; STL コンテナの最低必要メモリ量をサイズとして表記)
(7/26  02:00; dda を公開したので再計測．ライブラリごとにキー集合の型が異なる場合
              に，全ライブラリ用のキー集合を用意してからトライ・コンテナを構築して
              いたところを，各ライブラリのキー集合のみ用意するように変更した
             （全体的にキャッシュ効率が改善）．tx のランダム順追加実験を追加．
              検索キーのシャッフリングにメルセンヌ・ツイスタを利用．

その他の性能評価情報へのポインタ．

キーには登録順で固有のIDをレコードとして格納．Search* はランダム順の検索時間．'*' がついたものはノード数が大きく制限される圧縮 (BASE 3 bytes + CHECK 1 byte で表現) を利用しているのでサイズ面で有利 (通常のダブル配列の 1/2，BASE 4 byte + CHECK 1 byte のダブル配列の 4/5 のサイズで済む; darts-clone 0.32g もダブル配列の一要素は 4 bytes だが，親のアドレスからの offset で BASE を表現することでノード数の制限を回避している)．std::map, std::tr1::unordered_map (FNV) はキーが char* と std::string の場合を実験 (ただし，char* の方は，構築時間に文字列のメモリ確保が時間が含まれていないため有利; キーの大小・等価判定には std::strcmp を利用)．また，tx のみ API の都合上，構築時間にファイルへの保存時間を含んでいる．

比較しているものが多過ぎて，何に注目すれば良いのか困るだろうから以下まとめ．

構築速度

  • ダブル配列では動的にキーを追加する dda がほぼ最速．STL コンテナでは hash は追加順序によらず安定，map は追加順序に強い影響を受ける．
  • TAIL を実装したダブル配列は，密なキー集合からのトライの構築は苦手（特に DASTrie で顕著）．
  • doar (dynamic) は富豪的に逐次追加で冗長なダブル配列を構築して，保存時にダブル配列を再構築することでサイズを圧縮しているので，doar (static) の構築時間＋メモリが追加で保存時に必要 (+ と表記した)．
  • std::string を使った場合に std::map の構築速度が大幅に劣化しているのは，要素のコピーのコストの差が大きいからで，std::tr1::unordered_map より std::map の方が速度の低下の度合いが大きいのは，ハッシュ表と赤黒木の拡張の仕方の違いから．
  • 注: 上記の実験は，キー集合が与えられた時の連想配列の構築時間のみを計測しているが，STL コンテナや動的ダブル配列ではキーの逐次追加が可能であり，キーや値を一時的にコンテナに保存したりソートする必要がないため（これらの処理は上記の構築時間には含まれていない），実際の構築時間や空間効率の点でソートされたキー集合を入力とするライブラリに対して本質的に有利．

検索速度

  • ダブル配列は基本的には文字単位で配列へのランダムアクセスが発生するものの，キャッシュが効く限り hash より有意に高速な検索が可能 (文字列の走査が一回で済み，等価性・衝突のチェックが必要無いため; hash の場合は通常，キー全体を見て hash 関数を計算し，さらにキーの等価判定を行う)．従って，キー集合が小さいときや検索順序に偏りがある場合，hash より高速な検索が期待できる．また，キーが未登録の場合はキー全体を走査することがないので（トライが辿れなくなった時点で終了）hash より有利．この点も考慮する必要がある．キーの検索頻度が分かっているときは，適切な符号化を行い，子ノードの配置を工夫することでキャッシュ効率を改善することができる．
  • TAIL，共通部分木併合，共通接尾辞併合 (TAIL の圧縮) などでダブル配列のサイズを圧縮すると，一般的にキャッシュ効率が上がるため，検索速度は改善する．また，TAIL を実装したダブル配列は，TAIL 部分でキャッシュが効くことが保証されるので，キーが疎で長い場合や，ランダム順検索時には特に有利．ただし，辞書順検索時には TAIL へのアクセス時にキャッシュミスが起きやすいため検索が遅くなることもある．
  • ランダム順追加時の doar (dynamic) の検索時間は参考（静的に再構築したダブル配列に対する検索時間）
  • tx, map は検索速度重視の時は論外．

サイズ

  • ダブル配列では，darts-clone の圧縮率が高い．キーが疎なら 0.32eç³» (共通接尾辞併合)，キーが密なら 0.32gç³» (共通部分木併合) を使う．
  • 値が不要なら tx より darts-clone 方が良い (レコードの値を1で固定した結果を載せた)．キーが疎なら 0.32e系，密なら 0.32g 系が有効．
  • 値が必要な場合は，tx ã‚„ taijuなどの簡潔データ構造ベースのトライが良い．ただ，未登録キーを検索しない場合は bep で良いかも．
  • [追記; 2010/04/06] ダブル配列とコンテナでどちらがメモリを節約できるかはキーの冗長性に依存する．大雑把に言うと，STL コンテナでは，キー中の一文字に 1 byte 使うことになるが，ダブル配列だと，（一ノード辺り）4, 5, or 8 bytes 必要（TAIL を実装していれば，キーの共有数が 1 のノードをコンテナと同じ 1 byte で格納できる）．従って，圧縮なし，TAIL 無しでキー間でノードの共有がないキー集合だと，4-8倍のメモリを消費する (TAIL 有りなら，最初の文字の振り分けだけになるので unordered_map とほぼ同じ; ノード辺りのキーの重複数 x が 1 < x < 4, 5, or 8 のノードばかりだと，共通部分木圧縮しない限り，ハッシュよりメモリ効率は悪くなる)．Wikipedia 英語版タイトルだと，キー数: 6890514，キーサイズ: 136297337 bytes なので，データの格納に必要なサイズはレコードを 4 bytes とした場合で最低 136297337 + 4 * 6890514 = 163859393 bytes, 郵便番号辞書だと，キー数: 118821, キーサイズ: 950568 bytes なので，最低 950568 + 4 * 118821 = 1425852 bytes 以上のメモリが必要となる．表に載せてみると，TAIL と CHECK の 1 byte 表現を併用した静的ダブル配列であれば，STL コンテナより少ないメモリ消費で済みそうな感じ．キーが増えれば増えるほど，トライの根に近いところではノードが多数のキーで共有されるので，TAIL を実装していればメモリ効率は良いと考えてよさそう．

動的ダブル配列 (dda) の構築速度が速かったので安心した．hash の代替としても使えるレベル．圧縮とかをしないぶん静的ダブル配列に比べれば構築速度では有利なのだけど，キーが整列されていることを利用していないので必ずしも速くなるとは言えない．ちなみに郵便番号のランダム順追加で未使用要素 0.1% 未満のダブル配列を高速に作るのは結構大変なので，我こそはと思う人はトライしてみて欲しい．
静的ダブル配列なら構築速度はあまり重要ではないので，圧縮が強力な darts-clone が良い（検索速度はどれも大差なしだけど，サイズが小さい方がキャッシュの観点からは有利）．数字に現れる性能の違いの他にもインタフェースの使い易さや，微妙な制限の違い（key に \0 を使えるとかレコードの型の制限等）もあるので，（そもそも何らかの圧縮をサポートした静的ダブル配列ライブラリの間には神経質になるほどの性能差は無いし）好みで選ぶのが吉．超大規模なトライを構成する場合や，組み込みなどでメモリの制限が厳しい場合を除き，簡潔データ構造を用いたトライは必要無いかも．
動的ダブル配列は更新をサポートする関係上，構築時に CHECK ã‚’ 1 byte にする圧縮が難しい（衝突時に後から追加したノードを常に移動するなら可能だが，未使用要素数が増えやすくなるため，結局サイズが大きくなったりする．例えば上記の実験データだと，ランダム順追加で2倍前後構築が遅くなり，未使用要素数が（特に郵便番号辞書では）顕著に増えた; DoubleArray(3-3): BASEとCHECK配列圧縮 - sileのブログ参照）．同様に，1 byte の CHECK を利用した共通部分木併合も逐次追加では難しい．ただ，BASE が重ならないようにダブル配列を構築すれば，保存時に CHECK を圧縮するのはカンタン．一方で，TAIL の実装や共通接尾辞の併合は出来そうだが，TAIL 部分は unary なので TAIL 無しでもそもそも配置コストは低いし，TAIL が短くなることが頻繁にあるため，注意しないとメモリ確保のオーバーヘッドが無視出来ないかもしれない．

[追記; 2010/03/28] darts-clone 0.32g が更新されて (beta5)，値の指定がないとき（build () の引数で value を省略して，全てのキーに固有の値を与えるとき）の構築速度が速くなっていたので実験結果を更新した（ついでに，value を省略できるライブラリは全て省略するように合わせた）．ノード数が制限される圧縮を用いた 0.32e5 の DoubleArray で，レコードに固定値にした場合にはサイズが大きく削減されたのでついでに載せておく (HugeDoubleArray についてはほとんど削減されず)．