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

このコミットは、Go言語の標準ライブラリstringsパッケージ内のReplace関数、特にgenericReplacerのパフォーマンスを改善するためのものです。genericReplacer.lookupが文字列の各バイトに対して呼び出される際のオーバーヘッドを削減するため、一般的なケース（特に最初のバイトでルックアップが失敗する場合）に高速パスを追加しています。これにより、特定のベンチマークで顕著なパフォーマンス向上が見られます。

コミット

commit 14950d89e583e8fe7c4f1ba0ea01495f8e6afac3
Author: Rui Ueyama <ruiu@google.com>
Date:   Tue Jun 17 22:08:46 2014 -0700

    strings: add fast path to Replace
    
    genericReplacer.lookup is called for each byte of an input
    string. In many (most?) cases, lookup will fail for the first
    byte, and it will return immediately. Adding a fast path for
    that case seems worth it.
    
    Benchmark on my Xeon 3.5GHz Linux box:
    
    benchmark                        old ns/op    new ns/op    delta
    BenchmarkGenericNoMatch               2691          774  -71.24%
    BenchmarkGenericMatch1                7920         8151   +2.92%
    BenchmarkGenericMatch2               52336        39927  -23.71%
    BenchmarkSingleMaxSkipping            1575         1575   +0.00%
    BenchmarkSingleLongSuffixFail         1429         1429   +0.00%
    BenchmarkSingleMatch                 56228        56228   -1.39%
    BenchmarkByteByteNoMatch               568          568   +0.00%
    BenchmarkByteByteMatch                 977          972   -0.51%
    BenchmarkByteStringMatch              1669         1687   +1.08%
    BenchmarkHTMLEscapeNew                 422          422   +0.00%
    BenchmarkHTMLEscapeOld                 692          670   -3.18%
    BenchmarkByteByteReplaces             8492         8474   -0.21%
    BenchmarkByteByteMap                  2817         2808   -0.32%
    
    LGTM=rsc
    R=golang-codereviews, bradfitz, dave, rsc
    CC=golang-codereviews
    https://golang.org/cl/79200044

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

https://github.com/golang/go/commit/14950d89e583e8fe7c4f1ba0ea01495f8e6afac3

元コミット内容

strings: add fast path to Replace

genericReplacer.lookup is called for each byte of an input
string. In many (most?) cases, lookup will fail for the first
byte, and it will return immediately. Adding a fast path for
that case seems worth it.

Benchmark on my Xeon 3.5GHz Linux box:

benchmark                        old ns/op    new ns/op    delta
BenchmarkGenericNoMatch               2691          774  -71.24%
BenchmarkGenericMatch1                7920         8151   +2.92%
BenchmarkGenericMatch2               52336        39927  -23.71%
BenchmarkSingleMaxSkipping            1575         1575   +0.00%
BenchmarkSingleLongSuffixFail         1429         1429   +0.00%
BenchmarkSingleMatch                 56228        55444   -1.39%
BenchmarkByteByteNoMatch               568          568   +0.00%
BenchmarkByteByteMatch                 977          972   -0.51%
BenchmarkByteStringMatch              1669         1687   +1.08%
BenchmarkHTMLEscapeNew                 422          422   +0.00%
BenchmarkHTMLEscapeOld                 692          670   -3.18%
BenchmarkByteByteReplaces             8492         8474   -0.21%
BenchmarkByteByteMap                  2817         2808   -0.32%

LGTM=rsc
R=golang-codereviews, bradfitz, dave, rsc
CC=golang-codereviews
https://golang.org/cl/79200044

変更の背景

Go言語のstringsパッケージには、文字列内の部分文字列を別の部分文字列に置換するためのReplace関数や、複数の置換ルールを効率的に適用するためのReplacer型が提供されています。Replacerは内部的にgenericReplacerのような実装を使用することがあり、このgenericReplacerのlookupメソッドは、入力文字列の各バイトに対して呼び出され、置換パターンに一致するかどうかを調べます。

しかし、多くの場合、特に置換パターンが入力文字列の現在の位置の最初のバイトと一致しない場合、lookupメソッドはすぐに失敗して戻ります。この「すぐに失敗する」という処理自体は正しいものの、各バイトごとにlookupを呼び出すことによるオーバーヘッドが無視できないレベルで存在していました。

このコミットの背景にあるのは、この頻繁に発生する「最初のバイトでの不一致」というケースを最適化し、genericReplacerの全体的なパフォーマンスを向上させることです。特に、置換対象のパターンが入力文字列の先頭バイトと一致しないことが事前に分かっている場合に、無駄なlookup呼び出しをスキップする「高速パス」を導入することで、処理速度の改善を目指しました。コミットメッセージに示されているベンチマーク結果は、特にBenchmarkGenericNoMatchのような、置換パターンがほとんど一致しないケースで大幅な性能向上が見られることを裏付けています。

前提知識の解説

