今回はクソ真面目にクイズを書いていきます。
なぜ真面目を強調しているかといえば、昔書いた記事が不真面目だったからです。
鬱陶しいくらい「いいね」するよう勧めてくるgoroutineクイズ
それではクイズに行きましょう。
最初の３問は小手調べ、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)
}
解答
解答（折りたたみ）
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
第二問：スライスの定義
初心者がよくハマるあれです。
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
}
解答
解答（折りたたみ）
$ 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を確保するかどうかで大分変わります。
メモリの再確保は時間がかかるのです。
第三問：再帰関数
よくある再帰関数です。
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
}
解答
解答（折りたたみ）
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
第四問：正規表現その１
本題です。
遅いと勘違いされがちな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)のとき速いのはどっち？
解答
解答（折りたたみ）
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
第五問：正規表現その２
第四問でlength=1024*1024(1Mi)の場合は？
解答
解答（折りたたみ）
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
第六問：正規表現その３
第四問、第五問でlength=1024*1024*1024(1Gi)の場合は？
解答
解答（折りたたみ）
だいたい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秒程度になります。
第七問：正規表現同士の比較１
解答
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のときです。（この後増えます）
解答（折りたたみ）
$ 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
第八問：正規表現同士の比較２
length=1024*1024
解答
解答（折りたたみ）
$ 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
あんまり変わりませんね（つまらぬ）
第九問：正規表現同士の比較３
一応、length=1024*1024*1024(1Gi)のときもやってみましょう。
解答
解答（折りたたみ）
$ 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
やっぱりあまり変わりません。
もうちょっと複雑な正規表現を試してみましょう。
最終問題：正規表現同士の比較
"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それぞれの場合の速い方を答えてください！
解答
解答（折りたたみ）
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
まとめ
さて、ここまでやってきてお気づきの方もいらっしゃるかもしれませんが、Goの正規表現は実行時間がほぼ線形に増えます。
1Miと1Giの実行時間を比べてみると、ほぼ1024倍に近い差になっています。
1ki程度に短い場合には、大分長くなるようです。
というわけで、長い文字列を処理する場合には、regexpは優秀です。
MiB単位くらい長くないとあまり効果は発揮できないようですね。
以上、Goにまつわるとっても真面目なBenchmarkクイズ！「goの正規表現(regexp)は速いのか？」編でした。
私の読みたいものリストに「regexpのソースコード」が追加されました。