regexpとの付き合い方 〜 Go言語標準の正規表現ライブラリのパフォーマンスとアルゴリズム〜

こんにちは! エンジニアの臼井です。
この記事は、 eureka Advent Calendar 2016 20日目の記事です。
昨日は、太田さんの angular-cliで始めるAngular2 という記事でした。
 
今日の記事では、Go言語標準の正規表現ライブラリ、 regexp についてお話します。
 
本稿において使用するGo言語のバージョンは 1.7系とします。

regexp は遅い

残念ながら regexp は、PHP や Ruby 等のメジャーなスクリプト言語の正規表現処理ライブラリと比較して、多くの利用ケースにおいて同等のパフォーマンスとなっています。
 
他の通常の処理において、Go言語のパフォーマンスは C++ など VM を必要としない実行ファイルを生成する言語と比肩するパフォーマンスがありますが、 regexp はスクリプト言語の正規表現処理と同等あるいはそれより劣る処理時間となるケースが多いです。
すぐに作成出来る小さな正規表現に対して使用した場合、マイクロベンチマークですが以下のような結果となります。

<?php
// PHP 7.0.8
$count = 1000000;
$start = microtime(true);
for($i = 0;$i < $count; $i++) {
    preg_match("/^foo/", "foo");
}
$end = microtime(true);
echo 1000000000 * (($end - $start) / $count) . " ns/op" . PHP_EOL;
// -> 200 ns/op 程度
// go 1.7.4 以下のベンチマークコードで go test -v -bench -benchmem を実行
func BenchmarkMatchFooBarBaz(b *testing.B) {
    r := regexp.MustCompile("^foo")
    const input = "foo"
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        r.MatchString(input)
    }
}
// -> BenchmarkMatchFoo-4 10000000 230 ns/op 0 B/op 0 allocs/op

本来多くの処理で高パフォーマンスが期待できる Go言語において、なぜこんなにも差が出るのでしょうか。
この部分に関して、公式ドキュメントとその周辺およびソースコードから紐解くことを試み、Go言語における文字列検査との付き合い方を身につけましょう。
 
OS 開発者など低レイヤーのソフトウェア開発者がカーネルのソースコードを読むように、Go言語開発者にとっては公式ドキュメントを理解することも重要な仕事のひとつです。

公式ドキュメント

regexp には、以下のような記述があります。

The regexp implementation provided by this package is guaranteed to run in time linear in the size of the input.
(This is a property not guaranteed by most open source implementations of regular expressions.)
For more information about this property, see
http://swtch.com/~rsc/regexp/regexp1.html
or any book about automata theory.

大まかに訳しますと、以下のようになります。
 

この regexp の実装は、入力に対して線形の時間で行われることが保証されています。
(これは他のほとんどのオープンソースの正規表現の実装には無い性質です。)
この性質の詳細については、 http://swtch.com/~rsc/regexp/regexp1.html またはオートマトンについての書籍を参照して下さい。

アルゴリズムが他の多くの正規表現実装とは異なることが、最初の方に記述されています。
 
オートマトンについての書籍、または提示されたURLを参照のこと、とあります。今回は提示されたURLを読み解いていきます。

Russ Cox による解説の概要

Russ Cox は Go の開発者の一人で、 regexp のコミットログからもそのことが確認できます。
以下、上記で提示されたWebページについて、そこで説明されている内容の概略を示します。
本節での画像は、特に断りの無い場合は上記URLからの引用となります。
 
上記のページの冒頭の解説では、以下のことが述べられています。
 
– 正規表現のマッチングには2つのアプローチがあり、広く多くの言語で使われる標準的なものと、Thompson NFA と呼ばれる実装がある。
(a\?){n}a{n} (n は 0 以上の整数。n=3 のとき a?a?a?aaa) で定まる正規表現を用いて、同じnに対して a がn文字連続した文字列(n = 3 のとき aaa)をマッチングにかけると、Perl 5.8.7 の実装においては n = 100 で 10の15乗年(1000兆年)の時間がかかる。
 
あるバージョン(2005年頃)の Perl における正規表現の実装では、上記の様な繰り返しを多く含むパターンにおいて、繰り返し数に対して指数関数的に処理時間が増加していることを例に出しています。
以下にそのグラフを引用しますが、文中にあるように桁の表記がタイポなのではないかなど、信じられないような結果となっています。

https://swtch.com/~rsc/regexp/grep3p.png より引用 https://swtch.com/~rsc/regexp/grep4p.png より引用

