[インデックス 15309] ファイルの概要
このコミットは、Go言語の標準ライブラリ src/pkg/strings パッケージ内の Count および Index 関数のパフォーマンス改善を目的としています。具体的には、文字列検索アルゴリズムの最適化と、特定のケースにおける処理の効率化が図られています。変更されたファイルは以下の通りです。
src/pkg/strings/strings.go:CountおよびIndex関数の実装が変更されました。src/pkg/strings/strings_test.go: パフォーマンスベンチマークのための新しいテストケースが追加されました。
コミット
commit 937f91e1daadfe55aa57e3482485494a0765c849
Author: Donovan Hide <donovanhide@gmail.com>
Date: Tue Feb 19 10:36:15 2013 -0500
strings: faster Count, Index
Slightly better benchmarks for when string and separator are equivalent and also less branching in inner loops.
benchmark old ns/op new ns/op delta
BenchmarkGenericNoMatch 3430 3442 +0.35%
BenchmarkGenericMatch1 23590 22855 -3.12%
BenchmarkGenericMatch2 108031 105025 -2.78%
BenchmarkSingleMaxSkipping 2969 2704 -8.93%
BenchmarkSingleLongSuffixFail 2826 2572 -8.99%
BenchmarkSingleMatch 205268 197832 -3.62%
BenchmarkByteByteNoMatch 987 921 -6.69%
BenchmarkByteByteMatch 2014 1749 -13.16%
BenchmarkByteStringMatch 3083 3050 -1.07%
BenchmarkHTMLEscapeNew 922 915 -0.76%
BenchmarkHTMLEscapeOld 1654 1570 -5.08%
BenchmarkByteByteReplaces 11897 11556 -2.87%
BenchmarkByteByteMap 4485 4255 -5.13%
BenchmarkIndexRune 174 121 -30.46%
BenchmarkIndexRuneFastPath 41 41 -0.24%
BenchmarkIndex 45 44 -0.22%
BenchmarkMapNoChanges 433 431 -0.46%
BenchmarkIndexHard1 4015336 3316490 -17.40%
BenchmarkIndexHard2 3976254 3395627 -14.60%
BenchmarkIndexHard3 3973158 3378329 -14.97%
BenchmarkCountHard1 4403549 3448512 -21.69%
BenchmarkCountHard2 4387437 3413059 -22.21%
BenchmarkCountHard3 4403891 3382661 -23.19%
BenchmarkIndexTorture 28354 25864 -8.78%
BenchmarkCountTorture 29625 27463 -7.30%
BenchmarkFields 38752040 39169840 +1.08%
BenchmarkFieldsFunc 38797765 38888060 +0.23%
benchmark old MB/s new MB/s speedup
BenchmarkSingleMaxSkipping 3367.07 3697.62 1.10x
BenchmarkSingleLongSuffixFail 354.51 389.47 1.10x
BenchmarkSingleMatch 73.07 75.82 1.04x
BenchmarkFields 27.06 26.77 0.99x
BenchmarkFieldsFunc 27.03 26.96 1.00x
R=dave, fullung, remyoudompheng, rsc
CC=golang-dev
https://golang.org/cl/7350045
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/937f91e1daadfe55aa57e3482485494a0765c849
元コミット内容
このコミットの目的は、Go言語の strings パッケージにおける Count および Index 関数のパフォーマンスを向上させることです。特に、検索対象の文字列と区切り文字が同等である場合のベンチマークを改善し、内部ループでの分岐を減らすことで効率化を図っています。コミットメッセージには、変更前後のベンチマーク結果が詳細に記載されており、多くのシナリオでパフォーマンスが向上していることが示されています。
変更の背景
strings.Count と strings.Index は、Go言語のプログラムで頻繁に使用される基本的な文字列操作関数です。これらの関数のパフォーマンスは、文字列処理を多用するアプリケーション全体の速度に大きな影響を与えます。
コミットメッセージに示されているベンチマーク結果を見ると、特に BenchmarkIndexHard や BenchmarkCountHard といった「ハード」なシナリオ（おそらく、検索対象の文字列が長く、区切り文字が頻繁に出現したり、複雑なパターンを持つ場合）で大幅な改善が見られます。また、BenchmarkIndexRune のような単一ルーン（Unicode文字）の検索でも顕著な改善があります。
この変更の背景には、これらの基本的な文字列操作の効率をさらに高め、Go言語で記述されたアプリケーションの全体的な実行速度を向上させたいという意図があったと考えられます。特に、文字列と区切り文字が同等である場合の処理や、内部ループの分岐を減らすことで、CPUのパイプライン効率を向上させ、より高速な実行を目指したものです。
前提知識の解説
このコミットの変更内容を理解するためには、以下の概念について基本的な知識が必要です。
1. strings.Count 関数
strings.Count(s, sep string) int は、文字列 s 内に sep が重複しない形で何回出現するかを数える関数です。
- 例:
strings.Count("banana", "na")は2を返します。 - 特殊ケース:
sepが空文字列""の場合、sのUnicodeルーン数 + 1 を返します。これは、空文字列が各ルーンの間と文字列の最初と最後に存在すると見なされるためです。sepがsよりも長い場合、0を返します。
2. strings.Index 関数
strings.Index(s, sep string) int は、文字列 s 内で sep が最初に出現するインデックス（0から始まる）を返します。sep が s 内に見つからない場合は -1 を返します。
- 例:
strings.Index("banana", "na")は2を返します。 - 特殊ケース:
sepが空文字列""の場合、0を返します。これは、空文字列が常に文字列の先頭に存在すると見なされるためです。sepがsよりも長い場合、-1を返します。
3. Rabin-Karp アルゴリズム
strings.Count および strings.Index 関数は、内部的にRabin-Karpアルゴリズムに似たハッシュベースの文字列検索アルゴリズムを使用しています。
- 概要: Rabin-Karpアルゴリズムは、パターン（
sep）のハッシュ値と、テキスト（s）の同じ長さの部分文字列のハッシュ値を比較することで、パターンを効率的に検索します。ハッシュ値が一致した場合のみ、実際の文字列比較を行います。これにより、比較回数を大幅に減らすことができます。 - ローリングハッシュ: このアルゴリズムの鍵となるのは「ローリングハッシュ」です。これは、テキストの次の部分文字列のハッシュ値を、前の部分文字列のハッシュ値から効率的に計算する手法です。これにより、各部分文字列のハッシュ値をゼロから計算し直す必要がなく、計算コストを削減できます。
- 衝突: 異なる文字列が同じハッシュ値を持つ「ハッシュ衝突」が発生する可能性があります。Rabin-Karpでは、ハッシュ値が一致した場合にのみ、実際の文字列比較（
s[i-len(sep):i] == sepのような比較）を行うことで、偽陽性（false positive）を排除します。
4. Go言語のベンチマーク
Go言語の testing パッケージは、コードのパフォーマンスを測定するためのベンチマーク機能を提供します。
go test -bench=.: このコマンドを実行すると、ベンチマーク関数（Benchmarkプレフィックスを持つ関数）が実行され、各操作にかかる時間（ns/op）や処理速度（MB/s）などのパフォーマンスメトリクスが出力されます。ns/op(nanoseconds per operation): 1回の操作にかかる平均ナノ秒。値が小さいほど高速です。MB/s(megabytes per second): 1秒あたりに処理できるメガバイト数。値が大きいほど高速です。delta: 変更前後のパフォーマンス変化率。負の値は改善、正の値は悪化を示します。
技術的詳細
このコミットにおける strings.Count および strings.Index 関数の主な技術的改善点は以下の通りです。
1. 特殊ケースの switch 文による効率化
変更前は、sep の長さに基づく特殊ケースの処理が if 文の連鎖で行われていました。変更後は、switch 文を使用することで、これらの特殊ケースの分岐処理がより明確かつ効率的になっています。
len(sep) == 0の場合:Count:utf8.RuneCountInString(s) + 1を返します。これは、空文字列が各ルーンの間と文字列の最初と最後に存在するという定義に基づいています。Index:0を返します。空文字列は常に文字列の先頭に存在すると見なされます。
len(sep) == 1の場合:- 単一バイトの区切り文字（
c := sep[0]）の場合、文字列sを直接ループし、バイト単位で比較することで高速化を図っています。これは、Rabin-Karpのようなハッシュアルゴリズムを使用するよりも、単純なバイト比較の方がオーバーヘッドが少ないためです。
- 単一バイトの区切り文字（
len(sep) == len(s)の場合:Count:sep == sであれば1、そうでなければ0を返します。Index:sep == sであれば0、そうでなければ-1を返します。- このケースは、Rabin-Karpアルゴリズムの初期化やループに入る前に、文字列全体が区切り文字と一致するかどうかを効率的にチェックするために追加されました。
2. Rabin-Karpアルゴリズムの最適化
Rabin-Karpアルゴリズムの内部ループが最適化され、分岐が削減されています。
- 初期マッチの事前チェック:
- 変更前は、Rabin-Karpのハッシュ計算ループに入ってから最初のマッチをチェックしていました。
- 変更後は、ループに入る前に
s[:len(sep)] == sep（Indexの場合はs[:n] == sep）という条件で、文字列の先頭が区切り文字と一致するかどうかを事前にチェックしています。これにより、最初のマッチが文字列の先頭にある場合に、ハッシュ計算のオーバーヘッドなしに即座に結果を返すことができます。
- ループ条件とインクリメントの変更:
- 変更前は
for i := len(sep); ; i++のように無限ループを回し、内部でif i >= len(s) { break }という条件でループを抜けていました。 - 変更後は
for i := len(sep); i < len(s);のようにループ条件を明示し、ループの最後にi++を移動しています。これにより、ループの各イテレーションでi >= len(s)のチェックが不要になり、分岐予測の効率が向上し、CPUのパイプラインストールが減少する可能性があります。
- 変更前は
- ハッシュ計算とマッチチェックの順序:
- 変更前は、ハッシュ値を更新してからマッチチェックを行っていました。
- 変更後は、ループの開始時にハッシュ値を更新し、その後にマッチチェックを行うことで、より自然なフローになっています。特に
Count関数では、lastmatch変数を使って重複しないマッチを正確にカウントするためのロジックが改善されています。
これらの変更は、特に長い文字列や頻繁に検索が行われるシナリオにおいて、関数の実行時間を短縮し、全体的なパフォーマンスを向上させることを目的としています。ベンチマーク結果が示すように、多くのケースで顕著な速度向上が達成されています。
コアとなるコードの変更箇所
src/pkg/strings/strings.go
Count 関数
--- a/src/pkg/strings/strings.go
+++ b/src/pkg/strings/strings.go
@@ -59,21 +59,26 @@ func hashstr(sep string) (uint32, uint32) {
// Count counts the number of non-overlapping instances of sep in s.
func Count(s, sep string) int {
- if sep == "" {
- return utf8.RuneCountInString(s) + 1
- }
- c := sep[0]
n := 0
- if len(sep) == 1 {
+ // special cases
+ switch {
+ case len(sep) == 0:
+ return utf8.RuneCountInString(s) + 1
+ case len(sep) == 1:
// special case worth making fast
+ c := sep[0]
for i := 0; i < len(s); i++ {
if s[i] == c {
n++
}
}
return n
- }
- if len(sep) > len(s) {
+ case len(sep) > len(s):
+ return 0
+ case len(sep) == len(s):
+ if sep == s {
+ return 1
+ }
return 0
}
hashsep, pow := hashstr(sep)
@@ -82,17 +87,19 @@ func Count(s, sep string) int {
h = h*primeRK + uint32(s[i])
}
lastmatch := 0
- for i := len(sep); ; i++ {
- // Invariant: h = hash(s[i-l : i])
+ if h == hashsep && s[:len(sep)] == sep {
+ n++
+ lastmatch = len(sep)
+ }
+ for i := len(sep); i < len(s); {
+ h *= primeRK
+ h += uint32(s[i])
+ h -= pow * uint32(s[i-len(sep)])
+ i++
if h == hashsep && lastmatch <= i-len(sep) && s[i-len(sep):i] == sep {
n++
lastmatch = i
}
- if i >= len(s) {
- break
- }
- h = h*primeRK + uint32(s[i])
- h -= pow * uint32(s[i-len(sep)])
}
return n
}
Index 関数
--- a/src/pkg/strings/strings.go
+++ b/src/pkg/strings/strings.go
@@ -115,11 +122,11 @@ func ContainsRune(s string, r rune) bool {
// Index returns the index of the first instance of sep in s, or -1 if sep is not present in s.
func Index(s, sep string) int {
n := len(sep)
- if n == 0 {
+ switch {
+ case n == 0:
return 0
- }
- c := sep[0]
- if n == 1 {
+ case n == 1:
+ c := sep[0]
// special case worth making fast
for i := 0; i < len(s); i++ {
if s[i] == c {
@@ -127,9 +134,12 @@ func Index(s[i] == c) {
}
}
return -1
- }
- // n > 1
- if n > len(s) {
+ case n == len(s):
+ if sep == s {
+ return 0
+ }
+ return -1
+ case n > len(s):
return -1
}
// Hash sep.
@@ -138,16 +148,17 @@ func Index(s, sep string) int {
for i := 0; i < n; i++ {
h = h*primeRK + uint32(s[i])
}
- for i := n; ; i++ {
- // Invariant: h = hash(s[i-n : i])
+ if h == hashsep && s[:n] == sep {
+ return 0
+ }
+ for i := n; i < len(s); {
+ h *= primeRK
+ h += uint32(s[i])
+ h -= pow * uint32(s[i-n])
+ i++
if h == hashsep && s[i-n:i] == sep {
return i - n
}
- if i >= len(s) {
- break
- }
- h = h*primeRK + uint32(s[i])
- h -= pow * uint32(s[i-n])
}
return -1
}
src/pkg/strings/strings_test.go
BenchmarkCountTortureOverlapping 関数
--- a/src/pkg/strings/strings_test.go
+++ b/src/pkg/strings/strings_test.go
@@ -1052,6 +1052,14 @@ func BenchmarkCountTorture(b *testing.B) {
}
}
+func BenchmarkCountTortureOverlapping(b *testing.B) {
+ A := Repeat("ABC", 1<<20)
+ B := Repeat("ABC", 1<<10)
+ for i := 0; i < b.N; i++ {
+ Count(A, B)
+ }
+}
+
var makeFieldsInput = func() string {
x := make([]byte, 1<<20)
// Input is ~10% space, ~10% 2-byte UTF-8, rest ASCII non-space.
コアとなるコードの解説
Count 関数と Index 関数の共通の変更点
if文からswitch文への変更:- 以前は
if sep == ""やif len(sep) == 1のように複数のif文で特殊ケースを処理していました。 - 新しいコードでは
switch文を使用し、len(sep)の値に基づいて処理を分岐させています。これにより、コードの可読性が向上し、コンパイラがより効率的な分岐コードを生成できる可能性があります。
- 以前は
len(sep) == len(s)の特殊ケース追加:sepの長さがsの長さと等しい場合、Rabin-Karpアルゴリズムの複雑なハッシュ計算を行う前に、単純な文字列比較sep == sで結果を判断できるようになりました。これにより、この特定のケースでのオーバーヘッドが削減されます。
- Rabin-Karpループの最適化:
- 初期マッチの事前チェック: Rabin-Karpのハッシュ計算ループに入る前に、
sの先頭がsepと一致するかどうかをif h == hashsep && s[:len(sep)] == sep(Count) またはif h == hashsep && s[:n] == sep(Index) でチェックするようになりました。これにより、文字列の先頭にマッチがある場合に、不要なループ処理をスキップして即座に結果を返すことができます。 - ループ条件の変更:
for i := len(sep); ; i++のような無限ループと内部のbreak文の組み合わせから、for i := len(sep); i < len(s);のように明確なループ条件を持つ形式に変更されました。これにより、ループの各イテレーションでの条件チェックが効率化され、CPUの分岐予測が改善される可能性があります。 - ハッシュ更新とインクリメントの順序: ハッシュ値の更新 (
h *= primeRK; h += uint32(s[i]); h -= pow * uint32(s[i-len(sep)])) とi++の位置が調整され、より効率的な処理フローになっています。特にCount関数では、lastmatchの更新ロジックが改善され、重複しないカウントがより正確かつ効率的に行われるようになっています。
- 初期マッチの事前チェック: Rabin-Karpのハッシュ計算ループに入る前に、
strings_test.go の変更点
BenchmarkCountTortureOverlappingの追加:- この新しいベンチマークは、非常に長い文字列
Aの中に、それよりも短い、しかし重複するパターンBが多数含まれる場合のCount関数のパフォーマンスを測定するために追加されました。 A := Repeat("ABC", 1<<20)は "ABCABC..." の繰り返しで約1MBの文字列を生成します。B := Repeat("ABC", 1<<10)は "ABCABC..." の繰り返しで約1KBの文字列を生成します。- このようなシナリオは、実際のアプリケーションで発生する可能性があり、Rabin-Karpアルゴリズムの効率性、特にハッシュ衝突の処理や重複するマッチのカウントにおけるパフォーマンスを厳しく評価するのに役立ちます。このベンチマークの追加は、
Count関数の最適化が、より複雑な現実世界のパターンにも対応していることを確認するためと考えられます。
- この新しいベンチマークは、非常に長い文字列
これらの変更は、Go言語の文字列処理の基盤となる関数の堅牢性とパフォーマンスをさらに向上させるための重要なステップです。
関連リンク
- Go CL (Change List): https://golang.org/cl/7350045
参考にした情報源リンク
- Go言語の
stringsパッケージ公式ドキュメント: https://pkg.go.dev/strings - Rabin-Karpアルゴリズムに関する情報 (例: Wikipedia): https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%93%E3%83%B3-%E3%82%AB%E3%83%BC%E3%83%97%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
- Go言語のベンチマークに関する情報 (例: Go公式ブログ): https://go.dev/blog/benchmarking