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

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

このコミットは、Goコンパイラ（cmd/gc）とランタイム（runtime）におけるappend組み込み関数の最適化に関するものです。具体的には、append関数の呼び出しを、コンパイル時にgrowsliceとmemmoveの組み合わせにインライン化することで、パフォーマンスを向上させています。

コミット

commit 045dbeaf053f0c78941a11140e5a877237ccc489
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Mon Sep 16 20:31:21 2013 -0400

    cmd/gc, runtime: inline append in frontend.
    
    A new transformation during walk turns append calls
    into a combination of growslice and memmove.
    
    benchmark                     old ns/op    new ns/op    delta
    BenchmarkAppend                     141          141   +0.00%
    BenchmarkAppend1Byte                 18           11  -39.56%
    BenchmarkAppend4Bytes                19           10  -42.63%
    BenchmarkAppend7Bytes                18           10  -42.16%
    BenchmarkAppend8Bytes                18           10  -40.44%
    BenchmarkAppend15Bytes               19           11  -41.67%
    BenchmarkAppend16Bytes               19           11  -41.97%
    BenchmarkAppend32Bytes               23           14  -38.82%
    BenchmarkAppendStr1Byte              14           10  -23.78%
    BenchmarkAppendStr4Bytes             14           11  -21.13%
    BenchmarkAppendStr8Bytes             14           10  -25.17%
    BenchmarkAppendStr16Bytes            19           11  -41.45%
    BenchmarkAppendStr32Bytes            18           14  -19.44%
    BenchmarkAppendSpecialCase           62           63   +1.77%
    
    R=golang-dev, khr, cshapiro, rsc, dave
    CC=golang-dev
    https://golang.org/cl/12815046

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

https://github.com/golang/go/commit/045dbeaf053f0c78941a11140e5a877237ccc489

元コミット内容

cmd/gc, runtime: inline append in frontend.

このコミットは、append呼び出しをフロントエンドでインライン化するものです。 walkフェーズ中に新しい変換が導入され、append呼び出しがgrowsliceとmemmoveの組み合わせに変換されます。

ベンチマーク結果は以下の通りです。

benchmarkold ns/opnew ns/opdelta
BenchmarkAppend141141+0.00%
BenchmarkAppend1Byte1811-39.56%
BenchmarkAppend4Bytes1910-42.63%
BenchmarkAppend7Bytes1810-42.16%
BenchmarkAppend8Bytes1810-40.44%
BenchmarkAppend15Bytes1911-41.67%
BenchmarkAppend16Bytes1911-41.97%
BenchmarkAppend32Bytes2314-38.82%
BenchmarkAppendStr1Byte1410-23.78%
BenchmarkAppendStr4Bytes1411-21.13%
BenchmarkAppendStr8Bytes1410-25.17%
BenchmarkAppendStr16Bytes1911-41.45%
BenchmarkAppendStr32Bytes1814-19.44%
BenchmarkAppendSpecialCase6263+1.77%

変更の背景

Go言語のappend組み込み関数は、スライスに要素を追加するための非常に頻繁に使用される操作です。以前の実装では、appendはランタイム関数（runtime.appendsliceやruntime.appendstr）としてコンパイルされていました。しかし、関数呼び出しにはオーバーヘッドが伴い、特に小さなスライスへの追加や、頻繁なappend操作が行われる場合にパフォーマンスのボトルネックとなる可能性がありました。

このコミットの目的は、appendのパフォーマンスを向上させることです。具体的には、コンパイラの最適化フェーズ（walk）において、append呼び出しをより低レベルな操作であるgrowslice（スライスの容量を増やす）とmemmove（メモリをコピーする）の組み合わせに直接変換（インライン化）することで、関数呼び出しのオーバーヘッドを排除し、より効率的なコードを生成することを目指しています。これにより、特に小さなデータ（1バイトから32バイト程度）の追加において顕著なパフォーマンス改善が見込まれます。

ベンチマーク結果が示すように、ほとんどのappend操作で大幅な速度向上が達成されており、これはこの最適化が成功したことを示しています。

前提知識の解説

