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

このコミットは、Go言語のランタイムにおける文字列連結処理の最適化と、それに伴う内部実装の変更に関するものです。特に、可変長引数（vararg）を持つC関数 concatstring の使用を廃止し、代わりに引数の数に応じた専用の関数（concatstring2 から concatstring5）と、多数の文字列を連結する場合にスライスを使用する concatstrings 関数を導入しています。これにより、ガベージコレクション（GC）のスキャン効率とスタックコピーのオーバーヘッドが改善されます。

コミット

commit 24699fb05c897dbaec3fe4f1d565c3c9da5078fc
Author: Keith Randall <khr@golang.org>
Date:   Tue Dec 3 10:39:19 2013 -0800

    runtime: get rid of concatstring's vararg C argument.
    
    Pass as a slice of strings instead.  For 2-5 strings, implement
    dedicated routines so no slices are needed.
    
    static call counts in the go binary:
     2 strings: 342 occurrences
     3 strings:  98
     4 strings:  30
     5 strings:  13
    6+ strings:  14
    
    Why?  C varags, bad for stack scanning and copying.
    
    R=golang-dev, iant
    CC=golang-dev
    https://golang.org/cl/36380043

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

https://github.com/golang/go/commit/24699fb05c897dbaec3fe4f1d565c3c9da5078fc

元コミット内容

Go言語のランタイムにおいて、文字列連結を行う concatstring 関数がC言語の可変長引数（vararg）を使用していました。このコミットは、その可変長引数の使用を廃止し、代わりに文字列のスライスを引数として渡すように変更します。また、2〜5個の文字列を連結する場合には、スライスを必要としない専用のルーチンを実装します。

コミットメッセージには、Goバイナリにおける静的な呼び出し回数の統計が含まれています。

• 2つの文字列連結: 342回
• 3つの文字列連結: 98回
• 4つの文字列連結: 30回
• 5つの文字列連結: 13回
• 6つ以上の文字列連結: 14回

この変更の理由は、「C言語の可変長引数は、スタックスキャンとコピーにとって都合が悪い」ためと明記されています。

変更の背景

Go言語のランタイムは、ガベージコレクション（GC）を効率的に行うために、スタック上のポインタを正確に識別し、スキャンする必要があります。C言語の可変長引数（vararg）は、引数の型と数がコンパイル時に固定されないため、ランタイムがスタック上の引数を正確に解釈し、ポインタを識別することが困難になります。

具体的には、concatstring のような関数がCの vararg を使用している場合、GoのGCはスタックフレームをスキャンする際に、どのメモリ位置が文字列（ポインタ）であり、どのメモリ位置が単なる整数や他のデータであるかを区別するのが難しくなります。これにより、GCの正確性が損なわれたり、スタックのコピー（例えば、goroutineのスタック拡張時）の際に余分なオーバーヘッドが発生したりする可能性がありました。

このコミットの背景には、GoランタイムのパフォーマンスとGC効率の向上という明確な目標があります。特に、文字列連結は頻繁に行われる操作であるため、その内部実装の最適化は全体的なパフォーマンスに大きな影響を与えます。コミットメッセージに示されているように、2〜5個の文字列連結が全体の大部分を占めていることから、これらのケースを特別に最適化することで、最も一般的なシナリオでのオーバーヘッドを削減しようとしています。

前提知識の解説

このコミットを理解するためには、以下の前提知識が必要です。

1. Go言語の文字列: Goの文字列はイミュータブル（不変）であり、内部的にはバイトスライスと長さのペアとして表現されます。文字列連結は新しい文字列を生成する操作であり、メモリ割り当てが発生します。

2. Go言語のランタイムとガベージコレクション (GC):

   • ランタイム: Goプログラムの実行を管理する部分で、スケジューラ、メモリ管理（GCを含む）、goroutineの管理などを担当します。
   • ガベージコレクション (GC): 不要になったメモリを自動的に解放する仕組みです。GoのGCは、スタックとヒープ上のポインタをスキャンして、到達可能なオブジェクトを特定します。
   • スタックスキャン: GCがスタック上のポインタを識別し、それらが指すヒープ上のオブジェクトをマークするプロセスです。これにより、GCは生きているオブジェクトを正確に追跡できます。
   • スタックコピー: goroutineのスタックが不足した場合、より大きなスタック領域に内容をコピーする操作です。この際、スタック上のポインタを正確に移動させる必要があります。

