FreyaSX開発メモ(2) -- 15 June, 2004, Yutaka Sato
索引作成のひとケタ高速化達成(^^)
昨日から集中的に FreyaSX での索引作成の高速化に取り組んでみたところ、 オリジナルのFreya での索引作成に較べてひと桁高速になりました。 例えばメールの索引を作成する際、Freyaではだいたいの目安として、1秒 あたり10メールくらいの処理速度ですが、FreyaSX では 100メール/秒ほどに なりました (測定環境: 1GHz PowerPC + 512MB + MacOSX 10.3)。
実は先週、この前処理用のプログラムとして "any2fdif" というものを C で 自作したところ、こちらは Freya附属の Perl スクリプト (mail2fdif, html2fdif) に較べて30倍ほど高速になりました。 本家Freyaの前処理プログラムが遅いのは当然で、まずはそれが Perl で 書かれていること、そして、ドキュメントの数の回数だけ繰り返して、文字 コード変換等の外部プログラムを起動したり、テンポラリファイルを作成 したりしているからでしょう。ですからこれらを一つのCプログラムで実現 すればこの程度の高速化が実現するのは、当然といえば当然です。
もともと、この前処理プログラムを作成した動機は、性能の向上というより 移植性の問題でした。Freya の html2fdif は HTML の処理系モジュール？ を必要とするのですが、これは MacOSX のデフォルト Perl 環境にはあり ませんでした。どこからか探してくれば良いのでしょうけれど、個人的には そういう作業がすごく億劫です。複数のOS上で使用することも考えて、 こういうのは自分で作ってしまえば、いちいち Perl の環境を用意する必要 もなくなるし、処理速度も上がるでしょうから、一石二鳥です。 mail2fdif や html2fdif を読めば、何をやっているかはほぼ自明なので、 同等なことをCで書きました。MIMEの処理やHTMLの処理にはDeleGateを ライブラリとして使用することで、だいぶ手間が省けました。 (このプログラムは DeleGate/8.9.6に同梱して配布する予定です)
さて、すると今度は前処理に較べて本体の索引作成処理に10倍以上時間が かかることになりまして、そちらが気になり出します。なんとかこちらも 高速化できないかと考えて、ちょっと様子を探ってみましたが、最初は プログラムの構成や動きがよくわからず比較的あっさり撤退。 したのですが、やはり気になるので昨日から少し腰を入れて追跡してみました。
単語のハッシュ関数
あちこちにトレース文などを挟んで動作をみてみると、どうやら追加した 単語の数が増加するにつれて、単語あたりの処理時間がリニアに増えている ことがわかります。Freyaでは(おそらく一般的な方法だと思いますが)、ソースの ドキュメントから切り出した単語をメモリ上のハッシュ表に登録して行き、 上限の単語数 (config.h 中の MAXBUFFERINGWORDS) に達したらそれまでの状態をファイル上の索引ファイルに一時的 に書き出し、最後に複数の索引をひとつに併合するという処理を行っています。 この、最大収容単語数に近付くにつれて、ほんとどリニアに、単語あたりの 処理コストが増加しているのです。
となるとまず考えるのは、単語のハッシュ表の実装に何か問題があるのでは無いか ということです。ハッシュの衝突状況を調べてみると、確かに異常に衝突が多い。 するとハッシュ表がいっぱいになっているのか？と思ってみると、あらかじめ 最大収録単語数の4倍のエントリ数が割り当てられていますので、これで十分 でしょう(HashBag.h 中の if(slotNum> 3*n) )。 実際、これを大きくしてみてもほとんど状況が改善しませんし、 あまり大きくすると、メモリを余計に消費したりキャッシュのヒット率も 低下させるので望ましくありません。 では、どこに問題が。。。と思ってハッシュ関数を見てみると、Word.cc の中の Word::hashCode() に、
v = (v << 8) + *p; --(H1)とあります。おおっと、これはちょっとまずいのではないでしょうか、 原田さん？(^^; 末尾の4文字しかハッシュ値に反映されないので、ちょっと 長い単語では前半の部分が反映されないし、特に先頭が違って末尾が共通 している単語とか、ぶつかりまくりそうです。 (特に学生さんが限られた時間でシステムを開発しているような状況で、技術的 に高度なところに興味・注意が行っている時には、こういう基本的なところの コーディングがテキトーになってしまうのは、ままあることと思います)。 まずはこれを、私が個人的に昔からハッシュ関数用に愛用している、
v = (v << 2) ^ *p; --(H2)にしてみました。これだけでも大幅な改善を見たのですが、ほかにもいろいろ 試してみて、以下のようなものになりました。
v = key[0]; --(H3)
w = 0;
for(p = key; *p; p++){
v = (v << 2) ^ *p
w = (w >> 1) ^ (*p << 24)
}
v = v ^ w;
これは、前半に特徴のある文字列と後半に特徴のある文字列の、ぞれぞれを
ハッシュ値に反映させることを意図しています。（たぶん、しかるべき
教科書なんかをあたれば、
より適切な関数
がありそうですが。昔から教科書を読まないもので。。。）
比較のために、CRC32 でもやってみました(H4)。これは衝突率は最小に近い
と期待できますが、CRC の計算にそこそこ時間がかかってしまうので、
逆に多くの CPU を使ってしまう事のほうが多いかも知れません。
後になって改めて、それぞれのハッシュ関数による衝突状況と実行性能を 測定してみると、以下のようになりました。
表1) 平均ハッシュ衝突回数
----------------------------------------------------
対象データ: DeleGate-ML の最初の 1400 件(*a)の記事
単語数: 31605
ハッシュ表サイズ: 32768*4 (デフォルト)
平均衝突回数 所要処理時間(*b) 所要処理時間(*c)
(H1) 239.4 23.2 + 4.9 12.9 + 0.9
(H2) 83.5 19.9 + 4.6 10.5 + 0.9
(H3) 20.3 18.3 + 4.5 9.0 + 0.8
(H4) 1.1 17.8 + 4.4 8.8 + 0.7
(*a)ここでドキュメント数1400という中途半端な数を選んだのは、この
例ではたまたま、これがちょうど最大収容単語数(32768)に近い単語を
含むキリの良い数だから。これを越えると、複数の索引を作成してから
併合するという処理が加わるので、ここでは、ハッシュによる影響だけを
比較するために、その処理が起こらない数を選んだ。
(*b)は、オリジナルのFreyaに対してハッシュ関数だけを置き換えた際の
性能。(*c)は以下の「単語出現位置配列の拡張」の変更を加えた状態での
性能。
改めて見てみると、結局 CRC を使うのが良さそうにも思えます。
作業をしている時には、性能測定用のデータとして英語版DeleGateメーリング
リストのデータを用いていたのですが、日本語版で測定してみると、
状況が多少違うようです。
状況に応じてアダプティブにハッシュ関数を選択するというのも良いかも
知れません。
さて、このようにハッシュの衝突の問題はほぼ解消したのですが、処理性能の 改善は 20% ちょっと程度で、いまひとつもの足りません。 なにより、単語数が最大収容数に近付くにつれて、単語あたりの処理時間が ほとんどリニアに増加するという状況が、相変わらず見られたのです。
単語出現位置配列の拡張
いろいろ試している中で、単語の最大収容数を小さくしてやると、性能が 改善するのを見つけました。 具体的には、この数値はデフォルトでは 32*1024 ですが、これを 16*1024 に、 さらに 8*1024 にしてやると、処理時間が数十％も減少するのです。 ハッシュ表サイズによらず、その占有率は固定されている(衝突率はほぼ一定) なのに、表が大きくなるに従って性能が劣化して行くのはどうしたこと でしょう？原因はハッシュ表以外にあるようです。しかしどうもプログラム 全体の動作がわからないし。。。
最初はこの数値を小さくして（実行時に指定するオプションでも付けて）、 もうこの件は終りにしようとも思ったのですが、あまり小さくすると分割された 索引ファイルが多数になって、実際DeleGate-MLの12,400件の索引を併合する 際に256個のファイルディスクリプタ数上限を越えるという状況に見舞われ ました。ファイルディスクリプタの上限を増やして回避することもできますが、 これは一般的に通用するとは限りません。 そこでもうひとふんばりしてみることにしました。
ここで思い出したのが、最初に索引作成プログラム findex を走らせて gprof で関数毎のCPU使用率を調べた時に、free/alloc が最上位に来ていたことです。 当初これは、よくわかんないけど C++ だからかなぁ、と思って気にかけな かったのですが。 C++ のプログラムを gprof で見ても、結果の判読が困難なので、 プログラムの機能を一部分ずつ殺してみて、処理時間がどう変わるかを見て いくと、Indexer.cc から呼ばれている WordBreaker.cc の中の、
...
T *newvalues = new T[N + 1];
for(int i = 0; i < N; i++) newvalues[i] = values[i];
...
delete []values;
// 単語の出現位置の配列が、出現位置が1つ増える毎に再拡張されている
んーむ。これはちょっと大変なのではないでしょうか？
原田さん。。。(^^;
これだと、単語の出現位置の個数の回数だけ拡張が行われ、配列の
alloc + copy + free というのを毎回繰り返す事になります。
出現位置の個数に比例して alloc と free だけでなく copy のコストも増えます。
（フラグメンテーションでヒープを穴だらけにしそうな感じもします）。
なるほど、謎のCPU時間は、単語の個数ではなくて、出現位置の個数に比例
していたというわけですね。謎が解けました。
性能上の理想としてはポインタで繋がれたリストにするのが良いかもしれま せんが、実装が若干面倒？かもしれません（また配列上の逐次アクセスにおける メモリアクセスが局所性を持たないのは性能上不利かも？） 最初は反射的に、配列要素を8個ずつ拡張するようにしてみたら、性能が30% ほど改善。次に、2倍ずつ拡大していくようにしたら、50%ほど改善しました。
こうして、最大収容語数を増やしても処理性能が悪化しなくなりました。 そうなると、索引の分割と併合という処理のコストを減らすためには、 この値は大きくしたほうが有利になります。かといって、あまり大きくすると メモリの使用量が増えて、ホストのメモリ状況や他のプロセスの影響を 受け易くなるでしょう。そこで、デフォルトでは32*1024になっているところを、 64*1024に変更しました。
今回のまとめ
原作者のうっかりを、ちゃっかり指摘するような結果になりましたが、 特に性能向上が最重要の目標となっていない状況では、このようなうっかりは ありがちな事と思います（実際、原田さんの Freya TODO (or not to do)リストには、 索引作成の性能向上という項目はありません）。 逆に、このような大きめのうっかりもあり、ほとんど性能面でのチューンも されていないかも知れない状態で、当時の他のエンジンとコンパラ以上の性能を 実現していたことを立派だとも思います。
ともあれ、索引作成の基礎性能を約3倍に向上できました。前処理も併せると 全体でひと桁の性能向上を実現できたので、とりあえず満足です。 詳細に見れば、まだまだ(ここからが本当の)チューンアップができるのでは ないかと期待されます(まだうっかりもあるかも:p)。 また、入力のドキュメント数やサイズ、日本語か英語か、などによっても 性能上適切なハッシュ関数やテーブルのサイズが異なるようですので、入力に 動的に適応するようなアルゴリズムを試してみる価値もありそうです。
プロキシ(DeleGate)を通過するテキストを on the fly でインデックス化する、 という応用を考えると、現状でもかなりイイ線まで来ているとは思いますが、 もしさらにあと3倍とか高速化できれば、かなり広い応用に、実用上無問題、 という線までイケル感じがします。
[最後に蛇足ですが] 原田さんは開発の比較的早期からFreyaのソースを公開して いたようなのですが、この性能上の問題はずっと見過ごされていたものと 思われます。第三者による、他のエンジンとの性能比較などは結構なされて いるようなのですが、そもそも性能比較して意味のある状態になかったとも 言えます。 なんというか、ソースを公開するということがどれほど意味を持ち得るのかと いうことについても、考えさせられなくもありません。
------------------------------------------------------------------------
*** ../../orig/src/Word.cc Fri May 8 00:56:24 1998
--- Word.cc Tue Jun 15 18:55:14 2004
***************
*** 17,32 ****
--- 17,59 ----
}
if(that.buf == NULL) return 1;
return jstrcmp(buf, that.buf);
}
+ /* 1 0000 0100 1100 0001 0001 1101 1011 0111 */
+ #define CRC32POLY 0x04C11DB7
+ int strCRC32(char *str)
+ { int crc,bi,ovf;
+ char *s,oct;
+
+ crc = 0;
+ for( s = str; (oct = *s) != 0; s++ ){
+ for( bi = 0; bi < 8; bi++ ){
+ ovf = (crc < 0) ^ (oct < 0);
+ oct <<= 1;
+ crc <<= 1;
+ if( ovf ) crc ^= CRC32POLY;
+ }
+ }
+ return crc;
+ }
unsigned int
Word::hashCode() const{
+ // return strCRC32(buf);
+
unsigned int v = 0;
+ unsigned int vr = 0;
+
+ v = buf[0] << 7;
for(const char *p = buf; *p; p++){
+ /*
v = (v << 8) + *p;
+ */
+ v = (v << 2) ^ *p;
+ vr = (vr >> 1) ^ (*p << 24);
}
+ v = v ^ vr;
return v;
}
const Word &
Word::operator =(const Word &that){
*** ../../orig/src/valueSet.h Thu May 25 16:06:08 2000
--- valueSet.h Tue Jun 15 20:24:34 2004
***************
*** 8,20 ****
--- 8,24 ----
template
class valueSet { // 380yen
friend ostream& operator<<(ostream &stream, valueSet &set);
private:
int N;
+ int slots;
T *values;
public:
+ /*
valueSet() : N(0), values(NULL){}
+ */
+ valueSet() : N(0), slots(0), values(NULL){}
valueSet(const valueSet &that);
valueSet(const T *list, int listLen);
~valueSet(){ if(values) delete []values; }
operator const T *() const { return values; }
***************
*** 65,84 ****
--- 69,101 ----
return *this;
}
template valueSet &
valueSet::append(const T &x){
+ if(slots <= N){
+ if( slots == 0 )
+ slots = 2;
+ else
+ slots = 2 * slots;
+ T *newvalues = new T[slots];
+ for(int i = 0; i < N; i++) newvalues[i] = values[i];
+ delete []values;
+ values = newvalues;
+ }
+ values[N] = x;
+ /*
if(N == 0){
values = new T[1];
values[0] = x;
}else{
T *newvalues = new T[N + 1];
for(int i = 0; i < N; i++) newvalues[i] = values[i];
newvalues[N] = x;
delete []values;
values = newvalues;
}
+ */
N++;
return *this;
}
template valueSet &
------------------------------------------------------------------------