Centroid Path Decompositionを使ったトライでダブル配列と勝負してみた

Tag

# データ構造

# 大規模データ処理

preferred

釣りタイトルを付けたかったのですがさっぱり思いつかないのでもう諦めました。徳永です。

今回はCentroid Path Decomposition（以下CPD）についての話を書きます。直訳すると重心パス分解となるでしょうか。Trieを実現するためのテクニック（普通のツリーにも使えるのかな？なかなか難しそうですが…）の一つです。CPDは一年前の弊社岡野原の記事に出てきますが、私のような素人にはあれだけでは理解できない部分があったので、今回はちょっと論文を読んでみました。

Trieの実装によくある問題

Trieを実現するためのデータ構造というとダブル配列とかが挙げられますが、こういった高速なデータ構造にも、ランダムアクセスが多いという弱点があります。メモリはHDDなどと比べるとランダムアクセスに耐えうる記憶媒体ですが、とは言えランダムアクセスは避けられるに越したことはありません。CPDを使うことで、ランダムアクセスの回数を減らすことができます。

もちろん、ツリーを線形のアドレスで表現されるメモリに押し込めるのですから、完全にシーケンシャルにアクセスできるようになる、という訳ではないのですが、ツリーをある形に分解することで、よくありそうなパターンは比較的ランダムアクセスが少なく済ませられるというのがCPDのメリットになります。しかし、後述の通り、今回はこのメリットを確認することはできませんでした。

CPDの概要

CPDでは、ツリーをCentroid Pathとそれ以外の部分に分解する、という作業を再帰的に繰り返していきます。

まず、Centroidとはなにかですが、あるノードに着目した時に、その子ノードのうちで、最も子(着目ノードから見たら孫ですね)ノードの多いものがCentroidです。

今回は例として、以下のようなトライをCPDで分解してみます。

以下の図において、赤い線で示したところがCentroid Pathで、緑の部分がCentroid Pathから分岐しているノードです。2番と3番は子ノードの数が一緒ですが、今回は子ノードの数が等しい場合はIDが小さな物をCentroid Pathとして採用することにしています。緑の部分から先はまた再帰的にCP分解していくことになります。

次の図では、次のCP分解を行うツリーを図示してみました。左側の青色の囲みと、右側のピンク色の部分の囲みの中がCP分解の対象です。6番のノードはCentroid Pathからの分岐ではありますが、そこで終端なので今回はCP分解は必要ありません（ここらへんの細かいところは実装に依存すると思いますが）。

最後に、左右の部分木をCP分解しているところです。赤いパスがそれぞれの部分木に置けるCentroidです。

さて、Centroid Pathとしては各ノードに置ける文字と、各ノードからの分岐先の情報（どの文字でどこのノードに飛ぶか）を記録しておけば、このツリーの形を後から復元することができます。ということで、情報を失うことなく、Trieを3本のCentroid Pathへと分解することができました。

後は、これを使ってどうやってノードを辿るかですが、例えば「ab」で探索する場合だと、まずCentroid Path上の0→2のbと、探索の1文字目のaを比較します。比較した結果違う文字なので、Centroid Pathの1文字目から分岐するノードである1と3を探索します。0→1の枝はaという文字なので、探索に成功して1番に移動します。ここからまたCentroid Pathを辿ってbとbを比較して4番のノードが見つかります。

説明がかなりあっさり気味ですが、後述の実験に気合を入れすぎて、説明を詳しく書く時間がなくなってしまいました。要望があればまた今度詳しく書きます。

CPDのメリットとデメリット

CPDのメリットはランダムアクセスの回数が減らせることです。一方、Centroid Path以外の部分では線形探索が必要となります。Grossiらの論文[1]ではrank/select辞書を使ったSuccinctなTrieを作っていますが、今回はメモリを贅沢に使ったぜんぜんSuccinctではないTrieを実装してみました。

まずCPDベースのTrieを実装してみたのですが、分岐以外の部分における速度の低下が非常に深刻で、そのままでは使い物にはなりませんでした。根に近い所では最悪90程度の長さを線形探索する必要があり、ここが時間を大幅に消費している原因のようです。という訳で、今回はシンプルなCPDベースのトライを実装して終わるつもりだったのですが、分岐部分をダブル配列っぽい感じで処理する感じの実装に改造してみました。

実験結果

以下では、共通接頭辞検索を実装して実験してみた結果を述べます。比較対象としては、既存のTrie実装の中でもっとも高速なものの一つであるdarts-cloneを用いました。

