Edited at

なぜGo言語の正規表現は遅いと言われるの?


はじめに

以前からなぜGoの正規表現は遅いと言われているのか疑問だったので調査してみました。

こちらの記事やこちらの記事を拝見する限り


  • ① 現実的なユースケース(例えばURLのパースなど)ではGo言語の正規表現は使うべきではなく、stringsパッケージの標準の関数を利用した方がパフォーマンスとしては良い。

  • ② Go言語で正規表現を利用するために必要な"正規表現オブジェクト"を並行にアクセスするにはパフォーマンスが問題になるので注意が必要。

とあります。なぜそうなのかというのは、それぞれ以下に集約できるようです。


  • ① Go言語標準の正規表現ライブラリは、正規表現と検査文字列の長さに対して常に$O(n^2)$のオーダーで計算量が増加する安定したアルゴリズムを採用している。

  • ② "正規表現オブジェクト"を用いたマッチング処理には排他制御が行われている。


調べてみる

Go言語のpkg/regexpの公式ドキュメントページを見にいくとGoのリードメンテナのRuss Cox氏のRegular Expression Matching Can Be Simple And Fastという記事(本記事で以降何度も参照します)に詳細が載っていました。


① 安定したアルゴリズムとは?

Ken Thompsonという人が1968年に論文で発表したThompson NFAアプローチという正規表現の実装手法をほぼそのままGo言語の標準パッケージとして採用したようです。

上記のRuss Cox氏の記事では入力文字 $a^n$ に対する正規表現 $a?^na^n$ のケースでパフォーマンス評価を行っています。

※ $n$ が3の場合、入力文字は $aaa$ で正規表現は $a?a?a?aaa$ です。

PerlやRubyなどの言語で採用されている正規表現エンジニアでは、このケースでは指数関数的にコストがかかるのに対し、Thompson NFAアプローチならば"理論的には"線形に増加していくとのことです。

著者もTypoじゃないよ、と前置きしているようにPerlの場合、$n$がある部分を堺に処理時間が急激に増加することが下記画像でわかります。

※ 横軸は$n$

grep3p

grep4p

Thompson NFAアプローチでは始めに対象の正現表現から非決定性有限オートマトン(NFA)を生成します。

※ ちなみに正規表現ならばNFAに変換可、逆も可能です。$\Rightarrow$の方向はNFAが閉じた系であることから簡単に証明が可能。逆向き$\Leftarrow$は少し難しく、任意個のステートを持つNFAでも3つのステートを正規表現へ2つステートにできるので帰納法により証明が可能。

Goの実装ではregOjb := regexp.MustCompile("a?a?a?aaa")と正規表現をコンパイルすることでregOjbには*regexp.Regexp型としてNFA構造へと変換されます。この処理はコストがかかるので、Goのユーザは基本的にプロセス起動の初期化時のみに生成するよう実装するべきです。

生成されたNFAモデルをもとに入力文字列をマッチ処理をする際、下記図のように各分岐ルートを"並列に独立"して処理されるならば最悪ケースでも文字数に対して線形時間で処理できることがThompson NFAアプローチでは保証されます。

nfa_linear


② なぜ排他制御が必要なのか?

Go言語の正規表現が遅いと言われる理由の一つに、マッチ処理にて排他制御を実施しているためと指摘されていますが、なぜ排他制御を実施するのでしょう?

それもThompson NFAアルゴリズムが理由のようです。

記事での説明によると、Thompson NFAアルゴリズムはマッチング処理の際、辿るステップに応じた決定性有限オートマトン(DFA)を計算することになります。

この計算結果により生成されたDFAを次の機会にも利用できるように、Goの実装ではDFAをキャッシュします。

そのキャッシュの処理時に排他制御が必要になるということです。

実装を見ると以下の箇所にてmatchPoolという専用のメモリ領域でキャッシュ戦略をしていることがわかります。


excerpt_exec.go

// doExecute finds the leftmost match in the input, appends the position

