これは備忘録。
色々あって、まだ具体的なモノを何も作ってもないのにシェルスクリプトのパフォーマンス絡みでネタを収集してしまったので、ひとまずまとめてみた。
shellshock（bashのアレ）があったばかりなので、ちっとばかり微妙かも。
計測してボトルネックを探す
まずは何よりも計測すること。time(1)を活用すべし。
データ量が多いと問題が表面化するのが定番のパターンなので、ワンライナー等でさくっとテストデータを作成して実験すると吉。
ループ構文よりもテキストフィルタを使う
一般的には、ループ構文を使うよりも、パイプでテキストフィルタに連結して処理した方が高速だ。
# NG seq 1 1000000 | while read i; do echo "$i"; done # NG # while readほどではないが遅い # （bashでは動いたが、dashやbusyboxのshでは引数多すぎでダメだった） for i in `seq 1 1000000`; do echo $i; done # OK seq 1 1000000 | awk '{ print }'
ただし、ごく稀ながら例外もある。データ件数が少なく、且つループ内で内部コマンド（ビルトインコマンド）しか使わない場合だ。大抵のテキストフィルタは外部コマンドなので、実行時にプロセスを1つ生成するコストが発生する。パイプで数珠つなぎすればするほど、生成するプロセスの数は増える。このプロセス生成のコストよりも、内部コマンドOnlyのループの方が高速になることがある。
もっとも、Unix環境ではプロセス生成コストが比較的小さい上に、どう頑張ってもループ処理そのものが高速とはいえないので、データ件数が多いとテキストフィルタの方が高速になる。つまり、「プロセス生成コストを超えない程度のループ回数」に収まるデータ件数でなくてはならない。
しかし「プロセス生成コストを超えない程度」だなんて、プロセス生成コストが比較的大きくなるCygwin*1でさえも、ユーザの体感としては誤差みたいなものだ。正直なところ、ループ中などで頻繁に生成するのでもない限り、気にするほどのものではない。
それに、大抵はそこそこのデータ件数を取り扱うことになるので、やはり一般的にはループ構文よりもテキストフィルタを使ったほうがよい。
そもそも本当にループする必要があるのか考えてみる
例えばループ構文でファイル名を取り出して、各ファイル名を引数としてコマンドを実行しているスクリプト：
# NG for i do chmod +x "$i" done
chmod(1)は引数に複数のファイルを指定できるので、実のところループする必要はない。
# OK [ $# = 0 ] || chmod +x ${@+"$@"}
ループして毎回外部コマンドを実行するよりも、1回だけ実行する方が高速になる。
chmod(1)に限らず、一度に複数の引数を指定できるコマンドは非常に多い。ものすごく基本的なことなのだが、非Unix環境出身の他の言語の経験者がシェルスクリプトのことをよく知らないままに書くとやってしまいがちなミスである。
また、file(1)やgrep(1)のオプション-fのように、ファイル名や正規表現の一覧のテキストファイルを指定できるコマンドもある。こちらも、「while read」ループでパラメータを読み出して毎回実行するよりも、オプションを使用して1回だけ実行する方が高速だ。
# NG # ループで毎回「外部コマンド呼び出し＋foo.txt読み込み」という最悪パターン while read i do grep "$i" foo.txt done <patterns.txt # OK grep -f patterns.txt foo.txt
安易にループする前に、man(1)で実行したいコマンドの仕様を調べて、ループせずに済むか確認するべきだ。
xargs(1)を使う
「そもそも本当にループする必要があるのか考えてみる」の発展系。
例えばfind(1)やlocate(1)のようにファイル名一覧を出力するコマンドを実行し、出力結果の各ファイル名を引数として別のコマンドを呼び出したい場合：
# NG locate ~/bin/\*.sh | while read i; do chmod 755 "$i"; done
xargs(1)を使用すると、chmod(1)の引数に1度に複数のファイル名が指定されるので、chmod(1)の呼び出し回数が最小化されて高速になる。
# OK locate -0 ~/bin/\*.sh | xargs -0 chmod 755
注意点として、この方法はchmod(1)のように「1度に複数の引数を渡しても大丈夫」というシチュエーションでしか使えない。実行したいコマンドが1度に1つの引数しか取り扱わないとか、echo(1)のように「毎回1個の引数を渡す」と「1度に複数の引数を渡す」とで結果が異なる（そしてそれが問題となる）場合には、xargsは使えない。
find(1)では「-exec command {} \;」よりも「-exec command {} +」を使う
「xargs(1)を使う」の仲間。
find(1)のオプション-execは、「-exec command {} \;」の形式では各ファイルごとにコマンドが実行されるので遅くなるが、「-exec command {} +」の形式ではxargs(1)と同様の効果が得られる。
# NG find . -type f -exec chmod 644 {} \; # OK find . -type f -exec chmod 644 {} +
なお注意点もxargs(1)と同じ。
$ find . -type d -exec echo {} \;
.
./aaaa
./bbbb
./cccc
$ find . -type d -exec echo {} +
. ./aaaa ./bbbb ./cccc
ループ構文を使うなら、ループ中で外部コマンドを使わない
どうしてもループ構文を使う場合は、ループ中で外部コマンドを使わず、内部コマンド（ビルトインコマンド）で実現できないか検討すること。
以下は手元のUbuntu 12.04のbashで計測した結果だが、同じecho(1)でも内部コマンドと外部コマンドでは実行速度に大きな差がある。
$ uname -a Linux fabrico 3.2.0-70-generic-pae #105-Ubuntu SMP Wed Sep 24 20:08:22 UTC 2014 i686 i686 i386 GNU/Linux $ bash --version GNU bash, バージョン 4.2.25(1)-release (i686-pc-linux-gnu) Copyright (C) 2011 Free Software Foundation, Inc. ライセンス GPLv3+: GNU GPL バージョン 3 またはそれ以降 <http://gnu.org/licenses/gpl.html> This is free software; you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. $ time seq 1 1000 | while read i; do echo "$i"; done >/dev/null real 0m0.038s user 0m0.036s sys 0m0.000s $ time seq 1 1000 | while read i; do /bin/echo "$i"; done >/dev/null real 0m2.202s user 0m0.124s sys 0m0.452s
bashなどの独自拡張機能を備えたシェルを使ってもよいのなら、例えばブレース展開・パラメータ展開によるパターンの置換・算術式展開などを使用して、ループ中から外部コマンドを排除できないか検討してもよいだろう。
使用するコマンドのオプション等に注目する
例えば『フルスクラッチから1日でCMSを作る シェルスクリプト高速開発手法入門』では、次のようなTipsが紹介されている。
- ls(1)にオプション-fを付けてみる。
- LANG=Cでsort(1)してみる。
- sort(1)にオプション-sを付けてみる（キーフィールドを指定する場合など）。
ちょっとした違いで速度が変わることがあるので、あなどれない。
使用するコマンドを選ぶ
例えば、単純な文字の置換ならsed(1)よりもtr(1)の方が高速だ。
$ tr --version tr (GNU coreutils) 8.13 Copyright (C) 2011 Free Software Foundation, Inc. ライセンス GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>. This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. 作者 Jim Meyering。 $ sed --version GNU sed バージョン 4.2.1 Copyright (C) 2009 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE, to the extent permitted by law. 訳注: 非常に重要な文章のため、原文を残しています。 -- 参考訳 これはフリー・ソフトウェアです。複製の条件に関しては、ソースをご覧くださ い。保証は一切ありません。営利目的や法で定められた範囲での特定目的のため の適合性もありません。 GNU sed ホームページ: <http://www.gnu.org/software/sed/>. GNU ソフトウェアを使用する際の一般的なヘルプ: <http://www.gnu.org/gethelp/>. 電子メールによるバグ報告の宛先: <bug-gnu-utils@gnu.org> 報告の際、“Subject:” フィールドのどこかに “sed” を入れてください。 翻訳に関するバグは<translation-team-ja@lists.sourceforge.net>に報告してください。 $ time seq 1 10000000 | tr 0 _ >/dev/null real 0m15.283s user 0m14.969s sys 0m0.384s $ time seq 1 10000000 | sed 'y/0/_/' >/dev/null real 0m19.438s user 0m26.946s sys 0m0.232s
正規表現を使う場合、例えばsed(1)やawk(1)で頑張るよりもperl(1)の拡張された正規表現（例えばものぐさなマッチング）を使った方が効率的な場合もある。
最近気がついたのだが、手元のUbuntu 12.04ではgawk(1)とmawk(1)とで有意な差がある場合とない場合がある。入力されたテキストを文字列として扱う分には両者とも大きな差異はみられないのだが、数値への変換が発生する際にはmawk(1)の方が高速になるようだ。
$ gawk --version
GNU Awk 3.1.8
Copyright (C) 1989, 1991-2010 Free Software Foundation.
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see http://www.gnu.org/licenses/.
$ mawk -W version
mawk 1.3.3 Nov 1996, Copyright (C) Michael D. Brennan
compiled limits:
max NF 32767
sprintf buffer 1020
$ time seq 1 1000000 | gawk '{ printf("%s\n", $0) }' >/dev/null
real 0m1.377s
user 0m2.508s
sys 0m0.008s
$ time seq 1 1000000 | mawk '{ printf("%s\n", $0) }' >/dev/null
real 0m1.385s
user 0m1.884s
sys 0m0.028s
$ time seq 1 1000000 | gawk '{ printf("%d\n", $0) }' >/dev/null
real 0m3.555s
user 0m4.924s
sys 0m0.016s
$ time seq 1 1000000 | mawk '{ printf("%d\n", $0) }' >/dev/null
real 0m1.383s
user 0m2.152s
sys 0m0.028sもっともマルチバイトの扱いという点で、安易にgawk(1)からmawk(1)に替えられないこともあるのだが。
あと、個人的な話になるが、90MB弱のソート済み辞書ファイルを高速に検索するために、専用のコマンド*2を実装したことがある。ハードウェア性能が向上した今でも、辞書ファイルがキャッシュされた状態でgrep(1)するよりもわずかに高速だ。ただし汎用性は皆無だが。
ともかく、使用するコマンドによって処理速度が大きく変化する可能性がある。ただ、実行環境や処理内容に依存する部分があるので、一般論として語るのは難しい。各環境ごとに計測して確かめるべきだろう。
使用するUnixシェルを選ぶ
例えば純粋に内部コマンド（ビルトインコマンド）のみでwhile readさせた場合、bashよりもdashやbusyboxのshの方が高速だ。時にはbash以外の高速なUnixシェルの採用を検討してもよいだろう。
$ /bin/bash $ time seq 1 100000 | while read i; do echo "$i"; done >/dev/null real 0m2.889s user 0m2.460s sys 0m0.544s $ exit $ /bin/dash $ time seq 1 100000 | while read i; do echo "$i"; done >/dev/null 0.12user 0.00system 0:00.76elapsed 16%CPU (0avgtext+0avgdata 2608maxresident)k 0inputs+0outputs (0major+208minor)pagefaults 0swaps $ exit $ /bin/busybox sh BusyBox v1.18.5 (Ubuntu 1:1.18.5-1ubuntu4.1) built-in shell (ash) Enter 'help' for a list of built-in commands. ~ $ time seq 1 100000 | while read i; do echo "$i"; done >/dev/null real 0m 1.10s user 0m 0.12s sys 0m 0.00s ~ $ exit
ただし、bashでは一部の外部コマンドを独自拡張機能に置き換えることが可能だ。dashなどのシンプルなシェルに変更することで、外部コマンドの呼び出し回数が増加し、かえって遅くなってしまう可能性も考えられなくはない。
処理を分けてパイプで並列実行してみる
これはシェル芸の人*3が折に触れて書いている通り。パイプ中にデータが流れている限り、コマンドは並行して動作する。なので実行環境と処理内容と処理データ件数によっては、高速化を期待できる。
──何やら前提条件が色々出てきた。
バックグラウンドプロセスで並行実行してみる
例えばping(1)のように待ち時間が発生するかもしれないコマンドを逐次実行すると、最長で「コマンド1回あたりの最長待ち時間 × コマンド実行回数」だけ時間がかかる。
# NG : on Ubuntu 12.04 for i in `seq 1 254` do addr=192.0.2.$i ping -c 1 -w 1 $addr >/dev/null [ $? -eq 0 ] && echo $addr done
これをバックグラウンドプロセスで並行実行し、wait(1)するように書き換えてみる（bashの場合はcoprocでもよいだろう）。
# OK : on Ubuntu 12.04 do_ping() { ping -c 1 -w 1 $1 >/dev/null [ $? -eq 0 ] && echo $1 } { for i in `seq 1 254` do do_ping 192.0.2.$i & done wait } | sort -V
こうすると、最長でも概ね「コマンド1回あたりの最長待ち時間＋α」ぐらいで実行完了する。
この方法は、コマンドの実行順が重要となるケースでは採用できない。また、同一のリソースにアクセスするような場合、そのリソースへの最大同時アクセス数が高速化のボトルネックとなる可能性もある。
例えば、ping(1)ならともかく、curl(1)でISOイメージファイルをダウンロードする場合は、バックグラウンドプロセスを使用して複数のファイルを同時にダウンロードしても、ネットワーク帯域の上限により高速化されないかもしれない。
事前に準備しておけないか考えてみる
例えばfind(1)に似たコマンドにlocate(1)がある。find(1)が実行時にファイルシステムを舐めるのに対して、locate(1)は事前に作成しておいた検索インデックスを参照する。locate(1)はfind(1)よりも高速だ。しかしその反面、ファイルの追加・移動・削除にリアルタイムに追随できないという欠点もある。検索インデックスを更新する必要がある。
locate(1)の検索インデックスのように、事前に何らかの準備を行っておき、実際に処理を行う際に事前準備の成果を用いてスタートダッシュする、という方法で高速化できる可能性がある。
これは、多分ユニケージでいうレベル4データ（アプリケーションデータ）の作成だ。『フルスクラッチから1日でCMSを作る シェルスクリプト高速開発手法入門』でも、全文検索機能のCGIの高速化において似たようなこと*4を行っている。
