シェルスクリプトで「パイプライン並列化」をガチでやってみた 〜 パイプ＋並列処理でCPUの最大効率を引き出す知識

はじめに

シェルスクリプトはコマンドをパイプでつなぐだけで簡単にパイプライン並列化を行うことが出来ますが、効率よく並列処理を行えるかどうかは別の話です。ボトルネックやオーバーヘッドがあるので単純にパイプでいくつもコマンドをつないでいくだけで簡単にどこまでも効率よく並列処理が行われるなんて事は技術的にありえません。そんなに簡単なら他の言語でも採用しているはずです。この記事ではシェルスクリプトで「何も考えずに」パイプでコマンドを多数つなげるスタイルが CPU 性能を効率よく使う上でのアンチパターンであることを示し、パイプで CPU を効率的に使ってパフォーマンスをあげたい人が知らなければいけないパイプライン並列化の重要な基礎知識とtime コマンドの読み方を解説します。

コマンドをパイプでつないで並列処理を行うパイプライン並列化は簡単に使えますが、並列処理の手法の中でおそらくもっとも制御が難しいものです。制御が難しいのでパイプライン並列化で CPU の最大効率を引き出すためには多くの知識が必要になってきます。可能であればデータ並列化やタスク並列化といった他の並列化技術を使う（併用する）方が簡単で効果が高いです。そしてこれらの並列化技術を使用していたり、自然と並列実行が行われるシステム（サーバーサイドのウェブシステム等）では、パイプで多数のコマンドをつなぐスタイルを使ってしまうと「並列起動数×パイプでつないだコマンド数」という膨大な数のプロセスが生成とパイプ間通信が行われてしまい逆にシステムに過剰な負荷を与えて重くなってしまう可能性すらあります。つまりパイプで多数のコマンドをつなぐスタイルは、CPU 性能を使い切るためにコマンドを並列実行させるシステム設計と相性が悪いため、パイプを使うのは程々にしておけというのがこの記事の結論です。

とはいえシェルスクリプトにとってパイプはなくてはならないとても重要な機能ですので、そこは勘違いしないでください。私はパイプを使うなと言っているのではなく、中途半端な知識でパイプを使うのではなく、パイプの性質を正しく理解して「適切に"使え"」と言っています。（とは言ってもシェル上で使う場合だけとか使い捨てのスクリプトなどではそこまで考える必要はないと思いますが。）

本気でやるならシェルスクリプト以外の適切な言語を使う

「なんでシェルスクリプトなんかにマジになってんの？」って言われる前に自分から先に言いますが、**並列処理を本気でやりたいならシェルスクリプトではなく他の適切な言語を使ってください。**シェルスクリプトではプロセス単位での並列化（パイプライン並列化含む）しか利用することが出来ず性能も生産性も低いです。

シェルスクリプトの限界

例えばシェルスクリプトでは OS が基本機能として持っている並列化技術の POSIX スレッドすらまともに使うことが出来ません。OS にはいろんな技術が搭載されています。本来であればそれらの技術を比較検討して最適な技術を選択すべきです。しかしながらシェルスクリプトでは OS が持っている基本的な機能でさえ使えない、もしくは使うのが困難で、たとえ使えたとしてもパフォーマンスが悪く、そもそも比較検討すら出来ません。残念ながらシェルスクリプトの世界は利用可能な技術が少なく、使える技術だけで頑張るという世界です。他の言語では簡単に実現できることがシェルスクリプトでは大変です。それはシェルスクリプトが劣っているからではなく特定の用途に最適化された言語だからです。特定の用途に最適化されているために言語機能が小さくなっています。またシェルスクリプトはもともと大きなソフトウェアを作るための言語ではないためライブラリやフレームワークが整備されておらず、大きなソフトウェアを作ろうとすると**自分でライブラリ（関数やコマンド等）を作る必要が多くなり開発コストが高くなってしまいます。**シェルスクリプトは多くの環境で初期状態で使えるスクリプト言語であるため、セットアップの手間がいらないというメリットがありますが、言語やライブラリのセットアップなんてコマンドをいくつか実行してパッケージをインストールするだけで終わる簡単なお仕事です。今は適切なバージョンの言語とライブラリを簡単にインストールする仕組みがありますし、今は Docker などのアプリケーションコンテナ技術で 1 コマンドで複雑な構成のサービスを適切に動かすことも可能になっています。大きなソフトウェアは他の言語で作った方がはるかに開発コストが低いです。シェルスクリプトでは諦めなければならないような機能も簡単に実現することができます。**シェルスクリプトの主な役目は大きなソフトウェアを作ることではなく、他の言語で作られたソフトウェア（コマンド）を組み合わせることです。**シェルスクリプトと他の言語、この二つを組み合わせるのです。

他の言語はパイプやプロセスを使わない

**パイプとプロセスは OS の基礎技術であり重要な技術ですが最高の技術というわけではありません。考えてもみてください。パイプやプロセスは OS の基本機能なわけでシェルスクリプトだけの特権などではなく他の言語からでも使えるものです。もしパイプやプロセスが最高の技術であれば、他の言語でもそれらを中心に作られていたはずです。しかし多くの言語やライブラリの内部でパイプやプロセスを使うことはあまりありません。使えるのに使わない、それがパイプとプロセスが最高の技術ではないことのなによりの証拠でしょう。プロセスを使うとデータのやり取りにプロセス間通信が必要になります（パイプ通信もプロセス間通信の一つです）。プロセス間通信は同一プロセスでのやり取りよりもコストがかかります。スレッドによる並列化はプロセス間通信が不要なため、一般的にプロセスによる並列化より性能が高くなります。また並列処理に強い Go にはスレッドよりも軽い軽量スレッド (Goroutines) まであります。スレッドを正しく扱うのは難しいですが多くの言語にはそういった並列化技術を簡単に使えるフレームワークやライブラリが存在しており、環境の違いを意識することなく高度な機能を簡単に使うこと出来ます。**シェルスクリプトではプロセスによる並列化しかできない上に本格的な並列処理をしようと思ったら、ロックファイルを使った排他制御や CTRL-C を押したときの中断処理などを自分で実装しなくてはならずとても大変です。ソフトウェア技術はシェルスクリプトが誕生した時代よりもはるかに進んでいるわけで、現代的な他の言語の方がはるかに生産性が高いです。パイプとプロセスは OS の基礎技術ですが、基礎技術しか知らないようでは話になりません。基礎技術を知った上でその先の応用技術を使わなければ生産性を上げることは出来ません。

シェルスクリプトで他の言語の力を底上げする

この記事はシェルスクリプトやパイプライン並列化が最高の技術だからという理由で解説しているわけではなく、それらを使ってどうやってパフォーマンスを引き出すのかという話をしているにすぎません。シェルスクリプトがプロセスやパイプに強い理由は簡単な記述で使えるというその一点のみです。しかしそれはとても重要なことです。なぜなら全ての言語で作ったコマンドでマルチコア CPU の性能を手軽に利用することができるからです。他の言語で並列化技術が簡単に使えると言ってもやはり面倒くさいものです。並列処理を行わないコマンドを作る方が簡単です。シェルスクリプトを使えばそれらのコマンドを簡単に組み合わせることが出来ます。そこにプロセス単位の並列化ががうまく働くようにすることで**他の言語で作ったコマンドの力を底上げすることが出来ます。並列処理を行わないコマンドを並列実行させる。それがコマンドを連携させることが得意なシェルスクリプトの役目の一つです。ただし普通にパイプを使うだけでは CPU を効率的に使うことは出来ません。**もしパイプライン並列化で CPU の最大性能を引き出したいのであればこの記事を読んでしてください。実はこの記事はシェルスクリプトのための記事のようであってそうではありません。この記事はシェルスクリプトの力を使って、他の言語で作ったコマンドで CPU を効率よく使うための記事です。

この記事を書くことにした経緯

さて少し余談に近い話になってしまいますが、この記事は以前書いた「パイプを使って高速化したシェルスクリプトを並列実行すると逆に遅くなる謎現象について」の解答編とも言えるものです。書こうとしたきっかけは「シェルスクリプトの実験のために作った POSIX 準拠 awk 実装の JSON パーサー (SAX風ストリーミング対応)」を書いている時に、設計上の理由でパイプを使う必要が出てきたので、可能な限り CPU を効率的に使って速くなるように調整を行いました。その時にこの話を例にして説明すれば分かりやすいのではないか？と思ったからです。説明のためだけにでっち上げた例では不自然で現実的ではないものになりがちですし、ちょうどよい規模で説明に向いた例はそうそううまく作れません。

通常であれば私は JSON パーサーのような汎用のユーティリティー内部でパイプ（というか並列処理）を使うのは可能な限り避けようとします。例えばその前に作った「シェルスクリプトの実験のために作った POSIX 準拠 awk 実装の CSVパーサー (RFC4180対応)」では awk スクリプト一つだけで構成されています。なぜかと言うと汎用のユーティリティーは動かす環境を想定できないからです。例えば性能が低い 1 CPU の組み込み機器で動かすかもしれません。最近の高性能パソコンは多数の CPU コアを利用できますが、クラウドでは CPU コアの利用はコストに直結するので、あえて少ないコアを搭載した仮想マシンを負荷に応じてオートスケールさせてコストの最適化を行うことも一般的です。多数の CPU コア が搭載された環境を前提にすることは出来ません。

