いくつかのテーマごとに「どの Bash コマンドが一番早いのか」を計測した

# 概要

* Bash には早いコマンドと遅いコマンドがある
* コマンドの選択を間違うと、シェル上の処理で大きなボトルネックを作ってしまう羽目になる
* 実際に計測をして「どのコマンドがどれくらい早いのか」を調べた

# 環境

* Linux (CentOS 6)
  * VirtualBox 上の仮想環境
* Intel(R) Core(TM) i7-4810MQ CPU @ 2.80GHz
  * 1 コアのみ割り当て
* Memory 2GB
  * 少なすぎたかも..

# 実験に使ったファイル

* sequences.txt: 1000万行の連番テキストファイル

```bash
$ ll -h sequences.txt 
-rw-rw-r-- 1 vagrant vagrant 76M Dec 26 15:48 sequences.txt

$ head -5 sequences.txt 
1
2
3
4
5
```

# 実験テーマと比較したコマンド

|実験テーマ|比較したコマンド|
|---------|--------------|
|1. ファイルサイズの取得|du, ls, stat, wc|
|2. 四則演算|expr, let, $(( ))|
|3. テキストの各行処理|while (パイプ), while (リダイレクト), for|
|4. 条件分岐|[ ], [[ ]], echo & egrep|
|5. 数値判定|perl, grep, expr, [[ ]]|
|6. 文字の置換|awk, perl, sed, tr, ${ }|

# 実験結果

以下の結果は、3 回行った平均の経過時間となっている

## 1. ファイルサイズの取得

* for ループでファイルサイズを 10 万回取得する

### コマンド

```bash
# 1. du
$ time {
  for i in $(seq 100000); do
    du -b sequences.txt
  done
} >/dev/null

# 2. ls
$ time {
  for i in $(seq 100000); do
    ls -l sequences.txt
  done
} >/dev/null

# 3. stat
time {
  for i in $(seq 100000); do
    stat -c %s sequences.txt
  done
} >/dev/null

# 4. wc
$ time {
  for i in $(seq 100000); do
    wc -c sequences.txt
  done
} >/dev/null

```

NOTE: それぞれ `{ }` でくくって `/dev/null` にリダイレクトしているのは、ターミナルへの出力で負荷をかけたくなかったため

### 結果

|               | du | ls | stat | wc |
|--------------:|:---|:---|:-----|:---|
|**経過時間 [s]**|126.29|125.41|77.70|69.24|
|**速度アップ率**|1|1.01|1.63|1.82|

* `du` と `ls` に比べ、 `wc` はおよそ 2 倍の高速化が見込めている
  * ファイルの中身を見に行っている都合上、ファイルサイズによって結果が変わってくるかも

## 2. 四則演算

* for ループで 10 万回「1 引く 1」を行い、結果を出力する

### コマンド

```bash
# 1. expr
$ time {
  for i in $(seq 100000); do
    expr 1 - 1
  done
} >/dev/null

# 2. let
$ time {
  for i in $(seq 100000); do
    let result=1-1
    echo $result
  done
} >/dev/null

# 3. $(( ))
$ time {
  for i in $(seq 100000); do
    echo $(( 1 - 1 ))
  done
} >/dev/null

```

### 結果

|               | expr | let | $(( )) |
|--------------:|:-----|:----|:-------|
|**経過時間 [s]**|67.53|0.91|0.64|
|**速度アップ率**|1|74.02|105.65|

* `expr` だと 1 分以上かかるが、 `let` `$(( ))` だと 1 秒未満で終わる

## 3. テキストファイルの各行処理

* ここではループの仕方を比較する
* 1000 万行の `sequences.txt` を 1 行ずつ読み込む
* 今回は何もしない `:` コマンドをループの中に使った

### コマンド

```bash
# 1. while with pipe (and standard input)
$ time cat sequences.txt | while read line; do
  :
done

# 2. while with redirect
$ time while read line; do
  :
done < sequences.txt 

# 3. for
$ time for line in $(cat sequences.txt); do
  :
done
```

### 結果

|               | while with pipe | while with redirect | for |
|--------------:|:----------------|:--------------------|:----|
|**経過時間 [s]**|70.62|55.63|33.94|
|**速度アップ率**|1|1.27|2.08|

* オーソドックスな `for` が最も早かった
* これも読み込むテキストファイルのサイズに左右されるかもしれない

## 4. 条件分岐

* for ループで 100 万回の条件分岐をする
  * 「$PATH は asdf という文字列かどうか」という条件にした
* 分岐後の処理は「何もしない (`:`)」とした

### コマンド

```bash
# 1. [ ]
$ time for i in $(seq 1000000); do
  if [ $PATH = 'asdf' ]; then
    :
  else
    :
  fi
done

# 2. [[ ]]
$ time for i in $(seq 1000000); do
  if [[ $PATH = 'asdf' ]]; then
    :
  else
    :
  fi
done

# 3. echo and egrep
$ time for i in $(seq 1000000); do
  if echo "$PATH" | egrep "^asdf$"; then
    :
  else
    :
  fi
done
```


### 結果

|               | [ ] | [[ ]] | echo and egrep |
|--------------:|:----|:------|:---------------|
|**経過時間 [s]**|50.59|16.47|NO CONTEST|
|**速度アップ率**|1|3.07|NO CONTEST|

