シェルスクリプトで高速にファイル全体を読み込む方法

## はじめに

シェルスクリプトでデータを処理する場合、通常は一行一行処理していくので、ファイル全体をメモリ（一つの変数）に読み込むことはあまりないのですが何にでも例外はあります。ファイル全体をメモリに読み込むには一般的には `cat` を使うのが高速です。しかしながら数行程度の小さいファイルを読み込む場合は `read` でループを使って全行読み込んだ方が高速になります。これは `cat` が外部コマンドであるため使用するたびに新たにプロセスの起動が行われるのに対して、 `read` はシェルビルトインコマンドなのでそれが不要だからです。まず `cat` と `read` でどれだけ違うかを見てみましょう。

※ この記事で使用しているデータは1行100文字のファイルで `base64 -w 100 /dev/urandom | head -n 行数` で生成しています。また `sh` と書いている所は dash で `ash` と書いてある所は busybox ash です。

```sh:cat.sh
for i in $(seq ${2:-10000}); do
  # echo _ はファイル末尾の改行を削除されないようにするためです
  # この処理で 20% ～ 50% 程度遅くなってしまうのですが
  # この記事では原則としてファイル内容をあるがまま読み込むものとします
  data=$(cat "$1"; echo _)
  data=${data%_}
done
```

```sh:read.sh
LF="
"
for i in $(seq ${2:-10000}); do
  data=''
  while IFS= read -r line; do
    data="${data}${line}${LF}"
  done < "$1"
  data="${data}${line}" # 最終行に改行がない場合の処理です
done
```

1行のファイル読み込みを1万回繰り返した場合

```
cat.sh:
sh  : real 18.56 user 13.66 sys 4.84
bash: real 28.77 user 21.02 sys 8.50
ksh : real 15.38 user 11.20 sys 4.55
mksh: real 5.94 user 4.46 sys 1.89
posh: real 23.94 user 17.93 sys 6.97
yash: real 27.65 user 20.45 sys 9.02
zsh : real 30.58 user 22.08 sys 10.69
ash : real 21.13 user 16.07 sys 6.41

read.sh:
sh  : real 1.51 user 0.74 sys 0.76
bash: real 0.62 user 0.50 sys 0.12
ksh : real 0.45 user 0.34 sys 0.11
mksh: real 1.59 user 0.88 sys 0.70
posh: real 0.34 user 0.27 sys 0.07
yash: real 3.40 user 2.01 sys 1.38
zsh : real 1.90 user 1.16 sys 0.74
ash : real 2.63 user 1.57 sys 1.05
```

1万行のファイル読み込みを1回だけ行った場合

```
cat.sh:
sh  : real 0.02 user 0.02 sys 0.00
bash: real 0.06 user 0.03 sys 0.02
ksh : real 0.03 user 0.03 sys 0.00
mksh: real 0.03 user 0.03 sys 0.00
posh: real 0.05 user 0.06 sys 0.00
yash: real 0.08 user 0.08 sys 0.00
zsh : real 0.07 user 0.06 sys 0.01
ash : real 0.02 user 0.02 sys 0.00

read.sh:
sh  : real 10.36 user 9.70 sys 0.65
bash: real 140.23 user 121.62 sys 18.57
ksh : real 3.35 user 3.32 sys 0.02
mksh: real 44.63 user 38.90 sys 5.72
posh: real 42.70 user 37.52 sys 5.17
yash: real 190.77 user 179.26 sys 11.46
zsh : real 36.43 user 26.96 sys 9.46
ash : real 21.54 user 15.42 sys 6.12
```

このようにファイルの行数が少ない場合は `cat` は何度もプロセスを起動するため `read` の方が速く、逆にファイルの行数が多ければ `read` だと処理内容が増えるので `cat` の方が速くなります。特に bash (5.0.3) と yash (2.48) の速度低下が顕著です。（正確にはループの中で行ってる文字列結合が速度低下の根本的な原因です。）ファイルの行数が少なければ `read` の方が速いのですが（シェルや環境にもよりますが）わずか数十行程度で逆転してします。そのためある程度の行数があるとわかっているのであれば `cat` を使ったほうが良いということになります。

