longicornの日記

2012-01-24

[] GNU catとかGNU grepを読んでみた

最近少し理由があって、GNU catとGNU grepのソースを読んだので少しメモ


ソースコード入手

GNU catですが、catのような基本コマンドはcoreutilsというパッケージになっていますのでこれをダウンロードします。

http://www.gnu.org/software/coreutils/

gitはこちら

git clone git://git.sv.gnu.org/coreutils


GNU grepはここから。grepcoreutilsとは別で存在します。

http://www.gnu.org/software/grep/

gitはこちら

git clone git://git.savannah.gnu.org/grep.git


今回はgit版を使いました。両方共gnulibというsubmoduleがあるので注意。

最近はgit必須になってるなぁ。便利だけどコマンド体系がややこしい...



理由

先にソースコードリーディングをした理由なんですが、コマンドの処理速度がかなり処理が早いことに気がつきました。

Rubyとかで適当に1行1行読み込んで出力しても遅い。Cで同じように書いてもダメ。grepどころか、catでも同じ結果でなんだろうと思って読みました。

結果は当たり前といえば当たり前の内容でした。


GNU cat

coreutils/src/cat.cが本体です。

src/以下には他のコマンドもあるので必見。

読み込み処理関数は2つの関数があります。simple_cat()とcat()。オプションによって動く関数が違います。

そして実際に読み込み処理は結局gnulibのsafe_read()を使っている。safe_read()はsafe_rw()のdefine名になっており、最終的にread()が呼ばれる。

ということは、細かい部分を除けば、open()してread()を繰り返すだけのプログラムと同じ。


他に工夫しているのは、malloc()のサイズ。最大ブロックサイズ分のメモリを一気に取得している。

ブロックサイズは"struct stat"の"st_blksize"を見ているようだ。

ちなみに、少し古いとgetpagesize(2)というシステムコールを使っていたのですが、これ現在は使ってはいけない古い関数なので使わなくなった酔うです。

代わりに"sysconf(_SC_PAGESIZE)"使えとあるのに、使っていないのは何故だ???


いきなり結論

結局、何が問題だったのかと言えば、プログラムの都合で行処理をしていたのがまずかったというだけ。プログラムの都合でこうしていたのですがそれがまずかった。

何が行の単位を決めているかと言えば当たり前だけど改行。そして、バッファから改行を見つける処理が重かっただけのはなし。

Rubyで書いて遅いのは"f.read_line"とかしていたから。Rubyでも"f.read(1024)"とかで処理したらほとんど変わらなかった。

当たり前と言えば当たり前の理由。


GNU grep

せっかくなのでこっちも。

gnulibを使っているので、read()処理は同じです。

ここで疑問なのはgrepは特定の文字列正規表現で探すのでバッファを見にいくのに、fgets(3)を使うよりもかなり早いこと。

色々追ってみたらどうも、DFAをきちんと使っているらしく、またマッチしなかったらlseek(2)使って読み飛ばしをしている。

つまり、fgets(3)のような処理では(Rubyとかの行処理でも同じだけど)、全データを見にいくが、grepはlseek(2)で読み飛ばしをしていると。

そりゃあ早いな。


あ、grepではまだgetpagesize(2)を使っている。そのうち変更くるかな。



まとめ

ということでまとめと、推測。

  • バッファをブロックサイズ分容易し、この大きさで読み込みを行う。
  • できるだけデータの中身は見ない。必要でもアルゴリズムを頑張り、できる限りlseek(2)で飛ばす。
  • mmap(2)はオプションで指定されたら使用するように。デフォルトでは使わない。結構危険だしね。
  • readv(2)は使っていない。catとかだと使えば早いのに。オプションとかで処理が変わると使い物にならない可能性があるからかな?
トラックバック - http://d.hatena.ne.jp/longicorn/20120124