[Namazu-devel-ja 1495] Re: mknmz の add_key( ), make_phrase_hash() の負荷軽減

[Yukio USUDA]

臼田です

On 2007/02/22, at 0:41, Tadamasa Teranishi wrote:

> 寺西です。
>
> Yukio USUDA wrote:
>>
>> 今回、適度な長さの文字列になった段階で配列にすれば、規模の大 
>> きい
>> 文字列領域の移動によるガベージコレクション回数が減るのではと 
>> 考え、
>> 下記のスクリプトを作成して試してみました。
>
> これは、ガベージコレクションの回数が減ることによる速度向上を期 
> 待した
> ものという理解でよろしいですよね?

今のところその通りです

>
>> メモリ量、OSの種類、Perlのバージョン等で違うと思 
>> われ
>> ますが
>> （同じ環境でも複数回試すと結果に大きくばらつきがでます）
>> テスト用スクリプトでは
>> 1.2〜3倍程度の処理時間の違いが出ました。
>
> 手元の環境ではそこまでの性能はでていませんが、このテストスクリ 
> プト
> では、やや速くなっています。

UNIX系では違いが小さいようですが、データ生成ループ回数を増やすと
違いがでてきます。
また、MS-Windows の ActivePerl では違いが大きく出て 
います。

>
>> 他の環境等で試してみても悪くなることがないようでしたら
>> cvs に
>> 入れてみようと思います。
>
> ん〜。
> このテストスクリプトでは、こういった結果が出ていますが、 
> mknmz では
> 処理が異なるので、ここまでの性能差がでるのかどうか、やや疑問で 
> す。

他にも時間のかかる処理があるので改善程度から見ると全体に占める割合
はあまり大きくならないと思います。

>
> テストスクリプトでは sub3 の後に sub2 を呼び出して 
> いるのが気になり
> ます。
> ガベージコレクションの影響を考えるなら、テストスクリプトを 
> 2つに分け
> て、テストするべきでしょう。

もともと分けて試していました。
乱数を用いてデータを生成しているので出来上がる結果が違わないことを
確認するために一回で実行するようにしました。
メモリ解放のタイミングが重ならないように速度、メモリ使用量の比較に
はスクリプトを分けてテストする必要があります。

>
> 次に単語がアルファベット2文字固定というのも気になります。
> 文字列が長くなれば、
> length($keyindex{$word} だとか、@{$keyindexarray 
> {$word}} のところの
> (ハッシュ値計算を含めて)処理時間に影響が出てくるのではな 
> いかとも
> 思います。
>
> それと if (length($keyindex{$word}) > 1000){ のところで 
> すが、
> $keyindex{$word} が、"[$n]" とテキストでデータを格納して 
> いるので、
> 実際のデータよりも平均すると文字列長が長くなっているのではない 
> かと
> 思います。(実際のデータはpackされたバイナリデータ)
> 今回のテストでは、文字列が長くなれば長いほど、ガベージコレク 
> ションの
> 回数が減る可能性が高まるわけですので、有利に働いているのではな 
> いか
> と思われます。

仮説を少しづつ確認していく段階なので違いが大きめに出るほうが観測
しやすいと考え試しています。データ構造についてはご指摘の通りです。

とりあえず mknmz に入れてみて試してみることにします。
HEAD で試した diff をつけます。


diff -u -r1.178 mknmz.in
--- mknmz.in    10 Nov 2006 16:43:31 -0000      1.178
+++ mknmz.in    21 Feb 2007 22:14:02 -0000
@@ -59,8 +59,10 @@
my $UpdatedFilesCount = 0;
my $APPENDMODE = 0;
my %PhraseHash = ();
+my %PhraseHashArray = ();
my %PhraseHashLast = ();
my %KeyIndex = ();
+my %KeyIndexArray = ();
my %KeyIndexLast = ();
my %CheckPoint = ("on" => undef, "continue" => undef);
my $ConfigFile = undef;
@@ -621,6 +623,10 @@
         $KeyIndex{$word} .= pack("w2",
                                  $docid - $KeyIndexLast{$word},
                                  $keyref->{$word});
+        if (length($KeyIndex{$word}) > 250){
+            push(@{$KeyIndexArray{$word}}, $KeyIndex{$word});
+            $KeyIndex{$word} = '';
+        }
         $KeyIndexLast{$word} = $docid;
      }
}
@@ -2197,6 +2203,10 @@
             $tmp{$hash} = 1;
             $PhraseHashLast{$hash} = 0 unless defined $PhraseHashLast 
{$hash};
             $PhraseHash{$hash} .= pack("w", $docid - $PhraseHashLast 
{$hash});
+            if (length($PhraseHash{$hash}) > 250){
+                push(@{$PhraseHashArray{$hash}}, $PhraseHash{$hash});
+                $PhraseHash{$hash} = '';
+            }
#          util::dprint("<$word_b, $word> $hash\n");
             $PhraseHashLast{$hash} = $docid;
         }
@@ -2245,14 +2255,22 @@
         if (defined($PhraseHash{$i})) {
             if ($baserecord eq "") {
                 print $fh_tmp_pi pack("N", $ptr);
-               my $record = $PhraseHash{$i};
+               my $record = '';
+                if (defined($PhraseHashArray{$i})) {
+                   $record = join('', @{$PhraseHashArray{$i}});
+                }
+               $record .= $PhraseHash{$i};
                 my $n2 = length($record);
                 my $data = pack("w", $n2) . $record;
                 print $fh_tmp_p $data;
                 $ptr += length($data);
             } else {
                 print $fh_tmp_pi pack("N", $ptr);
-               my $record = $PhraseHash{$i};
+               my $record = '';
+                if (defined($PhraseHashArray{$i})) {
+                   $record = join('', @{$PhraseHashArray{$i}});
+                }
+               $record .= $PhraseHash{$i};
                 my $last_docid = get_last_docid($baserecord, 1);
                 my $adjrecord = adjust_first_docid($record,  
$last_docid);
                 check_records(\$record, \$baserecord, 1) unless  
defined $adjrecord; # namazu-bugs-ja#31
@@ -2285,6 +2303,7 @@
      util::fclose($fh_tmp_pi);
      %PhraseHash = ();
+    %PhraseHashArray = ();
      %PhraseHashLast = ();
}

@@ -2384,7 +2403,11 @@
             for (; $cnt < @words; $cnt++) {
                 last unless $words[$cnt] le $current_word;
-               my $record = $KeyIndex{$words[$cnt]};
+                my $record = '';
+                if (defined ($KeyIndexArray{$words[$cnt]})) {
+                    $record = join('', @{$KeyIndexArray{$words 
[$cnt]}});
+                }
+               $record .= $KeyIndex{$words[$cnt]};
                 my $leng = length($record);
                 if ($current_word eq $words[$cnt]) {
@@ -2435,7 +2458,11 @@
      while ($cnt < @words) {
         my $leng = length($KeyIndex{$words[$cnt]});
         my $tmp = pack("w", $leng);
-       my $record = $KeyIndex{$words[$cnt]};
+       my $record = '';
+        if (defined ($KeyIndexArray{$words[$cnt]})) {
+            $record = join('', @{$KeyIndexArray{$words[$cnt]}});
+        }
+       $record .= $KeyIndex{$words[$cnt]};
         my $data_i = "$tmp$record";
         my $data_w = "$words[$cnt]\n";
@@ -2449,6 +2476,7 @@
         $cnt++;
      }
      %KeyIndex = ();
+    %KeyIndexArray = ();
      %KeyIndexLast = ();
      util::fclose($fh_wi);

臼田幸生