3. C言語の可変長引数 (Variadic Arguments / vararg):

   • C言語では、printf のように引数の数が可変な関数を定義できます。これらは stdarg.h ヘッダの va_list, va_start, va_arg, va_end マクロを使って実装されます。
   • 可変長引数は、コンパイル時に引数の型や数が決定されないため、実行時に引数リストを解析する必要があります。
   • この動的な性質が、Goのランタイムがスタック上のポインタを静的に（コンパイル時に）識別するのを困難にします。GCは、スタック上のどの部分がポインタであるかを知る必要がありますが、vararg の場合、その情報が不足しがちです。

4. Goコンパイラの内部構造 (gcツールチェーン):

   • src/cmd/gc: Goコンパイラのフロントエンドとバックエンドの一部が含まれます。Goソースコードを解析し、中間表現に変換し、最終的にアセンブリコードを生成します。
   • src/cmd/gc/builtin.c: Goの組み込み関数（print, panic など）やランタイム関数（concatstring など）の宣言がC言語の形式で記述されています。これらはコンパイラがGoコードから呼び出すためのインターフェースを提供します。
   • src/cmd/gc/runtime.go: Goのランタイム関数の一部がGo言語で宣言されています。これらはコンパイラがGoコードから呼び出すためのGo言語のシグネチャを提供します。
   • src/cmd/gc/walk.c: コンパイラの「ウォーカー」フェーズの一部で、抽象構文木（AST）を走査し、最適化やコード生成のための変換を行います。文字列連結のような操作は、このフェーズでランタイム関数への呼び出しに変換されます。
   • src/pkg/runtime/string.goc: Goランタイムの文字列関連の関数が実装されています。.goc ファイルは、GoとCのハイブリッドコードを記述するための特殊なファイル形式で、Goの構文とCの構文を混在させることができます。これは、GoのランタイムがC言語で書かれた部分とGo言語で書かれた部分を橋渡しするために使用されます。

技術的詳細

このコミットの核心は、GoランタイムがC言語の可変長引数関数 runtime·concatstring を使用して文字列連結を処理していた問題を解決することです。

問題点: C言語の可変長引数は、Goのガベージコレクタにとって大きな課題でした。GCはスタックをスキャンしてポインタを識別し、ヒープ上のオブジェクトをマークする必要がありますが、可変長引数では引数の型と数が実行時まで不明なため、スタック上のどの部分がポインタ（文字列データへの参照）であるかを正確に判断できませんでした。これにより、GCの正確性が損なわれたり、スタックのコピー（goroutineのスタック拡張時など）の際に、ポインタの移動が不正確になるリスクがありました。

解決策: このコミットでは、以下の戦略でこの問題を解決しています。

1. 可変長引数の廃止: runtime·concatstring のC言語の可変長引数シグネチャを廃止します。

2. 専用関数の導入 (2〜5個の文字列):

   • Goバイナリの静的解析結果から、2〜5個の文字列連結が最も頻繁に行われることが判明しました。
   • これらのケースのために、concatstring2, concatstring3, concatstring4, concatstring5 という専用のランタイム関数が導入されました。
   • これらの関数は固定数の引数（Goの string 型）を取るため、コンパイラとランタイムはスタック上の引数のレイアウトを正確に把握できます。これにより、GCのスタックスキャンが容易になり、スタックコピーも安全に行えます。
   • これらの関数は NOSPLIT プラグマが付けられており、スタックの拡張を伴わない（つまり、スタックフレームが非常に小さい）ことを示唆しています。

3. スライス引数の導入 (6個以上の文字列):

   • 6個以上の文字列を連結する場合、concatstrings という新しいランタイム関数が使用されます。
   • この関数は、連結する文字列を []string 型のスライスとして受け取ります。
   • スライスは、Goにおいて要素の型と数が明確に定義されたデータ構造であるため、GCはスライス内のポインタ（文字列データへの参照）を正確に識別できます。これにより、可変長引数の問題を回避しつつ、任意の数の文字列連結に対応できます。

実装の詳細:

