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

このコミットは、Go言語のランタイムにおける文字列結合（concatstring関数）の最適化に関するものです。具体的には、空文字列との結合や、単一の非空文字列のみを含む結合の場合に、不要なメモリ割り当てを回避することでパフォーマンスを向上させています。

コミット

commit 8744d35dd3429b175559ca89799858b1fd497bcb
Author: Russ Cox <rsc@golang.org>
Date:   Wed Jun 27 17:06:49 2012 -0400

    runtime: avoid allocation for "" + x + ""
    
    R=golang-dev, r
    CC=golang-dev
    https://golang.org/cl/6359043

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

https://github.com/golang/go/commit/8744d35dd3429b175559ca89799858b1fd497bcb

元コミット内容

commit 8744d35dd3429b175559ca89799858b1fd497bcb
Author: Russ Cox <rsc@golang.org>
Date:   Wed Jun 27 17:06:49 2012 -0400

    runtime: avoid allocation for "" + x + ""
    
    R=golang-dev, r
    CC=golang-dev
    https://golang.org/cl/6359043
---
 src/pkg/runtime/string.goc | 9 ++++++++-\n 1 file changed, 8 insertions(+), 1 deletion(-)\n
diff --git a/src/pkg/runtime/string.goc b/src/pkg/runtime/string.goc
index 090c4cd20e..8a5d59b81d 100644
--- a/src/pkg/runtime/string.goc
+++ b/src/pkg/runtime/string.goc
@@ -141,15 +141,22 @@ runtime·catstring(String s1, String s2)
 static String
 concatstring(int32 n, String *s)
 {
-	int32 i, l;
+	int32 i, l, count;
 	String out;
 
 	l = 0;
+	count = 0;
 	for(i=0; i<n; i++) {
 		if(l + s[i].len < l)
 			runtime·throw("string concatenation too long");
 		l += s[i].len;
+		if(s[i].len > 0) {
+			count++;
+			out = s[i];
+		}
 	}
+	if(count <= 1) // zero or one non-empty string in concatenation
+		return out;
 	
 	out = gostringsize(l);
 	l = 0;

変更の背景

Go言語において、文字列は不変（immutable）な値型です。そのため、複数の文字列を結合する際には、新しい文字列を格納するためのメモリがヒープ上に割り当てられ、元の文字列の内容がコピーされます。これは、特に頻繁な文字列結合が行われる場合に、ガベージコレクション（GC）の負荷を増やし、パフォーマンスのボトルネックとなる可能性があります。

このコミットが行われた2012年当時、Goのランタイムは文字列結合の際に常に新しいメモリを割り当てていました。しかし、"" + x + "" のような結合、つまり空文字列との結合や、実質的に単一の非空文字列しか含まない結合の場合、新しいメモリを割り当ててコピーを行うことは無駄なオーバーヘッドとなります。例えば、"hello" + "" や "" + "world" のような操作は、結果として元の文字列 "hello" や "world" と同じ内容になるため、新しい文字列オブジェクトを作成する必要はありません。

このコミットの目的は、このような自明なケースを検出し、不要なメモリ割り当てとデータコピーを回避することで、文字列結合の効率を向上させることにありました。これにより、特に文字列操作が頻繁に行われるアプリケーションにおいて、ランタイムのパフォーマンスが改善され、GCの頻度や時間が削減されることが期待されます。

前提知識の解説

Go言語の文字列

Go言語の文字列は、バイトの読み取り専用スライスとして内部的に表現されます。これは、文字列が不変であることを意味します。文字列変数は、基となるバイト配列へのポインタと、その長さを保持する構造体です。

type StringHeader struct {
    Data uintptr // ポインタ
    Len  int     // 長さ
}

この不変性のため、Goで文字列を結合する（+演算子を使用する）と、常に新しい文字列が生成されます。例えば、s3 := s1 + s2 のような操作では、s1とs2の内容を結合した新しいバイト配列がメモリ上に確保され、その新しい配列を指すStringHeaderがs3に割り当てられます。

メモリ割り当てとガベージコレクション (GC)

Goは自動メモリ管理（ガベージコレクション）を採用しています。プログラムが新しいオブジェクト（この場合は新しい文字列）を必要とすると、ランタイムはヒープからメモリを割り当てます。不要になったオブジェクトはGCによって自動的に解放されます。

しかし、頻繁なメモリ割り当てはGCのトリガーとなりやすく、GCが実行されるとプログラムの実行が一時停止（ストップ・ザ・ワールド）することがあります。これは、特に低レイテンシが求められるアプリケーションにおいて、パフォーマンスの低下や応答性の悪化につながる可能性があります。したがって、不要なメモリ割り当てを減らすことは、Goアプリケーションのパフォーマンス最適化において重要な戦略の一つです。

`runtime`パッケージと`string.goc`

Go言語の標準ライブラリには、Goで書かれたコードだけでなく、C言語（またはGoのランタイムが使用する特殊なC言語のサブセット）で書かれた部分も含まれています。src/pkg/runtime/string.gocは、Goランタイムの一部であり、文字列操作に関する低レベルな処理、特に文字列結合のようなプリミティブな操作の実装が含まれています。.goc拡張子は、GoのランタイムがC言語とGo言語のハイブリッドコードを扱うための特別なファイルであることを示しています。

concatstring関数は、Goの+演算子による文字列結合の内部的な実装を担う関数の一つです。この関数は、結合される複数の文字列（String *s）と、その数（int32 n）を受け取り、結合された新しい文字列を返します。

技術的詳細

このコミットの技術的な核心は、concatstring関数における早期リターンパスの導入です。変更前は、concatstring関数は常に結合される文字列の合計長を計算し、その長さに基づいて新しいメモリを割り当て、すべての文字列の内容をコピーしていました。

変更後は、以下のロジックが追加されました。

非空文字列のカウント (count): 結合される文字列の配列 s をループする際に、各文字列の長さ s[i].len をチェックします。
- もし s[i].len > 0 であれば、つまりその文字列が空でなければ、count 変数をインクリメントします。
- 同時に、最後に発見された非空文字列を out 変数に保持します。これは、count が1以下の場合にその文字列を直接返すための準備です。
早期リターン条件: ループが終了した後、if(count <= 1) という条件がチェックされます。
- count == 0 の場合：これは、結合されるすべての文字列が空文字列であったことを意味します（例: "" + "" + ""）。この場合、結果は空文字列になるべきです。out は初期値の空文字列のままか、あるいはループ内で一度も非空文字列が検出されなかったため、適切な空文字列が返されます。
- count == 1 の場合：これは、結合される文字列の中に非空文字列がちょうど1つだけ存在し、残りはすべて空文字列であったことを意味します（例: "" + "hello" + "" や "world" + ""）。この場合、結果は唯一の非空文字列そのものになるべきです。out 変数にはその唯一の非空文字列が保持されているため、それを直接返します。

この if(count <= 1) の条件が真である場合、関数は out を返して終了します。これにより、その後の gostringsize(l) による新しいメモリ割り当てと、続く文字列内容のコピー処理が完全にスキップされます。

この最適化は、特にコンパイル時に文字列リテラルが結合される場合や、実行時に動的に生成される文字列が空文字列と結合されるようなシナリオで効果を発揮します。例えば、fmt.Sprintfのような関数が内部で文字列結合を多用する場合、このような自明なケースの最適化は全体的なパフォーマンスに寄与します。

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

diff --git a/src/pkg/runtime/string.goc b/src/pkg/runtime/string.goc
index 090c4cd20e..8a5d59b81d 100644
--- a/src/pkg/runtime/string.goc
+++ b/src/pkg/runtime/string.goc
@@ -141,15 +141,22 @@ runtime·catstring(String s1, String s2)
 static String
 concatstring(int32 n, String *s)
 {
-	int32 i, l;
+	int32 i, l, count;
 	String out;
 
 	l = 0;
+	count = 0;
 	for(i=0; i<n; i++) {
 		if(l + s[i].len < l)
 			runtime·throw("string concatenation too long");
 		l += s[i].len;
+		if(s[i].len > 0) {
+			count++;
+			out = s[i];
+		}
 	}
+	if(count <= 1) // zero or one non-empty string in concatenation
+		return out;
 	
 	out = gostringsize(l);
 	l = 0;

コアとなるコードの解説

変更は src/pkg/runtime/string.goc ファイル内の concatstring 関数に集中しています。

変数の追加:
- int32 count; が追加されました。これは、結合対象の文字列の中に、空ではない文字列がいくつあるかを数えるためのカウンターです。
ループ内の変更:
- for(i=0; i<n; i++) ループ内で、各文字列 s[i] の長さ s[i].len がチェックされます。
- if(s[i].len > 0): もし現在の文字列が空でなければ、以下の処理が行われます。
  - count++;: 非空文字列のカウントを増やします。
  - out = s[i];: 現在の非空文字列を out 変数に代入します。これにより、ループの最後に out には、もし非空文字列が1つしかなければその文字列が、複数あれば最後に処理された非空文字列が格納されます。
早期リターンロジックの追加:
- ループの直後に if(count <= 1) という条件が追加されました。
- この条件が真の場合（つまり、結合対象の文字列がすべて空文字列であるか、または非空文字列が1つだけである場合）、関数は return out; を実行して終了します。
- コメント // zero or one non-empty string in concatenation が追加され、この条件が何を意味するかが明確にされています。

この変更により、count が0または1の場合、gostringsize(l) による新しいメモリ割り当てと、その後の文字列内容のコピー処理が完全にスキップされます。これにより、これらの自明なケースでのパフォーマンスが向上し、不要なメモリ割り当てが削減されます。

参考にした情報源リンク

Go CL 6359043: https://golang.org/cl/6359043 (コミットメッセージに記載されているChangeListへのリンク)
Go言語の文字列結合のパフォーマンスに関する議論や記事 (一般的な情報源として、このコミットの背景を理解するために参照しました。特定のURLは挙げませんが、"Go string concatenation performance"などで検索すると多数見つかります。)
Go言語のガベージコレクションに関する情報 (一般的な情報源として、メモリ割り当ての背景を理解するために参照しました。)

comemo