シェルスクリプトでファイルを一行ずつreadする処理を高速化するテクニック

期待してる人ががっかりしないように、最初に結論を書いておくと dash、busybox (ash)、mksh、yash、zshにおいて読み込み速度は大幅に速くなりますが **bash においては変わりません。**ただしは使用メモリが減ります。kshは少し速くなりますが逆に使用メモリは大幅に増えます。シェルスクリプトでの読み込み速度を上げるもので、他の言語を使ったりコマンドを呼び出すよりも速くなるわけではありません。

シェルスクリプトでファイルを一行ごとに読み込む時、一般に使われているのは `read` 関数です。ですが、この `read` 関数、遅いというわさを聞きました。たしかに一行毎ずつ読み込むのですから `cat` を使ってファイル全体を読み込むのに比べれば遅いでしょうが、そのままでは一行ずつ処理をすることは出来ません。

さて一行ずつ処理したい場合に使えるのは `read` 以外どのような方法があるでしょうか？一つは、`for` を使います。`cat`でファイル全体を読み取った後、`IFS`を使って改行区切りで位置パラメータ `$@` に `set` します。ただしこの方法は改行が複数連続する場合は一つとみなされるので厳密には異なります。ですが改行のみの行は無視したいという要件は比較的あると思うので使えないということにはならないでしょう。

もう一つは、bash 専用の `readarray` とzsh専用の `mapfile` を使います。`readarray` は `mapfile` という別名でも使えるのですが、ややこしいのでこの記事では bash 用を `readarray`、zsh 用を `mapfile` と呼びます。

さて、まずは計測です。一行100文字×10万行（およそ10MB）のファイルを処理します。メモリ使用量はスクリプトの最後で `ps axu` して RSS の値を書いているだけです。計測対象のシェルは面倒なので dash, bash, ksh, zsh の4つに絞ります。

```sh
use_cat() { # 参考
  data=$(cat ./data.txt)
}

use_read() {
  while IFS= read -r line; do i=$((i+1)); done <./data.txt
}

use_for() {
  [ "$ZSH_VERSION" ] && setopt shwordsplit
  data=$(cat ./data.txt)
  IFS=$(printf '\n_') && IFS=${IFS%_}
  for line in $data; do i=$((i+1)); done
}

for_loop() { for line in $data; do i=$((i+1)); done; }
use_for_loop() {
  [ "$ZSH_VERSION" ] && setopt shwordsplit
  data=$(cat ./data.txt)
  IFS=$(printf '\n_') && IFS=${IFS%_}
  set -- $data
  for_loop "$@"
}

use_readarray() {
  readarray -t lines < ./data.txt
  for line in "${lines[@]}"; do i=$((i+1)); done
}

use_mapfile() {
  zmodload zsh/mapfile
  lines=("${(f)mapfile[./data.txt]}")
  for line in "${lines[@]}"; do i=$((i+1)); done
}

mapfile_loop() { for line in "${lines[@]}"; do i=$((i+1)); done; }
use_mapfile() {
  zmodload zsh/mapfile
  lines=("${(f)mapfile[./data.txt]}")
  mapfile_loop
}
```

|                | dash               | bash                | ksh                | zsh                |
| -------------- | ------------------ | ------------------- | ------------------ | ------------------ |
| cat (参考)     | 0.083s : 11,656 KB | 0.127s :  22,796 KB | 0.046s : 23,492 KB | 0.103s : 13,676 KB |
| read           | 5.173s :    800 KB | 0.979s :   3,344 KB | 0.488s :  3,876 KB | 5.853s :  4,088 KB |
| for            | 0.198s : 11,600 KB | 0.552s :  40,072 KB | 0.314s : 27,908 KB | 0.903s : 14,204 KB |
| for + loop     | 0.359s : 46,844 KB | 1.065s : 155,688 KB | 0.640s : 66,980 KB | 1.104s : 35,756 KB |
| readarray      | -                  | 0.812s :  72,068 KB | -                  | -                  |
| mapfile        | -                  | -                   | -                  | 0.425s : 15,836 KB |
| mapfile + loop | -                  | -                   | -                  | 0.431s : 15,708 KB |

