🚀

Goの正規表現が遅いって言う人がいたから、（速い）正規表現エンジンを作ったよ

2021/12/19に公開

正規表現

tech

はじめに

「Goの正規表現は遅い」
そんなふうによく言われていました。（最近はあまり聞かなくなりましたが）
たとえば、↓の記事ではPythonの正規表現と比較して1.5倍くらい遅いという結果になっています：

この話には「Goの正規表現は最悪時間が短くなるように安定したアルゴリズムを採用しているから」という回答があります：

↑の記事の比較では、GoがPerlに対して約10倍以上高速という結果が出ているので、「Goの正規表現は遅くない！はい、論破ー！」というわけですね。

なんでこうなるのかも↑の記事で説明されているとおりですが、Perl（などのバックトラック型エンジン）が入力長に対して指数関数的に実行時間が伸びていくのに対し、Goの正規表現エンジンは入力長に対して線形時間で実行時間が伸びていくアルゴリズムを採用しているため、入力が長くなると急激にGoのほうが有利になるからです：

Perl vs Go

一方で、入力が短いケースではGoの正規表現が遅いのは事実なので、ここの領域でGoが遅いと言われるのは言い逃れできないのではないかと思います^[1]：

ここの領域

実際問題として、「Goの正規表現が遅い」と言っている人たちは、この領域で正規表現を使いたくて文句を言っているのだと思います。

文句言ってるヒマがあるなら、自分で正規表現エンジン作ればいんじゃね？と思ったので作りました（ぇ^[2]

そう、作れるんですよ、Go言語ならね！

どれくらい遅いの？

作る前に、まずは現状と目標の確認といきましょう。

ベンチマークとして、最初にあげた記事で使われているSIPアドレスにマッチする正規表現を使います。
記事が3年前とちょっと古いので、今の環境で測定し直しておきましょう。

こんなPythonスクリプトを書いて測定しました↓

import pytest
import re

sip_re = re.compile('^["]{0,1}([^"]*)["]{0,1}[ ]*<(sip|tel|sips):(([^@]*)@){0,1}([^>^:]*|\\[[a-fA-F0-9:]*\\]):{0,1}([0-9]*){0,1}>(;.*){0,1}$')
test_strings = [
    "\"display_name\"<sip:0312341234@10.0.0.1:5060>;user=phone;hogehoge",
    "<sip:0312341234@10.0.0.1>",
    "\"display_name\"<sip:0312341234@10.0.0.1>",
    "<sip:whois.this>;user=phone",
    "\"0333334444\"<sip:[2001:30:fe::4:123]>;user=phone"
]

def exec_re():
    for s in test_strings:
        sip_re.match(s)
    return True

def test_re_benchmark(benchmark):
    assert benchmark(exec_re)

if __name__ == '__main__':
    pytest.main(['-v', __file__])

なお測定環境は次の通りです：

