A7Mの日記： 与太話：マルチスレッドでgrepを実行ってどうよ？

せっかくのマルチコアな時代なのだから、大量のテキストファイルに対してgrepを使って検索する場合、メインのループでファイルのワイルドカード検索を行い、マッチしたファイルに対して片っ端から1スレッドを割り当てて同時並行で検索をかけたらどうなるんだろ。
何となく、ハードディスクのアクセスがボトルネックになりそうな気がしないでもないし、スレッドのマネージメントが面倒そうだから、やっぱりシンプルな方がいいかもしれない。
試してみる価値はありそうだけど。

キャッシュに載っている分に関しては速かろう

[okky (2487)]

mkdir /tmp/resultstore
for i in ./some/where/over/the/*; do
    grep 'yellow brick road' $i > /tmp/resultstore/${i}.result &
done
for i in ./some/where/over/the/*; do
    sed "s/^/${i}: /" /tmp/resultstore/${i}.result
done > finalresult
rm -f /tmp/resultstore

こんな感じ?

マルチコアではなく、複数のマシンがあって、Andrew File System (AFS)のようにキャッシュとして「ディスク」まで使うよう、なおかつどのマシンから見ても絶対パスが同じになるようなネットワークファイルシステムを使っている場合、ssh でばらばらに grep させて、最後にかき集める、というのは、対象が膨大な場合、本当にやります。

でも、上記のようなスクリプトは使いません。上記のような動かし方をすると、CPUコアが全部 grep 作業に持っていかれてしまって、処理が終わるまでの間、Spider が動かなくなってしまうからです :p

--
fjの教祖様

Re:キャッシュに載っている分に関しては速かろう

[A7M (259)]

こんな感じ?

やりたいことはそんな感じです。
grepというのは比喩で、自前でテキストファイルをboost::regexに食わせてマッチングさせるのが目的です。

でも、上記のようなスクリプトは使いません。上記のような動かし方をすると、CPUコアが全部 grep 作業に持っていかれてしまって、処理が終わるまでの間、Spider が動かなくなってしまうからです :p

確かに。:-)
僕の場合、SpiderではなくFirefoxですが。（ぉぃ

Re:キャッシュに載っている分に関しては速かろう

[Deasuke (34806)]

find . -type f -exec sh -c 'grep abc {} &' \;
で駄目かなぁ。

--
Best regards, でぃーすけ

Re:キャッシュに載っている分に関しては速かろう

[okky (2487)]

多分 GNU grep の -H オプションをつけて、あとでソートしないと、『分散しないで実行した場合』と同じ結果にはできないかと。

もちろん、出力の順序性(同一ファイルのマッチ結果が連続する)とか、非分散 grep の場合との互換性なんかいらないとか、そういう条件の場合は気にしなくてよいのでしょうが。

あと、私のほうにもある間違いですが、「最後に wait をかけて全部の子プロセスが終わるのを待つ」必要がある。でないと、出力が完了していない結果を見ることになってしまいかねない。ところが、find の子プロセスとして sh を動かし、その子プロセスとして grep を動かしなおかつ非同期にすると、find を起動した shell プロセスから、すべての grep の終了を待つ事ができるのか?という問題が出るかと思います。

多分、この辺じゃないでしょうか。実際に利用しようとすると問題になるのは。

--
fjの教祖様

えーっと

[visha (779)]

結果の表示はどうするんでしょ。ごちゃまぜ?

あと、すごいどっちゃりPOSIXスレッド起こすと、それだけでかなりでかい負荷になるし、資源を使い切ってあぼーんしそうな気がします。ちゃんとやるなら、

• ワイルドカードの展開結果をキューに登録
• 検索用スレッドはコマンドラインオプションか何かで決めた数だけ起こす
• 検索用スレッドはキューからファイルパス取って来て検索開始
• 検索が終わったら再びキューからファイルパスをフェッチし、空だったらスレッド終了
• 全ての検索スレッドが終わったらメインスレッドも終了

ってなのがよさげ。検索結果はメインスレッドに全部渡しといてメインスレッドがまとめて出力するくらいしか、ファイル間で出力が混ざらない方法はないと思う。

;; などと、釣られてみました。

Re:えーっと

[A7M (259)]

ロジックはそのものズバリです。:-)
Windowsで動作するGUIフロントエンド付きのgrepを考えていて、結果はスレッドからバッファへ片っ端から突っ込んで、最後にソートしてから、ListViewに表示したり、テキストファイルに保存することを考えています。
バッファの持ち方も、共通のバッファを一つだけ用意し適宜突っ込んでいくか、バッファをスレッドことに用意しスレッドが終了したら、それをまとめて共通のバッファにいれるとか、いくつかやり方があると思います。
バッファのロック・アンロックとか、スレッドの管理とかは最低限必要なので、たかがGUI付きgrepでそこまでやる必要があるのか微妙なところです。(^^;

馬鹿正直に一つ一つ検索するタイプは作ったのですが、メインの部分をスレッドにしたときに、その先の検索の部分も別スレッドに出来るのではないかというのを思いついた次第です。
富豪的プログラミングっぽく、マッチしたら使い捨てのスレッドを即時生成ってのも、どのような惨劇を生み出すか興味があったりします。

単に

[L.Entis (21733)]

（ファイルの読み込み時間）≧（grep時間）

がほぼ成り立つならば、ファイルからの読み込みを非同期読み込み関数を利用するか、あるいは読み込み専用スレッドにすればよろしいのでは？
（つまり、grep処理をしている間、バックグラウンドで次のファイルを読み込む）

もしファイルごとに両者にかかる時間の関係がばらつくならば、ある程度吸収できるだけの数、ファイルを先読みするようにしてあげれば良いだけで、パフォーマンスの上でスレッドは最大でも２つ以上は必要ないのでは？
（あくまで、ファイルの読み込み時間が、grep処理の時間と大差ない範囲という前提であるならば。というより、grep処理ならば、仮にファイルがメモリ上にあったとしてもそれほど大差ないといえるとは思いますが）

Re:単に

[A7M (259)]

なるほど・・・
対象はあくまでもテキストファイルが前提で、文字コード判別をしていますの、でどっちみちキャッシュは必要です。
ファイルの読み込みとgrep処理を別スレッドにするのはありかもしれません。

ここまでアドバイスをもらうと、ちゃんとしたものを公開しないとまずいような・・・。（ぉぃ