このコミットを理解するためには、以下のGo言語の概念とコンパイラの内部動作に関する知識が必要です。

  1. Goスライス (Slice): Goのスライスは、配列への参照のようなものです。内部的には、ポインタ（基底配列の先頭要素へのポインタ）、長さ（len）、容量（cap）の3つの要素で構成されます。

    • len: スライスが現在保持している要素の数。
    • cap: スライスが参照している基底配列の最大容量。 append操作は、スライスの容量が足りない場合（lenがcapに達している場合）に、より大きな新しい基底配列を割り当て、既存の要素をコピーし、新しい要素を追加するという動作をします。

  2. append組み込み関数: appendはGoの組み込み関数で、スライスに要素を追加するために使用されます。 newSlice = append(oldSlice, elements...) この関数は、必要に応じて新しいスライスを返します（特に容量が不足した場合）。

  3. Goコンパイラのフェーズ: Goコンパイラは複数のフェーズを経てソースコードを実行可能なバイナリに変換します。

    • Parsing: ソースコードを抽象構文木（AST）に変換します。
    • Type Checking: 型の整合性をチェックします。
    • Walk (AST Transformation): ASTを走査し、最適化や組み込み関数の変換など、様々な変換を行います。このコミットの変更は、このwalkフェーズで行われます。
    • SSA (Static Single Assignment) Form: ASTをSSA形式に変換し、さらに最適化を行います。
    • Code Generation: 最終的な機械語コードを生成します。

  4. growslice: Goランタイム内部の関数で、スライスの容量が不足した場合に新しい、より大きな基底配列を割り当て、既存の要素を新しい配列にコピーする役割を担います。これはappend操作において、既存の容量を超える要素を追加する際に暗黙的に呼び出されます。

  5. memmove: メモリブロックをコピーするための低レベルな関数です。Goランタイムでは、スライス要素のコピーや、新しい要素の追加時に既存の要素を移動させる際などに使用されます。C言語のmemmoveと同様に、オーバーラップするメモリ領域のコピーも安全に行えます。

  6. インライン化 (Inlining): 関数呼び出しのオーバーヘッドを削減するためのコンパイラ最適化手法の一つです。関数呼び出しの代わりに、呼び出される関数の本体のコードを呼び出し元に直接埋め込みます。これにより、関数呼び出し/戻りのスタック操作やレジスタ保存/復元などのコストが削減され、パフォーマンスが向上します。

技術的詳細

このコミットの核心は、GoコンパイラのwalkフェーズにおけるOAPPEND（append操作を表すASTノード）の処理方法の変更です。

以前は、append呼び出しはruntime.appendsliceやruntime.appendstrといったランタイム関数への呼び出しに変換されていました。これらのランタイム関数は、スライスの容量チェック、必要に応じたgrowsliceの呼び出し、そして要素のコピー（memmoveを使用）といったロジックをカプセル化していました。

このコミットでは、src/cmd/gc/walk.c内のappendslice関数（これはAST変換を行うコンパイラ側の関数であり、ランタイムのruntime.appendsliceとは異なる）が大幅に書き換えられました。新しいappendslice関数は、append呼び出しを以下の一連の低レベルな操作に展開します。

  1. 一時変数の導入: s := l1 のように、元のスライスl1を保持するための一時変数sを導入します。
  2. 容量チェックとgrowsliceの呼び出し: n := len(l1) + len(l2) - cap(s) を計算し、追加後の要素数が現在の容量を超えるかどうかを判断します。 もしn > 0であれば、s = growslice(s, n) を呼び出してスライスの容量を拡張します。ここでgrowsliceはランタイム関数runtime.growsliceを指します。
  3. 要素のコピー (memmove): memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T)) を使用して、追加される要素l2をスライスの既存要素の末尾にコピーします。
    • &s[len(l1)]: コピー先の開始アドレス（既存要素の直後）。
    • &l2[0]: コピー元の開始アドレス。
    • len(l2)*sizeof(T): コピーするバイト数。 memmoveはランタイム関数runtime.memmoveを指します。 flag_raceが有効な場合（データ競合検出が有効な場合）は、memmoveの代わりにslicestringcopyまたはcopyランタイム関数が使用され、競合検出のための計測が行われます。
  4. スライスの長さの更新: s = s[:len(l1)+len(l2)] のように、スライスの長さを更新します。これは、スライスのポインタと容量は変わらず、長さだけが新しい要素数に合わせて調整されることを意味します。