やはり `read` は遅いですね・・・と思いましたが `bash`、`ksh` は結構善戦しているようです。（※ bash 2.03 では8秒ぐらいかかりましたが 2.05a 以降は大差ありません）`readarray`、`mapfile` は特定のシェルに専用の機能であるいう点が問題なければ速いです。

メモリ使用量に関しては当然といえば当然ですが、一行のみ読み込む `read` が圧倒的に少なく、その他はファイルすべてを読み込んでいるためメモリ使用量は多くなります。

`for + loop`, `mapfile + loop` に関しては次の項目で説明します。今はそういう書き方をしてもさほど変わらないと思っていて下さい。

参考ですが、他のコマンドを使用した場合はこのとおりです。

|                                                 | time   |
| ----------------------------------------------- | ------ |
| `wc -l`                                         | 0.006s |
| `awk 'BEGIN{i=0}{i++} END{print i}' ./data.txt` | 0.014s |
| `sed -n '' ./data.txt`                          | 0.015s |
| `sed -n 's/^/_/g' ./data.txt`                   | 0.021s |

圧倒的ですね。他のコマンドで処理が完結できる場合はその方がいいでしょう。

## ループの中の処理を関数化する

さて、この処理を改善する方法はないでしょうか？・・・の前に、先程のコードはループの中で直接カウントをしていました。コードの可読性、テスト容易性を上げるために、一行を処理する関数にしたいというのはよくある話だと思います。ということで先程のコードを次のようにカウントする関数を呼び出すように変更してみます。

```sh
count() { i=$((i+1)); }

use_read() {
  while IFS= read -r line; do count "$line"; done <./data.txt
}

use_for() {
  [ "$ZSH_VERSION" ] && setopt shwordsplit
  data=$(cat ./data.txt)
  IFS=$(printf '\n_') && IFS=${IFS%_}
  for line in $data; do count "$line"; done
}

for_loop() { for line in "$@"; do count "$line"; done; }
use_for_loop() {
  [ "$ZSH_VERSION" ] && setopt shwordsplit
  data=$(cat ./data.txt)
  IFS=$(printf '\n_') && IFS=${IFS%_}
  set -- $data
  for_loop "$@"
}

use_readarray() {
  readarray -t lines < ./data.txt
  for line in "${lines[@]}"; do count "$line"; done
}

use_mapfile() {
  zmodload zsh/mapfile
  lines=("${(f)mapfile[./data.txt]}")
  for line in "${lines[@]}"; do count "$line"; done
}

mapfile_loop() { for line in "${lines[@]}"; do count "$line"; done; }
use_mapfile() {
  zmodload zsh/mapfile
  lines=("${(f)mapfile[./data.txt]}")
  mapfile_loop
}
```

|                        | dash               | bash                | ksh                | zsh                     |
| ---------------------- | ------------------ | ------------------- | ------------------ | ----------------------- |
| read                   | 5.173s :    800 KB | 0.979s :   3,344 KB | 0.488s :  3,876 KB | 5.853s      :  4,088 KB |
| read + count           | 5.211s :  2,600 KB | 1.580s :  10,500 KB | 0.909s :  3,996 KB | 7.246s      :  3,980 KB |
| for                    | 0.198s : 11,600 KB | 0.552s :  40,072 KB | 0.314s : 27,908 KB | 0.903s      : 14,204 KB |
| for + loop             | 0.359s : 46,844 KB | 1.065s : 155,688 KB | 0.640s : 66,980 KB | 1.104s      : 35,756 KB |
| for + count            | 0.261s : 11,668 KB | 1.140s :  39,948 KB | 0.709s : 28,308 KB | **87.674s** : 22,100 KB |
| for + loop + count     | 0.425s : 46,868 KB | 1.627s : 155,760 KB | 1.013s : 75,276 KB | **5.585s**  : 35,704 KB |
| readarray              | -                  | 0.812s :  72,068 KB | -                  | -                       |
| readarray + count      | -                  | 1.381s :  79,316 KB | -                  | -                       |
| mapfile                | -                  | -                   | -                  | 0.425s      : 15,836 KB |
| mapfile + loop         | -                  | -                   | -                  | 0.431s      : 15,708 KB |
| mapfile + count        | -                  | -                   | -                  | **9.003s**  : 15,704 KB |
| mapfile + loop + count | -                  | -                   | -                  | **2.913s**  : 23,696 KB |