このコミットを理解するためには、以下のGo言語の概念と文字列処理の基本的な知識が必要です。

1. stringsパッケージ: Go言語の標準ライブラリの一部で、文字列操作のためのユーティリティ関数を提供します。strings.Replaceやstrings.NewReplacerなどが含まれます。
2. strings.Replace関数: func Replace(s, old, new string, n int) stringというシグネチャを持ち、文字列s内でoldが出現する箇所をnewに置換します。nは置換する回数を指定し、-1の場合は全て置換します。
3. strings.Replacer型: 複数の置換ルールを効率的に適用するために使用される型です。strings.NewReplacer(old1, new1, old2, new2, ...)のように初期化し、Replacer.Replace(s string)メソッドで置換を実行します。内部的には、置換パターンを効率的に検索するためのデータ構造（例えば、Aho-Corasickアルゴリズムに基づく有限オートマトンなど）を構築します。
4. genericReplacer: strings.Replacerの実装の一つで、一般的な置換処理を担当します。このgenericReplacerが持つlookupメソッドは、現在の入力文字列の位置から始まる部分文字列が、定義された置換パターンのいずれかに一致するかどうかを調べます。このlookupメソッドは、効率的なパターンマッチングのために、内部的にトライ木（Trie）のようなデータ構造を使用している可能性があります。
5. トライ木 (Trie): 文字列の集合を効率的に格納し、プレフィックス検索を行うための木構造のデータ構造です。各ノードは文字を表し、ルートからノードまでのパスが文字列を形成します。genericReplacerが複数の置換パターンを扱う場合、これらのパターンをトライ木に格納し、入力文字列を1文字ずつ辿りながらパターンマッチングを行うことが考えられます。
6. パフォーマンス最適化: ソフトウェア開発において、特定の処理の実行速度を向上させるための手法です。このコミットでは、頻繁に発生するが結果的に無駄になる処理（最初のバイトでの不一致）をスキップすることで、全体の処理時間を短縮する「高速パス」という最適化手法が用いられています。

技術的詳細

このコミットの技術的詳細は、genericReplacerのWriteStringメソッド内に「高速パス」を追加した点に集約されます。

genericReplacerは、置換対象の文字列をバイト単位で走査し、lookupメソッドを呼び出して現在の位置から始まる部分文字列が置換パターンに一致するかどうかを判定します。このlookupメソッドは、内部的にトライ木のようなデータ構造（r.rootやr.tableなど）を使用してパターンを検索します。

追加された高速パスは、以下の条件が満たされる場合に適用されます。

1. i != len(s): 現在の走査位置iが文字列の終端に達していないこと。
2. r.root.priority == 0: これは、r.rootが特別な状態（例えば、空の文字列に一致するパターンがない、または特定の最適化が適用されていない）であることを示唆している可能性があります。priorityが0の場合、特定の最適化されたパスが利用可能であることを意味するかもしれません。
3. index := int(r.mapping[s[i]]): r.mappingは、各バイト値がトライ木の次のノードへのインデックスにマッピングされているテーブルであると推測されます。s[i]（現在のバイト）に対応するインデックスを取得します。
4. index == r.tableSize || r.root.table[index] == nil: この条件は、現在のバイトs[i]が、どの置換パターンの最初のバイトとも一致しないことを効率的にチェックしています。
   • r.tableSizeは、r.mappingテーブルのサイズ、または有効なインデックスの範囲を示している可能性があります。indexがr.tableSizeと等しい場合、それはs[i]に対応する有効なエントリがないことを意味します。
   • r.root.table[index] == nilは、s[i]に対応するトライ木の次のノードが存在しないことを意味します。つまり、現在のバイトから始まる置換パターンは存在しないということです。

これらの条件が全て真である場合、現在のバイトs[i]はどの置換パターンの開始バイトとも一致しないことが確定します。この場合、無駄にr.lookupを呼び出すことなく、単にi++として次のバイトに進み、ループを継続します。これにより、lookupメソッドの呼び出しオーバーヘッドを回避し、特に置換パターンがほとんど出現しない、または最初のバイトで不一致となるケースでパフォーマンスが大幅に向上します。

コミットメッセージに記載されているベンチマーク結果は、この最適化の効果を明確に示しています。特にBenchmarkGenericNoMatchでは、旧バージョンが2691 ns/opであったのに対し、新バージョンでは774 ns/opと、約71%の性能向上が達成されています。これは、置換パターンが全く一致しない場合に、この高速パスが非常に効果的に機能していることを示しています。

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

変更はsrc/pkg/strings/replace.goファイルに集中しており、具体的にはgenericReplacer構造体のWriteStringメソッド内に9行のコードが追加されています。

