パイプを使って高速化したシェルスクリプトを並列実行すると逆に遅くなる謎現象について

はじめに

パイプを使って高速化したシェルスクリプトを、多数並列に実行するとパイプを使わない場合より遅くなります。なぜでしょうか？

2021-12-16 追記

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

おはなし

（つまらない話を読みたくない人はまとめへどうぞ）

ある日たかしくん（仮名）は、awk を駆使して巨大なログファイルの中に記録された IP アドレスの一覧を作るスクリプトを書いていました。

注意 ログは ifconfig の実行結果をコピーして 100 万行 ぐらいにしたものを使っています。実際の所どんな処理をするかは関係ありません。ベンチマークには hyperfine を使用しています。

no-pipe.sh

#!/bin/sh
cat list.txt |
mawk '
  /^[[:space:]]*inet6?/{
    sub(/[[:space:]]*/, "")
    sub(/^inet6?[[:space:]]+/, "")
    sub(/[[:space:]].*/, "")
    print
  }
'

実行結果は 260.4 ミリ秒でした。

Benchmark #1: ./no-pipe.sh
  Time (mean ± σ):     260.4 ms ±  26.0 ms    [User: 248.9 ms, System: 34.1 ms]
  Range (min … max):   233.3 ms … 307.3 ms    10 runs

たかしくん「これもっと速くできないかなぁ？」

たかしくんは、コマンドをパイプでつなげると速くなるという話をどこかで聞いてきました。そこで処理を細切れにしてパイプでつないでみました。

use-pipe.sh

#!/bin/sh
cat list.txt |
mawk '/^[[:space:]]*inet6?/{ print }' |               # grep 相当
mawk '{ sub(/[[:space:]]*/, ""); print }' |           # sed 相当
mawk '{ sub(/^inet6?[[:space:]]+/, ""); print }' |    # sed 相当
mawk '{ sub(/[[:space:]].*/, ""); print }'            # sed 相当

実行結果は約 1.7 倍、151.1 ミリ秒に向上しました。

Benchmark #2: ./use-pipe.sh
  Time (mean ± σ):     151.1 ms ±  22.6 ms    [User: 357.9 ms, System: 86.6 ms]
  Range (min … max):   119.4 ms … 194.8 ms    24 runs

たかしくん「すごいや！噂は本当だったんだ！ コマンドをパイプでつなぐスタイルに変えると処理速度が速くなるぞ！」

たかしくんはパイプの力を盲信し、すべてのスクリプトを小さな処理をするコマンドをパイプで多数つなげるスタイルに書き換えました。

実はこのシェルスクリプトはウェブシステムで動かすシェルスクリプトでした。同時アクセスの数だけ並列で実行することになります。たかしくんは以下ようなシェルスクリプトを作って並列実行の実験をしてみました。

multi.sh

#!/bin/sh
for i in $(seq "$1"); do
  "$2" &
done
wait

たかしくん「あれれー？」

$ hyperfine "./multi.sh 10 ./no-pipe.sh" "./multi.sh 10 ./use-pipe.sh"
Benchmark #1: ./multi.sh 10 ./no-pipe.sh
  Time (mean ± σ):     668.9 ms ±  14.2 ms    [User: 4.085 s, System: 0.629 s]
  Range (min … max):   652.7 ms … 697.5 ms    10 runs

Benchmark #2: ./multi.sh 10 ./use-pipe.sh
  Time (mean ± σ):     847.9 ms ±  14.2 ms    [User: 5.084 s, System: 1.497 s]
  Range (min … max):   829.6 ms … 879.1 ms    10 runs

なんと同時に並列（同時 10 並列）でシェルスクリプトを実行すると、逆にコマンドをパイプでつなげたほうが 1.2 倍遅くなってしまったのです。

たかしくん「へんだなー？最初はコマンドをパイプでつなげたほうが速かったのに？」

信じられない結果に戸惑いながらも、同時 100 並列で実験してみました。

$ hyperfine "./multi.sh 100 ./no-pipe.sh" "./multi.sh 100 ./use-pipe.sh"
Benchmark #1: ./multi.sh 100 ./no-pipe.sh
  Time (mean ± σ):      6.168 s ±  0.014 s    [User: 42.603 s, System: 6.420 s]
  Range (min … max):    6.152 s …  6.200 s    10 runs

