FreyaSX開発メモ(6) -- 17 August, 2004, Yutaka Sato
インデックス圧縮法の簡素化
「体操ニッポン復活」しました。かなりドキドキハラハラ、とてもウルウルでした。 さて、FreyaSX はこの一ヶ月間、XMap, IndexFile, LexiconFile, ... と大幅な 改造（主に簡素化と一般化、64bits拡幅）を行ってきまして、リリース毎に ファイル非互換という状況が続いて来ました。version 0.99でそろそろ落ち着いて 来て、version 1.0 も近付いて来たかなと思っていたのですが、、、
昨日ボウリングをしにクルマを走らせている時、当面やるとしたらあとは索引の マージの高速化かなぁというようなことを考えていました。索引の作成自体に ついてはもう現状からヒト桁早くするというのは難しいと思われます。そこで やっている処理がそこそこ複雑ですので(Patricia木の辞書やHashの検索等)。 一方、マージについては、基本的にはマージだけですから理想的にはディスクの 読み書きの時間くらいでイケル可能性もあるようにも思います（あくまで理想 ですが）。
マージが高速化できれば、索引の作成も（テンポラリな分割索引の作成・併合が 高速化するので）高速化します。また、特に大きな索引と小さな索引のマージが 高速にできれば、索引の仮想的な逐次的更新の実現につながります。
ここで、これまでマージがそこそこ時間がかかってしまうのはインデックスの圧縮・ 伸長の処理時間のためだったので、圧縮法を変更（ビット単位からバイト単位へ 単純化）したら効果絶大（約2倍高速化）したというのが、今回のお話です。
索引のマージの高速化の意義
マージがある程度高速になれば、索引の逐次的な追加機能は実用上必要なくなる と思われます。プロキシを通過したデータをリアルタイムに索引に追加する （でもって自動的に索引を更新維持したり、検索機能付きのヒストリみたいに使う） ような用途を考えると、逐次的な追加や削除の機能はどうしても欲しいのです。 しかし、それが可能なように索引ファイルの構造自体を設計すると、それはどう しても索引のゼロからの作成に対しても、検索に対しても、最適な構造となり 得ないと思われます。 ですので、索引の構造自体には、逐次更新を実現するためのブロック構造等は 入れないで行ってみよう、と思っています。
既に FreyaSX-0.98で、オリジナルにあったIndexFileのブロック構造は廃止して しまい、単純なベタ詰めにしました。これは索引の作成を20%〜30%位高速化したと 思います。検索のオーバヘッドもそこそこ減少したはずです。（いずれちゃんと 計測しなくては...）
また、FreyaSX-0.95から、本体の索引と追加分の索引を、検索時に別々に検索 して結果を併合するようにしていて、これも実用上の性能に問題無いようです。 問題は追加分への逐次的な追加なのですが、こちらは索引同士のマージで行えば 良いでしょう。検索時のマージと、追加分索引へのマージ、という組合せで、 実用上十分な逐次的な追加機能が得られるのではないかと思います。 そのためには、索引同士のマージの速度が重要です。
マージ処理のコスト要因と改良法
しかし、現状のマージはかなり低速です。索引をゼロから作る場合（大きな索引 が一時的に分割作成され、マージされる場合）にも、その処理時間の20%〜30%を マージ処理の時間が占めています。 このマージの時間の大半が、ポインタ(語の出現位置を指す)の伸長・再圧縮の ためのCPU時間だということは、gprofで観測してわかっていました。具体的には、 ポインタ(の値の差分)を可変長ビット列に圧縮・伸長する Coder の処理時間です。
ポインタ長が64ビットの場合、圧縮しない場合に較べて索引ファイルのサイズ が1/3くらいになるので、この圧縮は外せません。もうディスクがバカみたいに 安い時代ではありますが、ファイルが小さくなることはファイルアクセスの 時間を短縮するという面で重要です。
で、クルマの中で思いついたことというのは、大きな索引と小さな索引をマージ する場合、マージする必要のある、共通のキーを対象とする索引（ポインタ）は 割合としてわずかだということです。現状の実装では、なにはともあれ読み込んだ 全てのポインタ列を全て伸長して、キーが共通のものは併合して、圧縮して書き 込むという手順になっています。これを、キーが共通のものだけ伸長して併合して 圧縮、他は単に読み込んだものをそのまま書き出す、ということにすれば、 性能は大幅に改善する。はずです。
併合する際には、2番目以降の索引についてはポインタの書き換え（オリジナル Freyaではバイトオフセットの加算、FreyaSXではドキュメント番号の加算）も 必要になりますが、大きな(本体)索引と小さな(追加分)索引の併合の場合では、 大きな索引を1番目の索引とすれば、ほとんど書き換え無しで左から右へ流す だけになります。
ということで、この線でやってみようと思ったのですが、その前にまず、圧縮の 方法自体を簡素化してみたらどうだろう、と思ってやってみたわけです。
圧縮法の変更とその効果: 可変長ビットから可変長バイトへ
オリジナルFreyaでは、一つの語を参照しているポインタの並びに対して、 ポインタの値の間の差分をとってそれを可変長ビットに圧縮しています。この 圧縮は、FreyaSXでポインタを64ビットに拡幅して、値の空間がスパースになって からは不可欠のものになりました。
しかし、可変長ビットに圧縮するには、ビット数の分の処理を必要とするわけで、 これがとても重い。これに対して、可変長バイトへの圧縮なら、最大で 8倍ないしヒト桁程度軽くなる可能性が考えられます。
可変長のバイト列による整数の表現というのはすでに0.98でIndexFileをべたファ イルに変更した際（圧縮ポインタ列のバイト長の表現のため）に導入していました。 これは整数を可変長の7bit列で表現し、8bit目は継続を表すビットとする、という 簡単なものです。 その後それを、LexiconFile中でのポインタの表現や、検索時のポインタの表現に 利用していましたが、これをIndexFileにも使ってみたらどうか？というわけです。 基礎となる圧縮・伸長自体のコストが安くなれば、かつその圧縮率の低下がそこ そこであれば、マージの高速化だけでなく、全ての処理に効用があります。
で、例によってDeleGate-ML(12,500件)の索引に適用してみた結果です。 (MacOSX 10.2 + 1GHz iMac)
予想外でしたが、索引ファイルは大きくはならず、多少小さくなりました。 timeで測定すると、所要のCPU時間も実時間も約半分になりました。 gprof で見てみると、オリジナルの可変長ビットCoderでは処理時間の 70%以上を 占めていたのが、可変長バイトへのコーディング処理では 20%程になりました。 速度が約2倍になったのと整合しています。 変更後のものを gprof で見ると、C++固有のI/Oと思われるもの(getとか basic_streambufとか)が大半を占めるようになりました。これらを削減するには、 このあたりを C で書いてしまうのが素直なような気がします。
なお、初期索引作成時には「テンポラリの分割索引を圧縮しない」ようにする、 というのを以前考えたのですが、これは特に64ビットになった場合テンポラリ ファイルのI/Oがそこそこ重くなることもあって、逆効果のようでした。 圧縮・伸長が十分に軽くなれば、これも必要ないことだと思います。
おわりに
今朝は朝から体操競技の決勝だったので、テレビを見ながらちょこっとやって みたら結構うれしい大当たりだったので久しぶりにメモを書きました。思ったより 簡単な変更で効果があったのと、その結果C++固有のオーバヘッドらしきものが 支配的になってしまったので、「併合時に実際に書き換え・併合が必要なもの だけ伸長・再圧縮する」という当初の思いつきを実現するには至っていません。 これはまあ、ファイルの仕様を変更しなくてもいつでもできるので、いずれ やりたいと思います。 マージの速度はあと2倍から3倍はイケルんじゃないかと思っています。となれば 「約1000ドキュメントの索引の併合を1秒で処理」が十分堅い感じになって、 イイ感じです。
実のところ、0.97でポインタを64ビットに拡幅した時にパンドラの箱を開けて しまったという感じです。その後の変更について書くべき事はあまりに多くて 書くのに気合いが必要で、簡単に書き出せない感じです。 とにかく言えるのは、オリジナルFreyaで、ポインタが32ビットで、テキストの バイトオフセットだったというのは、色んな意味で、オリジナルFreyaの使われ 方や設計に調和した、すっきりさわやかな選択だったんだと思います。 対してFreyaSXで64ビットに拡張したのは間違いだったかもと疑っていた時期も あるのですが、やはり用途や拡張性を広げるには避けて通れないことだったの ではないかとも思っています。
そういう重い話にくらべて、今度のようにちょっとした思いつきでうまくいった というのは気楽です。金メダルだし。
それにしても、昔の黄金時代の体操選手って結構ふけ顔だったように記憶している のは当時自分が幼少だったせいかと思ったら、今テレビで見てもやっぱりふけてる ので安心(^^?しました。対して最近の選手は実際、実に若い。今度の黄金時代は 長いかも？