Try Golang! Goの正規表現は遅いとよく言われるが…
How slow is Golang’s regular expression?
「Goの正規表現は遅い」とよく言われます。どれくらい遅いかというと、一般的なインタープリタ言語と同じくらいの速度らしいです（雑）。なんでそんなに遅いのか、という話はこちら（英語本家）やこちら（日本語）で触れられている通り、探索対象のテキストが長文になった場合でも、線形に処理できるアルゴリズムが採用されているから、とのこと。他の言語で採用されているアルゴリズムだと、テキストが長文になると、指数関数的に速度が悪化するのだとか。
そんなわけで、ざっくり「Goの正規表現は遅い」という話は聞いていたのですが、機会があったので今更ながら試してみました。なお、今回比較するのは、短い文字列のパターンマッチ（true or false）について、Goの正規表現を使用した実装と使用しない実装の速度を比較しています。長文探索や文字列置換、他言語との比較は他の記事を参考にしてください。
まずは正規表現のベンチマーク
比較するにあたり、対象として下記のような関数を使用します。文字列が時刻表記hh:mmにマッチするかどうかを判定するだけの関数です。簡単のため、00:00~29:59までの入力を許容します。また、時間hhについては、一桁での入力も許容します（08:00だけでなく8:00もOK）。
var timeRe = regexp.MustCompile(`^[0-2]?[0-9]:[0-5][0-9]$`)func TimeRegExp(str string) bool {
return timeRe.MatchString(str)
}
ベンチマーク結果は下記のようになりました。
BenchmarkTimeRegExp-4 5000000 248 ns/op 0 B/op 0 allocs/op
BenchmarkTimeRegExp-4 5000000 208 ns/op 0 B/op 0 allocs/op
BenchmarkTimeRegExp-4 10000000 221 ns/op 0 B/op 0 allocs/op
BenchmarkTimeRegExp-4 10000000 242 ns/op 0 B/op 0 allocs/op
BenchmarkTimeRegExp-4 10000000 242 ns/op 0 B/op 0 allocs/op正規表現を使わずに書いてみる
続いて、同じ機能を持つ関数を、正規表現を使わずに書いてみます。まずはコロンで分割して、文字列の長さをチェックして。。かなり行数が増えましたが、こんな感じでしょうか（バグはないかな？）。
func TimeNoRegExp(str string) bool {
ts := strings.Split(str, ":")
if len(ts) != 2 {
return false
} // hh
switch len(ts[0]) {
case 1:
if ts[0][0] < '0' || '9' < ts[0][0] {
return false
}
case 2:
if ts[0][0] < '0' || '2' < ts[0][0] {
return false
}
if ts[0][1] < '0' || '9' < ts[0][1] {
return false
}
default:
return false
} // mm
switch len(ts[1]) {
case 2:
if ts[1][0] < '0' || '5' < ts[1][0] {
return false
}
if ts[1][1] < '0' || '9' < ts[1][1] {
return false
}
default:
return false
} return true
}
ベンチマーク結果はこちら。処理時間は平均で約半分になっています。ただ、正規表現を使用した場合よりも、少しだけですがメモリは使用するようになっていますね。
BenchmarkTimeNoRegExp-4 10000000 121 ns/op 32 B/op 1 allocs/op
BenchmarkTimeNoRegExp-4 10000000 118 ns/op 32 B/op 1 allocs/op
BenchmarkTimeNoRegExp-4 10000000 135 ns/op 32 B/op 1 allocs/op
BenchmarkTimeNoRegExp-4 10000000 106 ns/op 32 B/op 1 allocs/op
BenchmarkTimeNoRegExp-4 20000000 112 ns/op 32 B/op 1 allocs/op正規表現オブジェクトの関数使用時は排他制御がかかる
上で参照した記事でも触れられていますが、正規表現オブジェクトである*regexp.Regexp型のオブジェクトの関数の大半は、使用時に排他制御をかけているようです。つまり、Webサーバのバリデーションとして正規表現を使う場合、上の実装では高負荷時のボトルネックになりかねません。
そこで、対策としてCopy関数を使用した下記の関数についても、同様にベンチマークを測定してみましょう。
func TimeRegExpCopy(str string) bool {
return timeRe.Copy().MatchString(str)
}結果はこちら。Copyを使わない実装と比べて50倍以上の時間がかかっています。また、メモリの使用量も大幅に増加してしまっています。
BenchmarkTimeRegExpCopy-4 100000 13370 ns/op 39896 B/op 11 allocs/op
BenchmarkTimeRegExpCopy-4 100000 12299 ns/op 39896 B/op 11 allocs/op
BenchmarkTimeRegExpCopy-4 200000 10635 ns/op 39896 B/op 11 allocs/op
BenchmarkTimeRegExpCopy-4 100000 12630 ns/op 39896 B/op 11 allocs/op
BenchmarkTimeRegExpCopy-4 100000 12880 ns/op 39896 B/op 11 allocs/opざっとベンチマークを測定してみましたが、やはり正規表現を用いるより、ごりごりと頑張って実装した方がパフォーマンスの観点では大きく有利なようです。
と言っても、この程度の関数であればCopyを用いた実装ですら0.1msecもかからないので、可読性や品質（自前実装だとバグが混入しやすい）も考慮して、最適な実装を選択しましょう。