ということで、ここまでが前書きです。この記事では `cat` を使うか `read` を使うか問題を改善すべく、シェル固有の拡張機能やアルゴリズムの工夫によってファイルの行数に大きく左右されずに安定して高速にファイルを読み込む方法を紹介します。

## bash の場合

bash にはファイル全体を配列に入れることができる `readarray` (`mapfile`) というコマンドが実装されています。これを使用するのが最も速いようです。

```sh
IFS=
readarray data < "file"
data="${data[*]}" # 配列に読み込んだものを結合する
```

ただし、このコマンドは bash 4.x からしか使えないため、macOS の bash 3.2.57 では使用できません。bash 4.x では少し遅くなりますが `IFS= read -r -d ""` を使用して同等のことができます。`-d ""` は正確にはファイル全体を読み込むのではなく、区切り記号 NULL 文字を見つけるまで読み込むという意味ですが、原則としてシェルスクリプトは NULL 文字を扱えないので読み込むファイルには NULL 文字はないという前提です。`cat` で NULL文字を含むファイルを読み込んだとしても（警告を出して）NULL 文字は削除されるのでどちらにしろ正しく扱うことはできません。

```sh
IFS= read -r -d "" data < "file" ||:
# ||: は終了ステータスが非ゼロの場合にそれをを無視するためのものです
# ファイルに NULL 文字が含まれてない場合は、区切り記号が
# 見つからないということなので必ず非ゼロになります
```

また末尾の改行が削除されてしまい厳密には同じではない（`data=$(cat "file")`と同等）ので参考となりますが、以下のような書き方でもファイルを読み込むことができます。bash 3.2.57 でも使用可能で `cat` の呼び出しは行われないので末尾の改行が不要で大きなファイルを読み込む場合は高速です。

```sh
data=$(<"file")
```

1行のファイル読み込みを1万回繰り返した場合

```
cat:       real 28.77 user 21.02 sys 8.50
read:      real 0.62 user 0.50 sys 0.12

readarray: real 0.38  user 0.32  sys 0.06
read -d:   real 1.66 user 1.01 sys 0.65
array:     real 0.78 user 0.60 sys 0.16 （yashの場合を参照）
$(<file):  real 7.26 user 5.61 sys 2.41 （参考）
```

1万行のファイル読み込みを1回だけ行った場合

```
cat:       real 0.06 user 0.03 sys 0.02
read:      real 140.23 user 121.62 sys 18.57

readarray: real 0.06 user 0.05 sys 0.00
read -d:   real 1.38 user 0.76 sys 0.62
array:     real 9.01 user 5.28 sys 3.56 （yashの場合を参照）
$(<file):  real 0.07 user 0.07 sys 0.02 （参考）
```

`readarray` を使用するとファイルの行数が少ない場合の速度が改善されます。`read -d` はファイルの行数によって `cat` と `read` に勝ったり負けたりしていますが、どちらも大幅な速度低下がないので総合的に見れば優れています。

## zsh の場合

zsh ではシェル付属モジュールの `mapfile` を使うのが一番高速です。なんらかの理由で `mapfile` が使用できない場合は `IFS= read -r -d ""` を使用することで大きなファイル読み込み時の速度低下が解消されます。末尾の改行が削除されてしまう `$(<"file")` も使用可能でこちらも高速です。

```sh
zmodload zsh/mapfile # mapfile` を使えるようにするために必要
data="${mapfile[file]}"
```

1行のファイル読み込みを1万回繰り返した場合

```
cat :     real 30.58 user 22.08 sys 10.69
read:     real 1.90 user 1.16 sys 0.74

mapfile:  real 0.20 user 0.09 sys 0.10
read -d:  real 1.79 user 0.98 sys 0.81
array:    real 1.99 user 1.20 sys 0.79 （yashの場合を参照）
$(<file): real 0.20 user 0.13 sys 0.06 （参考）
```

1万行のファイル読み込みを1回だけ行った場合

```
cat:      real 0.07 user 0.06 sys 0.01
read:     real 36.43 user 26.96 sys 9.46

