2007年4月12日

[Namazu-devel-ja 1552] Re: hash の負荷軽減

寺西です。

更に修正してD1,D2を測定しました。D1 と D2 の違いはインデックスの書き
出し回数のみです。

[修正3の内容]
- 修正1の内容を元に臼田さんの修正内容を取り込みました。
- 1つ前の単語のhash値をキャッシュすることで性能向上が見られたので、

その次の単語のhash値をキャッシュするようにしました。
しかし、hash値は前の単語の長さによって4種類の値のいずれかとなる
  ため、キャッシュを配列にして4種類保存できるようにしました。
- mknmz::indexer::_splitsymbol が mknmz::hash を抜いて重い処理と
なったので、記号が含まれない場合は即リターンするように処理を
省きました。

* 修正後も NMZ.p はもちろんインデックスの中身は同じです。

[デメリット]
- 最大 単語数 x 4 x ハッシュ 分のデータが主メモリに余分に必要と
なります。
- ソースが分かりにくくなりました。


A1:
修正前 インデックス書き出し3回
User+System Time = 329.6541 Seconds

A2:
修正前 インデックス書き出し1回
User+System Time = 289.0096 Seconds

B1:
修正1 インデックス書き出し3回
User+System Time = 302.7359 Seconds

B2:
修正1 インデックス書き出し1回
User+System Time = 280.9919 Seconds

D1:
修正3 インデックス書き出し3回
User+System Time = 283.1735 Seconds

D2:
修正3 インデックス書き出し1回
User+System Time = 239.5587 Seconds

という結果でした。A1 の時間を 1.0 として比較した結果は次の通りです。
* C1, C2 の修正内容は省略。

A1: 1.000
A2: 0.877
B1: 0.918
B2: 0.852
D1: 0.859
D2: 0.727

- A2 と D2 を比較すると D2 は A2 の 0.829 でした。(修正の差)
- D1 と D2 を比較すると D2 は D1 の 0.846 でした。(インデックスの
書き出し回数の差)


修正3によって約15%ほど高速化していることが分かります。
また、インデックスの書き出しを1回にすると、約27%も高速化して
います。
# mknmz ったら...。


[補足]
上記の結果はあくまでも手元の環境で、テストデータ(メール)を処理した
 場合の結果に過ぎません。
マシンの性能、OS、Perl のバージョンなどによっては結果に差がでる
でしょう。
文書数、1文書のテキストの量によっても結果は異なるでしょう。
また、文書のメディアタイプがPDF,Word, Excel, HTML 等では、それぞれ
用の重い処理が加わるため、ここまでの効果はでないでしょう。


[D1]

Total Elapsed Time = 481.2735 Seconds
User+System Time = 283.1735 Seconds
Exclusive Times
%Time ExclSec CumulS #Calls sec/call Csec/c Name
10.3 29.34 46.368 4136 0.0071 0.0112 mknmz::make_phrase_hash
9.37 26.53 24.950 794790 0.0000 0.0000
mknmz::indexer::_splitsymbol
6.72 19.01 17.483 768357 0.0000 0.0000 mknmz::hash
6.31 17.86 41.691 24816 0.0007 0.0017
mknmz::indexer::_wordcount_sub
4.45 12.59 12.362 118804 0.0001 0.0001 Text::Kakasi::xs_do_kakasi
4.10 11.60 255.21 4136 0.0028 0.0617 mknmz::namazu_core
4.01 11.34 19.768 3 3.7814 6.5893 mknmz::write_index_sub
3.98 11.26 11.285 4136 0.0027 0.0027 mknmz::add_key
3.95 11.19 11.192 4136 0.0027 0.0027
File::MMagic::checktype_data
3.12 8.845 37.303 4136 0.0021 0.0090 mknmz::put_field_index
3.09 8.756 8.791 4136 0.0021 0.0021
mailnews::mailnews_citation_filter
3.02 8.548 17.156 3 2.8493 5.7185
mknmz::write_phrase_hash_sub
2.87 8.118 8.633 4136 0.0020 0.0021 mailnews::mailnews_filter
2.82 7.988 7.781 104675 0.0001 0.0001 mknmz::get_last_docid
2.72 7.708 7.693 8486 0.0009 0.0009 NKF::nkf


[D2]