以降、正規表現の基本について解説した後、文字列と正規表現を有限オートマトン(状態機械(ステートマシン))として表現する方法について、具体的な文字列と正規表現を用いて説明しています。
 
探査の効率が最悪のケースで非効率なアルゴリズムを有限オートマトンで示した後、改善されたアルゴリズムを示し、そのC言語によるNFA(非決定性有限オートマトン)実装を用いて詳細に解説しています。
nをパラメータとした (a\?){n}a{n} の正規表現について、入力を通常のアルゴリズムによる計算量が O(2^n) に対して、 NFA実装による計算量が O(n^2) であることが示されています。
また、n を正規表現の長さ、m を入力文字列の長さとすると、NFA実装による計算量は O(mn) となり、入力文字列の長さに対して線形となるため、複数の様々な入力文字列に対して処理時間が安定するであろうことがわかります。

https://swtch.com/~rsc/regexp/grep1p.png より引用

正規表現と入力の長さn

引用した上記のグラフでは、実際の処理系における処理時間を測定し補完した処理時間が示されています。
縦軸が対数目盛となっていることに注意して下さい。
Thompson NFA 実装は多項式時間のアルゴリズムであるため、このグラフ上では対数関数のような曲線となっています。
一方で、もう一方の標準的なアルゴリズムについては対数グラフであるにもかかわらず直線を示しており、この計算量が指数関数時間であることが示されています。

Go言語における regexp パッケージの使いどころ

Russ Cox が regexp に採用したアルゴリズムの説明を見る限り、他言語の正規表現アルゴリズムよりもGo言語の正規表現アルゴリズムの方が常に高速であるように理解できますが、始めに述べた様に現実的には他のスクリプト言語と同等の速度となっています。
この問題により、Go言語で文字列を検査する際に regexp パッケージを盲目的に使用するのは良しとされていません。
strings パッケージを使用した方がパフォーマンス上の問題を回避できるため、こちらの利用が推奨されます。
正規表現の前方一致のみと同じ結果を与える、 strings.HasPrefix についてベンチマークを試みます。

func BenchmarkHasPrefixFoo(b *testing.B) {
    const input = "foo"
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        strings.HasPrefix(input, input)
    }
}
// -> BenchmarkHasPrefixFoo-4 300000000 4.31 ns/op 0 B/op 0 allocs/op

1回の実行につき10ナノ秒未満という、 regexp パッケージを使用した場合と比べて数十倍早い結果が得られました。
なぜここまで早いのか、この実装を見てみましょう。

// github.com/golang/go/src/strings/strings.go
// HasPrefix tests whether the string s begins with prefix.
func HasPrefix(s, prefix string) bool {
    return len(s) >= len(prefix) && s[0:len(prefix)] == prefix
}

ビルトイン関数の len による文字列の長さ比較とスライス演算のみの1行で記述されています。
後方一致の strings.HasSuffix 関数についても同様です。
 
では、パフォーマンスを重視するならいつでも strings パッケージのみを用いて正規表現の代替処理を実装することが良いことなのでしょうか。
例えば、/user/8213473c846e3822b95b802ee91c1229 のようなパスの検査を考えてみます。
つまり正規表現では、 ^/user/[0-9a-f]+$ と表される文字列を検査する時、 strings パッケージの関数ではどのように入力を検査すればよいでしょうか。
strings.HasPrefix^/user/ を判定し、 strings.Split/ で分割し、分割後のスライスのサイズが3であることを確認します。その後、スライスの最後の要素が数値とaからfまでのアルファベットのみからなるかどうかを見れば判定はできそうです。
しかし、利用側からは関数で隠蔽するとはいえかなり実装が汚くなり、バグを仕込んでしまいそうなにおいがします。
また、細かい判定処理が増えパフォーマンス劣化と可読性低下がいずれも発生するのでこの場合は、 regexp を使った方がより良い判定処理であると考えます。
 
ただし、regexp を使用するにあたり、さらに注意すべき点があります。
正規表現オブジェクトのコンパイルはコストのかかる処理であり、これは以下のようにグローバル領域にコンパイル済みの状態で宣言します。
検査時に随時生成することは推奨されません。

package somepackage

import "regexp"

var re = regexp.MustCompile("^/user/[0-9a-f]+$")
...

ただし、この正規表現オブジェクトは多くの関数の実行時に排他制御がかかっているため、複数の処理から同時にアクセスされる場合にもパフォーマンス劣化が発生します。
 

当該部分のソースコードを見るとそのことがわかります。

