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はここから。grepはcoreutilsとは別で存在します。
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)を使っている。そのうち変更くるかな。