また、マルチコア CPU が使える場合でも、汎用ユーティリティーで使用する CPU コアを節約すれば、ユーザーは他の用途に CPU コアを使用することが出来ます。一言で言うならば**「たかが一便利コマンドのくせに CPU リソースをフルに持っていこうとするな」**ということです。たとえ速度が速かったとしても、それだけで 32 コア使って他の処理が遅くなるようなコマンドは嫌だと思います。例えば JSON パーサーは、その出力を処理するためにさらに別のコマンドにパイプでつなぐことを想定しています。そのため JSON パーサーだけで CPU を使い切ってしまってはいけません。仮にユーティリティーをマルチコア CPU に対応させるのであれば、デフォルトは 1 CPU での動作としオプションで指定した場合のみ並列処理を機能を有効にします。ただ今回の JSON パーサー（正確には今後の開発予定の改良版の方）ではそれを行うのが設計上難しく、実装するのが大変なので内部的に二つのコマンドをパイプでつなぐ設計にしています。

パイプ＋並列処理でCPUを効率よく使うための「基礎知識」

ここだけ読めば十分という内容を「基礎知識」としてまとめました。もし「基礎知識」の内容に納得がいかない人や詳細を知りたい人は「詳細な検証」を読んでください。

「パイプでつながない」の意味

最初に明確にしておきますが、この記事で言っている「パイプでつながない」というのは「パイプでつないだ複数のコマンドを一つにまとめる」という意味です。「一時ファイルに書き出して複数のコマンドに分けて処理すればパイプでつないでない」などの意味ではありません。

一時ファイルなどを使ったら遅くなるのは当たり前です。パイプが遅くなる原因はパイプ通信のオーバーヘッドですが、その代わりにファイル読み書きというもっと大きなオーバーヘッドを使ったらもっと遅くなるのは当たり前です。この記事で言っている「パイプでつながない」とは「パイプでつないだ複数のコマンドを一つにまとめること」で、同一プロセスでメモリ内でデータを処理することでパイプ間通信のオーバーヘッドをなくすことです。

論より証拠

コマンドをパイプでつなぐとパイプ間通信とコマンド処理のオーバーヘッドによって使用する CPU 時間は必ず増えます。「CPU 時間が増えたとしても休んでいる CPU コアを使うから実時間が改善できる」というのが並列化の本質です。

# データ生成
$ cat /dev/urandom | base64 | head -n 1000000 > data.txt

# time コマンドの出力に CPU 使用率を加える （注意 bash 専用）
# 注意2 macOS の /bin/bash は古くてバグがあるようで CPU 使用率が正しく表示されない
$ TIMEFORMAT="real %3lR  user %3lU  sys %3lS  cpu %P%%"

# パターン1 パイプでつなぐ場合
$ time cat data.txt \
  | sed 's/a/A/g;' | sed 's/b/B/g;' | sed 's/c/C/g;' | sed 's/d/D/g;' \
  >/dev/null
real 0m0.537s  user 0m1.850s  sys 0m0.215s  cpu 384.87%

# パターン2 パイプでつながない場合
$ time cat data.txt \
  | sed 's/a/A/g; s/b/B/g; s/c/C/g; s/d/D/g;' \
  >/dev/null
real 0m1.360s  user 0m1.336s  sys 0m0.073s  cpu 103.59%

パターン 1（パイプでつないだ場合）はパターン 2（パイプでつながない場合）よりも CPU 時間 （user + sys) が増えています。実時間 (real) は短くなっていますが代わりに余計に CPU を使っている（4 コア中 384.87%)ことに注意しなければいけません。**他のことをする余力が無くなっています。**逆に言えばパターン 2 では余力が有るので、この処理を同時に 3 つ動かすことで 1 つのデータを処理する時間で 3 倍のデータ量を処理する事が可能です。

ちなみにこの例のパターン 1 は並列化の効果が最も高い例です。なぜなら各コマンドの処理時間がほぼ同等だからです。現実にはこのように都合よく各コマンドの処理時間がほぼ同等になることはありません。この結果からパイプでつなぐことの効果がすごく高いように見えてもそれは非現実的な例でしかありません。

そこで現実的になるようにボトルネックとなる sed 's/[0-9]//g' を追加します。

# パターン1 パイプでつなぐ場合（ボトルネックあり）
$ time cat data.txt \
  | sed 's/a/A/g;' | sed 's/b/B/g;' | sed 's/c/C/g;' | sed 's/d/D/g;' \
  | sed 's/[0-9]//g' >/dev/null
real 0m4.080s  user 0m6.156s  sys 0m0.493s  cpu 162.97%

# パターン2 パイプでつながない場合（ボトルネックあり）
$ time cat data.txt \
  | sed 's/a/A/g; s/b/B/g; s/c/C/g; s/d/D/g;' \
  | sed 's/[0-9]//g' >/dev/null
real 0m3.789s  user 0m5.194s  sys 0m0.219s  cpu 142.88%

すると処理時間は簡単に逆転してしまいます。この場合パイプでつないだパターン 1 は パターン 2 に比べて実時間 (real) も ユーザー CPU 時間 (user) も システム CPU 時間 (sys) も増えているので一つもメリットがありません。また先程は 384.87% も CPU を使っていたのに 162.97% まで落ちました。追加したボトルネックの sed 's/[0-9]//g' よりも速く実行することができないので、その他の sed は休んでいる状態となり、パイプ間通信とコマンドの処理が多い分、パターン 1 の方が遅くなっているわけです。パターン 2 のように複数の小さな処理を行うコマンドは一つにまとめた方が良いという結果になっています。

各コマンドの CPU 使用率の詳細を見てみましょう。（このようにすると /usr/bin/time が呼び出されるので出力が変わっています。）

# パターン1 パイプでつなぐ場合（ボトルネックあり、詳細版）
$ cat data.txt \
    | time sed 's/a/A/g;' \
    | time sed 's/b/B/g;' \
    | time sed 's/c/C/g;' \
    | time sed 's/d/D/g;' \
    | time sed 's/[0-9]//g' >/dev/null
0.48user 0.05system 0:03.90elapsed 13%CPU (0avgtext+0avgdata 2772maxresident)k
0inputs+0outputs (0major+129minor)pagefaults 0swaps
0.50user 0.04system 0:03.90elapsed 14%CPU (0avgtext+0avgdata 2632maxresident)k
0inputs+0outputs (0major+124minor)pagefaults 0swaps
0.56user 0.08system 0:03.90elapsed 16%CPU (0avgtext+0avgdata 2544maxresident)k
0inputs+0outputs (0major+127minor)pagefaults 0swaps
0.43user 0.08system 0:03.91elapsed 13%CPU (0avgtext+0avgdata 2764maxresident)k
0inputs+0outputs (0major+128minor)pagefaults 0swaps
3.89user 0.01system 0:03.91elapsed 99%CPU (0avgtext+0avgdata 2636maxresident)k
0inputs+0outputs (0major+127minor)pagefaults 0swaps

# パターン2 パイプでつながない場合（ボトルネックあり、詳細版）
$ cat data.txt \
    | time sed 's/a/A/g; s/b/B/g; s/c/C/g; s/d/D/g;' \
    | time sed 's/[0-9]//g' >/dev/null
1.47user 0.06system 0:03.79elapsed 40%CPU (0avgtext+0avgdata 2748maxresident)k
0inputs+0outputs (0major+137minor)pagefaults 0swaps
3.76user 0.03system 0:03.80elapsed 100%CPU (0avgtext+0avgdata 2836maxresident)k
0inputs+0outputs (0major+129minor)pagefaults 0swaps

ここで見ていただきたいのは CPU 使用率です。ボトルネックとなるコマンドは CPU をほぼ 100% 使用していることがわかります。しかしその他のコマンドは、パターン 1 は 13% 〜 16%（合計 46%）です。これはボトルネックとなるコマンドがデータを処理しきれずバッファがあふれ、その他のコマンドはデータ出力がブロックされ全力でデータを処理できない = 休んでいる時間が多くなっているからです。（注意 CPU 1 コアを 4 プロセスで分割して使っているから 13% 〜 16% になるという意味ではありません。）

もしボトルネックを改善できればその他のコマンドは休んでいる時間が減って CPU 使用率は増えるでしょう。**ボトルネックの処理を変更して、その他のコマンドの CPU 使用率が増えたのであれば、それは改善されたことになります。**パイプライン並列化ではそれぞれのコマンドが独立して並列で動作しているわけではなく、パイプラインを流れるデータに同期して動作するため、ボトルネックとなるコマンド（CPU 1 コアを 100% 使用しているコマンド）によってデータの流れが滞ると、それ以外のコマンドはデータが届くまでは休む事しかできず CPU は遊んでしまいます（ベルトコンベア式の流れ作業で前または後の人の作業が遅くて、その人の作業が終わるまで次に進められない状況を想像してください）。

