[インデックス 10650] ファイルの概要

このコミットは、Go言語の標準ライブラリであるregexpパッケージにおいて、正規表現エンジンの入力インターフェースに関するメモリ割り当てを削減し、特に短い入力に対するパフォーマンスを向上させることを目的としています。

コミット

commit 2f2cc24cd8e930b26c220f75b96606abf2bebcbc
Author: Russ Cox <rsc@golang.org>
Date:   Wed Dec 7 15:03:05 2011 -0500

    regexp: avoid allocation of input interface

    Matters most for small inputs, because there is no real work
    to amortize the allocation effort against.

    benchmark                                old ns/op    new ns/op    delta
    BenchmarkLiteral                               613          473  -22.84%
    BenchmarkNotLiteral                           4981         4931   -1.00%
    BenchmarkMatchClass                           7289         7122   -2.29%
    BenchmarkMatchClass_InRange                   6618         6663   +0.68%
    BenchmarkReplaceAll                           7843         7233   -7.78%
    BenchmarkAnchoredLiteralShortNonMatch          329          228  -30.70%
    BenchmarkAnchoredLiteralLongNonMatch           322          228  -29.19%
    BenchmarkAnchoredShortMatch                    838          715  -14.68%
    BenchmarkAnchoredLongMatch                     824          715   -13.23%

    benchmark                                 old MB/s     new MB/s  speedup
    BenchmarkMatchEasy0_32                      119.73       196.61    1.64x
    BenchmarkMatchEasy0_1K                      540.58       538.33    1.00x
    BenchmarkMatchEasy0_32K                     732.57       714.00    0.97x
    BenchmarkMatchEasy0_1M                      726.44       708.36    0.98x
    BenchmarkMatchEasy0_32M                     707.77       691.45    0.98x
    BenchmarkMatchEasy1_32                      102.12       136.11    1.33x
    BenchmarkMatchEasy1_1K                      298.31       307.04    1.03x
    BenchmarkMatchEasy1_32K                     273.56       274.43    1.00x
    BenchmarkMatchEasy1_1M                      268.42       269.23    1.00x
    BenchmarkMatchEasy1_32M                     266.15       267.34    1.00x
    BenchmarkMatchMedium_32                       2.53         3.38    1.34x
    BenchmarkMatchMedium_1K                       9.37         9.57    1.02x
    BenchmarkMatchMedium_32K                      9.29         9.67    1.04x
    BenchmarkMatchMedium_1M                       9.42         9.66    1.03x
    BenchmarkMatchMedium_32M                      9.41         9.62    1.02x
    BenchmarkMatchHard_32                         6.66         6.75    1.01x
    BenchmarkMatchHard_1K                         6.81         6.85    1.01x
    BenchmarkMatchHard_32K                        6.79         6.85    1.01x
    BenchmarkMatchHard_1M                         6.82         6.83    1.00x
    BenchmarkMatchHard_32M                        6.80         6.80    1.00x

    R=golang-dev, r
    CC=golang-dev
    https://golang.org/cl/5453076

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/2f2cc24cd8e930b26c220f75b96606abf2bebcbc

元コミット内容

このコミットは、Go言語のregexpパッケージにおける正規表現マッチング処理のパフォーマンス改善を目的としています。具体的には、正規表現エンジンが入力データを処理する際に発生する「入力インターフェース」のメモリ割り当てを削減することで、特に短い入力に対する処理速度を向上させます。

コミットメッセージには、変更前後のベンチマーク結果が詳細に記載されており、ns/op（1操作あたりのナノ秒）とMB/s（1秒あたりの処理メガバイト数）の両方で改善が見られます。特に、BenchmarkLiteralやBenchmarkAnchoredLiteralShortNonMatchなど、短い入力や単純なパターンに対するベンチマークで顕著なパフォーマンス向上が確認できます。これは、割り当てコストが全体の処理時間に占める割合が大きいため、その削減が大きな効果をもたらすことを示しています。

変更の背景

Go言語の正規表現パッケージは、様々な形式の入力（バイトスライス、文字列、io.RuneReader）を統一的に扱うために、inputというインターフェースとその具体的な実装（inputBytes、inputString、inputReader）を使用しています。従来の設計では、正規表現のマッチング処理が実行されるたびに、これらのinputインターフェースの実装がヒープ上に新たに割り当てられていました。

この「都度割り当て」の方式は、特に正規表現のマッチングが頻繁に、かつ短い入力に対して行われる場合に、パフォーマンス上のボトルネックとなることがありました。ヒープ割り当ては、ガベージコレクションの負荷を増加させ、CPUキャッシュの効率を低下させる可能性があるため、高頻度で実行されるコードパスでは避けるべきとされています。

