[インデックス 18835] ファイルの概要
このコミットは、Go言語のテストスイートの一部である test/run.go ファイルにおけるパフォーマンス改善を目的としています。具体的には、errorcheck テストの実行速度を向上させるための変更が含まれています。
コミット
commit d5887c5aaca74080c4b167e11559305c7154901c
Author: Russ Cox <rsc@golang.org>
Date: Tue Mar 11 23:58:24 2014 -0400
test/run: make errorcheck tests faster
Some of the errorcheck tests have many many identical regexps.
Use a map to avoid storing the compiled form many many times
in memory. Change the filterRe to a simple string to avoid
the expense of those regexps as well.
Cuts the time for run.go on index2.go by almost 50x.
Noticed during debugging of issue 7344.
LGTM=bradfitz
R=bradfitz, josharian
CC=golang-codereviews
https://golang.org/cl/74380043
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/d5887c5aaca74080c4b167e11559305c7154901c
元コミット内容
test/run: make errorcheck tests faster
Some of the errorcheck tests have many many identical regexps.
Use a map to avoid storing the compiled form many many times
in memory. Change the filterRe to a simple string to avoid
the expense of those regexps as well.
Cuts the time for run.go on index2.go by almost 50x.
Noticed during debugging of issue 7344.
変更の背景
Go言語のコンパイラやツールチェインのテストには、特定のコードが期待通りのエラーを生成するかどうかを検証する errorcheck テストが存在します。これらのテストは、ソースコード内の特定の行にコメント形式で期待されるエラーメッセージの正規表現を記述し、コンパイラ出力と照合することで機能します。
このコミットが行われた当時、errorcheck テストの実行においてパフォーマンス上の問題が顕在化していました。特に、多くのテストケースで同一の正規表現が繰り返し使用されている場合、その都度正規表現をコンパイルし、メモリに保持することがオーバーヘッドとなっていました。また、エラーメッセージのフィルタリングに使用される正規表現 (filterRe) も、その複雑さゆえに処理コストが高かったと考えられます。
コミットメッセージにある「Cuts the time for run.go on index2.go by almost 50x.」という記述は、この最適化が非常に大きな効果をもたらしたことを示しています。index2.go は、おそらく多数のエラーチェックを含む大規模なテストファイルであり、このファイルでの実行時間が劇的に改善されたことから、正規表現のコンパイルとマッチングがボトルネックとなっていたことが裏付けられます。
「Noticed during debugging of issue 7344.」という記述がありますが、現在のGoプロジェクトのIssueトラッカーでIssue 7344を検索すると、HTTP/2の脆弱性に関する情報が表示されます。これは、コミット当時のIssue番号と現在のIssue番号の体系が異なるか、あるいは単にコミット作者がデバッグ中に偶然このパフォーマンス問題に気づいたという文脈で言及されている可能性があります。このコミット自体は、直接的にセキュリティ脆弱性とは関係なく、テストインフラのパフォーマンス改善に焦点を当てています。
前提知識の解説
Go言語の正規表現 (regexpパッケージ)
Go言語には、正規表現を扱うための標準ライブラリ regexp パッケージが提供されています。このパッケージは、Perl互換の正規表現構文をサポートしており、文字列のマッチング、検索、置換などの機能を提供します。
regexp.Compile 関数は、与えられた正規表現文字列をコンパイルし、*regexp.Regexp 型のオブジェクトを返します。このコンパイル処理は、正規表現のパターンを内部的な有限オートマトンなどの形式に変換するもので、比較的コストの高い操作です。一度コンパイルされた *regexp.Regexp オブジェクトは、複数の文字列に対して効率的にマッチングを行うことができます。
しかし、同じ正規表現パターンを何度も regexp.Compile でコンパイルすると、その都度コンパイルコストが発生し、メモリも余分に消費されます。特に、ループ内で同じ正規表現を繰り返しコンパイルするようなコードは、パフォーマンス上の問題を引き起こす可能性があります。
errorcheck テストの仕組み
Go言語のテストスイートには、コンパイラが特定のコードに対して期待されるエラーを正しく報告するかどうかを検証する errorcheck テストがあります。これらのテストは、Goのソースファイル内に特別なコメントを記述することで定義されます。
例えば、以下のようなGoコードがあるとします。
package main
func main() {
var x int
x = "hello" // ERROR "cannot use \"hello\" (type string) as type int in assignment"
}
このコードでは、x = "hello" の行の末尾に // ERROR "..." というコメントがあります。これは、この行でコンパイラが cannot use "hello" (type string) as type int in assignment というエラーメッセージを報告することを期待していることを示します。
test/run.go は、このようなテストファイルを読み込み、コンパイラを実行し、その出力されたエラーメッセージと、ソースファイルに記述された期待されるエラーメッセージの正規表現を照合します。この照合処理において、正規表現のコンパイルとマッチングが頻繁に行われるため、パフォーマンスが問題となっていました。
メモ化 (Memoization)
メモ化とは、関数の計算結果をキャッシュしておき、同じ入力が与えられた場合にはキャッシュされた結果を返すことで、計算を省略しパフォーマンスを向上させる最適化手法です。正規表現のコンパイルのように、同じ入力（正規表現文字列）に対して常に同じ出力（コンパイル済み正規表現オブジェクト）を返すようなコストの高い操作には、メモ化が非常に有効です。
このコミットでは、map を使用してコンパイル済みの正規表現をキャッシュすることで、メモ化を実現しています。
技術的詳細
このコミットは、test/run.go ファイル内の errorCheck および wantedErrors 関数を中心に変更を加えています。主な変更点は以下の2つです。
-
正規表現のコンパイル結果のキャッシュ (
wantedErrors関数内):wantedErrors関数は、テストファイル内の// ERROR "..."コメントから期待されるエラーの正規表現を抽出します。- 変更前は、抽出された正規表現ごとに
regexp.Compileを呼び出していましたが、変更後はcache := make(map[string]*regexp.Regexp)というマップを導入し、コンパイル済みの正規表現をキャッシュするようになりました。 - これにより、同じ正規表現が複数回出現する場合でも、一度だけコンパイルすればよく、その後のコンパイルコストを削減できます。
-
filterReからprefixへの変更とmatchPrefix関数の導入 (errorCheckおよびpartitionStrings関数内):wantedError構造体には、エラーメッセージをフィルタリングするためのfilterRe *regexp.Regexpフィールドがありました。これは、エラーメッセージが特定のファイル名と行番号で始まることを確認するための正規表現でした。- この
filterReは、errorCheck関数内でpartitionStrings関数に渡され、エラーメッセージのフィルタリングに使用されていました。 - 変更後は、
filterReフィールドがprefix stringに変更され、正規表現ではなく単純な文字列プレフィックスを保持するようになりました。 partitionStrings関数は、正規表現のマッチングの代わりに、新しく導入されたmatchPrefix関数を使用するようになりました。matchPrefix関数は、与えられた文字列が特定のプレフィックス（例:ファイル名:行番号）で始まるかどうかを、正規表現を使わずに文字列操作（strings.Index,strings.LastIndex,strings.HasPrefixのような操作）で効率的にチェックします。これにより、フィルタリング処理における正規表現のオーバーヘッドが完全に排除されました。
これらの変更により、特に多数の同一正規表現や単純なプレフィックスマッチングが必要なテストケースにおいて、errorcheck テストの実行速度が大幅に向上しました。
コアとなるコードの変更箇所
--- a/test/run.go
+++ b/test/run.go
@@ -760,7 +760,7 @@ func (t *test) errorCheck(outStr string, fullshort ...string) (err error) {
for _, we := range want {
var errmsgs []string
- errmsgs, out = partitionStrings(we.filterRe, out)
+ errmsgs, out = partitionStrings(we.prefix, out)
if len(errmsgs) == 0 {
errs = append(errs, fmt.Errorf("%s:%d: missing error %q", we.file, we.lineNum, we.reStr))
continue
@@ -802,9 +802,29 @@ func (t *test) errorCheck(outStr string, fullshort ...string) (err error) {
}
-func partitionStrings(rx *regexp.Regexp, strs []string) (matched, unmatched []string) {
+// matchPrefix reports whether s is of the form ^(.*/)?prefix(:|[),\
+// That is, it needs the file name prefix followed by a : or a [,\
+// and possibly preceded by a directory name.
+func matchPrefix(s, prefix string) bool {
+ i := strings.Index(s, ":")
+ if i < 0 {
+ return false
+ }
+ j := strings.LastIndex(s[:i], "/")
+ s = s[j+1:]
+ if len(s) <= len(prefix) || s[:len(prefix)] != prefix {
+ return false
+ }
+ switch s[len(prefix)] {
+ case '[', ':':
+ return true
+ }
+ return false
+}
+
+func partitionStrings(prefix string, strs []string) (matched, unmatched []string) {
for _, s := range strs {
- if rx.MatchString(s) {
+ if matchPrefix(s, prefix) {
matched = append(matched, s)
} else {
unmatched = append(unmatched, s)
@@ -818,7 +838,7 @@ type wantedError struct {
re *regexp.Regexp
lineNum int
file string
- filterRe *regexp.Regexp // /^file:linenum\\b/m
+ prefix string
}
var (
@@ -828,6 +848,8 @@ var (\
)
func (t *test) wantedErrors(file, short string) (errs []wantedError) {
+ cache := make(map[string]*regexp.Regexp)
+
src, _ := ioutil.ReadFile(file)
for i, line := range strings.Split(string(src), "\n") {
lineNum := i + 1
@@ -856,15 +878,20 @@ func (t *test) wantedErrors(file, short string) (errs []wantedError) {
}
return fmt.Sprintf("%s:%d", short, n)
})
- re, err := regexp.Compile(rx)
- if err != nil {
- log.Fatalf("%s:%d: invalid regexp in ERROR line: %v", t.goFileName(), lineNum, err)
+ re := cache[rx]
+ if re == nil {
+ var err error
+ re, err = regexp.Compile(rx)
+ if err != nil {
+ log.Fatalf("%s:%d: invalid regexp in ERROR line: %v", t.goFileName(), lineNum, err)
+ }
+ cache[rx] = re
}
- filterPattern := fmt.Sprintf(`^(\w+/)?%s:%d[:[]`, regexp.QuoteMeta(short), lineNum)
+ prefix := fmt.Sprintf("%s:%d", short, lineNum)
errs = append(errs, wantedError{
reStr: rx,
re: re,
- filterRe: regexp.MustCompile(filterPattern),
+ prefix: prefix,
lineNum: lineNum,
file: short,
})
コアとなるコードの解説
wantedError 構造体の変更
-
変更前:
type wantedError struct { re *regexp.Regexp lineNum int file string filterRe *regexp.Regexp // /^file:linenum\b/m }filterReフィールドは、エラーメッセージのフィルタリングに使用される正規表現を保持していました。 -
変更後:
type wantedError struct { re *regexp.Regexp lineNum int file string prefix string }filterReがprefix stringに変更されました。これにより、正規表現オブジェクトを保持する必要がなくなり、単純な文字列比較でフィルタリングが可能になります。
wantedErrors 関数の変更
この関数は、テストファイルから期待されるエラー情報を抽出する役割を担っています。
-
正規表現キャッシュの導入:
func (t *test) wantedErrors(file, short string) (errs []wantedError) { + cache := make(map[string]*regexp.Regexp) // ... // 変更前: re, err := regexp.Compile(rx) // 変更後: + re := cache[rx] + if re == nil { + var err error + re, err = regexp.Compile(rx) + if err != nil { + log.Fatalf("%s:%d: invalid regexp in ERROR line: %v", t.goFileName(), lineNum, err) + } + cache[rx] = re + } // ... }cacheというmap[string]*regexp.Regexpが導入され、正規表現文字列 (rx) をキーとして、コンパイル済みの*regexp.Regexpオブジェクトを値として保存します。regexp.Compileを呼び出す前にキャッシュをチェックし、既にコンパイル済みであればそれを使用します。これにより、同じ正規表現の重複コンパイルが回避されます。 -
filterPatternからprefixへの変更:// 変更前: filterPattern := fmt.Sprintf(`^(\w+/)?%s:%d[:[]`, regexp.QuoteMeta(short), lineNum) // 変更後: + prefix := fmt.Sprintf("%s:%d", short, lineNum) // ... // 変更前: filterRe: regexp.MustCompile(filterPattern), // 変更後: + prefix: prefix,wantedError構造体のfilterReフィールドに設定されていた正規表現パターンが、単純な文字列prefixに置き換えられました。このprefixは、ファイル名:行番号の形式で、エラーメッセージの先頭部分を効率的にチェックするために使用されます。
partitionStrings 関数の変更
この関数は、エラーメッセージのリストを、期待されるエラーにマッチするものとしないものに分割する役割を担っています。
-
引数の変更:
// 変更前: func partitionStrings(rx *regexp.Regexp, strs []string) (matched, unmatched []string) { // 変更後: +func partitionStrings(prefix string, strs []string) (matched, unmatched []string) {第一引数が
*regexp.Regexpからstring(prefix) に変更されました。 -
matchPrefix関数の利用:// 変更前: if rx.MatchString(s) { // 変更後: + if matchPrefix(s, prefix) {正規表現のマッチング (
rx.MatchString) の代わりに、新しく導入されたmatchPrefix関数が使用されるようになりました。
matchPrefix 関数の導入
+func matchPrefix(s, prefix string) bool {
+ i := strings.Index(s, ":")
+ if i < 0 {
+ return false
+ }
+ j := strings.LastIndex(s[:i], "/")
+ s = s[j+1:]
+ if len(s) <= len(prefix) || s[:len(prefix)] != prefix {
+ return false
+ }
+ switch s[len(prefix)] {
+ case '[', ':':
+ return true
+ }
+ return false
+}
この新しい関数は、エラーメッセージ文字列 s が、指定された prefix（例: ファイル名:行番号）で始まるかどうかを効率的にチェックします。正規表現を使用せず、strings.Index や strings.LastIndex、文字列スライス、および switch ステートメントといった基本的な文字列操作のみで実装されています。これにより、正規表現エンジンを起動するオーバーヘッドが完全に排除され、パフォーマンスが向上します。具体的には、エラーメッセージが ファイル名:行番号: または ファイル名:行番号[ の形式で始まることを確認します。
errorCheck 関数の変更
partitionStringsへの引数変更:// 変更前: errmsgs, out = partitionStrings(we.filterRe, out) // 変更後: + errmsgs, out = partitionStrings(we.prefix, out)wantedError構造体のfilterReフィールドがprefixに変更されたことに伴い、partitionStrings関数に渡す引数もwe.filterReからwe.prefixに変更されました。
これらの変更により、errorcheck テストにおける正規表現のコンパイルとマッチングのオーバーヘッドが大幅に削減され、テスト実行時間が劇的に短縮されました。
関連リンク
- Go言語の
regexpパッケージ: https://pkg.go.dev/regexp - Go言語の
stringsパッケージ: https://pkg.go.dev/strings - Go言語のテストに関するドキュメント (一般的な情報): https://go.dev/doc/code#Testing
参考にした情報源リンク
- Go言語の公式ドキュメント
- Go言語のソースコード (特に
test/run.goの変更履歴) - 正規表現のパフォーマンスに関する一般的な知識
- メモ化の概念