mapfile:  real 0.01 user 0.01 sys 0.00
read -d:  real 1.41 user 0.72 sys 0.69
array:    real 1.66 user 0.96 sys 0.69 （yashの場合を参照）
$(<file): real 0.02 user 0.01 sys 0.00 （参考）
```

**余談** zsh では `data=$(<"file"; echo _)` のようなコードが動作し、これを利用すると末尾の改行を保持することが可能なように見えます。しかしこれはファイルを読み込みの特殊な書き方である `$(<file)` とは関係なく `<"file"` （と `echo`）を実行しています。コマンドなしのリダイレクション（`<"file"`）は「[7.3 Redirections with no command](http://zsh.sourceforge.net/Doc/Release/Redirection.html#Redirections-with-no-command)」に書いてあるとおり、zsh では他のシェルと異なり `:` ではなく `NULLCMD` や `READNULLCMD` で呼び出すコマンドを変更することができデフォルトは `cat` と `more` です。そのためファイル読み込みと同等の結果となりますが、実際にはコマンドを呼び出しているので遅いです。

## ksh93 の場合

ksh93 ではドキュメント上は `IFS="" read -r -d ""` が使用できるように思えますが、実際には `-d` を指定すると `-r` （バックスラッシュをエスケープ文字として解釈しない）が無視されてしまうバグがあるため事実上使い物になりません。（このバグは ksh93u+m で[修正](https://github.com/ksh93/ksh/pull/17)されています。）

しかし ksh93 ではファイルディスクリプタのシーク（読み込み位置の変更）が可能で（外部コマンドを使用せずに）ファイルサイズの取得もできるため、これと指定したサイズだけファイルを読み込む `read -N サイズ` を使うことで、ファイル全体を高速に読み込むことが可能です。また、末尾の改行が削除されてしまう `$(<"file")` も使用可能でこちらも高速です。

```sh
{ read -N "$(<#((EOF)))" data <#((0)); } <"file"
```

ファイルのシークは他のシェルにはない珍しい機能なので補足します。シークは `<#((式))` という形で行います。例えば `<#((1000))` のように実行すると標準入力（ファイルディスクリプタ 0）を 1000 バイト目にシークします。ただし標準入力はファイルからの入力などのシーク可能でなければならないのでパイプラインからの入力では機能しません。`EOF` と `CUR` という特殊変数が利用でき、それぞれファイルの最後と現在位置を意味します。例えば `<#((EOF-100))` を実行するとファイルの後ろから100バイト目にシークします。また `$( <#((式)) )`' と書くことでシーク後の位置（バイト）を取得することができます。シークに関するその他の機能はマニュアルを参照してください。

上記のコードでは「`<"file"` でファイルを標準入力に変更」し「`$(<#((EOF)))` で ファイルを EOF までシークしてその位置を取得」し「` <#((0))` でファイルの先頭に再度シーク」してファイル全体（EOFの位置まで）を読み込むという処理を行っています。

1行のファイル読み込みを1万回繰り返した場合

```
cat :     real 15.38 user 11.20 sys 4.55
read:     real 0.45 user 0.34 sys 0.11

read -N:  real 0.04 user 0.00 sys 0.00
array:    real 0.51 user 0.36 sys 0.15 （yashの場合を参照）
$(<file): real 0.16 user 0.07 sys 0.08 （参考）
```

1万行のファイル読み込みを1回だけ行った場合

```
cat:      real 0.03 user 0.03 sys 0.00
read:     real 3.35 user 3.32 sys 0.02

read -N:  real 0.02 user 0.01 sys 0.00
array:    real 0.51 user 0.36 sys 0.15 （yashの場合を参照）
$(<file): real 0.00 user 0.00 sys 0.00 （参考）
```

## mksh の場合

`IFS= read -r -d ""` が使用可能です。また末尾の改行が削除されてしまう `$(<"file")` も使用可能でこちらも高速です。なお `cat` を使った場合の速度が他のシェルに比べて速いですが、これは mksh では `cat` がシェルビルトインになっているからです。

1行のファイル読み込みを1万回繰り返した場合

```
cat:      real 5.94 user 4.46 sys 1.89
read:     real 1.59 user 0.88 sys 0.70

read -d:  real 1.51 user 0.87 sys 0.63
array:    real 1.80 user 1.03 sys 0.73 （yashの場合を参照）
$(<file): real 0.15 user 0.09 sys 0.06 （参考）
```

1万行のファイル読み込みを1回だけ行った場合

```
cat:      real 0.03 user 0.03 sys 0.00
read:     real 44.63 user 38.90 sys 5.72

read -d:  real 1.33 user 0.66 sys 0.66
array:    real 44.63 user 38.90 sys 5.72 （yashの場合を参照）
$(<file): real 0.02 user 0.01 sys 0.00 （参考）
```

## yash の場合

残念ながら yash には `read` に拡張機能がありません。そのためアルゴリズムの工夫によって対処します。まずファイル読み込みが遅い根本的な原因は文字列結合です。ループのたびに結合する文字列が長くなっていくため速度が大きく低下していきます。つまりこの文字列結合を避けるようにすればよいわけです。yash には配列があるので文字列を結合するのではなく配列に追加していくことでファイルの行数が多い場合の読み込み速度を改善することができます。そして最後に配列を一つの文字列に結合します。

このやり方は配列に対応している他のシェルでも行えますが、それらのシェルでは他の方法に比べて大きなメリットがないため解説は省略し計測値のみ載せています。注意点として yash では配列処理の書き方が他のシェルと異なるので注意してください。（余談ですが yash の配列処理の書き方は、POSIX 準拠のコードとして解釈しても文法エラーにならないというメリットがあります。）

```sh
LF="
"
array -- data
while IFS= read -r line; do
  array -i -- data -1 "${line}$LF"
done < "file"
array -i -- data -1 "${line}"
IFS=""
data="${data[*]}"
```

1行のファイルを1万回読んだ場合

```
cat:   real 27.65 user 20.45 sys 9.02
read:  real 3.40 user 2.01 sys 1.38

array: real 3.62 user 2.12 sys 1.47
```

1万行のファイルを1回読んだ場合

```
cat:   real 0.08 user 0.08 sys 0.00
read:  real 190.77 user 179.26 sys 11.46

array: real 3.19 user 1.79 sys 1.38
```

## POSIX 準拠シェル（dash, posh, busybox ash）の場合

POSIX 準拠シェルの場合、当然ながら `read` に拡張機能はありませんし配列もありません。`$(<"file")`も使用できません。yash の場合と同様に遅い原因は文字列結合です。yash ではそれを配列に入れることで回避しましたが、POSIX 準拠シェルでは配列もないのでファイル全体を一つの変数に入れるには文字列を結合していくしかなさそうですが、~~ひどい方法~~巧妙な方法で改善することができます。

※ busybox ash は 1.28.0 から `read -d` がサポートされています。

**疑似配列に read する**

POSIX準拠シェルの場合は配列が存在しないので、変数名に `_数字` をつけて擬似的な配列を表現します。そしてこの疑似配列に `read` コマンドで読み込んでいくのですが（運がいいことに？）代入する変数名は `read` の引数で渡すので `read -r "line_$i"` と書くことで擬似配列の指定したインデックス (`$i`)の変数に直接代入することができます。

**eval を駆使する**

疑似配列に入れた値は最終的に一つのデータとして結合します。変数を結合するには `data="$line_1${LF}$line_2${LF}$line_3${LF}...`のようなコードを実行する必要がありますが、読み込む行数はファイルの内容によって変わるので動的にこの文字列を生成し `eval` しなければいけません。この文字列は `read` しつつ組み立てて行くわけですが、ここで速度低下の原因となる文字列結合が再度登場してしまいます。

**文字列結合の高速化**

文字列結合の処理を言い換えると文字列のデータ分だけメモリコピーを行う処理です。つまりこのメモリコピーの量を減らせば文字列結合の処理は速くなるということです。具体的に言うと `data="$line_1${LF}$line_2${LF}$line_3${LF}...` という文字列を組み立てるよりも、`data="$L_1${LF}$L_2${LF}$L_3${LF}...` とした方が文字列の長さが短くなる分、メモリコピーの量が減るので速度も速くなります。

**位置パラメーターを駆使する**

実用的レベルの話だと、上記のような変数名は他で同じ名前が使われてる可能性が高くなります。そこで変数の代わりに位置パラメーターを利用します。`$line`, `$LF` をそれぞれ位置パラメーターに設定し（`set -- '$line' '$LF'`) 組み立てる文字列を `data="${1}_1${2}${1}_2${2}${1}_3${2}...` とすることで変数名がかぶることを気にすること無く組み立てる文字列を短くすることができます。（読みやすさのために `{}` を使用していますが実際には不要です。）

