2007年4月11日

[Namazu-devel-ja 1549] hash の負荷軽減

寺西です。

以前 hash の処理時間が重いということが分かったので、少し手を加えた
テストを行いました。
# 以前の臼田さんの修正は今回は反映していません。


テストデータ:

「namazu-devel-ja.tar.gz
< http://www.namazu.org/ml/namazu-devel-ja.tar.gz>; 4,136通

mknmz のバージョン:
今回は、development-2-1 を使いました。

修正内容:
hash の計算コストが高いのは、文字列の長さ分のループ処理がある
だと推測しました。また、以前のテストから substr による文字列の
切り出しに時間がかかっていることもわかっています。

このため、hash 計算にもちいる文字列を短縮することで、負荷を
抑えようと考えました。

とは言うものの hash 値が変わってはインデックスの互換性がなくなる
ので重複する計算をキャッシュを用いて負荷を軽減します。

hash では 1つ前の文字列と連結してhash値を計算します。この時、
連結した文字列の先頭からhash値を計算しますが、同じ単語
が何度も出る場合には、(前の単語の部分は)同じ計算を何度も繰り
かえすことになっています。

そこで、単語ごとに計算したhash値を保存することで、その計算を
省略します。
substr の処理も対象とする文字列の長さが短くなるため、文字列
処理のオーバーヘッドが軽減されます。

デメリットとしては、hash の呼び出し回数が増えることと、
キャッシュによるオーバーヘッドが多少あること、キャッシュ分の
メモリを必要とすることです。

テスト結果では約8%ほど負荷が軽減していますが、これはこのデータ
だからでしょう。データの種類と量が変わればそこまでの性能は出ない
かもしれません。
ただ、substr 処理が減るので Windows だともう少し性能が向上する
のではないかと期待しています。

以前の臼田さんによる修正も加えると、もう少し性能が上がるでしょう。


[修正前]

Total Elapsed Time = 360.3041 Seconds
User+System Time = 329.6541 Seconds
Exclusive Times
%Time ExclSec CumulS #Calls sec/call Csec/c Name
16.5 54.41 52.963 733289 0.0001 0.0001 mknmz::hash
12.1 39.87 38.290 794790 0.0001 0.0000
mknmz::indexer::_splitsymbol
8.31 27.39 79.808 4136 0.0066 0.0193 mknmz::make_phrase_hash
5.72 18.84 56.031 24816 0.0008 0.0023
mknmz::indexer::_wordcount_sub
3.91 12.88 12.652 118804 0.0001 0.0001 Text::Kakasi::xs_do_kakasi
3.55 11.71 11.745 4136 0.0028 0.0028 mknmz::add_key
3.37 11.10 302.66 4136 0.0027 0.0732 mknmz::namazu_core
3.27 10.78 19.068 3 3.5947 6.3560 mknmz::write_index_sub
3.26 10.74 10.742 4136 0.0026 0.0026
File::MMagic::checktype_data
2.79 9.194 38.483 4136 0.0022 0.0093 mknmz::put_field_index
2.71 8.926 8.931 4136 0.0022 0.0022
mailnews::mailnews_citation_filter
2.50 8.248 16.796 3 2.7493 5.5985
mknmz::write_phrase_hash_sub
2.50 8.228 8.213 8486 0.0010 0.0010 NKF::nkf
2.43 8.008 7.801 104675 0.0001 0.0001 mknmz::get_last_docid
2.30 7.578 8.163 4136 0.0018 0.0020 mailnews::mailnews_filter


[修正後]