パターン 2 も同様にボトルネックとなるコマンドで休んでいる時間が発生していますが、パイプ間通信という余計な処理をしていないため　CPU 使用率はパターン 1 の合計 46% よりも少ない 40% で済んでいます。**ボトルネックの処理は変更せずに、その他のコマンドの CPU 使用率が減ったのであれば、それは改善されたことになります。**CPU 使用率だけを見れば先ほどと言っていることが正反対になったように見えますが、これはボトルネックとなるコマンドの実行時間 （real = user + sys) を基準（その他のコマンドの real と等しい）としてその他のコマンドの CPU 使用率が算出されているからであり、CPU 使用率が変わった原因が異なるからです。個々のコマンドの性能を見る場合は CPU 使用率ではなく user/sys を見たほうが分かりやすいでしょう。パイプライン全体の real と個々のコマンドの real と一致しますが、全体の user/sys は個々のコマンドの合計になるという違いの意味にも注意してください。

ということでこれらの話がパイプライン並列化で CPU を効率よく使うことの難しさです。同じ sed コマンドでも行う内容によって処理速度は違います。また他のコマンドだとどうなるでしょうか？同じコマンドでも環境が違えば実装も異なります。不確定要素が多いためどのようにすれば最も効率が良いかは一概には言えません。time も単に数字の大小だけを眺めていれば良いわけではなく、その意味を正しく判断するのは結構難しいです。

並列処理を語るならtimeのuser/sysを無視してはいけない

みなさんは time コマンドを使ったことがあるでしょうか？デフォルトでは以下のように出力されるでしょう。シェルによってはビルトインコマンドであるため、使っているシェルで出力が異なる場合があります。

# POSIX 準拠の場合
$ /usr/bin/time -p sleep 1
real         1.00
user         0.00
sys          0.00

# bash の場合
$ time sleep 1
real    0m1.008s
user    0m0.001s
sys     0m0.002s

# zsh の場合
$ time sleep 1
sleep 1  0.00s user 0.00s system 0% cpu 1.008 total

time コマンドは POSIX でも標準化されているコマンドで、-p オプション指定時は少なくとも real/user/sys の 3 つの値が出力されることになっています。なぜこれらの値が出力されるかといえば、もちろん real/user/sys が特に重要な値だからです。

• real - 実時間、実際に掛かった時間
• user - ユーザー CPU 時間、コマンドの処理に掛かった時間、
• sys - システム CPU 時間、システムコールに掛かった時間

CPU が 1 コアしかない場合（または 1 コアしか使ってない場合）は real は user + sys + 待ち時間になります。待ち時間とは I/O （ディスク書き込みやネットワーク通信やパイプ通信）による待ち時間で CPU が何もしてなかった（アイドル状態）時間です。上記の sleep 1 も CPU は何もしないで待っているだけなので、real は 1 秒ですが user と sys はともにごくわずかな時間になっています。また user は real を超える事があります。それはマルチコア CPU 環境で並列動作を行っている場合で、この記事が主に焦点を当てている部分です。

並列処理というのは user/sys を増やすことで real を短くする方法と言い換えられるかもしれません。しかし user/sys は無駄な処理によっても増えてしまうので「user/sys が増えた = 良くなった」とは限りません。例えばコードを修正して real が同じで user/sys が増えたという場合は性能が落ちたことを意味します。（ボトルネック以外のコマンドが余計に CPU を消費している状態）

このように並列処理が行われている場合は real だけを見ても意味がなく user/sys を無視したりしてはいけません。全ての値を見て、総合的に考えて良くなっているのかを検討する必要があります。例えば real が 10 % 良くなった反面 user/sys の時間が 2 倍になった場合、総合的に考えて良くなったと判断すべきかは難しい問題です。そのようなスクリプトを CPU が 1 コアしか搭載してない環境（または 1 コア相当分しか余力がない環境）で実行すると real は user + sys （つまり 2 倍）になってしまいます。

「実時間が短い方が良いに決まってる」は間違いである

「たとえユーザー CPU 時間 (user) やシステム CPU 時間 (sys) が増えていても実時間 (real) が短いほうが良いのではないか？」はい、一般的にはそうだと思いますが、すべてそうとは限りません。例えばパイプライン並列化以外の並列化技術を使う（併用する）場合です。

具体的に言うと xargs -P、make -j、GNU parallel 等を使ったり、シェルスクリプトのバックグラウンド実行を使ってプロセス単位の並列化を行う場合や、pigz のように内部でスレッドを使うコマンドを使用する場合です。またウェブシステム (CGI) 等のようにアクセス単位で独立したプロセスが起動する場合にもあてはまります。（念の為ですが FastCGI を使ってもシェルスクリプトではパフォーマンスを改善することはできません。シェルスクリプトの言語仕様上 FastCGI に対応する能力がなく、スクリプト内部で外部コマンドを起動するので意味がないのです。詳しくは「FastCGI shell script」を参照してください。これはシェルスクリプトを使って大規模なウェブシステムを作るべきではない理由の一つです。）

こういった**「パイプライン並列化以外の並列化技術を使う（併用する）場合」では、パイプライン並列化は重要性が低くなり、場合によっては逆効果になって実時間が長くなる可能性があります。なぜならパイプライン並列化で実時間が短くなるのは、何もしていない CPU コアが余っているという前提があって初めて成り立つもの**だからです。

他の並列化技術を併用する場合、並列で起動するコマンド数を増やすだけで簡単に CPU コアを使い切る事ができます。CPU コアが余ってない状況では他の CPU に処理を割り振る事ができません。1 プロセスで実行して user/sys が real を超えている状況というのは、複数の CPU コアを使っているということですから、割り振る他の CPU コアがない状況では、自分で処理するしかなく、したがって実時間 (real) の増加として跳ね返ってきます。1 プロセスだけ実行してコマンドの実行が速く完了したから「速くなった」と結論をだすことは明らかに考察が足りず詰めが甘いと言わざるを得ません。

並列処理で CPU を効率的に使い切りたいのであれば、実時間 (real) だけを見るのではなく、マルチコア CPU の影に隠れている CPU 時間の増加 (user/sys) にも気を配らなければいけません。でなければ「CPU を使い切る」どころか、データ処理速度変わらないのに CPU 使用時間だけが多くなってしまう状況、つまり「CPU を使い潰す」ことになってしまいます。

「user+sys が多い方が並列化の効果が高い」は間違いである

こんな屁理屈があります。「user+sys が real を超えた状態というのは並列化された状態である。つまり CPU コアを複数使っていることを意味する。だから user+sys が多ければ多いほど並列化の効果が出ている。並列化されているのでパフォーマンスが高い。」どこがおかしいのかわかるでしょうか？

ここまでの話ですでに説明していることですが、基本的に user/sys は低ければ低いほど良いです。user/sys は無駄な処理をしても多くなります。user/sys が real を超えている時に並列化されているのは事実ですが、並列化された状態であっても user/sys が少ない方が良いことに変わりはありません。user/sys が real を超えているというのは単に「並列化されている」という事実があるだけで、効率よく CPU を使い切っているかどうかとは別問題です。**目的はパフォーマンスを上げることであって並列化する（CPU コアを多く）ことではありません。**並列化されたからといってパフォーマンスが上がったとは限りません。

正しい考え方を提示しましょう。**「user/sys が増えるということはパフォーマンスが下がるということである。しかしそれを効率よく複数コアの CPU に振り分けて real を減らすことができれば、複数の CPU コアを利用できる環境ではメリットになる可能性が高い。」**です。user/sys というコストを支払いどれだけ real を改善できるか、そのコスト対効果を見極めるのが並列化の効果を見極めるということです。効果 (real) だけを見ていてはダメでコスト (user/sys) は少ない方が良いのです。

パイプライン並列化はボトルネックとの戦い

パイプでつないだ全てのコマンドは同時に起動しますが、データが到着するまでは待ち状態になります。データの流れと同期して動いているため、前のコマンドからデータが届くまでは何もしておらず並列で実行され続けているとは限りません。パイプラインの非効率な使い方は、小さな処理しか行わない単純なコマンドをいくつもパイプでつないでしまうことです。小さな処理しか行わない部分がボトルネックになることはありません。ここでいうボトルネックとはデータ処理に時間がかかり入力が行われてから出力まで時間を要するコマンドのことです。次のコマンドにデータを送るまで時間がかかるので、その間に次のコマンドは早く処理が済んでしまい手が空いていてもデータが到着するまで何も出来ずに待ち状態になります。パイプライン全体の実行時間はボトルネックによって決まります。ボトルネックとなる遅いコマンドを改善しなければパイプライン全体の実行時間が短くなることはなく、小さな処理しか行わないコマンドをいくつもパイプでつないだ所でパイプ間通信やコマンドの処理で無駄に CPU 使用時間を増やしてしまうだけです。ようするに小さな処理しか行わないコマンドはまとめてしまいましょうという話です。