Total Elapsed Time = 570.3587 Seconds
User+System Time = 239.5587 Seconds
Exclusive Times
%Time ExclSec CumulS #Calls sec/call Csec/c Name
11.8 28.43 44.307 4136 0.0069 0.0107 mknmz::make_phrase_hash
11.1 26.61 24.235 794790 0.0000 0.0000
mknmz::indexer::_splitsymbol
7.88 18.87 16.575 768357 0.0000 0.0000 mknmz::hash
7.24 17.35 39.896 24816 0.0007 0.0016
mknmz::indexer::_wordcount_sub
5.26 12.59 12.244 118804 0.0001 0.0001 Text::Kakasi::xs_do_kakasi
5.17 12.39 12.443 4136 0.0030 0.0030 mknmz::add_key
4.80 11.50 248.73 4136 0.0028 0.0601 mknmz::namazu_core
4.76 11.40 11.398 4136 0.0028 0.0028
File::MMagic::checktype_data
3.78 9.065 36.849 4136 0.0022 0.0089 mknmz::put_field_index
3.68 8.824 8.847 4136 0.0021 0.0021
mailnews::mailnews_citation_filter
3.42 8.188 8.165 8486 0.0010 0.0010 NKF::nkf
3.02 7.228 7.824 4136 0.0017 0.0019 mailnews::mailnews_filter
2.93 7.018 6.684 111827 0.0001 0.0001 IO::File::open
2.88 6.908 6.898 4136 0.0017 0.0017 mailnews::uuencode_filter
2.60 6.218 6.195 8272 0.0008 0.0007 gfilter::line_adjust_filter


--- mknmz.in.org 2007-04-11 05:49:15.000000000 +0900
+++ mknmz.in 2007-04-12 06:23:34.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'}) ;
@@ -2200,13 +2204,17 @@ sub make_phrase_hash ($$$) {
my %tmp = ();
$$contref =~ s!\x7f */? *\d+ *\x7f!!g; # remove tags of weight
$$contref =~ tr/\xa1-\xfea-z0-9 \n//cd; # remove all symbols
+ $$contref =~ s/^\s+//;
+ $$contref =~ s/\s+$//;
my @words = split(/\s+/, $$contref);
- @words = grep {$_ ne ""} @words; # remove empty words
+# @words = grep {$_ ne ""} @words; # remove empty words
my $word_b = shift @words;
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);
+ next if (length($word) == 0 || length($word) >
$conf::WORD_LENG_MAX);
+ $CacheHash[0]{$word_b} = hash(0, 0, $word_b)
+ if (!exists($CacheHash[0]{$word_b}));
+ my $hash = hash($CacheHash[0]{$word_b}, length($word_b), $word);
unless (defined $tmp{$hash}) {
$tmp{$hash} = 1;
$PhraseHashLast{$hash} = 0 unless defined
$PhraseHashLast{$hash};
@@ -2303,16 +2311,23 @@ 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 $offset = $start & 0x03;
+ return ($init ^ $CacheHash[$offset]{$word}) & 65535
+ if (exists($CacheHash[$offset]{$word}));

my $hash = 0;
- for (my $i = 0; $word ne ""; $i++) {
- $hash ^= $Seed[$i & 0x03][ord($word)];
- $word = substr $word, 1;
- # $word =~ s/^.//; is slower
+ my $rword = reverse($word);
+ my $i = $offset;
+ while(length($rword)) {
+ $hash ^= $Seed[$i++ & 0x03][ord(chop($rword))];
+ # $word = substr $word, 1; is slower
+ # $word =~ s/^.//; is slower
}
- return $hash & 65535;
+ $CacheHash[$offset]{$word} = $hash & 65535;
+ return $init ^ $hash;
}

sub do_wakatigaki ($$) {


--- pl/indexer.pl.org 2005-10-08 20:40:51.000000000 +0900
+++ pl/indexer.pl 2007-04-12 08:31:01.000000000 +0900
@@ -135,6 +135,8 @@ sub _splitsymbol {
my $word = shift @_;
my $weight = shift @_;
my $word_count = $self->{'_keyindex'};
+
+ return if $word !~ /[^\xa1-\xfea-z_0-9]/;
if ($word =~ /^[^\xa1-\xfea-z_0-9](.+)[^\xa1-\xfea-z_0-9]$/) {
$word_count->{$1} = 0 unless defined($word_count->{$1});
$word_count->{$1} += $weight;
@@ -148,8 +150,7 @@ sub _splitsymbol {
$word_count->{$1} += $weight;
return unless $1 =~ /[^\xa1-\xfea-z_0-9]/;
}
- my @words_ = split(/[^\xa1-\xfea-z_0-9]+/, $word)
- if $word =~ /[^\xa1-\xfea-z_0-9]/;
+ my @words_ = split(/[^\xa1-\xfea-z_0-9]+/, $word);
for my $tmp (@words_) {
next if $tmp eq "";
$word_count->{$tmp} = 0 unless defined($word_count->{$tmp});
--
=====================================================================
寺西 忠勝(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月12日 11:00
役に立ちました?:
過去のフィードバック 平均:(0) 総合:(0) 投票回数:(0)
本記事へのTrackback: http://hoop.euqset.org/blog/mt-tb2006.cgi/57158
トラックバック
コメント
コメントする




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