Total Elapsed Time = 448.6459 Seconds
User+System Time = 302.7359 Seconds
Exclusive Times
%Time ExclSec CumulS #Calls sec/call Csec/c Name
13.1 39.70 37.335 794790 0.0000 0.0000
mknmz::indexer::_splitsymbol
13.0 39.40 37.034 795386 0.0000 0.0000 mknmz::hash
10.1 30.64 66.925 4136 0.0074 0.0162 mknmz::make_phrase_hash
6.17 18.67 54.336 24816 0.0008 0.0022
mknmz::indexer::_wordcount_sub
4.23 12.80 12.454 118804 0.0001 0.0001 Text::Kakasi::xs_do_kakasi
3.97 12.03 285.23 4136 0.0029 0.0690 mknmz::namazu_core
3.74 11.33 11.383 4136 0.0027 0.0028 mknmz::add_key
3.73 11.29 11.288 4136 0.0027 0.0027
File::MMagic::checktype_data
3.56 10.78 19.022 3 3.5937 6.3406 mknmz::write_index_sub
3.23 9.787 36.439 4136 0.0024 0.0088 mknmz::put_field_index
2.91 8.804 8.847 4136 0.0021 0.0021
mailnews::mailnews_citation_filter
2.84 8.592 16.433 3 2.8640 5.4778
mknmz::write_phrase_hash_sub
2.62 7.938 7.915 8486 0.0009 0.0009 NKF::nkf
2.51 7.608 8.084 4136 0.0018 0.0020 mailnews::mailnews_filter
2.51 7.588 7.276 104675 0.0001 0.0001 mknmz::get_last_docid


--- mknmz.in.org 2007-04-11 05:49:15.000000000 +0900
+++ mknmz.in 2007-04-11 08:28:59.000000000 +0900
@@ -74,6 +74,8 @@ my $Document = undef;

my $ReceiveTERM = 0;

+my %CacheHash = ();
+
STDOUT->autoflush(1);
STDERR->autoflush(1);
main();
@@ -109,6 +111,8 @@ sub main {
my $flist_ptr = 0;
my $processed_files_size = 0;

+ %CacheHash = ();
+
if ($CheckPoint{'continue'}) {
# Restore variables
eval util::readfile($var::NMZ{'_checkpoint'}) ;
@@ -2206,7 +2210,11 @@ sub make_phrase_hash ($$$) {
my $docid = $docid_count + $docid_base;
for my $word (@words) {
next if ($word eq "" || length($word) > $conf::WORD_LENG_MAX);
- my $hash = hash($word_b . $word);
+
+ $CacheHash{$word_b} = hash(0, 0, $word_b)
+ if (!exists($CacheHash{$word_b}));
+
+ my $hash = hash($CacheHash{$word_b}, length($word_b), $word);
unless (defined $tmp{$hash}) {
$tmp{$hash} = 1;
$PhraseHashLast{$hash} = 0 unless defined
$PhraseHashLast{$hash};
@@ -2303,11 +2311,11 @@ sub write_phrase_hash_sub () {
}

# Dr. Knuth's ``hash'' from (UNIX MAGAZINE May 1998)
-sub hash ($) {
- my ($word) = @_;
+sub hash ($$$) {
+ my ($init, $start, $word) = @_;

- my $hash = 0;
- for (my $i = 0; $word ne ""; $i++) {
+ my $hash = $init;
+ for (my $i = $start & 0x03; $word ne ""; $i++) {
$hash ^= $Seed[$i & 0x03][ord($word)];
$word = substr $word, 1;
# $word =~ s/^.//; is slower
--
=====================================================================
寺西 忠勝(TADAMASA TERANISHI) yw3t-trns@xxxxx
http://www.asahi-net.or.jp/~yw3t-trns/index.htm
Key fingerprint = 474E 4D93 8E97 11F6 662D 8A42 17F5 52F4 10E7 D14E

_______________________________________________
Namazu-devel-ja mailing list
Namazu-devel-ja@xxxxx
http://www.namazu.org/cgi-bin/mailman/listinfo/namazu-devel-ja

投稿者 xml-rpc : 2007年4月11日 20:15
役に立ちました?:
過去のフィードバック 平均:(0) 総合:(0) 投票回数:(0)
本記事へのTrackback: http://hoop.euqset.org/blog/mt-tb2006.cgi/57112
トラックバック
コメント
コメントする




画像の中に見える文字を入力してください。