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

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

このコミットは、Go言語のコンパイラ（cmd/gc）とランタイム（runtime）において、map[string]型へのルックアップ時に、キーが[]byteスライスからstring(b)のように変換されて生成される場合に、その変換に伴う不要なメモリ割り当てを最適化するものです。これにより、特にパフォーマンスが重要な場面でのガベージコレクションの負荷を軽減し、実行速度を向上させます。

コミット

commit f5f5a8b6209f84961687d993b93ea0d397f5d5bf
Author: Russ Cox <rsc@golang.org>
Date:   Thu Apr 3 19:05:17 2014 -0400

    cmd/gc, runtime: optimize map[string] lookup from []byte key

    Brad has been asking for this for a while.
    I have resisted because I wanted to find a more general way to
    do this, one that would keep the performance of code introducing
    variables the same as the performance of code that did not.
    (See golang.org/issue/3512#c20).

    I have not found the more general way, and recent changes to
    remove ambiguously live temporaries have blown away the
    property I was trying to preserve, so that's no longer a reason
    not to make the change.

    Fixes #3512.

    LGTM=iant
    R=iant
    CC=bradfitz, golang-codereviews, khr, r
    https://golang.org/cl/83740044

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

https://github.com/golang/go/commit/f5f5a8b6209f84961687d993b93ea0d397f5d5bf

元コミット内容

cmd/gc, runtime: optimize map[string] lookup from []byte key

Brad has been asking for this for a while.
I have resisted because I wanted to find a more general way to
do this, one that would keep the performance of code introducing
variables the same as the performance of code that did not.
(See golang.org/issue/3512#c20).

I have not found the more general way, and recent changes to
remove ambiguously live temporaries have blown away the
property I was trying to preserve, so that's no longer a reason
not to make the change.

Fixes #3512.

LGTM=iant
R=iant
CC=bradfitz, golang-codereviews, khr, r
https://golang.org/cl/83740044

変更の背景

この変更の背景には、Go言語におけるmap[string]へのキーとして[]byteスライスをstring(b)のように文字列に変換して使用する際の、潜在的なパフォーマンス問題がありました。通常、[]byteからstringへの変換は、新しい文字列データのためのメモリ割り当てを伴います。これは、マップルックアップのたびに一時的な文字列オブジェクトが生成され、ガベージコレクションの対象となることを意味します。

Brad Fitzpatrick氏（Goチームの著名なメンバー）は、この最適化を以前から求めていました。コミットの著者であるRuss Cox氏は、より汎用的な最適化方法を見つけたいと考えており、変数を導入するコードとそうでないコードのパフォーマンスを同等に保つことを目指していました（golang.org/issue/3512#c20で言及されています）。しかし、より汎用的な方法が見つからず、また最近のコンパイラの変更（曖昧な生存期間を持つ一時変数の削除）によって、Russ Cox氏が保持しようとしていた特性が失われたため、この特定の最適化を導入する障壁がなくなったと判断されました。

この最適化は、特にネットワークプログラミングやデータ処理など、[]byte形式のデータを頻繁に文字列キーとしてマップに利用するアプリケーションにおいて、ガベージコレクションの頻度と負荷を大幅に軽減し、全体的なパフォーマンスを向上させることを目的としています。

前提知識の解説

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

  1. Goのstring型と[]byte型:

    • Goのstring型は不変（immutable）なバイト列です。一度作成されると内容を変更できません。
    • []byte型は可変（mutable）なバイトスライスです。内容を変更できます。
    • string(b []byte)のような型変換は、通常、bのバイト列をコピーして新しいstringを作成します。これはメモリ割り当てを伴います。

  2. Goのmap（ハッシュマップ）:

    • Goのmapはキーと値のペアを格納するデータ構造です。
    • mapのキーは比較可能（comparable）な型である必要があります。stringは比較可能ですが、[]byteは直接比較可能ではないため、map[[]byte]TのようなマップはGoでは定義できません。
    • mapへのルックアップは、キーのハッシュ値を計算し、そのハッシュ値に基づいて内部のバケットを検索することで行われます。

  3. ガベージコレクション（GC）とメモリ割り当て:

    • Goは自動メモリ管理（ガベージコレクション）を採用しています。
    • プログラムが新しいオブジェクトを生成するたびにメモリが割り当てられます。これらのオブジェクトが不要になると、ガベージコレクタがそれらを回収し、メモリを解放します。
    • 頻繁な小さなメモリ割り当ては、ガベージコレクタの実行頻度を高め、プログラムの実行を一時停止させる（ストップ・ザ・ワールド）原因となり、パフォーマンスに悪影響を与える可能性があります。

  4. Goコンパイラ（cmd/gc）とランタイム（runtime）:

    • cmd/gcはGoの公式コンパイラです。Goのソースコードを機械語に変換する際に、最適化を行います。
    • runtimeはGoプログラムの実行を管理する部分です。ガベージコレクション、スケジューリング、マップ操作などの低レベルな機能を提供します。
    • コンパイラとランタイムは密接に連携しており、コンパイラが特定のランタイム関数を呼び出すコードを生成したり、ランタイムがコンパイラによって生成されたコードの実行をサポートしたりします。

  5. testing.AllocsPerRun:

    • Goの標準ライブラリtestingパッケージに含まれるベンチマークヘルパー関数です。
    • 指定された関数が実行されるたびに発生するメモリ割り当ての平均回数を測定するために使用されます。このコミットでは、最適化が実際にメモリ割り当てを削減したことを検証するために利用されています。

  6. エスケープ解析（Escape Analysis）:

    • コンパイラ最適化の一種で、変数がヒープに割り当てられるべきか（エスケープするか）、スタックに割り当てられるべきか（エスケープしないか）を決定します。
    • スタック割り当てはヒープ割り当てよりも高速で、ガベージコレクションの対象にならないため、パフォーマンス向上に寄与します。
    • このコミットの背景でRuss Cox氏が言及している「曖昧な生存期間を持つ一時変数の削除」は、エスケープ解析に関連するコンパイラの変更を指している可能性があります。

技術的詳細

このコミットの核心は、map[string]Tへのルックアップにおいて、キーがstring([]byte)の形式で与えられた場合に、一時的なstringオブジェクトの生成を回避する最適化です。

従来の動作では、m[string(buf)]のようなコードが実行されると、buf（[]byte）の内容がコピーされて新しいstringが作成され、そのstringがマップルックアップのキーとして使用されていました。この新しいstringは一時的なオブジェクトであり、ルックアップが完了するとガベージコレクションの対象となります。

この最適化では、コンパイラ（cmd/gc）がmapルックアップのコンテキストでstring([]byte)変換を検出した場合、特別なランタイム関数runtime.slicebytetostringtmpを呼び出すようにコードを生成します。

runtime.slicebytetostringtmp関数の特徴は以下の通りです。

  1. メモリ割り当ての回避: この関数は、[]byteスライスの基盤となる配列をコピーせず、その配列を直接参照するstringヘッダ（ポインタと長さ）を作成します。これにより、新しいメモリ割り当てが発生しません。
  2. 一時的な性質: 生成されるstringは「一時的（temporary）」なものとして扱われます。これは、そのstringがマップルックアップのためだけに存在し、ルックアップが完了する前に元の[]byteスライスが変更されたり、他のゴルーチンと同期されたりしないことが保証される場合にのみ安全に使用できることを意味します。コンパイラは、このstringがすぐに使用され、その後破棄されることを知っているため、この最適化を適用できます。
  3. 特定のユースケースに限定: コミットメッセージにもあるように、この最適化は「m[string(k)] where m is a string-keyed map and k is a []byte」という特定のケースに限定されます。これは、[]byteをキーとするマップが存在しないため、このケースが実用上重要であるためです。

この最適化を実現するために、コンパイラとランタイムに以下の変更が加えられました。

  • src/cmd/gc/builtin.c: ランタイムの組み込み関数リストにslicebytetostringtmpが追加されました。
  • src/cmd/gc/go.h: コンパイラの内部表現で、一時的なstring([]byte)変換を表す新しいオペレーションコードOARRAYBYTESTRTMPが追加されました。
  • src/cmd/gc/order.c: コンパイラの順序付けフェーズ（orderstmt、orderexpr）で、mapルックアップの右辺値がOARRAYBYTESTR（通常のstring([]byte)変換）である場合に、それをOARRAYBYTESTRTMPに書き換えるロジックが追加されました。これにより、コンパイラは後続のフェーズでこの特殊なケースを認識できます。
  • src/cmd/gc/runtime.go: slicebytetostringtmp関数のシグネチャがGoコンパイラに認識されるように宣言されました。
  • src/cmd/gc/walk.c: コンパイラのウォークフェーズ（walkexpr）で、OARRAYBYTESTRTMPオペレーションが検出された場合に、runtime.slicebytetostringtmpランタイム関数を呼び出すコードを生成するように変更されました。
  • src/pkg/runtime/string.goc: runtime.slicebytetostringtmp関数の実際のC実装が追加されました。この実装は、[]byteスライスのポインタと長さを直接string構造体に設定することで、メモリコピーを回避します。また、raceenabledの場合にはデータ競合検出のためのracereadrangepc呼び出しも含まれています。
  • src/pkg/runtime/map_test.go: この最適化が実際にメモリ割り当てを削減していることを検証するためのベンチマークテストTestMapStringBytesLookupが追加されました。testing.AllocsPerRunを使用して、string([]byte)変換を伴うマップルックアップが0回のメモリ割り当てで実行されることを確認しています。

この最適化は、Goのコンパイラがコードのセマンティクスを維持しつつ、特定のパターンを認識してより効率的なランタイム関数に置き換える能力を示す良い例です。

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

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

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

    --- a/src/cmd/gc/builtin.c
+++ b/src/cmd/gc/builtin.c
@@ -33,6 +33,7 @@ char *runtimeimport =
 	"func @\".eqstring (? string, ? string) (? bool)\n"
 	"func @\".intstring (? int64) (? string)\n"
 	"func @\".slicebytetostring (? []byte) (? string)\n"
+	"func @\".slicebytetostringtmp (? []byte) (? string)\n"
 	"func @\".slicerunetostring (? []rune) (? string)\n"
 	"func @\".stringtoslicebyte (? string) (? []byte)\n"
 	"func @\".stringtoslicerune (? string) (? []rune)\n"

    runtime.slicebytetostringtmp関数の宣言を追加。

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

    --- a/src/cmd/gc/go.h
+++ b/src/cmd/gc/go.h
@@ -450,6 +450,7 @@ enum
 	OANDAND,	// b0 && b1
 	OAPPEND,	// append
 	OARRAYBYTESTR,	// string(bytes)
+	OARRAYBYTESTRTMP, // string(bytes) ephemeral
 	OARRAYRUNESTR,	// string(runes)
 	OSTRARRAYBYTE,	// []byte(s)
 	OSTRARRAYRUNE,	// []rune(s)

    新しいコンパイラ内部オペレーションOARRAYBYTESTRTMPを追加。

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

    --- a/src/cmd/gc/order.c
+++ b/src/cmd/gc/order.c
@@ -565,9 +565,13 @@ orderstmt(Node *n, Order *order)
 		// and make sure OINDEXMAP is not copied out.
 		t = marktemp(order);
 		orderexprlist(n->list, order);
-		orderexpr(&n->rlist->n->left, order);
-		orderexpr(&n->rlist->n->right, order);
-		orderaddrtemp(&n->rlist->n->right, order);
+		r = n->rlist->n;
+		orderexpr(&r->left, order);
+		orderexpr(&r->right, order);
+		// See case OINDEXMAP below.
+		if(r->right->op == OARRAYBYTESTR)
+			r->right->op = OARRAYBYTESTRTMP;
+		orderaddrtemp(&r->right, order);
 		ordermapassign(n, order);
 		cleantemp(t, order);
 		break;
@@ -935,6 +939,20 @@ orderexpr(Node **np, Order *order)
 		// key must be addressable
 		orderexpr(&n->left, order);
 		orderexpr(&n->right, order);
+
+		// For x = m[string(k)] where k is []byte, the allocation of
+		// backing bytes for the string can be avoided by reusing
+		// the []byte backing array. This is a special case that it
+		// would be nice to handle more generally, but because
+		// there are no []byte-keyed maps, this specific case comes
+		// up in important cases in practice. See issue 3512.
+		// Nothing can change the []byte we are not copying before
+		// the map index, because the map access is going to
+		// be forced to happen immediately following this
+		// conversion (by the ordercopyexpr a few lines below).
+		if(n->etype == 0 && n->right->op == OARRAYBYTESTR)
+			n->right->op = OARRAYBYTESTRTMP;
+
 		orderaddrtemp(&n->right, order);
 		if(n->etype == 0) {
 			// use of value (not being assigned);

    mapルックアップのコンテキストでstring([]byte)変換（OARRAYBYTESTR）をOARRAYBYTESTRTMPに変換するロジックを追加。

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

    --- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -1316,6 +1316,11 @@ walkexpr(Node **np, NodeList **init)
 		n = mkcall("slicebytetostring", n->type, init, n->left);
 		goto ret;
 
+	case OARRAYBYTESTRTMP:
+		// slicebytetostringtmp([]byte) string;
+		n = mkcall("slicebytetostringtmp", n->type, init, n->left);
+		goto ret;
+
 	case OARRAYRUNESTR:
 		// slicerunetostring([]rune) string;
 		n = mkcall("slicerunetostring", n->type, init, n->left);

    OARRAYBYTESTRTMPオペレーションをruntime.slicebytetostringtmp関数呼び出しに変換するコード生成ロジックを追加。

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

    --- a/src/pkg/runtime/string.goc
+++ b/src/pkg/runtime/string.goc
@@ -294,6 +294,25 @@ func slicebytetostring(b Slice) (s String) {
 	runtime·memmove(s.str, b.array, s.len);
 }
 
+func slicebytetostringtmp(b Slice) (s String) {
+	void *pc;
+
+	if(raceenabled) {
+		pc = runtime·getcallerpc(&b);
+		runtime·racereadrangepc(b.array, b.len, pc, runtime·slicebytetostringtmp);
+	}
+	
+	// Return a "string" referring to the actual []byte bytes.
+	// This is only for use by internal compiler optimizations
+	// that know that the string form will be discarded before
+	// the calling goroutine could possibly modify the original
+	// slice or synchronize with another goroutine.
+	// Today, the only such case is a m[string(k)] lookup where
+	// m is a string-keyed map and k is a []byte.
+	s.str = b.array;
+	s.len = b.len;
+}
+
 func stringtoslicebyte(s String) (b Slice) {
 	uintptr cap;

    runtime.slicebytetostringtmp関数のC実装を追加。これはメモリコピーを行わず、元の[]byteのバッキング配列を直接参照するstringを作成します。

  6. src/pkg/runtime/map_test.go:

    --- a/src/pkg/runtime/map_test.go
+++ b/src/pkg/runtime/map_test.go
@@ -438,3 +438,40 @@ func TestMapIterOrder(t *testing.T) {
  	}
  }
 +\n+func TestMapStringBytesLookup(t *testing.T) {
+\t// Use large string keys to avoid small-allocation coalescing,
+\t// which can cause AllocsPerRun to report lower counts than it should.
+\tm := map[string]int{
+\t\t"1000000000000000000000000000000000000000000000000": 1,
+\t\t"2000000000000000000000000000000000000000000000000": 2,
+\t}
+\tbuf := []byte("1000000000000000000000000000000000000000000000000")
+\tif x := m[string(buf)]; x != 1 {
+\t\tt.Errorf(`m[string([]byte("1"))] = %d, want 1`, x)
+\t}\n+\tbuf[0] = '2'
+\tif x := m[string(buf)]; x != 2 {
+\t\tt.Errorf(`m[string([]byte("2"))] = %d, want 2`, x)
+\t}\n+\n+\tvar x int
+\tn := testing.AllocsPerRun(100, func() {
+\t\tx += m[string(buf)]
+\t})\n+\tif n != 0 {
+\t\tt.Errorf("AllocsPerRun for m[string(buf)] = %v, want 0", n)
+\t}\n+\n+\tx = 0
+\tn = testing.AllocsPerRun(100, func() {
+\t\ty, ok := m[string(buf)]
+\t\tif !ok {
+\t\t\tpanic("!ok")
+\t\t}\n+\t\tx += y
+\t})\n+\tif n != 0 {
+\t\tt.Errorf("AllocsPerRun for x,ok = m[string(buf)] = %v, want 0", n)
+\t}\n+}

    最適化の有効性を検証するためのベンチマークテストTestMapStringBytesLookupを追加。

コアとなるコードの解説

  • src/cmd/gc/builtin.c と src/cmd/gc/go.h の変更: これらはコンパイラが新しいランタイム関数slicebytetostringtmpと、それに対応する内部オペレーションOARRAYBYTESTRTMPを認識できるようにするための定義です。コンパイラがコードを解析し、最適化を適用する際にこれらのシンボルが必要になります。

  • src/cmd/gc/order.c の変更: このファイルはコンパイラの「順序付け（ordering）」フェーズを担当します。ここでは、式の評価順序を決定し、一時変数を導入するなどの変換を行います。 追加されたロジックは、mapのインデックス操作（OINDEXMAP）の右辺値がstring([]byte)変換（OARRAYBYTESTR）である場合に、そのオペレーションをOARRAYBYTESTRTMPに書き換えます。これは、コンパイラがこの特定のパターンを認識し、後続のフェーズで特別な処理を適用するための「マーク付け」のようなものです。 コメントにあるように、「Nothing can change the []byte we are not copying before the map index, because the map access is going to be forced to happen immediately following this conversion」という保証があるため、この一時的な文字列参照が安全に使用できると判断されます。

  • src/cmd/gc/walk.c の変更: このファイルはコンパイラの「ウォーク（walking）」フェーズを担当します。ここでは、抽象構文木（AST）を走査し、高レベルなGoの操作を低レベルなランタイム関数呼び出しに変換します。 OARRAYBYTESTRTMPオペレーションが検出されると、通常のslicebytetostringではなく、新しく導入されたslicebytetostringtmpランタイム関数を呼び出すコードを生成するように変更されています。これにより、メモリ割り当てを伴わない文字列変換が実現されます。

  • src/pkg/runtime/string.goc の変更: このファイルはGoランタイムの文字列関連の低レベルなCコードを含んでいます。 slicebytetostringtmp関数の実装が追加されています。この関数は、引数として受け取った[]byteスライスbの基盤となるデータポインタ（b.array）と長さ（b.len）を、新しいstring構造体sの対応するフィールド（s.strとs.len）に直接コピーします。これにより、バイト列の実際のコピーは行われず、メモリ割り当てが回避されます。 raceenabled（データ競合検出が有効な場合）のチェックも含まれており、racereadrangepcを呼び出して、この一時的な文字列参照がデータ競合を引き起こさないことを保証します。

  • src/pkg/runtime/map_test.go の変更: このテストは、最適化が正しく機能していることを検証するためのものです。 testing.AllocsPerRunを使用して、map[string]intへのルックアップでstring([]byte)変換を使用した場合のメモリ割り当て回数を測定しています。最適化が成功していれば、この操作は0回のメモリ割り当てで実行されるはずです。これにより、ガベージコレクションの負荷が軽減されることが実証されます。

これらの変更が連携することで、特定のmapルックアップパターンにおいて、コンパイラが賢く動作し、不要なメモリ割り当てを排除してパフォーマンスを向上させています。

関連リンク

  • Go Issue 3512: https://github.com/golang/go/issues/3512 このコミットが修正したGoのイシューです。map[string]ルックアップにおける[]byteキーからの最適化に関する議論が含まれています。
  • Go Code Review 83740044: https://golang.org/cl/83740044 このコミットに対応するGoのコードレビューページです。変更の詳細な議論やレビューコメントが含まれています。

参考にした情報源リンク