この変換により、append呼び出しが直接ランタイム関数を呼び出すのではなく、コンパイル時に必要なメモリ管理とデータコピーのロジックが直接生成されるため、関数呼び出しのオーバーヘッドが削減されます。

また、src/pkg/runtime/slice.cからruntime.appendsliceとruntime.appendstr関数が削除され、src/cmd/gc/builtin.cとsrc/cmd/gc/runtime.goからもこれらの関数の宣言が削除されています。これは、これらのランタイム関数がもはやコンパイラによって直接呼び出されなくなったためです。

さらに、src/pkg/runtime/arch_*.hファイルからappendCrossoverという定数が削除されています。これは、以前のruntime.appendslice関数内で、小さなアペンドに対してmemmoveの代わりにバイト単位のループコピーを行うしきい値として使用されていましたが、インライン化によってこの最適化が不要になったためです。

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

このコミットにおける主要なコード変更は以下のファイルに集中しています。

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

    • OAPPEND（append組み込み関数呼び出し）の処理ロジックが大幅に書き換えられました。
    • appendslice関数（コンパイラ側のAST変換関数）が、append呼び出しをgrowsliceとmemmoveの組み合わせに展開するようになりました。
    • 以前はappendstrという特殊なケースを処理していましたが、新しいappendslice関数が文字列の追加もカバーするようになりました。

  2. src/pkg/runtime/slice.c:

    • runtime·appendslice関数とruntime·appendstr関数が完全に削除されました。これらの関数は、コンパイラがappend呼び出しをインライン化するようになったため、不要になりました。

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

    • runtime.appendsliceとruntime.appendstrの組み込み関数宣言が削除されました。

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

    • append, appendslice, appendstrのランタイム関数宣言が削除されました。

  5. src/pkg/runtime/arch_386.h, src/pkg/runtime/arch_amd64.h, src/pkg/runtime/arch_arm.h:

    • appendCrossoverという定数が削除されました。これは、以前のruntime.appendslice関数内で使用されていた最適化のしきい値でした。

コアとなるコードの解説

src/cmd/gc/walk.cのappendslice関数がこのコミットの最も重要な変更点です。