Wikipedia日本語版のタイトルリスト（1290607件）を使って実験してみたところ、darts-cloneでは共通接頭辞検索が辞書順とランダムでそれぞれ 105.6ns/key, 577.2ns/keyであったのに対し、自作Trieでは180.1ns/key, 1137.4ns/keyという結果になりました。

ここから、以下のようなことが読み取れます。

どちらの場合もdarts-cloneの方が圧倒的に速い

ほぼダブルスコアです。チューニングも頑張りましたが大して速くなりませんでした。残念ですがこれが今回の結論です。

さて、ここで終わってもいいのですが、そんな唐突なフィナーレは悲しすぎます。そこで、以下、どのあたりで遅くなっているのかをもう少し詳しく調べてみます。プロファイリングにはLinux Kernelに同梱されているperfコマンドを使いました。

詳しい結果を以下に示します。まずダブル配列の場合から。

       387,304,639 cache-references
       263,234,904 cache-misses              #   67.966 % of all cache refs
     4,104,638,532 branch-instructions
        84,182,522 branch-misses             #    2.05% of all branches
    32,808,085,084 instructions              #    0.59  insns per cycle
    55,575,220,656 cycles                    #    0.000 GHz

次に自作Trieです。

     1,006,797,327 cache-references
       672,031,146 cache-misses              #   66.749 % of all cache refs
    15,364,571,222 branch-instructions
       389,161,442 branch-misses             #    2.53% of all branches
    67,849,694,976 instructions              #    0.59  insns per cycle
   114,053,128,530 cycles                    #    0.000 GHz

キャッシュミスが微妙に減っているけれどもIPC（1クロックあたりの実行命令数、insns per cycleのところの数値です）を向上させるほどではなく、そして実行に必要であった命令数（instructionsのところの数値です）が32,808,085,084→67,849,694,976と大幅に上昇していることがわかります。ここから、たぶん複雑すぎるのだな、と予想ができます。

また、IPCがかなり低いこともわかります。実験したPCはSandy Bridgeアーキテクチャなので、理想的には2〜3程度のIPCが出るはずですが、実際には1にも届かないお粗末なIPCであることがわかります。IPCの向上を阻害する要因は（おそらく）たくさんありますが、分岐予測の失敗、メモリもしくはIOなど遅いデバイスへのアクセス、の2つが大きな原因となり得るでしょう。今回のプログラムは分岐予測の失敗は2.5%程度、キャッシュミスの割合は67%程度です。

が、正直ここまでがっつりチューニングすることは普段はあんまりない（ディスクアクセスが減って処理時間が減ったよ大勝利！みたいなおおざっぱなプログラミングをしています）ので、どちらが効いているのかはよくわかりません。そこでマニュアルを漁って調べてみました。

インテルのマニュアルには「分岐予測ミスには、約 20 サイクルのペナルティーが課せられる。」とあります。「約」というのは、命令によっておそらくペナルティが違うのと、μOP命令がキャッシュされてるかどうかでも変わってくるとか、複雑な状況を表現しているのでしょう。

また、こちらのIntelのセミナー資料によると、「L1キャッシュでのアクセスミスは数十クロックのペナルティーが生じる」「L2キャッシュでのアクセスミスは数十バスクロックのペナルティーが生じる」とあります。バスクロックということはCPUクロックに直すと3倍とか5倍とかの数字になりますから、L2キャッシュミスが発生すると、CPUからみると100クロックぐらいは待たされることになります。

という訳で、メインメモリまでデータを取りに行くのは本当に遅く、分岐予測よりも重いペナルティであることがわかりました。

これらのデータを元に上記のデータを読みなおしてみると、自作トライでIPCが向上していないのが不思議に感じられます。L2キャッシュミスのペナルティ数が増えてはいないので、命令数が増えた分、IPCは上がっていて良さそうなものですが。命令間の依存関係でIPCが上がらない、というぐらいの原因しか思いつきません。ここら辺は又今度もう少し深追いしてみたいですね。

余談ですが、perfは最近のCPUの機能がいろいろ使えるようになっているすごいプロファイラです。ビルドしなおしたりせずに使えるので、お手軽簡単でもあります。Linuxを使っているのであれば一度試しておく価値があるでしょう。Debian/Ubuntuであればapt-get install linux-toolsでインストールできます。

また、Intelの最適化マニュアルは非常に勉強になります。暇なときにだらだらと眺めておくと、そのうち役に立ちそうです。