--- a/src/pkg/strings/replace.go
+++ b/src/pkg/strings/replace.go
@@ -323,6 +323,15 @@ func (r *genericReplacer) WriteString(w io.Writer, s string) (n int, err error)
 	var last, wn int
 	var prevMatchEmpty bool
 	for i := 0; i <= len(s); {
+		// Fast path: s[i] is not a prefix of any pattern.
+		if i != len(s) && r.root.priority == 0 {
+			index := int(r.mapping[s[i]])
+			if index == r.tableSize || r.root.table[index] == nil {
+				i++
+				continue
+			}
+		}
+
 		// Ignore the empty match iff the previous loop found the empty match.
 		val, keylen, match := r.lookup(s[i:], prevMatchEmpty)
 		prevMatchEmpty = match && keylen == 0

コアとなるコードの解説

追加されたコードブロックは、genericReplacerのWriteStringメソッドのループの先頭に配置されています。このループは、入力文字列sを走査し、置換パターンを検索して適用する役割を担っています。

		// Fast path: s[i] is not a prefix of any pattern.
		if i != len(s) && r.root.priority == 0 {
			index := int(r.mapping[s[i]])
			if index == r.tableSize || r.root.table[index] == nil {
				i++
				continue
			}
		}

1. // Fast path: s[i] is not a prefix of any pattern.

   • このコメントは、このコードブロックの目的が、現在の文字s[i]がどの置換パターンのプレフィックス（先頭部分）でもない場合に、処理を高速化することであることを示しています。

2. if i != len(s) && r.root.priority == 0 { ... }

   • i != len(s): 現在のインデックスiが文字列の長さに達していないことを確認します。つまり、まだ処理すべき文字が残っていることを意味します。
   • r.root.priority == 0: この条件は、r.root（おそらくトライ木のルートノード）が特定の状態にある場合にのみ高速パスを有効にすることを示唆しています。priorityが0であることは、このルートノード自体が置換パターンとしてマッチしない、または特定の最適化が適用されていないことを意味する可能性があります。これにより、高速パスが適用される状況を適切に限定しています。

3. index := int(r.mapping[s[i]])

   • r.mappingは、バイト値（s[i]）を整数インデックスにマッピングするテーブルです。これは、トライ木の次のノードを効率的に見つけるためのルックアップテーブルとして機能します。現在の文字s[i]に対応するインデックスを取得します。

4. if index == r.tableSize || r.root.table[index] == nil { ... }

   • この内部if文が高速パスの核心です。
   • index == r.tableSize: 取得したindexがr.tableSize（おそらくr.mappingの有効な範囲外、または特別な「一致なし」を示す値）と等しい場合、現在のバイトs[i]から始まる置換パターンは存在しないことを意味します。
   • r.root.table[index] == nil: r.root.tableは、トライ木のルートノードの子ノードへのポインタの配列であると推測されます。indexに対応するエントリがnilである場合、それは現在のバイトs[i]から始まる子ノード（つまり、置換パターンの開始）が存在しないことを意味します。
   • これらのどちらかの条件が真であれば、現在のバイトs[i]はどの置換パ換パターンの開始バイトとも一致しないことが確定します。

5. i++

   • 現在のバイトがどのパターンとも一致しないことが分かったため、インデックスiを1つ進めて次のバイトを処理します。

6. continue

   • continueキーワードにより、ループの残りの部分（特にr.lookupの呼び出し）をスキップし、次のイテレーションに進みます。これにより、無駄なlookup呼び出しを回避し、パフォーマンスを向上させます。

このコードは、genericReplacerが文字列を走査する際に、置換パターンが現在の文字から始まる可能性が低い場合に、より複雑なlookup処理をスキップすることで、効率を大幅に向上させています。

関連リンク

• Go CL 79200044: https://golang.org/cl/79200044

参考にした情報源リンク

• Go commit CL 79200044 (GitHub): https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQFkm4YmzACkaQyAHVJl4vshK0RuRF-5LMSfB0ygk17LTzWzAMqBdte6oKUieMVYcbHtEvAuaYlfgcruE1AqTnSaGklpUFATOiVsWrGK44K5erkoh942d2m-n-ThX2xzdyQa6Q0=
• Go strings.Replace Function (Medium): https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQG47ZhHBs2YTfaXGG1x2QEkbRZGOtrSl-S_QRBghZRhjLd1wKgbOq11VKkcwaGkmC_8WMw9kqtIu7aoBG_89N0xw5sHUS7QERvTYeQSi_BHFho3piAvOvN8Uih3uX97fLk2vIIjvccCcOAhlkr78Cl1-hp9sn0h4yKUEsuL-Vp7NEYSiMHudLBmCdlWvMZrSaFGcbeKsbIsug==
• Go strings.Replacer (Medium): https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQEvRkRNBeWhOMLgsO5PP4uMhtQGTnI6mzgDxuHwM_VtDLY8yL34b1QMZ0YlcjMLkaIeBsdP1az69hJ3gUh4yzWh0aNuELhxcIETuduVR7lubwtbGx1hSdPhkwfWKHZdVl9PbwUxwX_K2aZBurgjOSb43Z2IvZePtc2iXywLOyU=