// of its subexpressions to dstCap and returns dstCap.
//
// nil is returned if no matches are found and non-nil if matches are found.
func (re *Regexp) doExecute(r io.ByteReader, b []byte, s string, pos int, ncap int, dstCap []int) []int {
// 中略
m := re.get() // キャッシュがあれば利用。なければ新しいDFAを生成。
i, _ := m.inputs.init(r, b, s)

m.init(ncap)
if !m.match(i, pos) {
re.put(m) // DFAのキャッシュを保存 ← このとき排他制御を実施
return nil
}

dstCap = append(dstCap, m.matchcap...)
re.put(m) // DFAのキャッシュを保存 ← このとき排他制御を実施
return dstCap


PoolにDFAを入れ込む箇所にて以下のように排他制御がかかっていることがわかります。


excerpt_pool.go

// Put adds x to the pool.

func (p *Pool) Put(x interface{}) {
if x == nil {
return
}
if race.Enabled {
if fastrand()%4 == 0 {
// Randomly drop x on floor.
return
}
race.ReleaseMerge(poolRaceAddr(x))
race.Disable()
}
// (後略)


計測してみる

上記記事でのケース(入力文字 $a^n$ に対する正規表現 $a?^na^n$)にてGoの標準正規表現エンジンとPerlのものでどのように差が出るか実際に計測してみます。


実行環境


  • Macbook Pro 13-inch, 2017


    • macOS Mojave version 10.14.6

    • プロセッサ 2.3GHz Intel Core i5



  • Go


    • go version go1.12.5 darwin/amd64



  • Perl


    • perl 5, version 18, subversion 4 (v5.18.4) built for darwin-thread-multi-2level




Goの場合


main.go

package main

import (
"fmt"
"regexp"
"time"
)

func main() {
for _, n := range []int{1, 10, 100, 1000, 10000} {
// Generate target string
var s1 string
for i := 0; i < n; i++ {
s1 += "a?"
}
var s2 string
for i := 0; i < n; i++ {
s2 += "a"
}
re := s1 + s2 // a?a?a?aaa (ex. n==3)

fmt.Println("n:", n)
start := time.Now()
// Compile to NFA
regOjb := regexp.MustCompile(re)
// Do matching
regOjb.MatchString(s2)
end := time.Now()
fmt.Printf("%f [sec]\n", (end.Sub(start)).Seconds())
}
}



出力結果

n: 1

0.000094 [sec]
n: 10
0.000053 [sec]
n: 100
0.000237 [sec]
n: 1000
0.050289 [sec]
n: 10000
3.086724 [sec]

上記の結果から$n$が10倍になる毎に処理時間がおおよそ100倍分になっているので、二次関数のオーダー$O(n^2)$ということがわかります。

この観測結果は上記記事の中でもPerformanceの節にて言及されており、正規表現の長さ$m$と入力文字列の長さ$n$のとき、実際には$O(mn)$のオーダーとなっていると記述されています。


Thompson's algorithm maintains state lists of length approximately n and processes the string, also of length n, for a total of O(n2) time. (The run time is superlinear, because we are not keeping the regular expression constant as the input grows. For a regular expression of length m run on text of length n, the Thompson NFA requires O(mn) time.)


実装を見ると、この部分からだいたいを読み取れるように、NFA構造上でマッチング処理が走る際、並行で走る複数スレッド分(正規表現の長さm分)に対してのfor文(step関数内のfor文)が、ステップ分(入力文字列の長さn分)に対してのfor文(match関数内のfor文)内で走っているため$O(mn)$のオーダーであると推測できます。


Perlの場合

上記のGoと同じ内容のプログラムをPerlで作って動かしてみます。


re_test.pl

use Time::HiRes qw( gettimeofday tv_interval );

my @ns = (1, 10, 25, 26, 27, 28, 29, 30);
foreach my $n (@ns) {
my $s1 = "";
for (my $i = 0; $i < $n; $i++) {
$s1 = $s1 . "a?";
}
my $s2 = "";
for (my $i = 0; $i < $n; $i++) {
$s2 = $s2 . "a";
}
my $re = $s1 . $s2; # a?a?a?aaa (ex. n==3)

my $t0 = [gettimeofday];
# Do matching
$s2 =~ /$re/;
my $elapsed = tv_interval($t0);
print "n: $n\n";
print "$elapsed [sec]\n";
}



出力結果

n: 1

1.4e-05 [sec]
n: 10
8.7e-05 [sec]
n: 25
1.31766 [sec]
n: 26
2.631269 [sec]
n: 27
5.284664 [sec]
n: 28
10.651156 [sec]
n: 29
20.998345 [sec]
n: 30
42.14693 [sec]

上記の結果から、$n$が1つ増えるごとに2倍に処理時間が増加しているので$O(2^n)$の指数関数のオーダーであることが確認できました。

記事の下記箇所にもあるようにPerlやRubyなどで実装されている手法(Backtracking)では正規表現$a?^na^n$にて$2^n$個の全パターンを網羅するよう処理してしまうためこの結果になるとわかります。


Backtracking regular expression implementations implement the zero-or-one ? by first trying one and then zero. There are n such choices to make, a total of 2n possibilities. Only the very last possibility—choosing zero for all the ?—will lead to a match. The backtracking approach thus requires O(2n) time, so it will not scale much beyond n=25.


GoとPerlの結果から記事における下記図の計測結果を再現することができました。

※ 下記グラフの縦軸は対数をとっています。

grep1p


感想

Go言語における正規表現パフォーマンスの特徴はGo言語の設計自体に依るものではなく、正規表現におけるGoの標準パッケージ上の実装がThompson NFAという他言語とは異なるモデルがもとになっていることに由来するとわかりました。

この調査前はGoの正規表現は使うべきではないと頭ごなしに思っていましたが、他言語が苦手とする大きな文字数の正規表現利用は得意とわかったので状況に応じてしっかりと検証しようと思います。


追記

2019年8月14日記載

コメント欄にてご指摘いただいたように、本記事では包括的に正規表現エンジンを扱えていないのにGo以外がすべて同じであるかのような言い方をしていたので修正しました。

また、本記事(Russ Cox氏の記事)の比較は正規表現 $a?^na^n$ というPerlやRuby等の正規表現エンジンでの方法(Backtracking)では苦手とする特殊なケースであるのでそういったケースであることを明示するように修正しました。


参考