* カッコの数が違うだけで処理速度が 3 倍ほど変わった
* "echo and egrep" の実験は時間がかかりすぎて断念した (1～2時間は待ったはず)
* 参考までに、条件分岐なし (素の for ループ) は 3.25 [s] だった

## 5. 数値判定

* for ループで 10 万回数値 (自然数) 判定をする

### コマンド

```bash
# 1. perl
$ time {
  for i in $(seq 100000); do
    perl -e "exit 1 unless $i =~ /^\d+$/"
    # returns 1 if $i is not numeric
  done
} >/dev/null

# 2. grep
$ time {
  for i in $(seq 100000); do
    echo $i | grep -qe '^[0-9]\+$'
    # returns 1 if $i is not numeric
  done
} >/dev/null

# 3. expr
$ time {
  for i in $(seq 100000); do
    expr $i + 1
    # returns 2 if $i is not numeric
  done
} >/dev/null 2>&1

# 4. [[ ]]
$ time {
  for i in $(seq 100000); do
    [[ $i =~ ^[0-9]+$ ]]
    # returns 1 if $i is not numeric
  done
} >/dev/null
```

### 結果

|               | perl | grep | expr | [[ ]] |
|--------------:|:-----|:-----|:-----|:------|
|**経過時間 [s]**|165.78|163.92|68.93|2.86|
|**速度アップ率**|1|1.01|2.41|57.90|

* 複数個の命令やコマンドが含まれている `perl` や `grep` のケースはやはり不利だった
* ここでも `[[ ]]` がとても早い

## 6. 文字の置換

以下の 2 パターンでそれぞれ計測した
* (a) 1 回のみの fork/exec (ファイルをパイプでストリーム処理)
* (b) 10 万回の fork/exec (ループで繰り返し処理)

### (a) 1 回のみ

* 1 ～ 100 万までの数値に対し '3' を 'E' に置換
* 各コマンドが呼び出されるのは 1回 のみ

#### コマンド

```bash

# 1. awk
$ time seq 1000000 | awk '{gsub("3", "E", $0); print $0}' >/dev/null

# 2. perl
$ time seq 1000000 | perl -pe 's/3/E/g' >/dev/null

# 3. sed
$ time seq 1000000 | sed -e 's/3/E/g' >/dev/null

# 4. tr
$ time seq 1000000 | tr '3' 'E' >/dev/null

# 5. ${ }
$ time { num=$(seq 1000000); echo ${num//3/E}; } >/dev/null
```

#### 結果

|               | awk | perl | sed | tr | ${ } |
|--------------:|:----|:-----|:----|:---|:-----|
|**経過時間 [s]**|1.04|0.98|0.91|0.55|NO CONTEST|
|**速度アップ率**|1|1.05|1.14|1.88|NO CONTEST|

* 1 文字しか置換できない分シンプルな `tr` が最も早かった
* `${ }` は例によって遅すぎて断念

### (b) 10 万回

* 1 ～ 10 万までの数値 それぞれ に対し "3" を "E" に変換
* 各コマンドが呼び出されるのは 10 万回

#### コマンド

```bash
# 1. awk
$ time {
  for i in $(seq 100000); do
    echo $i | awk '{gsub("3", "E", $0); print $0}'
  done
} >/dev/null

# 2. perl
$ time {
  for i in $(seq 100000); do
    echo $i | perl -pe 's/3/E/g'
  done
} >/dev/null

# 3. sed
$ time {
  for i in $(seq 100000); do
    echo $i | sed -e 's/3/E/g'
  done
} >/dev/null

# 4. tr
$ time {
  for i in $(seq 100000); do
    echo $i | tr '3' 'E'
  done
} >/dev/null

# 5. ${ }
$ time {
  for i in $(seq 100000); do
    echo ${i//3/E}
  done
} >/dev/null
```

#### 結果

|               | awk | perl | sed | tr | ${ } |
|--------------:|:----|:-----|:----|:---|:-----|
|**経過時間 [s]**|115.56|189.94|106.30|97.72|0.87|
|**速度アップ率**|1.64|1|1.79|1.94|217.44|

* `perl` が遅くなった
* `${ }` が爆速になった

### グラフ

![image.png](https://qiita-image-store.s3.amazonaws.com/0/49525/38ed9cde-d07f-5fa1-5491-1eb90622ce31.png)

# まとめ

だいたい各所で言われている通りの結果となった。

* 「繰り返し実行」に関しては Bash の組み込みコマンドが圧倒的に強い
  * `[[ ]]`, `$(( ))`, `${ }` など
  * 一般的なコマンドと比べて `fork` -> `exec` がないため
* 一方で 6.(a) のように「パイプを使った 1 度きりの実行」のときは `fork/exec` の影響がほぼ無視できるため、非組み込みコマンドでも戦える
  * むしろ実験結果をみると組み込みの `${ }` は劇的に遅い。一度メモリに展開するからだろうか?
* sh への互換性を考えないなら `[ ]` よりも `[[ ]]` を使ったほうがよい
* 四則演算で `expr` を使うのは避けたほうが良い

# 参考

* [シェルスクリプトを何万倍も遅くしないためには —— ループせずフィルタしよう](https://qiita.com/8x9/items/f1156503694d3683e78d)
* [bash Tips - コマンド置換と算術式展開、パラメータ展開](https://qiita.com/mashumashu/items/bbc3a79bc779fe8c4f99)
* [bashの組込みコマンド自作によるスクリプトの高速化](https://qiita.com/satoru_takeuchi/items/7d424fa5ef1e33ace4df)