関数呼び出しのオーバーヘッドがあるため、どれもわずかに処理時間が伸びてますね。・・・わずか？はい、おかしいところが二箇所あります。それは zsh の `for` と `mapfile` です。関数呼び出しのオーバーヘッドとは思えないほど時間が伸びています。しかし、`for + loop`, `mapfile + loop` のように関数を一つ間に入れるだけでその処理時間は大きく下がります。理由はかなり推測ですが、[別記事](https://qiita.com/ko1nksm/items/c89a12c3d3a26bc38803)にまとめました。

## 改善方法

さてこれを改善する方法はないでしょうか？実行速度もですがメモリ使用量も改善したいところです。ここでよくシェルスクリプトに awk のコードを埋め込んで awk で処理を実装するテクニックが紹介されるのですが、そうすると二つの言語を使うことになります。また別のプロセスですから、awk とシェルスクリプトの関数や変数は相互にアクセスすることが出来ません。処理速度だけを見ると awk が良いとは思いますが開発が面倒になります。

速度も速くメモリも使用せず、シェルスクリプトで処理を行う方法。実はあります。

```sh
count() { i=$((i+1)); }

use_callback1() {
  eval "$(sed "s/'/'\"'\"'/g; s/^/count '/; s/$/'/" ./data.txt)"
}

use_callback2() {
  sed "s/'/'\"'\"'/g; s/^/count '/; s/$/'/" ./data.txt > ./data.sh
  . ./data.sh
  rm ./data.sh
}
```

|                      | dash                   | bash                    | ksh                    | zsh                       |
| -------------------- | ---------------------- | ----------------------- | ---------------------- | ------------------------- |
| callback1 + count    | 0.266s   :  2,600 KB   | 1.685s   :  46,588 KB   | 0.829s   : 71,456 KB   | 63.002s     :  4,016 KB   |
| callback2 + count    | **0.243s :    724 KB** | **1.526s :   3,572 KB** | **0.685s : 52,460 KB** | **1.692s    :  3,900 KB** |
| read                 | 5.173s   :    800 KB   | 0.979s   :   3,344 KB   | 0.488s   :  3,876 KB   | 5.853s      :  4,088 KB   |
| read + count         | **5.211s :  2,600 KB** | **1.580s :  10,500 KB** | **0.909s :  3,996 KB** | **7.246s    :  3,980 KB** |
| for                  | 0.198s   : 11,600 KB   | 0.552s   :  40,072 KB   | 0.314s   : 27,908 KB   | 0.903s      : 14,204 KB   |
| for + count          | 0.261s   : 11,668 KB   | 1.140s   :  39,948 KB   | 0.709s   : 28,308 KB   | **87.674s** : 22,100 KB   |
| for + loop + count   | 0.425s   : 46,868 KB   | 1.627s   : 155,760 KB   | 1.013s   : 75,276 KB   | 5.585s      : 35,704 KB   |
| readarray            | -                      | 0.812s   :  72,068 KB   | -                      | -                         |
| readarray + count    | -                      | 1.381s   :  79,316 KB   | -                      | -                         |
| mapfile              | -                      | -                       | -                      | 0.425s      : 15,836 KB   |
| mapfile+loop + count | -                      | -                       | -                      | 2.913s      : 23,696 KB   |

仕組みとしては、データを `sed` を使用して、一行を引数として `count` 関数を呼び出すシェルスクリプト（`count '一行のデータ'`）に変換します。（シングルクォートはエスケープしています。）この変換にかかる時間は、0.05s ほどなので無視できるレベルです。そして変換されたシェルスクリプトを実行します。知っている人なら JSONP と似たような仕組みといえば理解しやすいと思います。`read` 関数の読み込みの遅さをシェルのソースコード読み込み速度に置き換えているわけです。`sed` を使用してはいますが、メインの処理を `sed` でやるわけではなく単に関数呼び出しのシェルスクリプトに変換してるだけで汎用的に使えます。

改善されている項目について見ていきます。まず dash と zsh において大きく速度が改善されています。zsh は巨大な文字列の `eval` が苦手のようで一旦別のファイルに出力してから `.` コマンドで読み取ったほうが速い（`callback1` より `callback2` の方が速い）です。ksh はメモリ使用量が多いので少し残念ですね。コードがそのままメモリに残っているように思えます。

全てにおいて最速という訳ではありませんがバランスに優れています。また忘れてはいけないもう一つのメリットは、この方法は `read` と同じようにデータを一行処理できるところです。データが全て揃うまで待つ必要はなく非同期で動作させることが出来ます。

`callback1` は `eval` を使用するため、全てをメモリに読み込みますが、以下のように FIFO ファイルを使うことで、データ生成 (+ `sed`) と `.` によるデータ読み込みを並列化することができます。また、シェルは `echo 'echo test' | sh` のように標準入力からソースコードを入力することができるので、データを生成するプロセスとデータを処理するプロセスを分けることができるなら、この方法でも同じように並列化が可能です。

FIFO を使用した並列化

```sh
use_callback3() {
  mkfifo ./fifo
  sed "s/'/'\"'\"'/g; s/^/count '/; s/$/'/" ./data.txt > ./fifo &
  . ./fifo
  rm ./fifo
  wait $!
}
```

また、ついでに `eval` によるパフォーマンス低下がどれくらいかも計測してみます。

```sh
use_callback4() {
  mkfifo ./fifo
  sed "s/'/'\"'\"'/g; s/^/eval count '/; s/$/'/" ./data.txt > ./fifo &
  . ./fifo
  rm ./fifo
  wait $!
}
```

最後なので他のシェルの計測結果も加えます。

|                   | dash               | bash               | busybox ash       | ksh                | mksh              | yash                | zsh                |
| ----------------- | ------------------ | ------------------ | ----------------- | ------------------ | ----------------- | ------------------- | ------------------ |
| read + count      | 5.211s :  2,600 KB | 1.580s : 10,500 KB | 9.151s :     4 KB | 0.909s :  3,996 KB | 5.467s :   932 KB | 12.129s :  1,248 KB | 7.246s  : 3,980 KB |
| callback1 + count | 0.266s :  2,600 KB | 1.685s : 46,588 KB | 0.936s : 1,660 KB | 0.829s : 71,456 KB | 0.599s : 1,812 KB | 1.371s  : 28,188 KB | 63.002s : 4,016 KB |
| callback2 + count | 0.243s :    724 KB | 1.526s :  3,572 KB | 0.929s : 1,572 KB | 0.685s : 52,460 KB | 0.636s : 1,944 KB | 1.138s  :  2,900 KB | 1.692s  : 3,900 KB |
| callback3 + count | 0.195s :    736 KB | 1.562s :  3,332 KB | 0.484s : 1,636 KB | 0.646s : 52,360 KB | 0.552s : 2,756 KB | 1.106s  :  2,828 KB | 1.777s  : 4,120 KB |
| callback4 + count | 0.464s :  2,600 KB | 3.345s :  3,512 KB | 0.896s : 1,640 KB | 1.376s : 56,624 KB | 1.309s : 1,840 KB | 2.464s  :  2,948 KB | 2.383s  : 4,104 KB |

busybox の結果が特徴的ですね。少メモリの組み込みデバイスに特化していると思われます。`callback3` と `callback4` の差から `eval` によって倍ぐらい時間がかかるようですが、10万回でこの程度なので私はあまり気にせず使っています。

## さいごに

ということで `read` 処理を高速化するテクニックでした。まあそもそもシェルスクリプトでこんな大量のデータを扱う人もいないとは思いますが。実装は簡単なので気が向いたらライブラリ化するかもしれません。