このコミットの背景には、このようなメモリ割り当てのオーバーヘッドを削減し、regexpパッケージ全体のパフォーマンス、特に小規模な入力に対する応答性を向上させるという明確な目的がありました。ベンチマーク結果が示すように、割り当てコストが処理時間全体に占める割合が大きいシナリオにおいて、この最適化は非常に有効です。

前提知識の解説

このコミットの変更内容を理解するためには、以下のGo言語の概念と正規表現の基本的な動作に関する知識が役立ちます。

1. Go言語のインターフェース: Goのインターフェースは、メソッドのシグネチャの集合を定義する型です。具体的な型がそのインターフェースのすべてのメソッドを実装していれば、その型はインターフェースを満たしていると見なされます。インターフェース型の変数は、そのインターフェースを満たす任意の具体的な型の値を保持できます。この際、具体的な値はヒープに割り当てられ、インターフェース値はデータと型情報へのポインタを保持します。インターフェース値の作成（具体的な型からインターフェース型への変換）は、通常、ヒープ割り当てを伴います。

2. メモリ割り当て（ヒープとスタック）:

   • スタック: 関数呼び出しやローカル変数など、生存期間が短いデータが割り当てられる領域です。割り当てと解放が非常に高速で、コンパイラによって管理されます。
   • ヒープ: プログラムの実行中に動的に割り当てられるメモリ領域です。生存期間が不定のデータ（例: newやmakeで作成されるオブジェクト）が割り当てられます。ヒープ割り当てはスタック割り当てよりもコストが高く、ガベージコレクタによる管理が必要です。ガベージコレクションは、不要になったメモリを解放するプロセスであり、その実行にはCPU時間が必要です。

3. エスケープ解析 (Escape Analysis): Goコンパイラは、変数がヒープに割り当てられるべきか、スタックに割り当てられるべきかを決定するために「エスケープ解析」を行います。変数が関数のスコープ外で参照される可能性がある場合（例: ポインタが返される、グローバル変数に代入されるなど）、その変数はヒープに「エスケープ」されます。そうでない場合は、スタックに割り当てられます。インターフェース値に具体的な値を代入する操作は、多くの場合、その具体的な値がヒープにエスケープされる原因となります。

4. 正規表現エンジンの入力処理: 正規表現エンジンは、マッチングを行うために、入力テキストを文字単位で読み取る必要があります。Goのregexpパッケージでは、この入力処理を抽象化するためにinputインターフェースが定義されており、バイトスライス、文字列、io.RuneReaderといった異なる入力ソースに対応する具体的な実装が存在します。

これらの知識を前提として、このコミットは、正規表現マッチングのたびに発生していたinputインターフェースの実装のヒープ割り当てを、regexp.Regexpオブジェクトに紐づくmachine構造体内で再利用可能な形で保持することで回避し、パフォーマンスを向上させています。

技術的詳細

このコミットの主要な技術的アプローチは、「オブジェクトプーリング」または「オブジェクトの再利用」の概念を、正規表現エンジンの入力処理に適用することです。

Goのregexpパッケージでは、正規表現のマッチングを実行する際に、内部的にmachineという構造体を使用します。このmachineは、正規表現の実行状態を管理し、入力テキストから文字を読み取る役割を担います。

変更前は、Regexp型のdoExecuteメソッドが呼び出されるたびに、入力の種類（[]byte、string、io.RuneReader）に応じて、newInputBytes、newInputString、newInputReaderといったヘルパー関数が呼び出され、それぞれ新しいinputBytes、inputString、inputReader構造体がヒープ上に割り当てられていました。これらのヘルパー関数は、regexp/regexp.goファイル内で定義されており、return &inputBytes{str: str}のように、新しい構造体へのポインタを返していました。

このコミットでは、この割り当てを回避するために、以下の変更が行われました。

1. machine構造体への入力インターフェース実装の埋め込み: src/pkg/regexp/exec.goのmachine構造体に、inputBytes、inputString、inputReaderの各構造体が直接フィールドとして追加されました。

   type machine struct {
       // ... 既存のフィールド ...
       // cached inputs, to avoid allocation
       inputBytes  inputBytes
       inputString inputString
       inputReader inputReader
   }
   

   これにより、machineが初期化される際にこれらの入力構造体も一緒に割り当てられ、以降の正規表現マッチングで再利用可能になります。

2. newInput*ヘルパー関数のmachineメソッドへの変更: regexp/regexp.goにあったグローバルなnewInputBytes、newInputString、newInputReader関数は削除されました。代わりに、exec.goにmachineのメソッドとしてnewInputBytes、newInputString、newInputReaderが追加されました。これらのメソッドは、machine自身のフィールドとして持つinputBytes、inputString、inputReader構造体の内容を更新し、そのポインタをinputインターフェース型として返します。

   func (m *machine) newInputBytes(b []byte) input {
       m.inputBytes.str = b
       return &m.inputBytes
   }
   // 同様に newInputString, newInputReader も変更
   

   これにより、新しいinput構造体をヒープに割り当てる代わりに、既存のmachine内の構造体を再利用できるようになりました。