OS: Windows 11
Python: 3.10.0
CPU: Core i7-1065G7 1.30GHz (ブースト時3.90GHz）
RAM: 16GB

実行結果がこちら↓

❯ python .\test_benchmark.py
================================================= test session starts =================================================
platform win32 -- Python 3.10.0, pytest-6.2.5, py-1.11.0, pluggy-1.0.0 -- C:\Python310\python.exe
cachedir: .pytest_cache
benchmark: 3.4.1 (defaults: timer=time.perf_counter disable_gc=False min_rounds=5 min_time=0.000005 max_time=1.0 calibration_precision=10 warmup=False warmup_iterations=100000)
rootdir: C:\Users\Daisu\go\src\github.com\Maki-Daisuke\go-yarex
plugins: benchmark-3.4.1
collected 1 item

test_benchmark.py::test_re_benchmark PASSED                                                                      [100%]


----------------------------------------------- benchmark: 1 tests -----------------------------------------------
Name (time in us)        Min       Max    Mean  StdDev  Median     IQR  Outliers  OPS (Kops/s)  Rounds  Iterations
------------------------------------------------------------------------------------------------------------------
test_re_benchmark     5.4000  157.9000  6.3692  3.8002  5.8000  0.3000  911;5042      157.0050   42373           1
------------------------------------------------------------------------------------------------------------------

Legend:
  Outliers: 1 Standard Deviation from Mean; 1.5 IQR (InterQuartile Range) from 1st Quartile and 3rd Quartile.
  OPS: Operations Per Second, computed as 1 / Mean
================================================== 1 passed in 1.44s ==================================================

色々出ていますが、今回は平均時間で比べるので Mean を見ます。
約6.4マイクロ秒かかっていますね。
これが今回の目標値となります。

次に、Goの標準ライブラリの regexp の速度を測定します。
ベンチマークプログラムは次の通り：

package main_test

import (
	"os"
	"regexp"
	"testing"
)

var sip = `^["]{0,1}([^"]*)["]{0,1}[ ]*<(sip|tel|sips):(([^@]*)@){0,1}([^>^:]*|\[[a-fA-F0-9:]*\]):{0,1}([0-9]*){0,1}>(;.*){0,1}$`
var re *regexp.Regexp

func TestMain(m *testing.M) {
	re = regexp.MustCompile(sip)
	os.Exit(m.Run())
}

var testStrings = []string{"\"display_name\"<sip:0312341234@10.0.0.1:5060>;user=phone;hogehoge",
	"<sip:0312341234@10.0.0.1>",
	"\"display_name\"<sip:0312341234@10.0.0.1>",
	"<sip:whois.this>;user=phone",
	"\"0333334444\"<sip:[2001:30:fe::4:123]>;user=phone",
}

func BenchmarkSipPattern(b *testing.B) {
	for i := 0; i < b.N; i++ {
		for _, s := range testStrings {
			re.MatchString(s)
		}
	}
}

なお、使用した Go のバージョンは 1.17.3 です:

❯ go version
go version go1.17.3 windows/amd64

実行結果は次の通り：

❯ go test '-test.bench' .
goos: windows
goarch: amd64
pkg: github.com/Maki-Daisuke/regexp-bench
cpu: Intel(R) Core(TM) i7-1065G7 CPU @ 1.30GHz
BenchmarkSipPattern-8             153391              7901 ns/op
PASS
ok      github.com/Maki-Daisuke/regexp-bench    1.344s

約7.9マイクロ秒。上のPythonの結果と比べると1.23倍遅いという結果でした。
前掲の記事に比べると差が小さくなっていますが、それでも20％以上遅いということですね。

バックトラック型エンジンを作ったよ

というわけで、バックトラック型のエンジンを作りました↓

これを使って、ベンチマークプログラムを次のように書き換えました。基本的には regexp を yarex に置き換えただけです：

package main_test

import (
	"os"
	"testing"

	"github.com/Maki-Daisuke/go-yarex"
)

var sip = `^["]{0,1}([^"]*)["]{0,1}[ ]*<(sip|tel|sips):(([^@]*)@){0,1}([^>^:]*|\[[a-fA-F0-9:]*\]):{0,1}([0-9]*){0,1}>(;.*){0,1}$`
var re *yarex.Regexp

func TestMain(m *testing.M) {
	re = yarex.MustCompile(sip)
	os.Exit(m.Run())
}

var testStrings = []string{"\"display_name\"<sip:0312341234@10.0.0.1:5060>;user=phone;hogehoge",
	"<sip:0312341234@10.0.0.1>",
	"\"display_name\"<sip:0312341234@10.0.0.1>",
	"<sip:whois.this>;user=phone",
	"\"0333334444\"<sip:[2001:30:fe::4:123]>;user=phone",
}

func BenchmarkSipPattern(b *testing.B) {
	for i := 0; i < b.N; i++ {
		for _, s := range testStrings {
			re.MatchString(s)
		}
	}
}

実行結果はこちら↓

❯ go test '-test.bench' .
goos: windows
goarch: amd64
pkg: github.com/Maki-Daisuke/regexp-bench
cpu: Intel(R) Core(TM) i7-1065G7 CPU @ 1.30GHz
BenchmarkSipPattern-8             174038              6426 ns/op
PASS
ok      github.com/Maki-Daisuke/regexp-bench    1.231s

結果は6.4マイクロ秒！偶然にも、Pythonの実行時間とほぼ同じになりましたね！

でも、まだちょっと負けてますよね…

まだだ！まだ終わらんよ！！

ベンチマークプログラムの正規表現文字列のところを次のように書き換えましょう：

//go:generate yarexgen benchmark_test.go

var sip = `^["]{0,1}([^"]*)["]{0,1}[ ]*<(sip|tel|sips):(([^@]*)@){0,1}([^>^:]*|\[[a-fA-F0-9:]*\]):{0,1}([0-9]*){0,1}>(;.*){0,1}$` //yarexgen

go generate 用のコメントと、正規表現文字列のうしろに //yarexgen というコメントをつけました。

そして、おもむろに yarexgen というコマンドをインストールして go generate を実行しましょう：

❯ go install "github.com/Maki-Daisuke/go-yarex/cmd/yarexgen"
❯ go generate

こうしてからさきほどのベンチマークを実行すると：

❯ go test '-test.bench' .
goos: windows
goarch: amd64
pkg: github.com/Maki-Daisuke/regexp-bench
cpu: Intel(R) Core(TM) i7-1065G7 CPU @ 1.30GHz
BenchmarkSipPattern-8             259381              4509 ns/op
PASS
ok      github.com/Maki-Daisuke/regexp-bench    2.193s

あら不思議！実行時間が30％も短くなりました！

yarexgen が何をしているのかというと、プログラムから //yarexgen とマーキングされた文字列を探して、その正規表現文字列にマッチングするためのGoプログラムを生成しています。
生成されたGoプログラムは、他のプログラムと一緒にGoコンパイラによってコンパイルされるという寸法です。

yarex.MustCompile (yarex.Compile) は、文字列の事前にコンパイルされたバージョンがあればそちらを、なければ実行時に構文解析してインタプリタで実行するようになっているので、同じAPIから透過的に利用することができます。

どんなコードが吐き出されているのかのぞいてみたりして、皆さんも遊んでみてくださいね！

おまけ

ちなみに、バックトラック型なので、Go標準の regexp がサポートしていない後方参照もサポートしています：

func TestBackRef(t *testing.T) {
	// re, err := regexp.Compile(`(hoge)\1fuga`) //←これだとエラーになる
	re, err := yarex.Compile(`(hoge)\1fuga`) //yarexgen
	if err != nil {
		panic(err)
	}
	if !re.MatchString("hogehogefuga") {
		t.Error(`should match against "hogehogefuga", but didn't`)
	}
	if re.MatchString("hogefuga") {
		t.Error(`shouldn't match against "hogefuga", but did`)
	}
}

まとめ

Goの regexp は最悪ケースの時間が短くなるアルゴリズムを採用している
- 短い入力の場合は逆に時間がかかる
なので、バックトラック型の正規表現エンジンを実装してみた
- Pythonの正規表現とほぼ同等
- Cで実装されてるのと同等の速度なら、がんばってるほうでは？
事前コンパイルをすればもっと速いよ！
ただし、SIPアドレスのマッチングでしかベンチマークしていないので、他の正規表現で速いのかはわからない（ぇ
Go標準の正規表現エンジンは短い文字列に対しても十分に速いので、 ほとんどのユースケースでは標準ライブラリを使っておくのが吉 ですよ！^[3]

山積した課題

まだ一部の正規表現しか実装していません
- ., *, +, ?, {}, (), [], ^, $ くらい
- (?msi:～) のような修飾子も未実装
public API もちょっとしか実装できてません
- MatchString, FindString, FindStringIndex のみ
ドキュメントが真っ白です

あとはひとつひとつ地道に実装するだけなので、手が空いたときにでも実装します。

脚注

ちなみに、２つ目の記事では排他制御があるから遅いという話がありますが、Go 1.12からはこの排他制御の問題がなくなったので、手動で Copy をする必要がなくなりました ↩︎
今回の記事の原題が「Goの正規表現が遅いって言ってるヤツが本当にイケてない件」だったのはここだけの話 ↩︎
ぶっちゃけ、一番大変だったのは標準のエンジンよりも速くするところだったりした… ↩︎