Grep処理を並列処理して高速化する

[7-rate]

要望機能

Grepが遅いです。
これを高速化したいです。

※
#467 に関連しています。

具体的な現象

スクリーンショットの設定にて
"grep"と"hogehogehoge"でベンチマークをとってみました。私の環境では以下のような結果になりました。

単語	時間
grep	平均1010ms
hogehogehoge	平均860ms

ちなみに秀丸エディタだとほぼ一瞬で終わります。

原因

CGrepAgentにてGrep処理を行っているが、シングルスレッドで処理しているため。

対策

#467 にあるように処理を並列化することで最近のマルチコアCPUの場合はコア数に比例して高速化できます。

スクリーンショット

設定

[7-rate]

というissueを立てさせていただきましたが、並列化はあまり経験がなくてパッと実装できそうにはないです。何かヒントとなるような実装やライブラリ、キーワード等募集します。

また、現状の実装だと
①カレントディレクトリ(最初はベースディレクトリ)にあるファイルをgrep。をファイル分繰り返す
②①が終わったらサブディレクトリに潜って①へ
という感じに再帰的に処理しています。

これを、以下のように直していこうと考えています。
①探索すべきファイル(サブディレクトリも含む)を内部リストに保持する
②スレッドを起こし、①で出したリストを分割して各スレッドに渡す
③各スレッドはリストにあるファイルをgrep

[berryzplus]

仕組み的なモノは #714(非同期カウントを実装してみた) が参考になるかな？と思います。
検索一致数を非同期でカウントさせる仕組みを試験的に実装してみたものなので、
スレッドを起こす、スレッドの処理結果をウインドウに表示する、の大枠が含まれています。

これを、以下のように直していこうと考えています。
①探索すべきファイル(サブディレクトリも含む)を内部リストに保持する
②スレッドを起こし、①で出したリストを分割して各スレッドに渡す
③各スレッドはリストにあるファイルをgrep

論理コア数を上限とするスレッドプールを作って、使いまわす感じかな？と思いました。

おそらく、目下最大の課題はこんな感じの非同期処理（？）をどう扱うかだと思ってます。

			/* 処理中のユーザー操作を可能にする */
			if( !::BlockingHook( pcDlgCancel->GetHwnd() ) ){
				goto cancel_return;
			}
			/* 中断ボタン押下チェック */
			if( pcDlgCancel->IsCanceled() ){
				goto cancel_return;
			}

ある程度 Windows プログラムを見たことがあるなら、BlockingHookのコードは衝撃的な内容だと思います。（こんなウラ技があったのか、的な意味で衝撃を覚えた気がします。）

イベント駆動プログラムの流儀に従って、呼ぶ側と呼ばれる側の立場を適宜考えながら構築していくのがWindowsのプログラムですが、強制的に呼ぶ側の論理のみで組めるように工夫したのがBlockingHook なんだと思います。素直にすごい発想だと思うんですが、王道的なスレッド方式に切り替えようとしたときに、弊害を生みそうな不安要素にもなっています。

スレッド化にあたっては、 CLSID_ProgressDialog を使って進捗ダイアログ部分を組み替えることを考えていました。

あと、たぶんサクラエディタの文字コード判定は遅いので、icu4cの文字コード判別ルーチンを使う方法を選択できるように提案しようかどうか迷っています。（どっちやねん！

インターネット配布のアプリにおいて、ファイルサイズが大きいことは「悪」だと思っていますが、icu4cのライブラリサイズはめちゃめちゃ大きいのです・・・。

まとまりなくてすんません。

[7-rate]

ありがとうございます。大分ゆっくりになると思いますが作っていきます。

[beru]

高速に grep を行ってくれるソフトに ripgrep というのがあります。

https://github.com/BurntSushi/ripgrep/releases/download/11.0.1/ripgrep-11.0.1-i686-pc-windows-msvc.zip

で試してみたところ検索自体は 0.1 秒以下で完了しているようです。

こんな風にして確認しました。

D:\projects\sakura>rg --stats grep >> grep_result.txt
D:\projects\sakura>rg --stats hogehogehoge >> grep_result.txt

出力された統計情報は以下のようになってました。

95 matches
88 matched lines
47 files contained matches
2571 files searched
11555 bytes printed
17620332 bytes searched
0.072761 seconds spent searching
0.189836 seconds

0 matches
0 matched lines
0 files contained matches
2571 files searched
0 bytes printed
17620332 bytes searched
0.073768 seconds spent searching
0.196431 seconds

サクラエディタの grep 処理の速度を上げる事の価値は高いと思いますが、待つのが嫌な場合は既存のソフトを使うのも選択肢として良いと思います。

[beru]

@berryzplus さん

あと、たぶんサクラエディタの文字コード判定は遅いので、icu4cの文字コード判別ルーチンを使う方法を選択できるように提案しようかどうか迷っています。（どっちやねん！

インターネット配布のアプリにおいて、ファイルサイズが大きいことは「悪」だと思っていますが、icu4cのライブラリサイズはめちゃめちゃ大きいのです・・・。

個人的には Optional であれば問題ないと思います。

ICUのファイルをサクラエディタのインストーラーに含めるのはファイルサイズ的に少し抵抗感が有ります。

今確認してみると、
https://github.com/unicode-org/icu/releases/download/release-64-2/icu4c-64_2-Win64-MSVC2017.zip

が 20.8 MB ぐらいなので。

設定画面で ICU4C の DLL ファイルがあるフォルダのパスを指定出来るようにして、文字コード判定を自前のでやるか ICU を使って行うかを選択出来るようにすると良いと思います。

[7-rate]

ripgrepいいですね。
これそのままサクラエディタに組み込んでもよさそうな気がしてきました。

[7-rate]

この件ですが、私の技量では少々厳しそうです。
少しでも期待されていた方には申し訳ないですが、issueとしてはこのまま残させて頂きますのでどなたかにご期待くださいm(__)m