3. doExecute関数のシグネチャ変更と入力処理の集約: regexp/regexp.goのRegexp.doExecuteメソッドのシグネチャが変更され、以前はinputインターフェースを直接受け取っていたものが、io.RuneReader、[]byte、stringの3つの具体的な型を引数として受け取るようになりました。

   // 変更前: func (re *Regexp) doExecute(i input, pos int, ncap int) []int
   // 変更後: func (re *Regexp) doExecute(r io.RuneReader, b []byte, s string, pos int, ncap int) []int
   

   doExecuteの内部では、これらの具体的な引数の中から実際に使用する入力タイプを判別し、machineの新しいnewInput*メソッド（例: m.newInputReader(r)）を呼び出して、再利用されたinputインターフェースを取得するように変更されました。

4. machine.freeでの入力クリア: machineがプールに戻される際に、キャッシュされた入力フィールドをクリアする処理が追加されました。これにより、以前の入力データへの参照が残り、意図しないメモリリークやデータ混同が発生するのを防ぎます。

   func (m *machine) free(t *thread) {
       m.inputBytes.str = nil
       m.inputString.str = ""
       m.inputReader.r = nil
       m.pool = append(m.pool, t)
   }
   

これらの変更により、正規表現のマッチングが実行されるたびに発生していた小さなオブジェクトのヒープ割り当てが大幅に削減され、ガベージコレクションの負荷が軽減され、特に短い入力に対するパフォーマンスが向上しました。ベンチマーク結果は、この最適化が成功したことを明確に示しています。

コアとなるコードの変更箇所

このコミットにおけるコアとなるコードの変更は、主に以下の3つのファイルに集中しています。

1. src/pkg/regexp/exec.go:

   • machine構造体にinputBytes, inputString, inputReaderフィールドが追加され、入力インターフェースの実装がキャッシュされるようになりました。
   • machine構造体に、これらのキャッシュされた入力構造体を初期化し、inputインターフェースとして返すnewInputBytes, newInputString, newInputReaderメソッドが追加されました。
   • machine.freeメソッドに、キャッシュされた入力フィールドをクリアする処理が追加されました。

2. src/pkg/regexp/regexp.go:

   • Regexp.doExecuteメソッドのシグネチャが変更され、inputインターフェースを直接受け取る代わりに、io.RuneReader, []byte, stringの具体的な型を引数として受け取るようになりました。
   • doExecuteの内部で、machineの新しいnewInput*メソッドを呼び出して、適切なinputインターフェースを取得するように変更されました。
   • newInputBytes, newInputString, newInputReaderというグローバルなヘルパー関数が削除されました。
   • MatchReader, MatchString, Match, ReplaceAllStringFunc, ReplaceAllFunc, allMatches, Find, FindIndex, FindString, FindStringIndex, FindReaderIndex, FindSubmatch, FindSubmatchIndex, FindStringSubmatch, FindStringSubmatchIndex, FindReaderSubmatchIndexなど、doExecuteを呼び出すすべての公開APIの呼び出し箇所が、新しいdoExecuteのシグネチャに合わせて修正されました。

3. src/pkg/regexp/exec_test.go:

   • ベンチマークコードが更新され、古いold/regexpパッケージとの比較ベンチマークが削除されました。
   • 新しいベンチマーク関数が追加され、様々な入力サイズ（32バイト、1KB、32KB、1MB、32MB）に対するパフォーマンスを測定するように調整されました。これにより、特に短い入力に対するパフォーマンス改善が明確に示されるようになりました。

コアとなるコードの解説

src/pkg/regexp/exec.go の変更点

// 変更前
// import "regexp/syntax"

// 変更後
import (
	"io"
	"regexp/syntax"
)

type machine struct {
	// ... 既存のフィールド ...
	// cached inputs, to avoid allocation
	inputBytes  inputBytes
	inputString inputString
	inputReader inputReader
}

func (m *machine) newInputBytes(b []byte) input {
	m.inputBytes.str = b
	return &m.inputBytes
}

func (m *machine) newInputString(s string) input {
	m.inputString.str = s
	return &m.inputString
}

func (m *machine) newInputReader(r io.RuneReader) input {
	m.inputReader.r = r
	m.inputReader.atEOT = false
	m.inputReader.pos = 0
	return &m.inputReader
}

func (m *machine) free(t *thread) {
	m.inputBytes.str = nil
	m.inputString.str = ""
	m.inputReader.r = nil
	m.pool = append(m.pool, t)
}