// expand append(l1, l2...) to
//   init {
//     s := l1
//     if n := len(l1) + len(l2) - cap(s); n > 0 {
//       s = growslice(s, n)
//     }
//     s = s[:len(l1)+len(l2)]
//     memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T))
//   }
//   s
//
// l2 is allowed to be a string.
static Node*
appendslice(Node *n, NodeList **init)
{
	NodeList *l;
	Node *l1, *l2, *nt, *nif, *fn;
	Node *nptr1, *nptr2, *nwid;
	Node *s;

	walkexprlistsafe(n->list, init);

	// walkexprlistsafe will leave OINDEX (s[n]) alone if both s
	// and n are name or literal, but those may index the slice we're
	// modifying here.  Fix explicitly.
	for(l=n->list; l; l=l->next)
		l->n = cheapexpr(l->n, init);

	l1 = n->list->n; // 最初の引数 (元のスライス)
	l2 = n->list->next->n; // 2番目の引数 (追加する要素)

	s = temp(l1->type); // var s []T (一時変数sを宣言)
	l = nil;
	l = list(l, nod(OAS, s, l1)); // s = l1 (元のスライスを一時変数に代入)

	nt = temp(types[TINT]);
	nif = nod(OIF, N, N);
	// n := len(s) + len(l2) - cap(s) (必要な追加容量を計算)
	nif->ninit = list1(nod(OAS, nt,
		nod(OSUB, nod(OADD, nod(OLEN, s, N), nod(OLEN, l2, N)), nod(OCAP, s, N))));
	nif->ntest = nod(OGT, nt, nodintconst(0)); // n > 0 かどうかをテスト

	// instantiate growslice(Type*, []any, int64) []any
	fn = syslook("growslice", 1); // growsliceランタイム関数への参照を取得
	argtype(fn, s->type->type);
	argtype(fn, s->type->type);

	// s = growslice(T, s, n) (容量が足りない場合、growsliceを呼び出してスライスを拡張)
	nif->nbody = list1(nod(OAS, s, mkcall1(fn, s->type, &nif->ninit,
					       typename(s->type),
					       s,
					       conv(nt, types[TINT64]))));

	l = list(l, nif); // if文をASTに追加

	if(flag_race) {
		// rely on runtime to instrument copy.
		// copy(s[len(l1):len(l1)+len(l2)], l2)
		nptr1 = nod(OSLICE, s, nod(OKEY,
			nod(OLEN, l1, N),
			nod(OADD, nod(OLEN, l1, N), nod(OLEN, l2, N))));
		nptr1->etype = 1;
		nptr2 = l2;
		if(l2->type->etype == TSTRING)
			fn = syslook("slicestringcopy", 1);
		else
			fn = syslook("copy", 1);
		argtype(fn, l1->type);
		argtype(fn, l2->type);
		l = list(l, mkcall1(fn, types[TINT], init,
				nptr1, nptr2,
				nodintconst(s->type->type->width)));
	} else {
		// memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T)) (要素をコピー)
		nptr1 = nod(OINDEX, s, nod(OLEN, l1, N));
		nptr1->bounded = 1;
		nptr1 = nod(OADDR, nptr1, N);

		nptr2 = nod(OSPTR, l2, N);

		fn = syslook("memmove", 1); // memmoveランタイム関数への参照を取得
		argtype(fn, s->type->type);	// 1 old []any
		argtype(fn, s->type->type);	// 2 ret []any

		nwid = cheapexpr(conv(nod(OLEN, l2, N), types[TUINTPTR]), &l);
		nwid = nod(OMUL, nwid, nodintconst(s->type->type->width));
		l = list(l, mkcall1(fn, T, init, nptr1, nptr2, nwid));
	}

	// s = s[:len(l1)+len(l2)] (スライスの長さを更新)
	nt = nod(OADD, nod(OLEN, l1, N), nod(OLEN, l2, N));
	nt = nod(OSLICE, s, nod(OKEY, N, nt));
	nt->etype = 1;
	l = list(l, nod(OAS, s, nt));

	typechecklist(l, Etop);
	walkstmtlist(l);
	*init = concat(*init, l);
	return s;
}

このコードは、Goのappend呼び出しがコンパイル時にどのように展開されるかを示しています。

  1. s = l1: まず、元のスライスl1が一時変数sにコピーされます。これは、appendが新しいスライスを返す可能性があるため、元のスライスを変更しないようにするためです。
  2. if n := len(l1) + len(l2) - cap(s); n > 0 { s = growslice(s, n) }:
    • len(l1) + len(l2): 追加後のスライスの論理的な長さ。
    • cap(s): 現在のスライスの容量。
    • n: 追加に必要な追加容量。 もしn > 0であれば、現在の容量では足りないため、growsliceランタイム関数を呼び出して、より大きな基底配列を持つ新しいスライスをsに割り当てます。
  3. memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T)):
    • &s[len(l1)]: sの現在の長さの場所から、追加する要素を書き込むためのポインタ。
    • &l2[0]: 追加する要素l2の先頭へのポインタ。
    • len(l2)*sizeof(T): 追加する要素の合計バイト数。 この行は、追加する要素を新しい（または既存の）基底配列の適切な位置にコピーします。flag_raceが有効な場合は、データ競合検出のためにcopyまたはslicestringcopyが使用されます。
  4. s = s[:len(l1)+len(l2)]: 最後に、sの長さが追加された要素の分だけ更新されます。これにより、スライスが新しい要素を含むように「見える」ようになります。

この一連の操作は、appendのロジックを直接コンパイルされたコードに埋め込むことで、ランタイム関数呼び出しのオーバーヘッドを排除し、パフォーマンスを向上させます。

関連リンク

参考にした情報源リンク

  • コミットメッセージと差分 (commit_data/17629.txt)
  • Go言語の公式ドキュメント (Slice, append)
  • Go言語のソースコード (特にsrc/cmd/gc/walk.c, src/pkg/runtime/slice.c)
  • Go言語のベンチマーク結果の解釈に関する一般的な知識
  • コンパイラの最適化（インライン化）に関する一般的な知識
  • memmove関数の一般的な動作に関する知識