基本的に tr や grep の処理（の一部）は sed に置き換えることができます。複数の sed や grep は一つの sed や grep にまとめることが出来ます。そして複数の tr や grep や sed は一つの awk に置き換えることができます。置き換え先の言語は awk に限定する必要もなく Perl や Python などのスクリプト言語、C 言語や Go と言ったコンパイラ言語に置き換えることが出来ます。したがってパイプでつないだ複数のコマンドは一つのコマンドにまとめることが可能です。

まず全ての処理を一つのコマンドで行うとします。それがオーバーヘッドのない CPU 使用時間が一番少ない状態です。それをスタート地点とします。そして「パイプを使った並列処理を行うことで実時間を短くできればメリットではないか？」と考えましょう。1 つのコマンドを 2 つのコマンドに分ける段階では、効果の大小はともかく実時間は短くなりますが、それ以上に分ける場合はボトルネックになっている部分を探す必要があります。ボトルネックになってない所を分割しても実時間は短くならず、無駄に CPU 時間が増えるだけです。パフォーマンスチューニングは計測なしにやってはいけません。time コマンドの real/user/sys の全てを見てボトルネックになってる部分を調べるのが最初の一歩です。

もちろんすべてを一つのコマンドにしろという話ではありません。独立した「役割」の単位でコマンドを作成します。そうすると一つのパイプラインでは 3 〜 5 個ぐらいのコマンドをつなぐ程度に収まるでしょう。それが適切な目安であり、**何十個ものコマンドをパイプでつなぐのは明らかにアンチパターンです。**普通に作れば何十個もコマンドをパイプでつなぐような事にはならないと思いますが、そんな状態になるとしたらボトルネックになってない所まで小さなコマンドに分割してる場合ぐらいしか考えられず、無駄に CPU 使用時間を増やしているだけになっています。

パイプラインの「外部コマンドを起動するのは遅い」

この記事では詳しく扱いませんが、外部コマンドの起動は比較的重い処理です。またシェル関数であってもパイプでつなぐと一部の例外を除きサブシェルになってしまうため、これも重い処理となってしまいます。

実際にコマンドの起動にどれだけかかるかはコマンドと環境によりますが、何もしないコマンド（/bin/true） で 1 ms、awk だと 3 ms が起動するだけ（処理時間は含めていません）でかかるというのが私の感覚です。（内部的には fork 0.5 ms、exec 0.5 ms。サブシェルは fork だけなので 0.5 ms）

1 コマンドあたりの起動時間は数ミリ秒と短いですが、呼び出すコマンドの数が何十個にもなると、100 ms なんて簡単に超えてしまい、そのあたりから遅延を感じてきます。数百、数千回繰り返すループの中で頻繁に呼び出していると無視できないパフォーマンス問題を引き起こします。パイプラインだけではなく、例えばコマンド置換（ret=$(echo "$var" | sed ...) みたいなもの）のようにサブシェルや外部コマンド起動になるものをループの中で何度も実行してしまうのがシェルスクリプトを重くしてしまう一番の原因です。

シェルスクリプトで効率よく処理を行うにはストリーミング処理を意識した書き方やコマンド設計が必要となります。ストリーミング処理とは何なのかという話は別の記事で解説しようと思いますが、単にパイプでコマンドをつないでいればストリーミング処理をしていることになるわけではなく、ストリーミング処理を妨げる sort コマンドや、ストリーミング処理をバッチ処理に変換する xargs コマンドなどがあるので注意が必要です。ストリーミング処理を正しく理解することもシェルスクリプトで効率よく処理を行うための重要な考え方です。

多数のコマンドをパイプでつなぐと可読性が低くなる

これはパフォーマンスの話ではありませんが、多数のコマンドをパイプでつなぐと可読性が低くなるということに留意する必要があります。なぜこれを書くのかと言うと、この記事を読んで、CPU の最大性能を出すにはいろいろと考えなければいけないことはわかったけど、そこまで作り込むわけじゃないから「とりあえずパイプでつないで置けば良いんだよ」と考えてしまう人へに対しての警告です。とりあえずパイプでつないでしまうと可読性とメンテナンス性が下がってしまいます。

多数のコマンドをパイプでつなぐスタイル（≒ 作業をコマンド入力一撃で終わらせる）を、ここではシェル芸スタイルと呼ばさせていただきますが、そういうスタイルは可読性が低くなってしまいます。シェル上で実行するだけとか、使い捨てのスクリプトではシェル芸スタイルでも良いと思いますが、自分以外の人がレビューしたり将来メンテナンスする場合は可読性を考慮した書き方をしなければいけません。自分がメンテナンスする場合でもしばらく経ってからコードを見た時、そこで何をやってるのか？と悩まなければいけないコードはよくありません。

シェル芸はもともとスクリプトファイルにしない使い捨てのものだったはずです。後で読むことがないのだから可読性が低くても許されていましたがそれをスクリプトにしてはいけません。パイプで「多数のコマンドを」つなぐことにメリットがなく、可読性が低いというデメリットがあるのであれば、パイプでつなぐコマンドの数はそこそこにしておくのがベストなのです。詳しくは以下の記事を参考にしてください。

詳細な検証

検証スクリプトの説明

誰でも再検証しやすいように、ソースコードとデータをこのリポジトリにアップロードしています。実行時間の表示に bash ビルトインの time コマンド（表示のカスタマイズが可能でパイプライン全体やシェル関数の時間を計測できるなど高機能）を使用しているため bash が必要です。ただし macOS の古い bash は time コマンドにバグが有るようで CPU 使用率が正しく表示されません。Homebrew で新しい bash をインストールしてください。

検証スクリプトは awk で実装した JSON パーサーです。実行するとこのようなログが出力されます。

$ $ cat test.json | AWK=/usr/bin/original-awk ./parsejson.sh > /dev/null
bash version: 5.0.17(1)-release
awk: /usr/bin/original-awk

tokenize awk: real 0m4.773s  user 0m2.894s  sys 0m0.114s  cpu 63.02%
parse    awk: real 0m4.786s  user 0m4.241s  sys 0m0.544s  cpu 99.98%
---------------------------------------------------------------------------
         ALL: real 0m4.787s  user 0m7.135s  sys 0m0.659s  cpu 162.83%

