2020.3.29 00:11 バッファサイズと shcat の本来の意図に関して文末に追記
まとまった文章を書く機会が減ってしまって、これではいかんと久しぶりに更新。
大学院に入った 19 年前。担当していた大学院生から研究室の計算機環境の管理を引き継いだ。動機は単純で、Unix 系 OS の管理に興味があったからだった。研究室では過去の管理者が構築したメールサーバが引き継がれていて、詳しいひとはすでにいなくなっていた。Unix 系 OS はデスクトップ用途で使われておらず、学生はほぼ全員、当時現役だった管理者が Windows NT で構築したファイルサーバと数台の Windows クライアントマシンを使っていた。
Windows の環境に問題があるわけではなかったが、クライアントマシンは台数が少なく、取り合いになっていた。ネットワークも共有フォルダがあるだけで、認証やホームディレクトリの管理がなく、ユーザのデータは基本的にローカルに保存されていた。つまり、同じマシンにログインしないと継続して作業ができない。こういうものなのかな、と思いつつ、マシンが混んでいて使えない状況はどうにかならないかを考えていた。
大学の研究室には、当時でさえもう廃棄されてもおかしくなかった古いワークステーションが多数放置されていた。Windows 環境になってから、誰も興味を持たなかったのだろうと思う。管理を引き継いでから、ワークステーション上でも研究に必要なソフトウェアは使えることが分かったため、それらをデスクトップ用途で使えるようにしようと考えた。
管理を引き継いだものの、ひとつ問題があった。自分自身は MS-DOS や Windows の経験はあったけれど、そもそも Unix 系 OS の管理も、ネットワーク管理の経験もほとんどない。どういうものなのかよく分からないまま、Unix 系 OS を触ってみたいという興味だけが動機だった。すでに構築されているメールサーバを調べつつ、放置されていたワークステーションに電源を入れて OS をインストールしながらの試行錯誤。FreeBSD を本格的に使い始めたのも、この時期だ。まず自宅の Windows 環境を FreeBSD をベースにした環境に置き換えて、Unix 系の OS でメール等の日常の作業をこなすことで、いろいろと学んだ。大学の学生用計算機室にもデスクトップ環境が整備された Unix 端末があったため、その管理手法を参考にしたりもした。
そのような管理の過程で、SunOS 4 マシンと Solaris 7 マシンと HP-UX マシンと OpenBSD/sparc マシンのすべてで、同じホームディレクトリを NFS マウントする環境を管理し始めた。こういう環境では、.cshrc や .profile のような、各ユーザがログイン時に実行するシェルスクリプトを、特定の環境に依存しないように書かないといけない。管理者は条件分岐を駆使して、環境変数等が適切に設定されるように初期スクリプトを書くことが多かった。一方、これらのシェルスクリプトはユーザのホームディレクトリに置かれていて、ユーザ自身が変更できる。そのため、ユーザがカスタマイズしたことが原因でログインできなくなることも良くあった。
当時は管理の勉強をしたくて、いろいろと試行錯誤をしていた。各種デーモンを起動する rc スクリプトを書いたり、前述のようなログイン時の初期設定スクリプトを管理していると、ひとつ変更を加えるたびに、コマンドのパス名や挙動の違いといった環境の差が見えてくる。そして、なるべく移植性が高くて効率の良いシェルスクリプトはどうすれば書けるのか、という点が気になってきた。
read コマンド
Korn Shell や Bourne Shell には read という組み込み (built-in) コマンドがある。標準入力から 1 行読み込み、内容を字句解析して変数をセットする。たとえば次のようにすれば、ファイル foo の内容を表示することができる。昔は $L に -a とか入ってたらどうなるの、みたいな話を気にしなければならなかった環境もあったけれど。
cat foo | while read L; do
echo "$L"
done
そして当時、あるソフトウェアのスクリプトに次のような関数が定義されていることに気がついた。
shcat() { while read L; do echo "$L"; done; }
shcat < foo
shcat 関数は、cat(1) のような動作をする。$@ を見て、ファイル名を取れるように書かれていた亜種もあったように思う。shcat の他に、basename(1) も変数のパラメータ展開パターンを使ってシェルスクリプト関数にしたものがあった。
最初に「なぜ cat(1) を使わないのだろう」と疑問に思って、たいして違いはないだろうとすぐに忘れてしまったのだが、SunOS 4 でシェルスクリプトを書いていた時にふと思い出して書き換えてみたところ、cat(1) よりも shcat を使ったほうがはるかに高速であることが分かった。cat(1) は fork(2) に加えてディスク I/O を伴うため、どうしても一定の遅延が避けられない。ファイルが大きければ遅延は相対的に小さくなるが、cat(1) で読み込むファイルは高々数キロバイト程度である。shcat はサブシェルを起動していても、十分に速かった。「ああ、これ書いた人は高速化が目的だったのか」と一人で納得した。ちなみに、SunOS 4 マシン（もっと具体的に言えば Sun IPC）はとても遅いマシンだったので速度の違いがはっきり分かったが、Solaris 7（こっちは Ultra 5）は体感できるほどの違いはなかった。
それからしばらくは、なるべく組み込みコマンドを使ってシェルスクリプトを書くようになった。バイナリの実行は遅い。多少効率が悪そうに見えても、組み込みコマンドだけで処理できるなら、そっちのほうが効率が良いだろう。そう考えたわけだ。
本当に速いのか?
それから 10 年以上経過して、シェルスクリプトだけである程度の大きな処理をするようなシステムを組む経験もしてから、ふとこの while read ... の構文の効率が気になってきた。結構長い間、なんとなく単純に組み込みコマンドのほうが速いよね、という印象を持っていた。ここまで読んで「ああそりゃ実は遅いよ」と思い至った人は、これ以降を読んでも面白くないと思う。
シェルスクリプトで組まれたシステムは、パイプで標準入出力を接続することで、バイトストリームになっているデータを複数のプログラムで処理するというのが基本になる。1入力・1出力の単純なデータフローモデルに基づいているため見通しがよくプロトタイプの構築にはとても便利だが、パイプを流れるバイトストリームのスループットと I/O 負荷が、システムの性能に大きく影響する。パイプで接続された複数のプログラムは一般的にそれぞれ処理の速度が異なり、入出力されるデータの量も対称ではない。つまり、接続されたパイプの中でもっとも遅いプログラムによってスループットが決まってしまう。また、パイプはユーザランド・カーネル間のデータコピーを伴うため、パイプをつなげばつなぐほど、I/O 処理によるコンテキストスイッチとデータのコピー量は増加する。たとえばパイプで単純に連結された 10 個の cat(1) プログラムに 1 MiB のデータを流すと、何もしなくとも合計で 10 MiB 分のデータがコピーされるわけだ。これが 100 GiB のデータだったら、1 つ処理（=プログラム）を追加するたびに、追加で 100 GiB のデータコピーが発生することを覚悟しなければならない。
モノリシックなプログラムと比較すると、データ量の増加や処理の複雑化に対して効率の低下が著しい。各プログラムのスループットを最適化することでピーク速度は改善できる可能性があるが、莫大な量のCPU時間をデータコピーに費やす問題は本質的で、避けることが難しい。したがって単純に考えると、シェルスクリプトに速度的な利点はなさそうに見える。しかし、パイプの I/O は並列処理が可能であることと、最近のマシンはマルチプロセッサが主流であることを考慮すると、シェルスクリプトは典型的なマルチプロセスモデルで並列動作するプログラムになる。シングルスレッドで手続き的にデータ処理するように書かれた Perl や Python スクリプトよりも、シェルスクリプトのほうが高速に動作することがあるのは、この特徴に起因する。たとえ CPU 時間を莫大なデータコピーに費やしていても、少しでも並列に動作するほうが勝ってしまう。パイプで連結されたプログラムは、それぞれが独立した実行コンテキストを持つので、並列動作しながらも副作用がない関数を組み合わせるのと同じような見通しのよさがあるのは利点だ。ただし、もちろんまともに並列処理するように書かれたプログラムには、データコピーが原因で効率の面ではほぼ勝てないけれど。
話を戻そう。昔のワークステーションの経験から、while read ... は cat(1) を呼ぶより速いと思っていた。「マシンが速くなって差が見えなくなっても、新しくプロセスを作る処理は必ず入るのだから効率は良いだろう」と信じていたが、「いた」と書いたように、結論から言うとそう単純な話ではない。鍵になるのは、このスクリプトで呼ばれるシステムコールの回数である。
read の仕様
read コマンドは単体で標準入力から 1 行読むという動作をするコマンドだ。while と組み合わせて使うことが多いが、組み合わせなければいけないわけではない。標準入力から読むのだから、基本的には read(2) を呼ぶ。では、どれくらいの単位で読むのだろう?
1 MiB のファイルを作成して、トレースコマンドでシステムコールの回数を調べてみる。*BSD 環境ならこれでカウントできるはずだ。手元の FreeBSD 環境で実行した結果である。今なら DTrace を使おうと言いたいところだが、今回の用途なら truss(1) で十分だ。
% truncate -s 1m /tmp/z.txt
% truss -f sh -c 'cat /tmp/z.txt > /dev/null' 2>&1 | grep read | wc -l
267
Linux は環境によって truncate(1) がなかったり、truss(1) の代わりに strace(1) があるかも知れない。これは CentOS の環境で実行してみた結果である。
% dd if=/dev/zero of=/tmp/z.txt count=1 bs=1024x1024
% strace -f sh -c 'cat /tmp/z.txt > /dev/null' 2>&1 | grep read | wc -l
263
256 よりちょっと大きめの数値が出る場合が多いと思う。これは多くのシステムの cat(1) は read(2) システムコールを 1 ページのバッファで呼ぶことと、1 ページが 4 KiB のシステムが多いことが理由だ。1 MiB は 256 ページ分になる。そして、cat(1) の実行前には locale データ等のファイルもいくつか読むため、若干多めに出る。
じゃあ肝心の、read コマンドを使ったシェルスクリプトの結果を見てみよう。
% truss -f sh -c 'cat /tmp/z.txt | while read L; do echo "$L"; done > /dev/null' 2>&1 | grep read | wc -l
1049612
% strace -f sh -c "cat /tmp/z.txt | while read L; do echo "$L"; done > /dev/null" 2>&1 | grep read | wc -l
1048844
この数値が正しく予測できたひとは、その理由も理解していると思う。しかしシェルスクリプトに慣れていないひとの多くにとって、この結果は予想外ではないだろうか。
原因は、read コマンドの仕様にある。read は、「1行」を読まなければならない。逆に言うと、1 行を越えてデータを読むことは許されていない。Unix系OSにおける1行とは、改行文字が区切りになる。ということは「/tmp/z.txt の内容を 1 文字ずつ読み、改行文字かどうか調べる」という処理が必要になる。改行文字の先の文字を読んではいけないからだ。パイプで接続されたバイトストリームは、一度読んだら戻ることができない。もし read コマンドが改行文字を越えてデータを読んでしまったら、その次に続くコマンドが読むべきデータが失われてしまう。したがって、read(2) システムコールを 1 バイトのバッファで呼ぶ以外に、方法がないのである。
read(2) システムコールを 1 バイトのバッファで呼ぶのは、非常に無駄が大きい。1 MiB のファイルを読むのに、およそ 100 万回のシステムコールを呼ぶ。単に cat(1) だけを使った場合と実行時間を比較してみると定量的な違いが分かるが、膨大な量の CPU 時間を消費する。
このような理由から cat foo | while read ... の構文は、とても遅いのである。コマンドの仕様から考えると、これはどうしようもないように見える。
改善するには
ここまで読んで、「最初の shcat の例とコードが違うのでは」と気づいたひとがいるかも知れない。文頭では、次のような例として紹介した。
shcat() { while read L; do echo "$L"; done; }
shcat < foo
当たり前だが、こちらは cat(1) を使っていない。先ほどのベンチマークは cat(1) を使っていたので、入力をリダイレクトにしてみよう。
% truss -f sh -c 'while read L; do echo "$L"; done < /tmp/z.txt > /dev/null' 2>&1 | grep read | wc -l
1048583
% strace -f sh -c "while read L; do echo "$L"; done < /tmp/z.txt > /dev/null" 2>&1 | grep read | wc -l
8199
すると、FreeBSD はほとんど変わらないが、Linux (GNU bash) はシステムコールの回数に変化が現れる。256 回には及ばないが、かなり少なくなった。これはどうしてだろう?
実は、シェルの実装によってはシーク可能な記述子を read(2) が読む場合に限り、システムコールのバッファを増やすという最適化が入っている。前述したとおり、read 組み込みコマンドは改行文字を飛び越さないために、1 文字ずつ読む必要がある。しかし読む対象がファイルであれば、ランダムアクセスできるので読み出す位置は自由に設定できる。そのため、read(2) で大きめに読み込んでから改行文字を探し、その直後に読み出し位置を再設定すれば 1 文字ずつ read(2) を呼び出す必要はない。
最適化が可能な場合にどれくらいの単位で read(2) を呼んでいるのか、さまざまな環境で実験したところ、次のような結果になった。
Solaris 7,8,9 /bin/sh: 128 バイト
Solaris 7,8,9 /usr/bin/ksh: 1024 バイト
Solaris 7,8,9 /usr/xpg4/bin/sh: 1024 バイト
Solaris 8 bash 2.03: 1 バイト
Solaris 7,9 bash 2.05: 128 バイト
FreeBSD 12 bash 5.0.7: 128 バイト
OpenBSD 3.6 /bin/sh: 512 バイト
FreeBSD 12 zsh 5.7.1: 1 バイト
FreeBSD の /bin/sh は、実験で示されたとおり、どのような場合でも 1 バイトで read(2) を呼んでしまう。それに対して Solaris の sh や ksh は 128-1024 バイト程度の長さのバッファを使う。ページ長にしていないのは、典型的な 1 行の長さはもっと短いと想定しているからだろう。
ソースファイルを細かく追いかけていないけれど、GNU bash は 2.05 付近で 128 バイトとするように変更が入ったようだ。ksh はかなり昔から 1024 バイトになっていた。一方、zsh は新しいバージョンでも最適化が入っていない。
FreeBSD が遅いままなのは悲しいので、簡単な最適化を実装して追加した。今後公開される 11.4, 12.2 以降には含まれる予定。
追記
cat(1) のバッファサイズはページ長よりも大きいのでは、という指摘が曽田さんからあったので追記。
catが使うバッファサイズは、FreeBSD以外だともっと大きな値じゃないかと思います。手元で試してみると wc -l の出力は以下の通りでした。
— SODA Noriyuki (@n_soda) March 28, 2020
NetBSD 9.0: 19
CentOS 7.5.1804: 22
CentOS 8.1.1911: 19
CentOSでの結果がだいぶ違うのはなんでしょうね…
FreeBSDのサイズが小さいのは知りませんでした。
確かにページ長になるというのは決めつけすぎですね。FreeBSD は一般ファイルの場合は MAXPHYS (=128 KiB) の 8 倍を最大のバッファサイズにしていて、たまたま（というかある程度は意図的に）ページ長と一致します。メモリが少ないシステムでは自動的に小さくなるので、いつも一定ではありません。もっと大きいシステムも多数あるでしょう。
また、shcat の本来の意図も曽田さんから。
SunOS 4は single userモードだと /sbin はあるけど /bin も /bin/cat もない状況になるので(/bin は /usr/bin への symbolic link で /usr はまだマウントされてない)、shcat は元々その環境で使うためのshell関数だった気がする。なお single userモード用に /bin/sh とは別に /sbin/sh があった https://t.co/GUYw8icMBM
— SODA Noriyuki (@n_soda) March 28, 2020
これはそのとおり（cat(1) や basename(1) が使えない段階でも動くようにするため）だと思います。当時は理由が分からず、たぶん速度だろうと思ったわけです。指摘のとおり、SunOS は少なくとも 5.8 まではデフォルトインストールで / と /usr が分かれていて cat(1) は /usr/bin/cat にあるので、cat(1) が使えないこと気づくまでには、それほど時間はかかりませんでした。そしてその後 /bin/cat が / にあるシステムでも、たぶんこっちが効率的なのだろうと信じて shcat を使い続けていました。