• コンパイラ (src/cmd/gc/) の変更:

  • src/cmd/gc/builtin.c と src/cmd/gc/runtime.go: 新しい concatstringN 関数と concatstrings 関数の宣言が追加され、古い concatstring の宣言が削除されました。これにより、コンパイラがこれらの新しいランタイム関数を認識できるようになります。
  • src/cmd/gc/walk.c: Goのソースコード中の文字列連結 (+ 演算子や fmt.Sprintf などが最終的に変換される OADDSTR ノード) を処理する addstr 関数が変更されました。
    • 連結される文字列の数 (count) に応じて、呼び出すランタイム関数を動的に決定します。
    • count が2〜5の場合、concatstring%d (例: concatstring2) という名前の関数を呼び出し、個々の文字列を引数として渡します。
    • count が6以上の場合、concatstrings 関数を呼び出し、連結する文字列すべてを含む []string 型のリテラルスライスを生成し、それを単一の引数として渡します。

• ランタイム (src/pkg/runtime/) の変更:

  • src/pkg/runtime/string.goc:
    • 古い runtime·concatstring の実装が削除されました。
    • concatstring2, concatstring3, concatstring4, concatstring5 の各関数が実装されました。これらは内部的に既存の concatstring ヘルパー関数（C言語で実装された、文字列の数と文字列ポインタの配列を受け取る関数）を呼び出します。USED(&sX) は、引数が使用されていることをコンパイラに伝えるためのマクロで、最適化によって未使用と判断されないようにします。
    • concatstrings 関数が実装されました。これも内部的に concatstring ヘルパー関数を呼び出しますが、引数として受け取ったスライスの長さと、スライスの基底配列へのポインタを渡します。

この変更により、Goランタイムは文字列連結処理において、C言語の可変長引数に起因するGCの課題を回避し、より効率的で安全なスタックスキャンとスタックコピーを実現できるようになりました。

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

このコミットは主に以下の4つのファイルに影響を与えています。

1. src/cmd/gc/builtin.c:

   • runtimeimport 文字列から、古い func @\"\".concatstring () の宣言が削除されました。
   • 新しい固定引数を持つ concatstring2 から concatstring5 までの関数と、スライス引数を持つ concatstrings 関数の宣言が追加されました。

   --- a/src/cmd/gc/builtin.c
   +++ b/src/cmd/gc/builtin.c
   @@ -23,7 +23,11 @@ char *runtimeimport =
    	"func @\"\".printnl ()\n"
    	"func @\"\".printsp ()\n"
    	"func @\"\".goprintf ()\n"
   -	"func @\"\".concatstring ()\n"
   +	"func @\"\".concatstring2 (? string, ? string) (? string)\n"
   +	"func @\"\".concatstring3 (? string, ? string, ? string) (? string)\n"
   +	"func @\"\".concatstring4 (? string, ? string, ? string, ? string) (? string)\n"
   +	"func @\"\".concatstring5 (? string, ? string, ? string, ? string, ? string) (? string)\n"
   +	"func @\"\".concatstrings (? []string) (? string)\n"
    	"func @\"\".cmpstring (? string, ? string) (? int)\n"
    	"func @\"\".eqstring (? string, ? string) (? bool)\n"
    	"func @\"\".intstring (? int64) (? string)\n"
   

2. src/cmd/gc/runtime.go:

   • Go言語側でのランタイム関数の宣言も同様に更新されました。古い concatstring のコメントアウトされた宣言が削除され、新しい関数群のGo言語シグネチャが追加されました。

   --- a/src/cmd/gc/runtime.go
   +++ b/src/cmd/gc/runtime.go
   @@ -36,8 +36,11 @@ func printnl()
    func printsp()
    func goprintf()
    
   -// filled in by compiler: int n, string, string, ...
   -func concatstring()
   +func concatstring2(string, string) string
   +func concatstring3(string, string, string) string
   +func concatstring4(string, string, string, string) string
   +func concatstring5(string, string, string, string, string) string
   +func concatstrings([]string) string
    
    func cmpstring(string, string) int
    func eqstring(string, string) bool
   

