LoginSignup
17
4

More than 5 years have passed since last update.

Go2Advent Calendar 2018Day 18
@aimof(Shiroshita Aito)

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

Posted at

今回はクソ真面目にクイズを書いていきます。
なぜ真面目を強調しているかといえば、昔書いた記事が不真面目だったからです。
鬱陶しいくらい「いいね」するよう勧めてくる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のソースコード」が追加されました。

17
4
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
17
4