sgykfjsm.github.com

Goの正規表現とReplacerを比較した

なんとなく色んな人のISUCON6の記事を読んでたら、Goの正規表現が遅くて苦労した、という話を多く見受けられた。そもそも一般的に正規表現自体が遅いとされており、だからこそ各言語では正規表現エンジンが色々実装されてたりするんだけど、Goではあまりそういう話を聞かない。自分が知らないだけでどこかで話題になっているかもしれないけど。

で、KLabの人の記事では、

まずGoの正規表現は遅いので strings.Replacer を使ってキーワードからリンクへの変換をします。

とあり、なるほどGoで単語の置き換えをするならstrings.Replacerが早いのか、ということを知った。じゃあ、どのくらい早いんですかっていうのを確認してみた。

結論から言うと、strings.Replacerのほうが圧倒的に早い。

比較対象に用いた関数は以下のような感じ。ほぼ等価だとは思うけど、もしかしたら不公平な部分があるかもしれない。

regexp_vs_replacer.go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package regexp_vs_replacer

import (
  "regexp"
  "strings"
)

func DoRegexp(re *regexp.Regexp, contents string) string {
  return re.ReplaceAllStringFunc(contents, func(s string) string {
      return strings.ToUpper(s)
  })
}

func DoReplacer(r *strings.Replacer, contents string) string {
  return r.Replace(contents)
}

ベンチマークに使ったテストコードは以下。なお、読み込んだテキストファイルは http://www.blindtextgenerator.com/lorem-ipsum で作成したダミーテキスト。ちなみに中身にはカフカの「変身」の原文だ。4000語でファイルサイズはおよそ21KB。

regexp_vs_replacer_test.go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package regexp_vs_replacer

import (
  "io/ioutil"
  "regexp"
  "strings"
  "testing"
)

var (
  r        *strings.Replacer
  re       *regexp.Regexp
  contents string
  keywords = []string{"One", "morning", "when", "Gregor", "Samsa", "woke", "from", "troubled", "dreams"}
  pairList = make([]string, len(keywords)*2)
)

func init() {
  _contents, err := ioutil.ReadFile("kafka.txt")
  if err != nil {
      panic(err)
  }
  contents = string(_contents)

  re = regexp.MustCompile(`(` + strings.Join(keywords, "|") + `)`)

  for i, keyword := range keywords {
      pairList[i*2], pairList[i*2+1] = keyword, strings.ToUpper(keyword)
  }
  r = strings.NewReplacer(pairList...)
}

func BenchmarkDoRegexp(b *testing.B) {
  b.ResetTimer()

  for i := 0; i < b.N; i++ {
      DoRegexp(re, contents)
  }
}

func BenchmarkDoReplacer(b *testing.B) {
  b.ResetTimer()

  for i := 0; i < b.N; i++ {
      DoReplacer(r, contents)
  }
}

func TestDoRegexp_Equal_To_DoReplacer(t *testing.T) {
  if DoRegexp(re, contents) != DoReplacer(r, contents) {
      t.Fatal("DoRegexp is not equal to DoReplacer")
  }
}

で、ベンチマークの結果は以下の通り。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
$ for i in $(seq 1 3); do go test -benchtime=10s -bench=. -benchmem; echo ; done
goos: darwin
goarch: amd64
pkg: github.com/sgykfjsm/sample-program-by-go/regexp_vs_replacer
BenchmarkDoRegexp-4                 2000           7200480 ns/op          130768 B/op        201 allocs/op
BenchmarkDoReplacer-4             100000            230524 ns/op           43552 B/op          3 allocs/op
PASS
ok      github.com/sgykfjsm/sample-program-by-go/regexp_vs_replacer     40.552s

goos: darwin
goarch: amd64
pkg: github.com/sgykfjsm/sample-program-by-go/regexp_vs_replacer
BenchmarkDoRegexp-4                 2000           6803820 ns/op          130768 B/op        201 allocs/op
BenchmarkDoReplacer-4             100000            240129 ns/op           43552 B/op          3 allocs/op
PASS
ok      github.com/sgykfjsm/sample-program-by-go/regexp_vs_replacer     40.670s

goos: darwin
goarch: amd64
pkg: github.com/sgykfjsm/sample-program-by-go/regexp_vs_replacer
BenchmarkDoRegexp-4                 2000           7402882 ns/op          130769 B/op        201 allocs/op
BenchmarkDoReplacer-4             100000            238944 ns/op           43552 B/op          3 allocs/op
PASS
ok      github.com/sgykfjsm/sample-program-by-go/regexp_vs_replacer     41.822s

10秒程度の実行でかなり差がついた。ざっくりと以下の様に言うことができると思う。

  • 実行回数だとstrings.Replacerは50倍程度多く実行することが出来る
  • 1回あたりの所要時間だと、strings.Replacerは1/35程度短い
  • 1回あたりのメモリ使用量だと、strings.Replacerは1/3程度に抑えることができる
  • メモリアロケーションの回数だと、strings.Replacerは1/70程度に抑えることができる

この結果から明らかなように、置換前後のリストを予め作成することができるのであれば、strings.Replacerを使うようにするべきだろう。また、なるべくなら正規表現は避けるようにしたほうが良さそうだ。