Goで正規表現を使うときに考えたいこと

# はじめに

以前コードレビューをしたときに、日時形式のバリデーションに正規表現が利用されていたので、 `time.Parse` 使おうとコメントしました。また、それについて記事にしてみようと伝え、[記事も書いてもらいました](https://qiita.com/shohei-ojs/items/17348a282add17c65ab2)。


あらためてベンチマークを実行すると、time.Parseによるチェックが高速なことが分かります。

```go
var validater = regexp.MustCompile(`\d{4}(/\d{2}){2} \d{2}(:\d{2}){2}`)
func BenchmarkRegexpPack(b *testing.B) {
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        validater.MatchString("2012/12/10 12:30:45")
    }
}

func BenchmarkTimePack(b *testing.B) {
    layout := "2006/01/02 15:04:05"
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        time.Parse(layout, "2012/12/10 12:30:45")
    }
}

// BenchmarkRegexpPack-12    	 4026220	       295 ns/op
// BenchmarkTimePack-12      	 7007890	       171 ns/op
```


ここでは、なぜ time.Parse は高速に処理ができるのかをチェックするとともに、Goでパターンマッチを高速に行いたい場合にどのように実装すればよいのかを見ていきます。

# time.Parse の実装

ソースコードでいうと、主な処理は [parse](https://github.com/golang/go/blob/8feeada50cf3f783fe3c8113d5da51ad8c0b3014/src/time/format.go#L824-L1242) と [nextStdChunk](https://github.com/golang/go/blob/8feeada50cf3f783fe3c8113d5da51ad8c0b3014/src/time/format.go#L149-L284) にまとめられています。

簡単に説明すると、以下のようなステップで実行されています。

1. layoutを元に、日時に関係がある部分の文字を文字列として切り出す
2. 切り出した文字列を数値に変換
3. layoutを元に、1→2を繰り返す
3. 文字列の長さが0になったら、数値への変換プロセスが終了
4. これまでの値を元に数値を微調整
5. 数値を元に `Date(year, Month(month), day, hour, min, sec, nsec, defaultLocation)` として`time.Time`を返却

この処理のうち、4~5の処理はパターンマッチに関係ない部分です。また1,2の処理も、様々な時間フォーマットに対応するために余分な処理が多く含まれています。しかし、その条件を含めても冒頭のベンチマークでわかったとおりtime.Parseを利用したパターンマッチのほうが高速にできます。

```go
func parse(layout, value string, defaultLocation, local *Location) (Time, error) {
	alayout, avalue := layout, value
	rangeErrString := "" // set if a value is out of range
	amSet := false       // do we need to subtract 12 from the hour for midnight?
	pmSet := false       // do we need to add 12 to the hour?

	// Each iteration processes one std value.
	for {
		var err error
		prefix, std, suffix := nextStdChunk(layout)
		stdstr := layout[len(prefix) : len(layout)-len(suffix)]
		value, err = skip(value, prefix)
		if err != nil {
			return Time{}, &ParseError{alayout, avalue, prefix, value, ""}
		}
		if std == 0 {
			if len(value) != 0 {
				return Time{}, &ParseError{alayout, avalue, "", value, ": extra text: " + value}
			}
			break
		}
		layout = suffix
		var p string
		switch std & stdMask {
		case stdYear:
			if len(value) < 2 {
				err = errBad
				break
			}
			hold := value
			p, value = value[0:2], value[2:]
			year, err = atoi(p)
			if err != nil {
				value = hold
			} else if year >= 69 { // Unix time starts Dec 31 1969 in some time zones
				year += 1900
			} else {
				year += 2000
			}
		// ...

	}
	if pmSet && hour < 12 {
		hour += 12
	} else if amSet && hour == 12 {
		hour = 0
	}

	// ...
	return Date(year, Month(month), day, hour, min, sec, nsec, defaultLocation), nil
}

func nextStdChunk(layout string) (prefix string, std int, suffix string) {
	for i := 0; i < len(layout); i++ {
		switch c := int(layout[i]); c {
		case 'J': // January, Jan
			if len(layout) >= i+3 && layout[i:i+3] == "Jan" {
				if len(layout) >= i+7 && layout[i:i+7] == "January" {
					return layout[0:i], stdLongMonth, layout[i+7:]
				}
				if !startsWithLowerCase(layout[i+3:]) {
					return layout[0:i], stdMonth, layout[i+3:]
				}
			}
			...

```

## 類似の事例

その他の標準ライブラリで見ると、 `url.Parse` もシンプルに実装されています。ソースコードは[こちら](https://github.com/golang/go/blob/8feeada50cf3f783fe3c8113d5da51ad8c0b3014/src/net/url/url.go#L503-L579)。

URLスキーマをチェックする部分では、パターンマッチではなく、 `'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z'` のように文字列をbyte型として取り出し、byteの比較を用いて実装されています。

```go
func getscheme(rawurl string) (scheme, path string, err error) {
	for i := 0; i < len(rawurl); i++ {
		c := rawurl[i]
		switch {
		case 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z':
		// do nothing
		case '0' <= c && c <= '9' || c == '+' || c == '-' || c == '.':
			if i == 0 {
				return "", rawurl, nil
			}
		case c == ':':
			if i == 0 {
				return "", "", errors.New("missing protocol scheme")
			}
			return rawurl[:i], rawurl[i+1:], nil
		default:
			// we have encountered an invalid character,
			// so there is no valid scheme
			return "", rawurl, nil
		}
	}
	return "", rawurl, nil
}
```

## Goで正規表現をあつかう場合

Goの正規表現が遅いのは、Perl, Ruby, PythonなどがCのライブラリを利用しているのに対し、Goの標準ライブラリはC言語を排除して実装されていることが一因です。
基本的には、言語を抽象化するほど速度は犠牲になるので速度の面ではC言語が有利です。例えばGoから高速に正規表現マッチを利用したい場合、Perl経由でC言語のライブラリを扱えるものを利用するのも手です。[様々な言語で正規表現のベンチマークをとったページ](https://benchmarksgame-team.pages.debian.net/benchmarksgame/performance/regexredux.html)を参考にすると、go-pcreを利用した正規表現は113個中21番目に位置しており、それほど悪い成績ではないことが分かります。
(それにしてもRustの成績が優秀なので、このあたりは別記事で深堀りしたい)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/14275/35ec39be-49d8-24f3-69b3-2279eef4bd60.png)
> https://benchmarksgame-team.pages.debian.net/benchmarksgame/performance/regexredux.html


ただし、Goの正規表現は[NFA(Nondeterministic finite automaton)](https://swtch.com/~rsc/regexp/regexp1.html)を利用して作られています。これは、Perl, Ruby, Pythonなどで利用されている再帰的にバックトラッキングしていく方法 `O(2^n)` に比べ、Goで採用されているのは最悪のパターンのときでも比較的速度を担保(`O(n^2)`)できます。
利用する正規表現によっては、Goの方が早くなることもあるので見極めが必要です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/14275/bbf1b453-50bd-60b4-32f8-190ad5dfddef.png)
> https://swtch.com/~rsc/regexp/regexp1.html

# まとめ

Go言語は、C言語のライブラリを利用している正規表現エンジンに比べて低速になりやすいです。
単純なパターンマッチしているかのチェックであれば、標準ライブラリで利用されている方法のように、文字列チェックして処理すると高速になります。

Goの正規表現を責める前に、まずはprofileの分析を行い、本当にパフォーマンスがクリティカルな部分で正規表現が問題になっているのかをチェック → 問題になっていれば、今回確認したような標準ライブラリを参考にして実装してみるとよいと思います。