Goにまつわるとっても真面目なBenchmarkクイズ！「goの正規表現(regexp)は速いのか？」編

今回はクソ真面目にクイズを書いていきます。
なぜ真面目を強調しているかといえば、昔書いた記事が不真面目だったからです。
[鬱陶しいくらい「いいね」するよう勧めてくるgoroutineクイズ](https://qiita.com/aimof/items/cf89d83b2760c65abd84)

それではクイズに行きましょう。
最初の３問は小手調べ、Goの基本事項のおさらいです。
その後、第四問から正規表現の速さ比べに入ります。

## 実行環境

こんなの

```
Distro: Ubuntu 18.04.1
Kernel: 4.15.0-42-generic
CPU:    Intel(R) Core(TM) i5-7600 CPU @ 3.50GHz
Mem:    16GB
Go:     go version go1.11.3 linux/amd64
```

書いている間にgo1.11.4がリリースされましたが、今回は1.11.3です。

## 形式

f0とf1の実行時間を比較してください。

Benchmarkはだいたい

```main_test.go
func BenchmarkF0(b *testing.B) {
	for i := 0; i < b.N; i++ {
		_ = f0()
	}
}

func BenchmarkF1(b *testing.B) {
	for i := 0; i < b.N; i++ {
		_ = f1()
	}
}
```

最初の３問はこんなノリです。f0とf1のどちらが速いか、あるいはだいたい同じくらいかを当ててください。


## 第一問：文字列のフォーマット、結合

割と基本的な文字列の結合です。

```main.go
var (
    a = 1
    b = "Fizz"
    c = false
)

func f0() string {
	return fmt.Sprintf("%d%s%v", a, b, c)
}

func f1() string {
	return strconv.Itoa(a) + b + strconv.FormatBool(c)
}
```

### 解答

<details><summary>解答（折りたたみ）</summary><div>

f1の方が速い。
printf系の関数は遅くなることが多いです。

```
BenchmarkF0-4   	10000000	       155 ns/op	      40 B/op	       3 allocs/op
BenchmarkF1-4   	30000000	        44.8 ns/op	      16 B/op	       1 allocs/op
```

</div></details>

## 第二問：スライスの定義

初心者がよくハマるあれです。

```main.go
func f0() []int {
	slice := []int{}
	for i := 0; i < 1024; i++ {
		slice = append(slice, i)
	}
	return slice
}

func f1() []int {
	slice := make([]int, 0, 1024)
	for i := 0; i < 1024; i++ {
		slice = append(slice, i)
	}
	return slice
}
```

### 解答

<details><summary>解答（折りたたみ）</summary><div>

```
$ go test --bench . --benchmem 
goos: linux
goarch: amd64
pkg: github.com/aimof/bench/slice0
BenchmarkF0-4   	  500000	      2522 ns/op	   16376 B/op	      11 allocs/op
BenchmarkF1-4   	 1000000	      1365 ns/op	    8192 B/op	       1 allocs/op
```

最初にcapを確保するかどうかで大分変わります。
メモリの再確保は時間がかかるのです。

</div></details>

## 第三問：再帰関数

よくある再帰関数です。

```main.go
func f0(n int) int {
	if n > 0 {
		return n + f0(n-1)
	}
	return 0

}

func f1(n int) int {
	sum := 0
	for i := 0; i <= n; i++ {
		sum += i
	}
	return sum
}
```

### 解答

<details><summary>解答（折りたたみ）</summary><div>

f1が速い
まあ、再帰は遅いよね。

```
$ go test --bench . --benchmem
goos: linux
goarch: amd64
pkg: github.com/aimof/bench/rec
BenchmarkF0-4   	     300	   5626446 ns/op	       0 B/op	       0 allocs/op
BenchmarkF1-4   	    3000	    520985 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	github.com/aimof/bench/rec	4.323s
```

</div></details>

## 第四問：正規表現その１

本題です。
遅いと勘違いされがちなgoの正規表現についてです。
ランダムな数字で構成された文字列、バイト列を生成して"123"を"999"に変換して出力します。
stringsパッケージとregexpパッケージの比較です。
仕様上f0が文字列、f1がバイト列をそれぞれ引数、返り値にしています。

```main.go
func f0(s string) string {
	return strings.Replace(s, "123", "999", -1)
}

func f1(b []byte) []byte {
	reg, err := regexp.Compile("123")
	if err != nil {
		log.Fatalln(err)
	}
	return reg.ReplaceAll(b, []byte("999"))
}
```

```main_test.go
var length = 1024
var target = makeBytes(length)
var str = string(target)

func makeBytes(n int) (b []byte) {
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < n; i++ {
		num := rand.Intn(10)
		b = append(b, []byte(strconv.Itoa(num))...)
	}
	return b
}

func Test(t *testing.T) {
	n0 := f0(str)
	n1 := f1(target)
	if n0 != string(n1) {
		t.Error()
	}
}

func BenchmarkF0(b *testing.B) {
	for i := 0; i < b.N; i++ {
		_ = f0(str)
	}
}

func BenchmarkF1(b *testing.B) {
	for i := 0; i < b.N; i++ {
		_ = f1(target)
	}
}
```

ここからはテストまで全部書きます。
クイズ始めましょう！

n = 1024(1Ki)のとき速いのはどっち？

### 解答

<details><summary>解答（折りたたみ）</summary><div>

f0(strings)の方が速い。やはり遅いですね、goの正規表現。

```
$ go test --bench . --benchmem 
goos: linux
goarch: amd64
pkg: github.com/aimof/bench/reg
BenchmarkF0-4   	 1000000	      3583 ns/op	    2048 B/op	       2 allocs/op
BenchmarkF1-4   	   50000	     23791 ns/op	   41720 B/op	      33 allocs/op
PASS
```

</div></details>

## 第五問：正規表現その２

第四問で`length=1024*1024`(1Mi)の場合は？

### 解答

<details><summary>解答（折りたたみ）</summary><div>

f1(regexp)の方が速い

```
$ go test --bench . --benchmem 
goos: linux
goarch: amd64
pkg: github.com/aimof/bench/reg
BenchmarkF0-4   	    1000	   4911563 ns/op	 2097152 B/op	       2 allocs/op
BenchmarkF1-4   	    1000	   2735865 ns/op	 5859064 B/op	      58 allocs/op
PASS
ok  	github.com/aimof/bench/reg	10.261s
```

</div></details>

### 第六問：正規表現その３

第四問、第五問で`length=1024*1024*1024`(1Gi)の場合は？

## 解答

<details><summary>解答（折りたたみ）</summary><div>

だいたいf1の方が速いです。

```
$ go test --bench . --benchmem 
goos: linux
goarch: amd64
pkg: github.com/aimof/bench/reg
BenchmarkF0-4   	       1	1939527170 ns/op	2147483744 B/op	       3 allocs/op
BenchmarkF1-4   	       1	1693673809 ns/op	6168930776 B/op	      84 allocs/op
PASS
ok  	github.com/aimof/bench/reg	48.742s
```

ループ数１なので10回くらい試しましたが、おおよそ、f0: 19.5秒程度、f1: 17秒程度になります。

</div></details>

## 第七問：正規表現同士の比較１

### 解答

```main.go
func f0(b []byte) []byte {
	reg, err := regexp.Compile("123")
	if err != nil {
		log.Fatalln(err)
	}
	return reg.ReplaceAll(b, []byte("999"))
}

func f1(b []byte) []byte {
	reg, err := regexp.Compile("1.3")
	if err != nil {
		log.Fatalln(err)
	}
	return reg.ReplaceAll(b, []byte("999"))
}
```

```main_test.go
var length = 1024
var target = makeBytes(length)

func makeBytes(n int) (b []byte) {
	rand.Seed(time.Now().UnixNano())
	return bytes.Repeat([]byte("12345678"), n/8)
}

func Test(t *testing.T) {
	n0 := f0(target)
	n1 := f1(target)
	if !reflect.DeepEqual(n0, n1) {
		t.Error()
	}
}

func BenchmarkF0(b *testing.B) {
	for i := 0; i < b.N; i++ {
		_ = f0(target)
	}
}

func BenchmarkF1(b *testing.B) {
	for i := 0; i < b.N; i++ {
		_ = f1(target)
	}
}
```

"123"と"1.3"の比較です。
文字列の生成方法を工夫したので"1.3"にマッチするのは"123"だけです。
どんな感じになるのでしょうか？
`length=1024`のときです。（この後増えます）

<details><summary>解答（折りたたみ）</summary><div>

```
$ go test --bench . --benchmem 
goos: linux
goarch: amd64
pkg: github.com/aimof/bench/reg1
BenchmarkF0-4   	   50000	     65917 ns/op	   40896 B/op	      37 allocs/op
BenchmarkF1-4   	   30000	     65174 ns/op	   41072 B/op	      40 allocs/op
PASS
ok  	github.com/aimof/bench/reg1	6.078s
```
</div></details>

### 第八問：正規表現同士の比較２

`length=1024*1024`

## 解答

<details><summary>解答（折りたたみ）</summary><div>

```
$ go test --bench . --benchmem 
goos: linux
goarch: amd64
pkg: github.com/aimof/bench/reg1
BenchmarkF0-4   	      50	  32877722 ns/op	 5865417 B/op	      66 allocs/op
BenchmarkF1-4   	      50	  32408068 ns/op	 5865597 B/op	      69 allocs/op
PASS
ok  	github.com/aimof/bench/reg1	3.464s
```

あんまり変わりませんね（つまらぬ）

</div></details>

### 第九問：正規表現同士の比較３

一応、`length=1024*1024*1024`(1Gi)のときもやってみましょう。

## 解答

<details><summary>解答（折りたたみ）</summary><div>

```
$ go test --bench . --benchmem 
goos: linux
goarch: amd64
pkg: github.com/aimof/bench/reg1
BenchmarkF0-4   	       1	32865004402 ns/op	6168960968 B/op	      97 allocs/op
BenchmarkF1-4   	       1	31682328432 ns/op	6168961144 B/op	     100 allocs/op
PASS
ok  	github.com/aimof/bench/reg1	195.128s
```

やっぱりあまり変わりません。
もうちょっと複雑な正規表現を試してみましょう。

</div></details>

## 最終問題：正規表現同士の比較

"1......8"
"12*8"
この２つのパターンで、"12222228"この繰り返しにマッチさせます。

```main.go
func f0(b []byte) []byte {
	reg, err := regexp.Compile("1......8")
	if err != nil {
		log.Fatalln(err)
	}
	return reg.ReplaceAll(b, []byte("19999998"))
}

func f1(b []byte) []byte {
	reg, err := regexp.Compile("12*8")
	if err != nil {
		log.Fatalln(err)
	}
	return reg.ReplaceAll(b, []byte("19999998"))
}
```

```main_test.go
var length = 1024 * 1024 * 1024
var target = makeBytes(length)

func makeBytes(n int) (b []byte) {
	return bytes.Repeat([]byte("12222228"), n/8)
}

func Test(t *testing.T) {
	n0 := f0(target)
	n1 := f1(target)
	if !reflect.DeepEqual(n0, n1) {
		t.Error()
	}
}

func BenchmarkF0(b *testing.B) {
	for i := 0; i < b.N; i++ {
		_ = f0(target)
	}
}

func BenchmarkF1(b *testing.B) {
	for i := 0; i < b.N; i++ {
		_ = f1(target)
	}
}
```

1Ki, 1Mi, 1Giそれぞれの場合の速い方を答えてください！

### 解答

<details><summary>解答（折りたたみ）</summary><div>

`1Ki`: 同じくらい
`1Mi`: f0の方が速い
`1Gi`: f0の方が速い

桁数が指定されていないf1のほうが遅いみたいですね。（それでも結構速いですが）

```1Ki.go
$ go test --bench . --benchmem 
goos: linux
goarch: amd64
pkg: github.com/aimof/bench/reg2
BenchmarkF0-4   	   50000	     70360 ns/op	   42592 B/op	      48 allocs/op
BenchmarkF1-4   	   20000	     68998 ns/op	   41216 B/op	      41 allocs/op
PASS
ok  	github.com/aimof/bench/reg2	5.872s
```

```1Mi.go
$ go test --bench . --benchmem 
goos: linux
goarch: amd64
pkg: github.com/aimof/bench/reg2
BenchmarkF0-4   	      30	  54123874 ns/op	 5867170 B/op	      77 allocs/op
BenchmarkF1-4   	      20	  71250299 ns/op	 5865864 B/op	      75 allocs/op
PASS
ok  	github.com/aimof/bench/reg2	3.372s
```

```1Gi.go
$ go test --bench . --benchmem 
goos: linux
goarch: amd64
pkg: github.com/aimof/bench/reg2
BenchmarkF0-4   	       1	55755956525 ns/op	6168962664 B/op	     108 allocs/op
BenchmarkF1-4   	       1	72950733405 ns/op	6168961416 B/op	     106 allocs/op
PASS
ok  	github.com/aimof/bench/reg2	324.925s
```

</div></details>

## まとめ

さて、ここまでやってきてお気づきの方もいらっしゃるかもしれませんが、Goの正規表現は実行時間がほぼ線形に増えます。
1Miと1Giの実行時間を比べてみると、ほぼ1024倍に近い差になっています。
1ki程度に短い場合には、大分長くなるようです。

というわけで、長い文字列を処理する場合には、regexpは優秀です。
MiB単位くらい長くないとあまり効果は発揮できないようですね。

以上、Goにまつわるとっても真面目なBenchmarkクイズ！「goの正規表現(regexp)は速いのか？」編でした。

私の読みたいものリストに「regexpのソースコード」が追加されました。