環境変数 AWK で使用する awk の実装（パス）を指定することが出来ます。上記は Ubuntu で実行しています。original-awk というのは nawk (new awk または one true awk）のことです。Linux ではデフォルトで nawk が使われることはないと思いますが、macOS や FreeBSD や Unix などで広く使われています。説明の都合上 nawk の話から始めています。

JSON パーサーは大きく二つの部分で構成されています。一つは tokenizer (tokenize 関数) で JSON を構成するトークンに分割して一行ごとに出力します。例えばこのような JSON ファイルの場合、

{"menu": {
  "id": "file",
  "value": "File",
  "popup": {
    "menuitem": [
      {"value": "New", "onclick": "CreateNewDoc()"},
      {"value": "Open", "onclick": "OpenDoc()"},
      {"value": "Close", "onclick": "CloseDoc()"}
    ]
  }
}}

このように出力されます。JSON ファイルは改行区切りでない一行の JSON の可能性があることを踏まえて、" 区切りとして読み取ることで小さい単位でのストリーミング処理でのパースを実現しています。

{
"menu"
:
{
"id"
:
"file"
,
"value"
:
"File"
,
   ︙

もう一つは parser (parse 関数) で上記の入力を元に次のようにパースした JSON の結果を出力します。この出力は jsoncallbask.awk でカスタマイズすることが出来ます。

@ <=> {
@."menu" <=> {
@."menu"."id": "file"
@."menu"."value": "File"
@."menu"."popup" <=> {
@."menu"."popup"."menuitem" <=> [
@."menu"."popup"."menuitem".0 <=> {
@."menu"."popup"."menuitem".0."value": "New"
@."menu"."popup"."menuitem".0."onclick": "CreateNewDoc()"
@."menu"."popup"."menuitem".0 <=> }
@."menu"."popup"."menuitem".1 <=> {
@."menu"."popup"."menuitem".1."value": "Open"
@."menu"."popup"."menuitem".1."onclick": "OpenDoc()"
@."menu"."popup"."menuitem".1 <=> }
@."menu"."popup"."menuitem".2 <=> {
@."menu"."popup"."menuitem".2."value": "Close"
@."menu"."popup"."menuitem".2."onclick": "CloseDoc()"
@."menu"."popup"."menuitem".2 <=> }
@."menu"."popup"."menuitem" <=> ]
@."menu"."popup" <=> }
@."menu" <=> }
@ <=> }

その他のファイルは以下の通りです。今回の検証では parser 部分は変更せず tokenizer の実装のみを変更しています。

• parsejson.sh 検証スクリプト１（パイプを使わない tokenizer）
• parsejson_old.sh 検証スクリプト２（パイプを使う tokenizer）
• jsonparser.awk パーサー（共通）
• jsoncallbacks.awk 出力形式（共通）
• example.json サンプル JSON
• test.json 上記の example.json を 10 万回繰り返したもの
  • ./gentest.sh ./example.json 100000 > test.json で生成

tokenizer の違いを以下に示します。

tokenize() {
    awk 'BEGIN { RS="\""; flag = 0 }
    {
        if (match($0, /(^|[^\\])(\\\\)*\\$/)) {
            printf "%s\042", $0
            next
        }
        if (flag) {
            print "\042" $0 "\042"
        } else {
            gsub(/[ \r\n\t\v]/, "")
            gsub(/([][{}:,]|[^][{}:,]+)/, "&\n")
            printf "%s", $0
        }
        flag = !flag
    }'
}

tokenize() {
    tr -d '\r\n\t\v' | tr '"' '\n' | awk '
    {
        if (match($0, /(^|[^\\])(\\\\)*\\$/)) {
            printf "%s\042", $0
        } else {
            print $0
        }
    }' | awk '
    {
        if ((NR % 2) == 0) {
            print "\042" $0 "\042"
        } else {
            gsub(/[ \r\n\t\v]/, "")
            gsub(/([][{}:,]|[^][{}:,]+)/, "&\n")
            printf "%s", $0
        }
    }
    '
}

処理内容はほぼ同じですが、parsejson_old.sh を書いた時点では、awk が改行区切りではなく " 区切りで読み取れることに気づいておらず tr コマンドを使って前処理していたのに対して parsejson.sh では処理を改善し tr を不要にし、さらに ２ つに分けていた awk スクリプトも一つにマージすることでパイプ通信をなくしています。

要するに検証内容とは**「parsejson.sh （パイプを使わない 1 コマンドのtokenizer）」と「parsejson_old.sh （パイプを使う複数コマンドの tokenizer）」**の 2 つを比較した結果です。

time コマンドの出力の読み方

通常 time コマンドを実行した場合の出力は以下のようになりますが、検証スクリプトでは bash の TIMEFORMAT 変数をカスタマイズすることで読みやすくして CPU 使用率を追加しています。CPU 使用率は (user + sys) / real です。（man basn より「%P CPU のパーセンテージ。(%U + %S) / %R で算出されます。」）

# bash の場合
$ time sleep 1
real	0m1.008s
user	0m0.001s
sys	0m0.002s

# zsh の場合
$ time sleep 1
sleep 1  0.00s user 0.00s system 0% cpu 1.008 total

# POSIX 準拠の場合
$ /usr/bin/time -p sleep 1
real         1.00
user         0.00
sys          0.00

$ cat test.json | AWK=/usr/bin/original-awk ./parsejson.sh > /dev/null
bash version: 5.0.17(1)-release
awk: /usr/bin/original-awk

tokenize awk: real 0m4.773s  user 0m2.894s  sys 0m0.114s  cpu 63.02%
parse    awk: real 0m4.786s  user 0m4.241s  sys 0m0.544s  cpu 99.98%
---------------------------------------------------------------------------
         ALL: real 0m4.787s  user 0m7.135s  sys 0m0.659s  cpu 162.83%

補足 cat コマンドにかかる時間は（zsh での出力より） cat test.json 0.00s user 0.02s system 0% cpu 11.355 total 程度なので十分無視できるレベルです。また検証では共に cat を使ってデータをパイプで渡してるのでこの部分で差は生まれません。

上記の出力から以下のようなことを読み取ることが出来ます。

• parser は 1 CPU をほぼ 100% 使い切っている
• tokenizer は parser に比べて負荷が低い
• parser がボトルネックになっており tokenizer は CPU 100% 使い切れていない
• 実時間 (real) はおよそ 4.8 秒だが、実際に CPU を使用している時間 (user + sys) は 7.8 秒である。
• 全体で CPU を 1.6 個使用している

ちなみに検証環境は物理マシン上の Ubuntu 20.04 で CPU は Intel Core i7 3770 (3.4Ghz) で 4 コア（8 スレッド）のマシンで検証しています。

検証結果および結論

A. ボトルネックによりすべてのコマンドが 100% の速度で実行できることはまずない

「1コマンドのtokenizer」の結果はこのようになります。

$ cat test.json | AWK=/usr/bin/original-awk ./parsejson.sh > /dev/null
bash version: 5.0.17(1)-release
awk: /usr/bin/original-awk

tokenize awk: real 0m4.773s  user 0m2.894s  sys 0m0.114s  cpu 63.02%
parse    awk: real 0m4.786s  user 0m4.241s  sys 0m0.544s  cpu 99.98%
---------------------------------------------------------------------------
         ALL: real 0m4.787s  user 0m7.135s  sys 0m0.659s  cpu 162.83%

上記の結果より tokenizer は 63.02% の速度でしか実行できていません。parser の方がデータ処理速度が遅く tokenizer に何もせずに待っている時間が発生しているためです。処理速度が遅いコマンド、これがボトルネックです。入力となるデータ（test.json）はすでにあるのだから、そのデータを tokenizer は全力で処理してしまうのではないか？と思うかもしれませんが、パイプ間の通信にはパイプバッファ（Linux の場合は 64KB）が存在し、そのバファが溢れてしまうと、処理はブロックされてしまいます。つまり tokenizer はデータを処理し parser に渡しますが、parser の処理が遅いため、バッファサイズを超える所で、parser にちょっと待ってと言われて tokenizer の出力はバッファに空きができるまで一時停止させられてしまいます。

もし仮に parser の処理速度が十分早けば tokenizner は 4.773s * 0.6302 = 3.007s の時間で処理することが出来たでしょう。tokenizer の処理はパイプで入力したデータを計算して出力するだけでディスクアクセスやネットワークアクセスと言った I/O 待ちを行う処理がありません。そのため出力がブロックされなければ cpu を 100% 使い切ることが可能で、その場合の real は user + sys の値と等しくなります。

しかし、parser の方が速すぎる場合、今度は tokenizer からデータが届かずに parser 側が待つことになります。2 つのプロセスで CPU を完全に使い切るには、tokenizer と parser の処理時間を同じでなければなりません。しかし異なる処理をしていて都合よく同じ処理時間になることなんてまずありません。つまり各コマンドの処理速度が異なり待ち時間が発生するので**単純にパイプでつないでも CPU を使い切ることは出来ません。**ちなみにもう一つ小さな処理をするコマンドを追加しても空いている CPU を有効活用したりはしません。パイプでつないでいる以上データが届かない限り待つことしかできないのですから。

もう一つの検証スクリプトである「複数コマンドの tokenizer」の結果はこのようになります。

$ cat test.json | AWK=/usr/bin/original-awk ./parsejson_old.sh > /dev/null
bash version: 5.0.17(1)-release
awk: /usr/bin/original-awk

tokenize tr : real 0m4.795s  user 0m0.065s  sys 0m0.058s  cpu 2.57%
tokenize tr : real 0m4.809s  user 0m0.046s  sys 0m0.116s  cpu 3.37%
tokenize awk: real 0m4.824s  user 0m1.674s  sys 0m0.032s  cpu 35.36%
tokenize awk: real 0m4.837s  user 0m2.878s  sys 0m0.033s  cpu 60.18%
parse    awk: real 0m4.852s  user 0m4.311s  sys 0m0.536s  cpu 99.91%
---------------------------------------------------------------------------
         ALL: real 0m4.853s  user 0m8.977s  sys 0m0.778s  cpu 201.01%

ボトルネックは parser にあるので、それぞれのコマンドで待ち時間が発生しているということがわかります。また処理が軽いコマンドほど休んでいる時間が多い（CPU 使用率が少ない）こともわかります。

この結果から言えることは**「ボトルネックとなってるコマンドを分割しない限り実時間は短くならない」**ということです。しかしながらボトルネックとなってる parser はその処理内容から分割することは難しいです。

B. ボトルネックでない箇所を複数コマンドにしてパイプでつなげると実時間もCPU時間も遅くなる

先程の結果の再掲です。

$ cat test.json | AWK=/usr/bin/original-awk ./parsejson.sh > /dev/null
bash version: 5.0.17(1)-release
awk: /usr/bin/original-awk

tokenize awk: real 0m4.773s  user 0m2.894s  sys 0m0.114s  cpu 63.02%
parse    awk: real 0m4.786s  user 0m4.241s  sys 0m0.544s  cpu 99.98%
---------------------------------------------------------------------------
         ALL: real 0m4.787s  user 0m7.135s  sys 0m0.659s  cpu 162.83%

$ cat test.json | AWK=/usr/bin/original-awk ./parsejson_old.sh > /dev/null
bash version: 5.0.17(1)-release
awk: /usr/bin/original-awk

tokenize tr : real 0m4.795s  user 0m0.065s  sys 0m0.058s  cpu 2.57%
tokenize tr : real 0m4.809s  user 0m0.046s  sys 0m0.116s  cpu 3.37%
tokenize awk: real 0m4.824s  user 0m1.674s  sys 0m0.032s  cpu 35.36%
tokenize awk: real 0m4.837s  user 0m2.878s  sys 0m0.033s  cpu 60.18%
parse    awk: real 0m4.852s  user 0m4.311s  sys 0m0.536s  cpu 99.91%
---------------------------------------------------------------------------
         ALL: real 0m4.853s  user 0m8.977s  sys 0m0.778s  cpu 201.01%

複数のコマンドをパイプでつないだほうが、real、user、sys の全てが遅くなっていることがわかります。わずかな差であるため何回か実行すると誤差で逆転することが有るのですが基本的な傾向としてはこのようになります。

まず「複数コマンドのtokenizer」の方が user と sys が増えている理由は簡単です。一つのコマンドで行っていた処理を、複数のコマンドに分けるということは、その分パイプ間通信が行われるからです。パイプ間通信はシステムコールですのでその呼び出しで sys が増えます。またパイプで渡ってきた（およそ 24 MBの）データをそれぞれのコマンドが処理しますので、当然 user も増えてしまいます。これは**「処理を複数のコマンドに分けると各コマンドのデータ処理とパイプ間通信のオーバーヘッドで遅くなる」**という単純な話でしかありません。

問題は real も遅くなっている点です。その理由は CPU が 4 コアであるということです。ハイパースレッディングがあるため 8 コア相当に見えていますが、これは擬似的なもので実際の物理的な CPU コア数は 4 コアです。「複数コマンドのtokenizer」は全部で 5 プロセスを起動しているため 4 コアを超えます。そのため余った 1 プロセス分が parser を実行してるコアに溢れてきて結果、parser が遅くなっていると考えています。そのため 6 コアやそれより多くのCPU コアを搭載したシステムであれば実時間が長くなることはなかったでしょう。しかしそれもパイプでつないだコマンドの数次第です。コマンドを 10 個も 20 個もパイプでつないでいれば当然、それを超える CPU コアが必要になるのは言うまでもありませんし、少ないコアのシステムであれば実時間は更に遅くなります。

C. 多数のコマンドをパイプでつなぐと「CPUを使い切れず」に「CPUを無駄に使い潰す」

A. で私は「待ち時間があるため単純にパイプでつないでも CPU を使い切ることは出来ません」と書きました。改めてその結果を見てみましょう。

$ cat test.json | AWK=/usr/bin/original-awk ./parsejson.sh > /dev/null
   ︙
---------------------------------------------------------------------------
         ALL: real 0m4.787s  user 0m7.135s  sys 0m0.659s  cpu 162.83%

$ cat test.json | AWK=/usr/bin/original-awk ./parsejson_old.sh > /dev/null
   ︙
---------------------------------------------------------------------------
         ALL: real 0m4.853s  user 0m8.977s  sys 0m0.778s  cpu 201.01%

おや？パイプを使わない場合は CPU を 1.6 コア （162.83%) しか使えていませんが、複数のコマンドをパイプで繋いだら 2 コア（201.01%) 使えてますね？「よっしゃー、コマンドをパイプでつないだ方が CPU を使い切れてるぞー！」・・・ということにはなりませんね。処理してるデータ量は同じで実時間も殆ど変わらないのに CPU を多く使ってるのであれば、それは**「CPU を使い切る（＝効率よく使っている）」のではなく「CPU を無駄に使い潰してる」**だけです。本来他の用途で使えたはずの CPU をデータ処理とパイプ間通信で無駄に失っています。同じ仕事量であれば、少ない労力（CPU 使用率）で処理できた方が負荷が軽いというのは言うまでもありません。

CPU 使用率が多い理由を考えずに間違った理解をしてると「CPU 使用率が多い ＝ 余ってる CPU 使い切ってるから多数のコマンドをパイプでつなぐのは素晴らしい手法だ」なんて間違った結果になります。CPU を使い切るのに必要なのは CPU を休ませずに働かせることですが、無駄な仕事を増やして休みなく働かせたって生産性は上がらないでしょう？生産性を上げるのに必要なのは、無駄な仕事を増やすことではなく手が空いて休んでいる人がいないように仕事を均等に割り振ることです。

D. ボトルネックとなっている部分がどこであるか断定できない

「なに言ってるの？ parser 部分がボトルネックになってるという話をしてたじゃん？」

はい、そうですね。nawk (original-awk) の場合は parser 部分がボトルネックになっていました。実はこの話が今回 JSON パーサーの開発の話をネタにパイプ並列処理を記事を書くことにした一番の理由です。

これはシェルスクリプトによる開発の難しい所で sed や awK と言った外部のコマンドに依存しているので環境によって異なる実装を使う事があるということです。使用するコマンドの実装が変わればボトルネックになる部分も変わってしまう可能性があります。理論上はそうなるはずですが、それを実現する良い例を思いていませんでした。それを今回の JSON パーサーは運良く実現してくれました。

UNIX や macOS や FreeBSD などの nawk が使われている環境であれば、ここまでの話のように parser がボトルネックになっていましたが、Linux の場合 Debian 系では mawk、RedHat 系では gawk が使われています。それぞれの結果を見てみましょう。

$ cat test.json | AWK=/usr/bin/original-awk ./parsejson.sh > /dev/null
bash version: 5.0.17(1)-release
awk: /usr/bin/original-awk

tokenize awk: real 0m4.773s  user 0m2.894s  sys 0m0.114s  cpu 63.02%
parse    awk: real 0m4.786s  user 0m4.241s  sys 0m0.544s  cpu 99.98%
---------------------------------------------------------------------------
         ALL: real 0m4.787s  user 0m7.135s  sys 0m0.659s  cpu 162.83%

$ cat test.json | AWK=/usr/bin/mawk ./parsejson.sh > /dev/null
bash version: 5.0.17(1)-release
awk: /usr/bin/mawk

tokenize awk: real 0m2.376s  user 0m2.364s  sys 0m0.012s  cpu 100.00%
parse    awk: real 0m2.376s  user 0m1.410s  sys 0m0.033s  cpu 60.73%
---------------------------------------------------------------------------
         ALL: real 0m2.377s  user 0m3.776s  sys 0m0.045s  cpu 160.72%

$ cat test.json | AWK=/usr/bin/gawk ./parsejson.sh > /dev/null
bash version: 5.0.17(1)-release
awk: /usr/bin/gawk

tokenize awk: real 0m6.407s  user 0m6.395s  sys 0m0.012s  cpu 100.00%
parse    awk: real 0m6.408s  user 0m3.037s  sys 0m0.033s  cpu 47.91%
---------------------------------------------------------------------------
         ALL: real 0m6.409s  user 0m9.434s  sys 0m0.046s  cpu 147.91%

ここまでの話は、ボトルネックになっている parser を複数のコマンドに分割しなければ、実時間 (real) は改善しないといけないという話でしたが、mawk や gawk では逆で tokenizer の方を複数のコマンドに分割しなければいけません。適切でない方を複数のコマンドに分割しても実時間が短くなることはなく、ただ CPU 時間が増えてしまうだけでデメリットしかありません。つまり使用する環境やコマンドの実装を限定しなければパイプライン並列化で効率よく CPU を使うことはできません。

これはシェルスクリプトだけではなく他のプログラミング言語でもカーネルや言語や使用しているライブラリのバージョンが変わった時にボトルネックになる部分が変わると言う点では同じなのですが、他の言語では全く異なる実装を使うことは少ないので、そうそう大きく変わることなんてありません。しかしシェルスクリプトでは外部の依存関係が多くなりがちで環境によって変わる部分が多いので、別の OS に変更したりすると簡単に特性が変わってしまいます。

この記事の話と直接関係ありませんが、非常に重要なことは mawk がとても速いということです。つまり awk を使うシェルスクリプトのパフォーマンスを気にするのであれば mawk をインストールした環境を構築した方が良いということです。どの awk の実装でも動くように POSIX に準拠し移植性を重視するのは良い考えだと思いますが、パフォーマンスが重要になるシステムであれば、結局 mawk をインストールして使うべきという結論になるでしょう。mawk 自体がオープンソースで移植性が有る限り mawk に依存してもどの環境でも同じように動くソフトウェアは作れます。これはオープンソースである GNU のコマンドセットにも当てはまります。それらを**インストールすればよいだけなので、高い移植性を実現するために POSIX で規定されたコマンドとオプションだけを使って開発する必要はありません。**POSIX で規定されたコマンドとオプションだけを使わなければ互換性・移植性が確保できないという状況は、自由にソフトウェアをインストールすることができない環境に限った話です。

E. ボトルネックとなっている部分を改善すると実時間は短くなるが CPU 時間はやっぱり増える

さて、mawk と gawk では tokenizer がボトルネックになっていますので、こちらを複数のコマンドに分割することは実時間を短くする改善になります。ということでやってみましょう。

$ cat test.json | AWK=/usr/bin/mawk ./parsejson.sh > /dev/null
bash version: 5.0.17(1)-release
awk: /usr/bin/mawk

tokenize awk: real 0m2.376s  user 0m2.364s  sys 0m0.012s  cpu 100.00%
parse    awk: real 0m2.376s  user 0m1.410s  sys 0m0.033s  cpu 60.73%
---------------------------------------------------------------------------
         ALL: real 0m2.377s  user 0m3.776s  sys 0m0.045s  cpu 160.72%

$ cat test.json | AWK=/usr/bin/mawk ./parsejson_old.sh > /dev/null
bash version: 5.0.17(1)-release
awk: /usr/bin/mawk

tokenize tr : real 0m1.677s  user 0m0.072s  sys 0m0.011s  cpu 4.99%
tokenize tr : real 0m1.682s  user 0m0.028s  sys 0m0.065s  cpu 5.52%
tokenize awk: real 0m1.686s  user 0m0.972s  sys 0m0.023s  cpu 59.03%
tokenize awk: real 0m1.690s  user 0m1.673s  sys 0m0.016s  cpu 99.89%
parse    awk: real 0m1.692s  user 0m1.421s  sys 0m0.004s  cpu 84.23%
---------------------------------------------------------------------------
         ALL: real 0m1.693s  user 0m4.168s  sys 0m0.122s  cpu 253.44%

mawk では余っている CPU を活用することで 1.4 倍速くなりました。しかし CPU 時間は 1.16 倍に増えています。

$ cat test.json | AWK=/usr/bin/gawk ./parsejson.sh > /dev/null
bash version: 5.0.17(1)-release
awk: /usr/bin/gawk

tokenize awk: real 0m6.407s  user 0m6.395s  sys 0m0.012s  cpu 100.00%
parse    awk: real 0m6.408s  user 0m3.037s  sys 0m0.033s  cpu 47.91%
---------------------------------------------------------------------------
         ALL: real 0m6.409s  user 0m9.434s  sys 0m0.046s  cpu 147.91%

$ cat test.json | AWK=/usr/bin/gawk ./parsejson_old.sh > /dev/null
bash version: 5.0.17(1)-release
awk: /usr/bin/gawk

tokenize tr : real 0m5.108s  user 0m0.088s  sys 0m0.044s  cpu 2.57%
tokenize tr : real 0m5.123s  user 0m0.021s  sys 0m0.041s  cpu 1.21%
tokenize awk: real 0m5.139s  user 0m2.152s  sys 0m0.053s  cpu 42.90%
tokenize awk: real 0m5.153s  user 0m5.132s  sys 0m0.020s  cpu 99.99%
parse    awk: real 0m5.154s  user 0m2.954s  sys 0m0.039s  cpu 58.07%
---------------------------------------------------------------------------
         ALL: real 0m5.155s  user 0m10.351s  sys 0m0.197s  cpu 204.66%

gawk では余っている CPU を活用することで 1.24 倍速くなりました。しかし CPU 時間は 1.11 倍に増えています。

CPU 時間は増えていますが実時間が短くなっているので、一般的に考えれば、これは両方とも改善されていると言えるでしょう。ただし CPU が余っていればの話です。CPU が余っていない状況では両方とも実時間は逆に長くなります（F.に続く）。

F. ボトルネックの改善で実時間は短くなるが休んでいる CPU がなければ逆に長くなる

以下の multi.sh は同じスクリプトを並列で 10 個実行します。これにより休んでいる CPU をなくしてしまおうという話です。実際のユースケースでは xargs -P やバックグラウンドを使った並列化、ウェブシステム（CGI）のように同時アクセスが発生して、アクセス毎にコマンドが起動するような状況に相当します。

# mawk の場合

$ AWK=/usr/bin/mawk time -p ./multi.sh ./parsejson.sh
real 9.07
user 70.37
sys 0.95

$ AWK=/usr/bin/mawk time -p ./multi.sh ./parsejson_old.sh
real 9.36
user 72.36
sys 2.02

# gwak の場合

$ AWK=/usr/bin/gawk time -p ./multi.sh ./parsejson.sh
real 23.00
user 181.58
sys 1.57

$ AWK=/usr/bin/gawk time -p ./multi.sh ./parsejson_old.sh
real 24.33
user 191.26
sys 2.41

mawk と gawk では parsejson_old.sh の方が real は短かったはずですが上記の例では逆になっています。つまり CPU が余っていて、その余っている CPU に処理を振り分けられていたから real が短くなったのであって、CPU が余ってない状況下では、このようにパイプ間通信によるオーバーヘッドで real までもが悪くなってしまいます。

G. 複数プロセスで並列処理するならばパイプライン並列化にこだわる意味がない

A.でボトルネックによってパイプでコマンドをつないだだけでは CPU を使い切れることはないと書きました。では CPU を使い切るにはどうすればいいか？ですが、F.でやったようにプロセス（コマンド）を複数起動するプロセス単位の並列処理を使うことです。

パイプライン並列化の欠点は、スクリプトを修正することなく並列数を変更することが事実上不可能であるということです。CPU コアが多いシステムだから CPU を 32 コア使うようにしようと思っても、パイプでつなぐコマンドという処理内容を変えないことには不可能です。そのためシステムが持っている CPU を効率よく使い切ろうと思ったら、コマンドを複数起動するしかありません。

そしてコマンドを複数起動するのであればパイプライン並列化を行う意味がほとんどなくなります。ボトルネックを探して処理を複数のコマンドに分散させるよりも、もう一つ追加でコマンドを起動するほうが圧倒的に簡単だからです。そうなるとにパイプは単にオーバーヘッドを増やしてしまうだけでしかないので、パイプでつなぐコマンドの数は少ない方が効率的に CPU を使い切ることができるということになります。

H. 並列実行を妨げるコマンドがある

パイプラインでつないだコマンドは同時に起動しますが、同時にデータを処理しているとは限りません。あるコマンドは前のコマンドからデータが到着するまでは何もせず休んでいます。

そしてコマンドによってはデータをすべて読み込むまでは、次のコマンドにデータを渡さないコマンドがあります。その典型的なものが sort コマンドです。以下のようなコードを実行するとそれを確かめることができます。

まず sort コマンドがない場合は、このようにパイプでつないだコマンド（コード）の左右が並列で実行されていることがわかります。

$ for i in $(seq 5); do date +%s; sleep 1; done \
    | while read t; do date +"生成時間:$t 到着時間:%s"; done
生成時間:1639483922 到着時間:1639483922
生成時間:1639483923 到着時間:1639483923
生成時間:1639483924 到着時間:1639483924
生成時間:1639483925 到着時間:1639483925
生成時間:1639483926 到着時間:1639483926

# データの生成と同時に次のコマンドが並列で動作しているから
# 「生成時間」と「到着時間」が同じ

しかし、間に sort コマンドを入れると、すべてのデータの生成が終わってるから、まとめてデータを画面に出力します。

$ for i in $(seq 5); do date +%s; sleep 1; done \
    | sort | while read t; do date +"生成時間:$t 到着時間:%s"; done
生成時間:1639483972 到着時間:1639483977
生成時間:1639483973 到着時間:1639483977
生成時間:1639483974 到着時間:1639483977
生成時間:1639483975 到着時間:1639483977
生成時間:1639483976 到着時間:1639483977

# すべてのデータの生成を待ってから次のコマンドを実行するため
# 「到着時間」がすべて「生成時間」の後で同じ時間になっている

つまり、この場合パイプラインでつないだコマンドは全く並列処理されていません。その理由は sort コマンドが何をやっているか？を考えるとわかると思います。データのソートには全てのデータを受け取る必要があるので、全てのデータの入力が完了するまでは全く出力されないのです。**コマンドをパイプでつないだからといって必ずしも並列で動作するわけではありません。**このように出力がブロックされてしまうコマンドを間に入れてしまうと、その前後で並列化の効果が無くなってしまいます。（注意 並列動作をしないのはブロックするコマンドの前後です。ブロックするコマンドの前、もしくは後に「複数のコマンド」がある場合は「複数のコマンド」の中は並列動作を行います。つまりブロックするコマンドで分割して 2 つのパイプラインを実行するような形の動作です。）

同様のコマンドには xargs コマンドがあります。このコマンドも、標準入力で受け取ったデータを蓄えてからまとめて実行するものなので xargs コマンドの前と、xargs で呼び出すコマンドは並列動作しません。

$ for i in $(seq 5); do date +%s; sleep 1; done
    | xargs sh -c 'for t; do date +"生成時間:$t 到着時間:%s"; done' --
生成時間:1639481260 到着時間:1639481265
生成時間:1639481261 到着時間:1639481265
生成時間:1639481262 到着時間:1639481265
生成時間:1639481263 到着時間:1639481265
生成時間:1639481264 到着時間:1639481265

# データを全て生成してから、まとめてコマンドを呼び出すため
# 「到着時間」がすべて「生成時間」の後で同じ時間になっている

ただし -n 1 を指定した場合は並列で動作します。

$ for i in $(seq 5); do date +%s; sleep 1; done \
    | xargs -n 1 sh -c 'for t; do date +"生成時間:$t 到着時間:%s"; done' --
生成時間:1639481294 到着時間:1639481294
生成時間:1639481295 到着時間:1639481295
生成時間:1639481296 到着時間:1639481296
生成時間:1639481297 到着時間:1639481297
生成時間:1639481298 到着時間:1639481298

# データを生成するたびにコマンドを実行しているから
# 「生成時間」と「到着時間」が同じ

パイプを使うと並列で動作するという思い込みから、xargs を使って速くなるのも並列動作しているからだと勘違いしがちですが、実は xargs は並列動作を妨げるコマンドです。「外部コマンドを起動するのは遅い」という話を思い出してください。xargs が速くなる理由は並列処理とは無関係で、外部コマンドの呼び出し回数を減らせるのが高速化する理由です。また -n 1 を指定して一つずつコマンドを実行させると並列動作を行いますが、代わりにデータの数だけ外部コマンドを呼び出すことになるためパフォーマンスが低下します。必ずしも並列動作の方が良いとは限らず外部コマンドの起動コストがどれだけ大きいかがわかる例です。

I. データを絞り込むコマンドはパイプラインの始めの方に置いた方が良い

おそらくこれは誰もが直感でわかることだと思いますが、

• cat data.txt | sed 's/a/A/g' | grep 00
• cat data.txt | grep 00 | sed 's/a/A/g'

はどちらも同じ結果を返しますが、後者のほうが速いです。

$ time cat data.txt | sed 's/a/A/g' | grep 00 > /dev/null
bb64b259dce518c796bdcf8b8f94642e  -
real 0m0.496s  user 0m0.480s  sys 0m0.108s  cpu 118.55%

$ time cat data.txt | grep 00 | sed 's/a/A/g' > /dev/null
real 0m0.089s  user 0m0.083s  sys 0m0.044s  cpu 141.35%

理由は明らかですね。　多くのデータを sed してから必要なデータを絞り込むよりも、先に必要なデータを絞り込んでから sed した方が sed が処理するデータ量が減るからです。

余談ですが実はこれは私が新しい JSON パーサーを書いている理由の一つでもあります。コマンドラインで使える JSON パーサーに gron というコマンドがあります。「Make JSON greppable!」と書いてあることからもわかるように、このコマンドは JSON データを grep しやすい形式に変換します。

▶ gron testdata/two.json | grep likes | grep -v cheese
json.likes = [];
json.likes[0] = "code";
json.likes[2] = "meat";

このコマンドの問題点は、JSON データの量が多くなった時、grep する量も多くなってしまうという所です。データは少ない方が速いので、絞り込むコマンドは先に実行すべきですが、JSON データはそのままでは grep できません。先に gron で grep 可能なデータに変換するしかありませんが、そうすると全てのデータをパイプ間通信で grep に渡さねばならず・・・どちらが先かという鶏卵問題になってしまいます。

この問題の根本的な原因は、JSON データのパースと絞り込みを別々のコマンドに分けてしまったことにあります。私が開発している新しい JSON パーサーではこの二つを同時に行います。つまりパースしながら必要なものだけを加工しながらデータを出力するという仕組みです。これは awk と同じ考え方で、awk も正規表現にマッチした文字列に対して加工しながらデータを出力します。

使い慣れた grep を使えるのは便利かもしれませんが JSON の場合は指定したキーで抽出したいので、個人的には grep で絞り込みたいとは思わないんですよね。それに「絞り込んだ後、どうやって値を取り出すの？」という問題は解決してないので、JSON をパースした gron の出力結果をさらにパースしなければならず二重のパースが必要になります。

話を戻すと、一般的に絞り込みを行うコマンドは初めの方に置いた方が良いのですが、実は上の計測結果には納得できないところがあって、それは先にデータを絞り込んだ方が、後ろのコマンドは暇になって休んでいる時間が多くなる = CPU 使用率は減ると予測していたのですが、そうはなっていません。どうもこれは sed と greｐ の速度差からくるもののようです。

grep の代わりに sed を使って絞り込みを行った場合は、先に絞り込みを行ったほうが CPU 使用率は減りました。

$ time cat data.txt | sed 's/a/A/g' | sed -n '/00/p' > /dev/null
real 0m0.466s  user 0m0.552s  sys 0m0.159s  cpu 152.56%

$ time cat data.txt | sed -n '/00/p' | sed 's/a/A/g' > /dev/null
real 0m0.180s  user 0m0.164s  sys 0m0.079s  cpu 135.09%

コマンドの違いからくる速度差、シェルスクリプトで CPU を効率良く使うことはとても難しいです。

まとめ パイプライン並列化で CPU の最大効率を引き出すのは難しい

パイプライン並列化はコマンドをパイプでつなげるだけで、簡単に使える並列化手法です。しかしオーバーヘッドがあり普通につなげるだけでは CPU の最大性能を引き出すことは出来ません。コマンドを多くつなげるほどオーバーヘッドも多くなり逆に悪い結果になることすらあります。前提として以下の事実があります。

• コマンドが増えれば必ずオーバーヘッドで CPU 時間の総合計は増える
• ボトルネックとなる一番遅いコマンドよりも速くならない
• パイプ間通信にオーバーヘッドがある
• フィルタコマンドの処理もオーバーヘッドになる
• コマンド起動のオーバーヘッドもある
• パイプライン並列化では並列数を変更するのが困難
• コマンドはまとめた方がオーバーヘッドが減る
• 並列動作を妨げるコマンドがある

もしパイプライン並列化だけで CPU を使い切ろうとするならば以下のことに留意する必要があります。

• パイプでつないだコマンドの数は CPU コア数と同じにすること
• パイプでつないそれぞれのコマンドの処理速度を同じすること
• 並列動作を妨げるコマンドを使わないこと

現実には上記のことを達成するのは困難です。なぜなら処理内容を変えないことにはパイプでつなぐコマンドの数を変えられず、それぞれのコマンドで同じ処理をすることはないので処理速度を同じにすることはできず、同じコマンドでも実装によって処理速度が異なり、環境によって CPU コア数は違うからです。また次のような間接的な問題もあります。

• 1 コマンドで CPU 性能を使い切るのは正しいとはいえない（他の処理用に余力を残す）
• 多くのコマンドをつなぐスタイルは可読性が低くなる

そうなるとデータ並列化やタスク並列化と言った他の並列化技術を使う（併用する）しかないのでパイプライン並列化にこだわる理由はなくなります。もちろんデータ並列化やタスク並列化も万能の解決策ではなく、並列処理を行う前にデータを分割しなければいけない場合があったり、データの性質によってはデータ並列化やタスク並列化が使えないこともあります。そういった場合はパイプライン並列化が適切な場合もありますが、その場合でもちゃんと計測してボトルネックを調べてその部分を改善しなければ効果は全くありませんし逆効果にもなりえます。

結論としてはパイプライン並列化で CPU を効率よく使い切ることはかなり難しく、むやみにコマンドをつなぎすぎるのはデメリットの方が大きく、オーバーヘッドを減らすためにもパイプでつなぐコマンドの数は必要最小限（3 〜 5 程度）にとどめて他の並列化を併用した方が CPU を効率よく使い切ることができるということになります。

いずれにせよ、並列化のパフォーマンスを語るのであれば以下のことを心がけなければいけません。

• 銀の弾丸（万能の解決策）はないという言葉の通り、状況に応じて適切な方法を使うこと
• 実際のユースケースに近い状況でパフォーマンスの計測をすること
• real だけではなく user/sys を計測してどれだけ CPU コアを使用しているか把握すること

シェルスクリプトもプログラミング言語なので、その他の言語の技術が応用できます。シェルスクリプトだけの独自理論なんてものはないので、シェルスクリプトにないものは他の言語を参考にすべきです。シェルスクリプトに特化してパイプラインによる並列処理の話を詳しく書いているページは殆どありませんが、一般的なパイプライン並列化の特性はシェルスクリプトにも当てはまります。それらのいくつかを引用して最後にしたいと思います。

　パイプライン並列化では，個々のデータに対する処理にかかる時間そのものは変わりません。むしろ，並列化の負荷などで遅くなります。このため，xがIntのような組み込みの型の場合，この式のそれぞれの関数による処理を並列化したところで意味はありません。しかし，xがリストのような複数の値を持つデータ型だった場合はどうでしょうか？ 関数f，g，hは流れ作業的にそれぞれの処理するべき値が来たところで適宜処理を行うことができるため，それぞれの関数の処理を並列化すれば全体的な処理能力（throughput，スループット）を向上させることができます。

　当然ながら，それぞれに処理にかかる時間に偏りがある場合には，処理に一番時間がかかる部分がボトルネック（bottleneck）になってしまいます。パイプライン並列化は，関数プログラミングのスタイルに一番近いため，一見使いやすそうに見えます。が，性能を出すためにはパイプラインのそれぞれの段（stage，ステージ）の処理時間ができるだけ均等になるよう工夫する必要があります。

優れた並列パフォーマンスを達成するには、アプリケーションが適切な粒度を持つことが重要です。粒度とは、並列タスクにおける実際の処理量を指します。粒度が細かすぎると通信オーバーヘッドによってパフォーマンスが損なわれ、粒度が粗すぎるとロード・インバランスによってパフォーマンスが損なわれます。ロード・インバランスと通信オーバーヘッドを回避しつつ、並列タスクに適切な粒度 (一般に大きいほど良い) を見極めて、優れたパフォーマンスを達成するようにします。

神戸大学大学院システム情報学研究科 計算科学演習I　第5回講義「並列計算とは」

適用に当たっての注意
プロセッサの利用効率を上げるには，パイプラインの各処理の実行時間をほぼ同じにする必要あり
パイプライン型並列化では，データ処理のスループットは向上するが，1個のデータに対する処理時間は短縮されないことに注意