これらを利用して作ったコードはこのようになります。

```sh
LF="
"

data='' i=1
while IFS= read -r "readfile_line_$i"; do
  # '$1_1$2$1_2$2$1_2$2 ...' という文字列を組み立てる
  data="$data\$1_$i\$2" 
  i=$((i+1))
done < "file"
data="$data\$1_$i"

set -- '$readfile_line' "$LF" # $1と$2に変数名のプリフィックスと改行をセットする
# data変数に '${readfile_line_1}${LF} ${readfile_line_2}${LF}...' という文字列を組み立てる
eval "data=\"$data\"" 

# 疑似配列 readfile_line_1 ... を unsetするための変数名を組み立て位置パラメーターにセットする
IFS="\$$LF "
set -- $data
shift

# 文字列 '${readfile_line_1}${LF} ${readfile_line_2}${LF}...' を評価し data変数に入れる
eval "data=\"$data\""
# 疑似配列 readfile_line_1, readfile_line_2, ...を unset する
unset "$@"
```

これだけの処理をするとさすがに1行のファイルを繰り返し読み込んだ場合の速度は落ちますが、それでも比較的少ない低下で行数が多い場合の速度を改善することができます。

1行のファイル読み込みを1万回繰り返した場合

```
[cat]
sh  : real 18.56 user 13.66 sys 4.84
posh: real 23.94 user 17.93 sys 6.97
ash : real 21.13 user 16.07 sys 6.41

[read]
sh  : real 1.51 user 0.74 sys 0.76
posh: real 0.34 user 0.27 sys 0.07
ash : real 2.63 user 1.57 sys 1.05

[改良版]
sh  : real 1.66 user 0.96 sys 0.70
posh: real 0.66 user 0.57 sys 0.09
ash : real 2.99 user 1.89 sys 1.10
```

