Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Go言語の標準ライブラリ strings パッケージにおける Split(s, "") 関数のメモリ割り当てを削減し、パフォーマンスを向上させることを目的としています。具体的には、文字列を個々のUTF-8文字に分割する際の explode 関数において、不要な文字列の再生成を避けることで、ベンチマークで約69%の性能改善を達成しています。

コミット

Author: Ewan Chou coocood@gmail.com Date: Wed Mar 6 15:21:19 2013 -0500

Commit Message: strings: remove allocations in Split(s, "")

BenchmarkSplit1 77984460 24131380 -69.06%

R=golang-dev, rsc, minux.ma, dave, extemporalgenome CC=golang-dev https://golang.org/cl/7458043

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

https://github.com/golang/go/commit/4f43201e51f36e7db909ff3c3a86104dada5161b

元コミット内容

commit 4f43201e51f36e7db909ff3c3a86104dada5161b
Author: Ewan Chou <coocood@gmail.com>
Date:   Wed Mar 6 15:21:19 2013 -0500

    strings: remove allocations in Split(s, "")
    
    BenchmarkSplit1     77984460     24131380  -69.06%
    
    R=golang-dev, rsc, minux.ma, dave, extemporalgenome
    CC=golang-dev
    https://golang.org/cl/7458043
---
 src/pkg/strings/strings.go      |  6 +++++-\n src/pkg/strings/strings_test.go | 18 ++++++++++++++++++\n 2 files changed, 23 insertions(+), 1 deletion(-)\n\ndiff --git a/src/pkg/strings/strings.go b/src/pkg/strings/strings.go\nindex ccf415e694..263fa02bab 100644\n--- a/src/pkg/strings/strings.go\n+++ b/src/pkg/strings/strings.go\n@@ -26,7 +26,11 @@ func explode(s string, n int) []string {\n \ti, cur := 0, 0\n \tfor ; i+1 < n; i++ {\n \t\tch, size = utf8.DecodeRuneInString(s[cur:])\n-\t\ta[i] = string(ch)\n+\t\tif ch == utf8.RuneError {\n+\t\t\ta[i] = string(utf8.RuneError)\n+\t\t} else {\n+\t\t\ta[i] = s[cur : cur+size]\n+\t\t}\n \t\tcur += size\n \t}\n \t// add the rest, if there is any\ndiff --git a/src/pkg/strings/strings_test.go b/src/pkg/strings/strings_test.go\nindex 09de49e5fb..68b658ca46 100644\n--- a/src/pkg/strings/strings_test.go\n+++ b/src/pkg/strings/strings_test.go\n@@ -1095,3 +1095,21 @@ func BenchmarkFieldsFunc(b *testing.B) {\n \t\tFieldsFunc(fieldsInput, unicode.IsSpace)\n \t}\n }\n+\n+func BenchmarkSplit1(b *testing.B) {\n+\tfor i := 0; i < b.N; i++ {\n+\t\tSplit(benchInputHard, \"\")\n+\t}\n+}\n+\n+func BenchmarkSplit2(b *testing.B) {\n+\tfor i := 0; i < b.N; i++ {\n+\t\tSplit(benchInputHard, \"/\")\n+\t}\n+}\n+\n+func BenchmarkSplit3(b *testing.B) {\n+\tfor i := 0; i < b.N; i++ {\n+\t\tSplit(benchInputHard, \"hello\")\n+\t}\n+}\n```

## 変更の背景

この変更の主な背景は、`strings.Split` 関数が区切り文字として空文字列 `""` を受け取った際の非効率なメモリ割り当てを解消し、パフォーマンスを大幅に向上させることです。

`strings.Split(s, "")` は、文字列 `s` を個々のUTF-8文字に分割する特殊なケースとして機能します。しかし、以前の実装では、各UTF-8文字を `string(ch)` のように `rune` から新しい `string` に変換する際に、不要なメモリ割り当てが発生していました。Go言語において、`string(rune)` の変換は新しい文字列オブジェクトを生成するため、ループ内で頻繁に呼び出されるとガベージコレクションの負荷が増大し、性能劣化の原因となります。

コミットメッセージに記載されているベンチマーク結果 `BenchmarkSplit1 77984460 24131380 -69.06%` は、この変更によって実行時間が約69%削減されたことを示しており、この最適化が非常に効果的であったことを裏付けています。これは、特に大きな文字列を文字ごとに分割するようなシナリオにおいて、アプリケーションの応答性やスループットに大きな影響を与える可能性があります。

## 前提知識の解説

### Go言語の文字列とUTF-8

Go言語の文字列は、読み取り専用のバイトスライスであり、UTF-8エンコードされたテキストを保持します。Goの文字列は、内部的にはバイト列として扱われますが、`range` ループなどでイテレートすると、各要素はUTF-8デコードされたUnicodeコードポイント（`rune` 型）として扱われます。

### `rune` 型

`rune` はGo言語におけるUnicodeコードポイントを表す型で、`int32` のエイリアスです。UTF-8エンコードされた文字列から1文字を読み取る際に使用されます。

### `utf8.DecodeRuneInString`

`unicode/utf8` パッケージの `DecodeRuneInString(s string)` 関数は、文字列 `s` の先頭から1つのUTF-8エンコードされたUnicodeコードポイントをデコードし、そのコードポイント（`rune`）と、そのコードポイントが占めるバイト数（`size`）を返します。もし無効なUTF-8シーケンスが検出された場合、`utf8.RuneError` と1バイトを返します。

### `utf8.RuneError`

`utf8.RuneError` は、無効なUTF-8シーケンスがデコードされた際に `DecodeRuneInString` が返す特別な `rune` 値です。通常、`U+FFFD` (REPLACEMENT CHARACTER) に対応します。

### Go言語におけるメモリ割り当てとガベージコレクション

Go言語はガベージコレクタを持つ言語であり、プログラムが動的にメモリを割り当てると、そのメモリはヒープに確保されます。不要になったメモリはガベージコレクタによって自動的に解放されますが、頻繁なメモリ割り当てと解放はガベージコレクタの実行頻度を高め、プログラムのパフォーマンスに悪影響を与える可能性があります。特に、ループ内で小さなオブジェクトを繰り返し生成するようなパターンは、"allocation hot spot" となりやすく、最適化の対象となります。

### `strings.Split` 関数

`strings.Split(s, sep string)` 関数は、文字列 `s` を区切り文字 `sep` で分割し、部分文字列のスライスを返します。
特殊なケースとして、`sep` が空文字列 `""` の場合、`Split` は文字列 `s` を個々のUTF-8文字に分割します。例えば、`strings.Split("Go言語", "")` は `["G", "o", "言", "語"]` を返します。

## 技術的詳細

このコミットの技術的な核心は、`strings.Split(s, "")` が内部的に呼び出す `explode` 関数における、各文字の文字列化の最適化です。

以前の実装では、`explode` 関数内で `utf8.DecodeRuneInString` を使って `rune` とそのバイトサイズ `size` を取得した後、`a[i] = string(ch)` のように `rune` を直接 `string` に変換していました。

```go
// 変更前
ch, size = utf8.DecodeRuneInString(s[cur:])
a[i] = string(ch) // ここで新しい文字列が割り当てられる

Go言語において、string(rune) は新しい文字列オブジェクトをヒープに割り当てます。例えば、string('A') は1バイトの文字列 "A" を、string('語') は3バイトの文字列 "語" をそれぞれ新しいメモリ領域に割り当てます。文字列 s が長ければ長いほど、この割り当てが繰り返され、ガベージコレクションのオーバーヘッドが大きくなっていました。

新しい実装では、この不要な割り当てを回避するために、以下の条件分岐が導入されました。

// 変更後
if ch == utf8.RuneError {
    a[i] = string(utf8.RuneError) // 無効なUTF-8シーケンスの場合のみ、RuneErrorを文字列化
} else {
    a[i] = s[cur : cur+size] // 有効なUTF-8シーケンスの場合、元の文字列のスライスを使用
}

この変更のポイントは、有効なUTF-8シーケンスの場合に s[cur : cur+size] というスライス操作を使用している点です。Go言語の文字列スライスは、元の文字列の基盤となるバイト配列を共有します。つまり、s[cur : cur+size] は新しいメモリを割り当てることなく、元の文字列 s の一部を指す新しい文字列ヘッダを作成するだけです。これにより、各文字を個別の文字列として表現する際に発生していた大量のメモリ割り当てが不要になり、ガベージコレクションの負荷が劇的に軽減されました。

utf8.RuneError の場合のみ string(utf8.RuneError) を使用するのは、utf8.RuneError が単一の rune であり、そのバイト表現が常に1バイトであるため、s[cur:cur+size] のように元の文字列からスライスしても、それが utf8.RuneError の正しい文字列表現 ("\xef\xbf\xbd") にならない可能性があるためです。utf8.RuneError は U+FFFD であり、UTF-8では3バイトでエンコードされます。したがって、無効なシーケンスが1バイトであったとしても、その結果として utf8.RuneError が返された場合は、正しく U+FFFD の文字列表現を生成する必要があります。

この最適化により、Split(s, "") のパフォーマンスが大幅に向上し、特に大量のテキストデータを文字単位で処理するようなアプリケーションにおいて、その恩恵を受けることができます。

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

src/pkg/strings/strings.go ファイルの explode 関数内の変更です。

--- a/src/pkg/strings/strings.go
+++ b/src/pkg/strings/strings.go
@@ -26,7 +26,11 @@ func explode(s string, n int) []string {
 	i, cur := 0, 0
 	for ; i+1 < n; i++ {
 		ch, size = utf8.DecodeRuneInString(s[cur:])
-		a[i] = string(ch)
+		if ch == utf8.RuneError {
+			a[i] = string(utf8.RuneError)
+		} else {
+			a[i] = s[cur : cur+size]
+		}
 		cur += size
 	}
 	// add the rest, if there is any

また、src/pkg/strings/strings_test.go には、この変更のパフォーマンスを測定するための新しいベンチマーク関数が追加されています。

--- a/src/pkg/strings/strings_test.go
+++ b/src/pkg/strings/strings_test.go
@@ -1095,3 +1095,21 @@ func BenchmarkFieldsFunc(b *testing.B) {
 		FieldsFunc(fieldsInput, unicode.IsSpace)
 	}
 }
+
+func BenchmarkSplit1(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		Split(benchInputHard, "")
+	}
+}
+
+func BenchmarkSplit2(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		Split(benchInputHard, "/")
+	}
+}
+
+func BenchmarkSplit3(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		Split(benchInputHard, "hello")
+	}
+}

コアとなるコードの解説

src/pkg/strings/strings.go の変更

explode 関数は、strings.Split(s, "") が呼び出された際に、文字列 s を個々のUTF-8文字に分割して文字列スライスを生成する内部ヘルパー関数です。

変更前は、ループ内で utf8.DecodeRuneInString から得られた rune 型の ch を直接 string(ch) として文字列に変換していました。これは、各 rune ごとに新しい文字列オブジェクトをヒープに割り当てる原因となっていました。

変更後は、以下の条件分岐が追加されました。

if ch == utf8.RuneError {
    a[i] = string(utf8.RuneError)
} else {
    a[i] = s[cur : cur+size]
}

  • if ch == utf8.RuneError:

    • utf8.DecodeRuneInString が無効なUTF-8シーケンスを検出した場合、ch は utf8.RuneError となります。
    • この場合、string(utf8.RuneError) を使用して、U+FFFD (REPLACEMENT CHARACTER) を表す文字列を明示的に生成します。これは、utf8.RuneError が3バイトのUTF-8シーケンス (\xef\xbf\xbd) であるため、元の文字列からスライスするだけでは正しい表現にならない可能性があるためです。

  • else:

    • ch が有効なUTF-8文字である場合、s[cur : cur+size] というスライス操作を使用します。
    • s[cur : cur+size] は、元の文字列 s の cur から cur+size までのバイト範囲を指す新しい文字列ヘッダを作成します。この操作は、新しいメモリ割り当てを伴いません。元の文字列の基盤となるバイト配列を再利用するため、非常に効率的です。

この変更により、ほとんどのケース（有効なUTF-8文字の場合）で不要なメモリ割り当てが回避され、Split(s, "") のパフォーマンスが大幅に向上しました。

src/pkg/strings/strings_test.go の変更

このファイルには、Split 関数のパフォーマンスを測定するための新しいベンチマーク関数が追加されています。

  • BenchmarkSplit1: Split(benchInputHard, "") のベンチマークです。このコミットで最適化された主要なケースです。
  • BenchmarkSplit2: Split(benchInputHard, "/") のベンチマークです。区切り文字が空文字列でない場合のパフォーマンスを測定します。
  • BenchmarkSplit3: Split(benchInputHard, "hello") のベンチマークです。区切り文字が複数文字の場合のパフォーマンスを測定します。

これらのベンチマークは、変更が特定のケース（Split(s, "")）にのみ影響を与え、他の一般的な Split の使用パターンに悪影響を与えないことを確認するために重要です。コミットメッセージの BenchmarkSplit1 の結果が、この最適化の成功を示しています。

関連リンク

参考にした情報源リンク