Benchmark #2: ./multi.sh 100 ./use-pipe.sh
  Time (mean ± σ):      8.488 s ±  0.156 s    [User: 52.661 s, System: 14.954 s]
  Range (min … max):    8.329 s …  8.761 s    10 runs

たかしくん「えぇー？どうしてぇー？」

なんと今度は 1.4 倍に遅くなってしまいました。実はこのシェルスクリプトを動かすシステムは 多数の同時アクセス数がある大規模ウェブシステムだったのです。たかしくんは同時 1000 並列実行で実験してみました。

$ hyperfine "./multi.sh 1000 ./no-pipe.sh" "./multi.sh 1000 ./use-pipe.sh"
Benchmark #1: ./multi.sh 1000 ./no-pipe.sh
  Time (mean ± σ):     64.903 s ±  1.511 s    [User: 447.517 s, System: 70.641 s]
  Range (min … max):   61.663 s … 66.072 s    10 runs

Benchmark #2: ./multi.sh 1000 ./use-pipe.sh
  Time (mean ± σ):     112.119 s ±  0.356 s    [User: 596.080 s, System: 299.422 s]
  Range (min … max):   111.571 s … 112.572 s    10 runs

たかしくん「・・・」

コマンドをパイプでつなげたほうが 1.7 倍遅くなりました。並列数を増やせば増やすほどコマンドをパイプでつないだ方が遅くなるという結果にたかしくんは絶望してしまいました。

さて彼は並列プログラミングに関して一体どんな勘違いしていたのでしょうか？

まとめ

おはなし（茶番）の内容をまとめるとこういうことです。

1. 同じ処理を行う ２つのスクリプト no-pipe.sh と use-pipe.sh を作って実行した
   ・no-pipe.sh は 1 つの mawk ですべての処理を行う
   ・use-pipe.sh は 4 つの mawk で分けて処理を行う（処理結果はパイプを使って渡す）
   ・use-pipe.sh の方が早く処理が完了した（0.6倍）
2. no-pipe.sh と use-pipe.sh 共に 10 個並列で実行した
   ・use-pipe.sh の方が遅くなった（1.2倍）
3. 同じく、共に 100 個並列で実行したら use-pipe.sh の方がさらに遅くなった（1.4倍）
4. 同じく、共に 1000 個並列で実行したら use-pipe.sh の方がもっと遅くなった（1.7倍）

並列数が少ないときはパイプを使った方が速かったのに、並列数が多いと逆に遅くなった。ということです。

さいごに

分かる人にはすぐ分かる謎ですね。ヒントは記事の中にあります。分かる人にはあたりまえやんって思うかもしれませんが、あることを見逃してしまうと結論を間違えてしまい、小さい規模での実験結果が大規模な事例にもそのまま当てはまると思い込んでしまいます。シェルスクリプトを大規模なシステムに適用すると失敗する原因の一つです。データは正しく読み取らねばいけません。

この話に関する記事やシェルスクリプトにおける並列プログラミングの記事を途中まで書いてたりするんですが、力尽きたので導入編ということで「事実」だけを公開してみることにしました。続きはそのうち書くことにします。私からはまだ答えは言いませんが、もし興味がある人がいればこの記事のコメント欄にでも予想を書き込んでください。できれば多くの人に興味を持ってもらって、この事実を検証・議論して欲しいのです。見落としている点だけじゃなくて、何が原因でそうなるのか？ということをです。ちなみにその原因をメインテーマとした記事は私はまだ書いていません。

あと安心してください。シェルスクリプトやパイプを使うなと言う話ではありませんから。適材適所、シェルスクリプトやパイプは万能のテクニックではない。シェルスクリプトが苦手な分野にシェルスクリプトを使うな。場合に応じて適切な方法で実装しろ。ソフトウェア技術の基礎を勉強しろ。ろくに検証もせずにデタラメな話を広めるな。言いたいのはそれだけです。

それにしても mawk 速いですね。awk は POSIX で標準化されている上に、1 コマンドで「データの絞り込み」と「欲しい形式へのデータ加工」の両方ができる万能の手続き型プログラミング言語ですし、これで全部やれば実は grep や sed っていらないんじゃ？