3. src/cmd/gc/walk.c:

   • addstr 関数（文字列連結のASTノードを処理する部分）が大幅に変更されました。
   • 古い concatstring への呼び出しを生成するロジックが削除されました。
   • 連結する文字列の数 (count) に応じて、concatstring%d または concatstrings のどちらを呼び出すかを決定する新しいロジックが追加されました。
   • concatstrings を呼び出す場合、連結する文字列を要素とするスライスリテラル (OCOMPLIT) を生成し、それを引数として渡すようになりました。

   --- a/src/cmd/gc/walk.c
   +++ b/src/cmd/gc/walk.c
   @@ -2558,33 +2558,39 @@ mapfndel(char *name, Type *t)\n static Node*\n addstr(Node *n, NodeList **init)\n {\n-	Node *r, *cat, *typstr;\n-	NodeList *in, *args;\n-	int i, count;\n+	Node *r, *cat, *slice;\n+	NodeList *args;\n+	int count;\n+	Type *t;\n \n     count = 0;\n     for(r=n; r->op == OADDSTR; r=r->left)\n     	count++;	// r->right\n     count++;	// r
   +	if(count < 2)
   +		yyerror("addstr count %d too small", count);
    
   -	// prepare call of runtime.catstring of type int, string, string, string
   -	// with as many strings as we have.
   -	cat = syslook("concatstring", 1);\n    -	cat->type = T;\n    -	cat->ntype = nod(OTFUNC, N, N);\n    -	in = list1(nod(ODCLFIELD, N, typenod(types[TINT])));	// count
   -	typstr = typenod(types[TSTRING]);\n    -	for(i=0; i<count; i++)
   -	in = list(in, nod(ODCLFIELD, N, typstr));\n    -	cat->ntype->list = in;\n    -	cat->ntype->rlist = list1(nod(ODCLFIELD, N, typstr));\n    -\n    +	// build list of string arguments
    	args = nil;\n     for(r=n; r->op == OADDSTR; r=r->left)\n     	args = concat(list1(conv(r->right, types[TSTRING])), args);\n     args = concat(list1(conv(r, types[TSTRING])), args);\n    -	args = concat(list1(nodintconst(count)), args);\n     
   +	if(count <= 5) {
   +		// small numbers of strings use direct runtime helpers.
   +		snprint(namebuf, sizeof(namebuf), "concatstring%d", count);
   +	} else {
   +		// large numbers of strings are passed to the runtime as a slice.
   +		strcpy(namebuf, "concatstrings");
   +		t = typ(TARRAY);
   +		t->type = types[TSTRING];
   +		t->bound = -1;
   +		slice = nod(OCOMPLIT, N, typenod(t));
   +		slice->list = args;
   +		slice->esc = EscNone;
   +		args = list1(slice);
   +	}
   +	cat = syslook(namebuf, 1);
    	r = nod(OCALL, cat, N);\n     r->list = args;\n     typecheck(&r, Erv);\n    ```
   
   

4. src/pkg/runtime/string.goc:

   • 古い runtime·concatstring の実装が削除されました。特に、// NOTE: Cannot use func syntax, because we need the ...,\n// to signal to the garbage collector that this function does\n// not have a fixed size argument count. というコメントが削除されている点に注目です。これは、まさに可変長引数の問題を示唆していました。
   • concatstring2, concatstring3, concatstring4, concatstring5 の各関数が、それぞれ固定数の String 引数を受け取り、内部で concatstring ヘルパー関数を呼び出す形で実装されました。
   • concatstrings 関数が、Slice 型の引数を受け取り、内部で concatstring ヘルパー関数を呼び出す形で実装されました。

   --- a/src/pkg/runtime/string.goc
   +++ b/src/pkg/runtime/string.goc
   @@ -179,14 +179,35 @@ concatstring(intgo n, String *s)\n     return out;\n }\n \n-// NOTE: Cannot use func syntax, because we need the ...,\n-// to signal to the garbage collector that this function does\n-// not have a fixed size argument count.\n #pragma textflag NOSPLIT\n-void\n-runtime·concatstring(intgo n, String s1, ...)\n-{\n-	(&s1)[n] = concatstring(n, &s1);\n+func concatstring2(s1 String, s2 String) (res String) {\n+	USED(&s2);\n+	res = concatstring(2, &s1);\n+}\n+#pragma textflag NOSPLIT\n+func concatstring3(s1 String, s2 String, s3 String) (res String) {\n+	USED(&s2);\n+	USED(&s3);\n+	USED(&s4);\n+	res = concatstring(3, &s1);\n+}\n+#pragma textflag NOSPLIT\n+func concatstring4(s1 String, s2 String, s3 String, s4 String) (res String) {\n+	USED(&s2);\n+	USED(&s3);\n+	USED(&s4);\n+	res = concatstring(4, &s1);\n+}\n+#pragma textflag NOSPLIT\n+func concatstring5(s1 String, s2 String, s3 String, s4 String, s5 String) (res String) {\n+	USED(&s2);\n+	USED(&s3);\n+	USED(&s4);\n+	USED(&s5);\n+	res = concatstring(5, &s1);\n+}\n+#pragma textflag NOSPLIT\n+func concatstrings(s Slice) (res String) {\n+	res = concatstring(s.len, (String*)s.array);\n }\n \n func eqstring(s1 String, s2 String) (v bool) {\
   

コアとなるコードの解説

このコミットの主要な変更は、Goコンパイラが文字列連結をどのようにランタイム関数に変換するか、そしてランタイムがそれらの連結をどのように処理するかという点にあります。

src/cmd/gc/walk.c の addstr 関数: この関数は、Goのソースコード中の文字列連結 (s1 + s2 + ...) を表す抽象構文木 (AST) ノード OADDSTR を処理します。 変更前は、連結される文字列の数 count と、個々の文字列をC言語の可変長引数として runtime·concatstring に渡していました。 変更後は、count の値によって処理を分岐させます。

• if(count <= 5):

  • 連結する文字列が2〜5個の場合、snprint(namebuf, sizeof(namebuf), "concatstring%d", count); を使って、呼び出すランタイム関数の名前（例: concatstring2, concatstring3）を動的に生成します。
  • 生成された名前の関数 (cat = syslook(namebuf, 1);) を探し、個々の文字列をそのまま引数 (args) として渡します。
  • これにより、コンパイラは固定引数の関数呼び出しを生成し、ランタイムはスタック上の引数を正確に認識できます。

• else (つまり count > 5):

  • 連結する文字列が6個以上の場合、strcpy(namebuf, "concatstrings"); で呼び出す関数名を concatstrings に設定します。
  • 連結するすべての文字列を要素とするGoのスライスリテラル (slice = nod(OCOMPLIT, N, typenod(t));) を生成します。このスライスは []string 型です。
  • このスライスリテラルを単一の引数 (args = list1(slice);) として concatstrings に渡します。
  • これにより、多数の文字列連結でも、GCが安全にスキャンできる単一のスライス引数として処理されます。

src/pkg/runtime/string.goc の新しいランタイム関数群: これらの関数は、Goコンパイラによって生成された呼び出しを受け取ります。

• func concatstring2(s1 String, s2 String) (res String) (および concatstring3 から concatstring5):

  • Goの string 型は、ランタイム内部では String 構造体（データポインタと長さを持つ）として扱われます。
  • これらの関数は、固定数の String 引数を受け取ります。
  • USED(&sX); は、これらの引数が使用されていることをコンパイラに伝え、最適化による削除を防ぎます。
  • 最終的に、concatstring(N, &s1); のように、C言語で実装された低レベルの concatstring ヘルパー関数を呼び出します。このヘルパー関数は、連結する文字列の数 N と、最初の文字列のポインタ（そこから連続して他の文字列のポインタが配置されていると仮定）を受け取ります。

• func concatstrings(s Slice) (res String):

  • Goのスライスは、ランタイム内部では Slice 構造体（基底配列へのポインタ、長さ、容量を持つ）として扱われます。
  • この関数は、連結する文字列を含む Slice 引数を受け取ります。
  • concatstring(s.len, (String*)s.array); のように、スライスの長さ (s.len) と、スライスの基底配列の先頭ポインタ ((String*)s.array) をC言語の concatstring ヘルパー関数に渡します。これにより、スライス内のすべての文字列が効率的に連結されます。

これらの変更により、Goの文字列連結は、C言語の可変長引数に依存することなく、Goの型システムとランタイムのGCメカニズムとより調和するようになりました。特に、頻繁に発生する少数の文字列連結は、オーバーヘッドの少ない専用パスを通ることでパフォーマンスが向上し、多数の文字列連結も安全かつ効率的に処理されるようになります。

関連リンク

• Go言語の文字列型: https://go.dev/blog/strings
• Go言語のガベージコレクション: https://go.dev/doc/gc-guide
• Goコンパイラの内部構造に関する一般的な情報: https://go.dev/doc/devel/compiler
• Goのランタイムソースコード: https://github.com/golang/go/tree/master/src/runtime

参考にした情報源リンク

• コミットメッセージ自体: https://github.com/golang/go/commit/24699fb05c897dbaec3fe4f1d565c3c9da5078fc
• Goのソースコード（特に src/cmd/gc/ と src/pkg/runtime/ ディレクトリ）
• C言語の可変長引数に関する一般的な知識
• Goのガベージコレクションとスタックスキャンに関する一般的な知識
• Goの文字列連結のパフォーマンスに関する議論（一般的な情報源）