// github.com/golang/go/src/regexp/exec.go
// doExecute finds the leftmost match in the input and returns
// the position of its subexpressions.
func (re *Regexp) doExecute(r io.RuneReader, b []byte, s string, pos int, ncap int) []int {
    m := re.get()
    // ... 中略
    if m.op != notOnePass {
        if !m.onepass(i, pos) {
            re.put(m)
            return nil
        }
    // ... 後略
}

// github.com/golang/go/src/regexp/regexp.go
// get returns a machine to use for matching re.
// It uses the re's machine cache if possible, to avoid
// unnecessary allocation.
func (re *Regexp) get() *machine {
    re.mu.Lock()
    if n := len(re.machine); n > 0 {
        z := re.machine[n-1]
        re.machine = re.machine[:n-1]
        re.mu.Unlock()
        return z
    }
    re.mu.Unlock()
    z := progMachine(re.prog, re.onepass)
    z.re = re
    return z
}

// put returns a machine to the re's machine cache.
// There is no attempt to limit the size of the cache, so it will
// grow to the maximum number of simultaneous matches
// run using re.  (The cache empties when re gets garbage collected.)
func (re *Regexp) put(z *machine) {
    re.mu.Lock()
    re.machine = append(re.machine, z)
    re.mu.Unlock()
}

doExecute は多くの regexp.Regexp の他のメソッドの中で呼ばれ、その処理の最初の get, put メソッドで自身にロックをかけています。
 

この問題は、バージョン1.6系から回避策が提示されており、 以下の regexp.Copy メソッドを用いて正規表現オブジェクトをコピーしてから実行することで対応が可能です。

// Copy returns a new Regexp object copied from re.
//
// When using a Regexp in multiple goroutines, giving each goroutine
// its own copy helps to avoid lock contention.
func (re *Regexp) Copy() *Regexp {
    // It is not safe to copy Regexp by value
    // since it contains a sync.Mutex.
    return &Regexp{
        regexpRO: re.regexpRO,
    }
}

regexp.Copy を使用した問題回避策について、 正規表現の検査時に goroutine を使用しないケースであれば実施の必要はないでしょう。 ですが、例えばWebサーバとして起動していてユーザからの入力のバリデーションを行うような用途では、高負荷時にこの回避策の有無で大きくパフォーマンスが異なってくると考えられます。regexp.Copy で正規表現オブジェクトのコピーを行ってから正規表現による検査を実施する処理は、イディオムとして覚えておくべきでしょう。

まとめ

Go言語の実装者によるアルゴリズム解説を読み、ソースコードを見たりベンチマークをとるなどいろいろなことをしましたが、まとめると以下のような結論になります。
 

  • Go言語標準の正規表現ライブラリは、正規表現や検査文字列の長さに対して線形で計算量が増加する安定したアルゴリズムを採用している。
    • シンプルな実装では正規表現の長さに対して指数関数で計算量が増加する。
  • だが、通常の使用上ではパフォーマンスがあまり高くない。
    • さらに排他制御の問題も抱える。
  • 可読性やパフォーマンスとのバランスをとった上で、 `strings` パッケージの関数を優先的に使用すること。
  • 並行アクセスが想定される正規表現オブジェクトに対しては `regexp.Copy` を使用してコピーされたオブジェクトを使用すること。
  • 公式ドキュメントから追っていくだけでこれだけの知見が容易に得られるGo言語はいい……

 
以上となります。

Go言語は公式ドキュメントが充実していることと言語仕様の小ささから、ドキュメントの内容とソースコードの往復による学習が比較的容易です。
なんらかのプログラミング言語をひとつ学習した人であれば、相当なスピードで習得することができるでしょう。 また、最近では初歩の解説の書籍も充実し始め、新しい言語を習得する際によくある開発環境構築でのつまずきもかなり解消されています。
 

eureka Advent Calendar では、本稿以外にもGo言語に関する記事がいくつかあります。 私たちの記事をきっかけに、冬休みにGo言語を習得してみようかなと考えて下さる方がいれば幸いです。
 
明日は@takochuuさんの「Go言語初心者がハマった2つのポイント」です。お楽しみに!
 

参考資料

  • このエントリーをはてなブックマークに追加

エウレカでは、一緒に働いていただける方を絶賛募集中です。募集中の職種はこちらからご確認ください!皆様のエントリーをお待ちしております!

Recommend

Swift3.0でJSONを厳しく安全に扱えるライブラリを作りました

Go言語の社内情報共有に関する試み、講演動画のすゝめとテストに関する翻訳を添えて