// doExecute finds the leftmost match in the input and returns
// the position of its subexpressions.
// 変更前: func (re *Regexp) doExecute(i input, pos int, ncap int) []int {
// 変更後:
func (re *Regexp) doExecute(r io.RuneReader, b []byte, s string, pos int, ncap int) []int {
	m := re.get()
	var i input
	if r != nil {
		i = m.newInputReader(r)
	} else if b != nil {
		i = m.newInputBytes(b)
	} else {
		i = m.newInputString(s)
	}
	m.init(ncap)
	if !m.match(i, pos) {
		re.put(m)

• machine構造体へのフィールド追加: inputBytes, inputString, inputReaderがmachine構造体のフィールドとして追加されました。これにより、これらの小さな構造体がmachineオブジェクトの一部としてヒープに割り当てられ、正規表現マッチングのたびに再利用されるようになります。
• newInput*メソッドの導入: machineのメソッドとしてnewInputBytes, newInputString, newInputReaderが定義されました。これらのメソッドは、引数として受け取った実際の入力データ（[]byte, string, io.RuneReader）を、machine自身のフィールドに格納し、そのフィールドへのポインタをinputインターフェース型として返します。これにより、新しいinputインターフェースの実装をヒープに割り当てる必要がなくなります。
• machine.freeでのクリア: machineがプールに戻される際に、キャッシュされた入力フィールド（inputBytes.str, inputString.str, inputReader.r）がnilや空文字列に設定されます。これは、以前の入力データへの参照が残ることを防ぎ、ガベージコレクタが不要なメモリを解放できるようにするためです。
• doExecuteのシグネチャ変更と入力の選択ロジック: doExecute関数は、具体的な入力型（io.RuneReader, []byte, string）を直接引数として受け取るようになりました。関数内部で、どの引数が非nilであるかに基づいて、適切なmachine.newInput*メソッドを呼び出し、再利用されたinputインターフェースを取得します。この変更により、呼び出し側で事前にinputインターフェースを構築する必要がなくなり、インターフェースの割り当てがmachineの内部で効率的に管理されるようになりました。

src/pkg/regexp/regexp.go の変更点

// 変更前:
// func newInputString(str string) *inputString {
// 	return &inputString{str: str}
// }
// ... 同様に newInputBytes, newInputReader も削除 ...

// 変更前:
// func (re *Regexp) MatchReader(r io.RuneReader) bool {
// 	return re.doExecute(newInputReader(r), 0, 0) != nil
// }
// 変更後:
func (re *Regexp) MatchReader(r io.RuneReader) bool {
	return re.doExecute(r, nil, "", 0, 0) != nil
}

// 変更前:
// func (re *Regexp) MatchString(s string) bool {
// 	return re.doExecute(newInputString(s), 0, 0) != nil
// }
// 変更後:
func (re *Regexp) MatchString(s string) bool {
	return re.doExecute(nil, nil, s, 0, 0) != nil
}

// 変更前:
// func (re *Regexp) Match(b []byte) bool {
// 	return re.doExecute(newInputBytes(b), 0, 0) != nil
// }
// 変更後:
func (re *Regexp) Match(b []byte) bool {
	return re.doExecute(nil, b, "", 0, 0) != nil
}

// ... 他の Find*, ReplaceAll* メソッドも同様に doExecute の呼び出しを修正 ...

• グローバルなnewInput*関数の削除: 以前は新しいinputインターフェースの実装をヒープに割り当てていたグローバルなヘルパー関数（newInputString, newInputBytes, newInputReader）が削除されました。これは、machine構造体内で入力がキャッシュされるようになったため、不要になったためです。
• 公開APIのdoExecute呼び出しの修正: Match, MatchString, MatchReaderなどのregexpパッケージの公開APIや、Find*, ReplaceAll*などの内部メソッドは、すべてdoExecuteを呼び出して正規表現マッチングを実行します。このコミットでは、doExecuteのシグネチャ変更に合わせて、これらの呼び出し箇所がすべて修正されました。具体的には、適切な入力引数（r, b, sのいずれか）に値を渡し、残りの引数にはnilや空文字列を渡すように変更されています。これにより、doExecute内部で適切なinputインターフェースが選択され、再利用されるようになります。

これらの変更により、regexpパッケージは、正規表現マッチングのホットパスにおけるメモリ割り当てを最小限に抑え、特に短い入力に対するパフォーマンスを大幅に向上させることができました。

関連リンク

• Go言語の正規表現パッケージのドキュメント: https://pkg.go.dev/regexp
• Go言語のインターフェースに関する公式ブログ記事 (英語): https://go.dev/blog/laws-of-reflection
• Go言語のエスケープ解析に関する解説 (英語): https://go.dev/doc/effective_go#allocation_efficiency

参考にした情報源リンク

• Go言語の公式ドキュメント
• Go言語のソースコード
• Go言語のベンチマークに関する一般的な知識
• Go言語のメモリ管理（ヒープとスタック、ガベージコレクション）に関する一般的な知識