1万行のファイル読み込みを1回だけ行った場合

```
[cat]
sh  : real 0.02 user 0.02 sys 0.00
posh: real 0.05 user 0.06 sys 0.00
ash : real 0.02 user 0.02 sys 0.00

[read]
sh  : real 10.36 user 9.70 sys 0.65
posh: real 42.70 user 37.52 sys 5.17
ash : real 21.54 user 15.42 sys 6.12

[改良版]
sh  : real 2.43 user 1.85 sys 0.57
posh: real 6.11 user 6.00 sys 0.10
ash : real 4.13 user 2.72 sys 1.40
```

## さいごに

いろいろとひどい（笑）

POSIX シェルは（いい意味で）最小限の機能しか実装されてないので、それ以上を求めようとするならシェル固有の拡張機能に頼らざるを得ないのですが、もう少しなんとかならないのでしょうかね。シェルが作られた当時（30～40年以上前）のコンピューターの性能を考えると最小限の機能にするのは仕方ないですし、これだけの機能で実用的になってるのでよく絞り込まれてると驚く所ですが、もうそろそろシェル間の非互換性を減らして使いやすくバージョンアップしてほしいものです。現在の POSIX 準拠の範囲でなんとかするのは大変な作業なので。

最後の最後にこれらのテクニックを駆使して高速化を行っている、POSIX 準拠シェル全てをサポートしながらも最も多くの機能を実現している、シェルスクリプト用のユニットテストフレームワーク [ShellSpec](https://github.com/shellspec/shellspec) を宣伝して終わります。