BugTrack/2171 の編集

* do_search()の効率化 [#l53ddc40]

- ページ: [[BugTrack2]]
- 投稿者: [[Cue]]
- 優先順位: 低
- 状態: 完了
- カテゴリー: その他
- 投稿日: 2006-04-14 (金) 13:58:15
- バージョン:

** メッセージ [#see2d2ff]
"PukiWiki/1.4/ちょっと便利に/do_search()の改造実験" (削除済み)から移動。

** do_search()の改造実験 by [[Cue]] [#s8e783f7]
検索文字列の含まれるページをリストアップする関数ですが、割と重い処理のようなので軽くできないか考えてみます。

** 期待する効果 [#y3371182]
1.4.6の配布ファイルで呼び出している以下の2箇所の処理が軽減されます。
- searchプラグインの単語検索
- Autolink対象となるページが新設された場合に、そのページに対してAutolinkする可能性のあるページをリストアップする時

** 改造点 [#oaf054bd]
+ pregの呼出し回数が多いのでパターンをstudyさせてみる。（効果大((普通はそれほど効果は出ないですが今回は効きます))）
+ キーワードを含むか否かの判定にpreg_grep()を使っているが、キーワードを含む全ての行を抽出する必要は無いのでpreg_match()に置き換える。（効果中）
+ ↑の結果、ページ内容を配列で取得しなくても良いのでfread()を使って一括読み込みする((func.php内部でファイル読み込みするという構成上の問題はありますが))。（効果大）
+ ファイル内容を読んだ場合にはfstat()で取得した時刻情報を流用する。（効果微妙((stat()とfstat()の速度差が大きい環境ではそこそこ効果的かも？))）
+ links_update()から呼ばれる場合(($non_formatが真の時はlinks_update()からの呼出しと想定して変更したので自作プラグインの中に影響を受けるものがあるかもしれません))、キーワードの完全一致で良いのでget_search_words()の呼出しを抑制する。（効果大((preg_match()の速度アップとリストアップの確実性が増す（=links_get_objects()を通すページ数が減る）ためですが、もう一歩踏み込むには他の方も指摘していますが2回ファイルを読まないように変えた方が良いのでしょう))）

** パッチ [#d26d1df8]
1.4.6（func.php,v 1.46）からの差分
 --- lib/func.php	Mon Jul 04 00:09:28 2005
 +++ lib/func.new.php	Thu Mar 30 21:42:50 2006
 @@ -190,32 +190,37 @@
  	$retval = array();
  
  	$b_type = ($type == 'AND'); // AND:TRUE OR:FALSE
 -	$keys = get_search_words(preg_split('/\s+/', $word, -1, PREG_SPLIT_NO_EMPTY));
 +	$keys = $non_format ? array(preg_quote($word, '/')) :
 +		get_search_words(preg_split('/\s+/', $word, -1, PREG_SPLIT_NO_EMPTY));
 +	$keys = preg_replace('/^.*$/', '/$0/S', $keys);
  
  	$_pages = get_existpages();
  	$pages = array();
  
  	$non_list_pattern = '/' . $non_list . '/';
 -	foreach ($_pages as $page) {
 +	foreach ($_pages as $file=>$page) {
  		if ($page == $whatsnew || (! $search_non_list && preg_match($non_list_pattern, $page)))
  			continue;
  
 +		$source = $non_format ? '' : $page . "\n";
  		// 検索対象ページの制限をかけるかどうか (ページ名は制限外)
  		if ($search_auth && ! check_readable($page, false, false)) {
 -			$source = get_source(); // Empty
 +			$stat = NULL;
  		} else {
 -			$source = get_source($page);
 +			if (($fp = fopen(DATA_DIR . $file, 'rb')) === FALSE)
 +				continue;	//	ページが消えている？
 +			flock($fp, LOCK_SH);
 +			$stat = fstat($fp);
 +			$source .= fread($fp, $stat['size']);
 +			fclose($fp);
  		}
 -		if (! $non_format)
 -			array_unshift($source, $page); // ページ名も検索対象に
  
 -		$b_match = FALSE;
  		foreach ($keys as $key) {
 -			$tmp     = preg_grep('/' . $key . '/', $source);
 -			$b_match = ! empty($tmp);
 +			$b_match = preg_match($key, $source);
  			if ($b_match xor $b_type) break;
  		}
 -		if ($b_match) $pages[$page] = get_filetime($page);
 +		if ($b_match) $pages[$page] = isset($stat) ?
 +			$stat['mtime'] - LOCALZONE : get_filetime($page);
  	}
  	if ($non_format) return array_keys($pages);

--------

** コメント [#d905ba4f]
- 違うところからアプローチしていたのですが、改造点2について、同じ結論にたどり着きましたので後ほどコミットしようとおもいます。ちなみに、コミットする際にBugTrackの方がよさそうなので、本件、BugTrackに移行します。 -- [[teanan]] &new{2006-04-14 (金) 13:51:29};
- 移行してコミットしました。-- [[teanan]] &new{2006-04-14 (金) 14:26:17};
-- [[cvs:lib/func.php]] (1.55)
-- [[cvs:lib/html.php]] (1.55)
-- 'preg_grep' => 'preg_match'へ修正(改善点2)
-- get_search_words()でアルファベットの大文字/小文字の考慮を外しました。
その代わり、preg_matchにおいて、大文字/小文字を区別しないようにしています。
- 改善点3(freadで一括読み出し)の件、実装しました。get_source() を拡張して配列ではない通常の文字列として返せるようにしましたので、他の同様な部分についても対応できます。 -- [[teanan]] &new{2006-04-15 (土) 03:41:08};
-- [[cvs:lib/file.php]] (1.61)
-- [[cvs:lib/func.php]] (1.56)
- 私は約2000ページのテスト環境ですが、ここまでの対応で大きな効果が出ています。 -- [[teanan]] &new{2006-04-15 (土) 04:29:28};
- 本来あるべき実装かどうかを確認し追究する、という良いサイクルが回っている気がします :) さてマルチバイト文字列に対する正規表現周りじゃないかと思うのですが、一つ例外を見つけました。(対象は数日前のdevサイトのバックアップデータ)。観察中 -- [[henoheno]] &new{2006-04-15 (土) 08:32:36};

|Search words|func.php| Hits/2020 | Time |h
|            |        |RIGHT:|RIGHT:|c
| "BugTrack" | r1.54 | 1428pages | 20.4sec |
|~|            r1.57 |~|            6.2sec |
| "開発日記" | r1.54 |  618pages |  3.9sec |
|~|            r1.57 |~|            2.0sec |
| "Web委員"  | r1.54 |   52pages |  4.1sec |
|~|            r1.57 | &color(red){51pages};|&color(red){10.2sec};|
| "b委"      | r1.54 |   52pages |  5.8sec |
|~|            r1.57 | &color(red){51pages};|&color(red){11.7sec};|
| "b"        | r1.54 | 1845pages | 18.3sec |
|~|            r1.57 |~|            3.3sec |
| "委"       | r1.54 |   58pages |  3.6sec |
|~|            r1.57 |~|            1.8sec |

- おはようございます。検証ありがとうございます。get_search_wordsの修正がマズかったのかもしれませんね・・・ (^^; -- [[teanan]] &new{2006-04-15 (土) 08:54:03};
-- %%get_search_words() に対する修正だけを含んでいる func.php を r1.54 に戻すだけで直る様ですので、そうかもしれません%% (単純に r1.54にして戻るのは)get_search_words() だけじゃなかった・・・-- [[henoheno]] &new{2006-04-15 (土) 09:20:58};
- 他に気になっている部分・・・(観察中) -- [[henoheno]] &new{2006-04-15 (土) 08:53:59};
-- get_source(): それぞれの挙動のポイントをコメントにしたいところ (追加し%%ておきます%% ました)
-- get_source(): $join 時に str_replace("\r", '') していないのは恐らくコールする側の想定外。これをキャンセルさせたいなら別途引数追加を要するやも(順番は多分$joinの手前)。 -> 追加しておきました。特に処理速度に影響がある様にも見えません
-- do_search(): ページ名だけで検索条件が成立するならば、ページの中を読む必要はない(このシチュエーションはOR条件の時や、検索単語が一つだけの時や、ありふれた極端に短い文字や、例えばここだと"BugTrack"の様に、ページ名として良く使われている検索キーワードで顕著に発生する)。また、現在は巨大な文字列の連結をしている。ただしこれらは、preg_match() を多く呼ぶ事につながるので実験を要する。
-- [[cvs:func.php]] (r1.55) のコメントログの指摘「'get_search_words' doesn't consider upper and lower cases of the alphabet.」は正しくありません。従来から foreach (array(strtoupper($char), strtolower($char)) の部分で大文字小文字を「確実に両方扱って」います。 そしてr.155 の修正は大文字小文字を文字単位では見なくなっていますから、「全角の」アルファベットを確実にケアしない状態になっている様です(例えば小文字のアルファベットが入力されたとき、全角小文字のための正規表現は作るが全角大文字のための正規表現は作らない) -- [[henoheno]] &new{2006-04-15 (土) 10:09:54};
--- mb_convert_kana('A') の部分ですね -- [[henoheno]] &new{2006-04-15 (土) 10:12:15};
--- あ、foreachがなくなっているので、entity reference のための正規表現(アスキーコード) についても同様で。 -- [[henoheno]] &new{2006-04-15 (土) 10:15:22};
- get_search_words() についてはbackoutするのがいいかもしれません -- [[henoheno]] &new{2006-04-15 (土) 10:16:46};
-- なるほど、ご指摘のとおりです。元に戻します。ありがとうございました。 -- [[teanan]] &new{2006-04-15 (土) 10:35:40};
-- [[cvs:lib/func.php]] (1.58)
-- [[cvs:lib/html.php]] (1.56)
-- 正規表現を長くするよりも、preg_matchで大小区別しない方が早いので効果が出たと思っていたのですが、比較条件が変わっていたとは検証不足でした・・・。((ちなみに、('A') が顔文字に見えてしまったのは動揺しているからでしょうか (^^; )) -- [[teanan]] &new{2006-04-15 (土) 11:55:37};
- 言われてみれば顔文字に見えますね (^^; これで「Web委員」で検索した時にヒットするページ数が従来通りになった様です。ただし12sec(少なくとも従来より改善はしていない)。何が良く無いのだろう? (予想: 正規表現末尾のオプション) -- [[henoheno]] &new{2006-04-15 (土) 12:20:23};
-- back out した時は、コミットログにどのリビジョンに対するback out なのかとか、なぜback outしたのか触れていただけると助かります(cvsリポジトリ単独で追跡できる様に) -- [[henoheno]] &new{2006-04-15 (土) 12:23:36};
-- 了解です。コミットログを修正しました。正規表現のオプションで"S"をつけると早くなりますね((改造点1))。もう少し調査中。 -- [[teanan]] &new{2006-04-15 (土) 17:31:14};
-- back out する修正は直前のものとは限りませんから、back out したリビジョンを具体的にログに書くのがお勧めです(コミットログを少々修正しました)。to r1.54 と書くと、そこから先の全ての修正を却下したかのようにも読めてしまいます。コミットログを簡潔に書ける様にするためには、もちろん前提として「個々の修正をなるべく論理的に分けてコミットしている」習慣付けが必要です。今回、問題の修正のリビジョン番号が、複数のファイルでたまたま同じなんですね。珍しいです -- [[henoheno]] &new{2006-04-15 (土) 17:42:10};
-- すみません、なかなか難しいです (^^; お手数をおかけしました。 -- [[teanan]] &new{2006-04-15 (土) 18:01:13};

- どの件もそうですが、日常生活に支障が出ない程度に、休み休み進めましょう。一つ一つがきちんとして行くのであれば、何日かかってもいいです (区切りがついたタイミングごとにリリースするだけです)。((と、ついさっきまで昼寝していた私が言う)) -- [[henoheno]] &new{2006-04-15 (土) 17:08:35};
-- お気遣いありがとうございます。やれる範囲でやらせて頂いておりますのでご安心を :) ((実は私も寝てました(笑) )) -- [[teanan]] &new{2006-04-15 (土) 17:33:16};
- 現在の状況は以下の通り。do_search() の中にある get_search_words() が返す正規表現はどちらでも同じであるため、これ("b委"周辺)は do_search() 内部の処理の差ではないかと思われます -- [[henoheno]] &new{2006-04-16 (日) 00:36:31};
|Search words|func.php| Hits/2020 | Time |h
|            |        |RIGHT:|RIGHT:|c
| "BugTrack" | r1.54 | 1428pages | 20.4sec |
|~|            r1.58 |~|            7.5sec |
| "開発日記" | r1.54 |  618pages |  3.9sec |
|~|            r1.58 |~|            2.1sec |
| "Web委員"  | r1.54 |   52pages |  4.1sec |
|~|            r1.58 |~|&color(red){13.0sec};|
| "b委"      | r1.54 |   52pages |  5.8sec |
|~|            r1.58 |~|&color(red){14.8sec};|
| "b"        | r1.54 | 1845pages | 18.3sec |
|~|            r1.58 |~|            3.7sec |
| "委"       | r1.54 |   58pages |  3.6sec |
|~|            r1.58 |~|            1.9sec |

- PCRE装飾子 S または i を付けるかどうかによって速度が変わります。PCREの内部的にどのようなことをやっているのか興味があるところですが、とりあえず、手元の環境で一番効果がありそうな "S" をつけたバージョンをコミットしました。 -- [[teanan]] &new{2006-04-16 (日) 03:08:53};
-- [[cvs:lib/func.php]] (1.59)
-- [[cvs:lib/html.php]] (1.57)
   http://jp.php.net/manual/ja/reference.pcre.pattern.modifiers.php
   パターン修飾子
   S
    あるパターンを複数回使用する場合は、マッチングにかかる時間を
    高速化することを目的として、パターンの分析に幾分か時間をかけても
    良いでしょう。この修飾子を設定すると、追加のパターン分析が
    行われます。現在、パターン分析は、最初の文字が単一ではなく、
    かつ固定でないパターンに対してのみ有用です。 
-- そう、マニュアルには具体的に何をやっているか書かれていないんです・・・ -- [[teanan]] &new{2006-04-16 (日) 10:02:24};

- 次に、一致したページ名を記録する部分で、$non_formatがtrueの場合にfiletimeを呼ばないように修正しました(こちらは検索の速度には関係しません)。 -- [[teanan]] &new{2006-04-16 (日) 03:13:49};
-- [[cvs:lib/func.php]] (1.60)
- 今回の修正の中で、ページ名とページ本文を収めた変数が直接連結される形になっていますが、その(文字連結等のコスト以外の)副作用として、例えば「456」というページの本文が「789」だった時、「456789」という単語検索にひっかかる様になっています。この意図しない状況を回避するのであれば、少なくとも %%半角スペース%% 改行コード1つなどを間に追加しておくと良いと思われます。 -- [[henoheno]] &new{2006-04-16 (日) 08:43:00};
-- ご指摘ありがとうございます。確かにそのとおりです (^^; -- [[teanan]] &new{2006-04-16 (日) 10:00:55};
--- [[cvs:lib/func.php]] (1.61)
-- r1.61で、今までのコンセプトに沿った本来の実装になったわけですが、余計なファイル処理をキャンセルする修正の都合、ページ名を別途先にチェックする形に改めさせていただきました。 -- [[henoheno]] &new{2006-04-16 (日) 20:02:31};

- 現状は以下の通り。 "S" オプションは他の要所でも使えそうですね。 -- [[henoheno]] &new{2006-04-16 (日) 19:10:20};
|Search words|func.php| Hits/2020 | Time |h
|            |        |RIGHT:|RIGHT:|c
| "BugTrack" | r1.54 | 1428pages |20.3sec |
|~|            r1.61 |~|           2.6sec |
|~|            r1.64 |~|           1.9sec |
|~|            r1.67 |~|           1.9sec |
| "開発日記" | r1.54 |  618pages |  3.9sec |
|~|            r1.61 |~|           2.1sec |
|~|            r1.64 |~|           1.8sec |
|~|            r1.67 |~|           1.8sec |
| "Web委員"  | r1.54 |   52pages | 4.1sec |
|~|            r1.61 |~|           2.2sec|
|~|            r1.64 |~|           2.1sec|
|~|            r1.67 |~|           2.2sec|
| "b委"      | r1.54 |   52pages | 5.8sec |
|~|            r1.61 |~|           2.1sec|
|~|            r1.64 |~|           2.1sec|
|~|            r1.67 |~|           2.2sec |
| "b"        | r1.54 | 1845pages | 18.1sec|
|~|            r1.61 |~|           2.7sec |
|~|            r1.64 |~|           1.9sec |
|~|            r1.67 |~|           1.9sec |
| "委"       | r1.54 |   58pages | 3.6sec |
|~|            r1.61 |~|           1.9sec |
|~|            r1.64 |~|           1.8sec |
|~|            r1.67 |~|           1.9sec |
- $search_non_list, $search_auth の除外処理を事前に行っておいたり、get_existpages() が返す値を軽くするか別の手段で最小限のデータを得るようにするともう少し軽くなるでしょう。 -- [[henoheno]] &new{2006-04-16 (日) 20:00:20};
- tracker_listとかにSオプションつけると効果がありそうですね :) -- [[teanan]] &new{2006-04-16 (日) 21:12:42};
- というわけで、他のこまごました修正と、ピーク時に大変になるだろう要求メモリの無駄を省いて [[cvs:lib/func.php]] (r1.67) まで持って来ました。これ以上やると 上で上げている別関数の拡張や見直しの話になりそう(=深みにはまりそう)ですから、上で盛り上がった話はひとまずここまででしょうか。他に採用できる部分があればコメントお願いします -- [[henoheno]] &new{2006-04-16 (日) 23:10:54};
- おっと、検索結果が $show_passage の設定を無視している事に気付いたので、対応させました。get_filetime() を一切発行しなくなるので、これは結構(0.1～0.2sec)効果が大きいです(ここの検索結果だと5秒短縮される・・・)。 [[cvs:lib/func.php]] (r1.68) 今やらないけど、検索wordの処理も削れる気がする・・・(新たに設定を追加して、検索/表示に関する一切のwordの処理を無効化する路線の話) -- [[henoheno]] &new{2006-04-16 (日) 23:32:33};
- 確認しました、お疲れ様です。私もこの辺で一段落付いたとおもいますので、一度「完了」にしておきます。他に効果がありそうなものが確認できたら、また蒸し返しましょう :) -- [[teanan]] &new{2006-04-17 (月) 01:00:34};
- ざっと見ただけですが、蒸し返し用に[[改造点>#oaf054bd]]と現況との比較の確認をさせて下さい。1～3については取込済。4については未取込だが、別方面の($show_passageを見る)対応済。5については未取込。って事で良いでしょうか。 -- [[にぶんのに]] &new{2006-04-17 (月) 04:02:43};
-- はい、私も同じ認識です。 -- [[teanan]] &new{2006-04-17 (月) 09:35:18};
-- にぶんのにさん、チェックありがとうございます。Cueさんの名前が今回多分cvsリポジトリに無い件、結果的に採用されたものが単独でコミットできているのであれば、できれば状況に応じて Pointed out by とか Patched by といった形で貢献を付記しておいて下さい。[[cvs:lib/file.php]] (1.61) 等。貢献者の((Changelogを見てニヤリと笑う))ためでもありますし、我々が後で修正点をまとめたり、Special Thanksの候補をピックアップする際の手助けにもなります。 -- [[henoheno]] &new{2006-04-19 (水) 00:03:39};
- searchプラグインで検索対象のページを指定した場合、正しく検索できなくなっていましたので修正しました。[[cvs:lib/func.php]] (1.73) -- [[teanan]] &new{2006-05-16 (火) 01:43:47};
- [[BugTrack2/330]] --  &new{2010-08-17 (火) 22:05:08};

#comment

** 取り込まれたコードを見て [#d943037f]
取り込み作業お疲れ様でした。遅まきながら感想など。

*** fstat()とstat()の速度差に関する補足説明 [#i2558509]
４番目の改造点を効果微妙と評しましたが、これは''多数のページにヒットするような検索はあまりないだろう''という前提に立っています。~
私[[Cue]]が書き込んだパッチの当該部分を見てもらうと$b_match=trueの場合だけページの更新時刻を調べる構造になっていますので、この前提に立てばそもそもget_filetime()の呼び出しはそれほど発生していない事になります。逆に言うと多量のページがヒットする検索ではfstat()とstat()の速度差は無視できないものとなります。

*** どの程度無視できないのか？ [#wd8e417c]
速度の計測は裏で何が動いているか把握できる隔絶された環境で厳密に比較すべきですが追試可能であることも重要でしょう。おあつらえ向き（？）に1.4.7のコードでは検索ヒットしたページのpassage取得のみ別ループでの処理((passage取得前にclearstatcache()しているのとほぼ等価))に変えられているので、この点を利用してstat()系の処理の重さを見積もることができたりします((あくまで参考程度ですが、コードに手をつけず自分のサイトで試すにはお手軽かと))。~
下の結果は''`''と''*''を使ってPlus!の公式サイトで検索したときのものです（勝手に実験に使って済みません＞plusの方々((動作しているコードが(ほぼ)把握できて、ページ数がそこそこあるサイトは他に思い当たらなかったのです))）。

|検索文字|convert time|hitしたページ数|h
|`|0.21sec程度|7|
|*|0.30sec程度|689|

多数のページにヒットする検索があまりないなら構う事もないのですが、実は同様の全ページに渡るstat()取得がget_source()呼び出しに隠されています（is_page()（の中のfile_exists()）とfilesize()((余談ですがflock()とfilesize()の間にclearstatcche()は不要？？))）。軽量化ネタなわけですし、このあたりもう少し配慮できたんじゃないの？と感じてしまいます。

*** links_update()からの呼び出し [#hf0b2cd4]
link.phpには踏み込みたくなかったので5番目の改造点で留めておいたのですが、もしteananさんがlink.php側からココに到達したとなると話は違ってきます（どこからとは書いてないですけど）。link.phpの各処理で最も重い部分はInlineConverterの呼び出しと考える方が自然でしょう。もしこの処理を軽くしようとするならばむしろpreg_grep()を使ってInlineConverterに渡す行数を絞るコードを別に用意する方が正しいと思います。((ついでながら、私は手をつける気がありませんのでlink.phpの他の変な点もメモしておきます。&br;a)links_init()では影響されないのにlinks_update()では$search_authの影響がある事&br;b)ページ削除時にlinks_delete()が呼ばれる事（関数名はそれっぽいけど？）&br;c)複数行プラグインの書式に対応していない事&br;d)ページ編集でAutolink←→BracketNameにリンク種別が変わった場合追随できない事&br;あと１つあった気がしますが失念しました。))

タイムスタンプを変更しない