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

このコミットは、Goランタイムにおける append([]byte, string) 操作のパフォーマンス改善を目的としています。具体的には、短い文字列をバイトスライスに追加する際の処理を最適化し、特定のサイズ以下の文字列に対しては memmove のような汎用的なメモリコピー関数ではなく、よりシンプルなバイトごとのコピーを行うように変更しています。これにより、特に1バイトや4バイトといった非常に短い文字列の追加において、大幅なパフォーマンス向上が見られます。また、この最適化の境界となる「クロスオーバーポイント」をアーキテクチャ依存の定数として定義し、将来的な調整を容易にしています。

コミット

commit f235d5d8d702778c7d16e573c855519a8238951c
Author: Rob Pike <r@golang.org>
Date:   Fri Mar 1 16:41:39 2013 -0800

    runtime: special-case append([]byte, string) for small strings
    Also make the crossover point an architecture-dependent constant,
    although it's the same everywhere for now.
    
    BenchmarkAppendStr1Byte            416          145  -65.14%
    BenchmarkAppendStr4Bytes           743          217  -70.79%
    BenchmarkAppendStr8Bytes           421          270  -35.87%
    BenchmarkAppendStr16Bytes          415          403   -2.89%
    BenchmarkAppendStr32Bytes          415          391   -5.78%
    
    R=golang-dev, iant
    CC=golang-dev
    https://golang.org/cl/7459044

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

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

元コミット内容

runtime: special-case append([]byte, string) for small strings
Also make the crossover point an architecture-dependent constant,
although it's the same everywhere for now.

BenchmarkAppendStr1Byte            416          145  -65.14%
BenchmarkAppendStr4Bytes           743          217  -70.79%
BenchmarkAppendStr8Bytes           421          270  -35.87%
BenchmarkAppendStr16Bytes          415          403   -2.89%
BenchmarkAppendStr32Bytes          415          391   -5.78%

R=golang-dev, iant
CC=golang-dev
https://golang.org/cl/7459044

変更の背景

Go言語の append 関数は、スライスに要素を追加するための基本的な操作です。特に []byte スライスに string を追加する操作は、文字列処理やI/O処理において頻繁に利用されます。このような基本的な操作のパフォーマンスは、Goプログラム全体の実行速度に大きな影響を与えます。

従来の append([]byte, string) の実装では、文字列の内容をバイトスライスにコピーするために runtime·memmove という汎用的なメモリコピー関数が使用されていました。memmove は任意のサイズのメモリブロックを効率的にコピーするために高度に最適化されていますが、非常に小さなサイズのコピーにおいては、関数の呼び出しオーバーヘッドや内部の複雑なロジックが、実際のデータコピーにかかる時間よりも支配的になることがあります。

コミットメッセージに含まれるベンチマーク結果は、この問題点を明確に示しています。

• BenchmarkAppendStr1Byte: 1バイト文字列の追加で65.14%の改善
• BenchmarkAppendStr4Bytes: 4バイト文字列の追加で70.79%の改善
• BenchmarkAppendStr8Bytes: 8バイト文字列の追加で35.87%の改善
• BenchmarkAppendStr16Bytes: 16バイト文字列の追加で2.89%の改善
• BenchmarkAppendStr32Bytes: 32バイト文字列の追加で5.78%の改善

これらの結果から、特に1バイトや4バイトといった非常に短い文字列の追加において、memmove のオーバーヘッドが顕著であり、これを回避することで大幅なパフォーマンス向上が期待できることが分かります。このコミットは、このパフォーマンスボトルネックを解消し、Goプログラムの全体的な効率を高めることを目的としています。

前提知識の解説

Go言語のスライスと文字列

• スライス ([]T): Goのスライスは、配列のセグメントを参照するデータ構造です。内部的には、要素へのポインタ、長さ (len)、容量 (cap) の3つのフィールドを持ちます。スライスは動的なサイズ変更が可能であり、append 関数を使って要素を追加すると、必要に応じて基盤となる配列が拡張されます。
• 文字列 (string): Goの文字列は不変なバイトのシーケンスです。内部的には、バイトデータへのポインタと長さの2つのフィールドを持ちます。Goの文字列はUTF-8エンコードされたテキストを扱うことが一般的ですが、バイトのシーケンスとして扱われるため、[]byte との間で変換が可能です。

append 関数

Goの組み込み関数 append は、スライスに要素を追加するために使用されます。 newSlice = append(oldSlice, elements...) append は、oldSlice の容量が不足している場合、より大きな新しい基盤配列を割り当て、既存の要素と新しい要素をコピーして新しいスライスを返します。容量が十分な場合は、既存の基盤配列の末尾に要素を追加し、スライスの長さを更新します。

memmove とメモリコピーの最適化

• memmove: memmove は、C言語の標準ライブラリ関数であり、メモリブロックをコピーするために使用されます。Goのランタイム内部でも、大きなデータ構造のコピーやスライス操作などで頻繁に利用されます。memmove は、コピー元とコピー先のメモリ領域が重なっている場合でも正しく動作するように設計されており、非常に高度に最適化されたアセンブリコードで実装されていることが多いです。
• 最適化の「クロスオーバーポイント」: ソフトウェアのパフォーマンス最適化において、「クロスオーバーポイント」という概念は非常に重要です。これは、あるタスクを実行するための複数のアルゴリズムや実装が存在する場合に、入力サイズが特定の閾値を超えると、ある実装が別の実装よりも効率的になる境界点を指します。
  • 例えば、小さなデータに対してはシンプルなループによるバイトごとのコピーが高速である一方、大きなデータに対しては memmove のような高度に最適化されたブロックコピーが高速である、といったケースが考えられます。
  • このコミットでは、append([]byte, string) において、文字列の長さがこのクロスオーバーポイント（ここでは appendCrossover）以下の場合には、memmove の代わりにバイトごとのコピーを行うことで、オーバーヘッドを削減しパフォーマンスを向上させています。

Goランタイムのアーキテクチャ依存定数

Goのランタイムは、異なるCPUアーキテクチャ（例: 386, amd64, arm）に対応するために、アーキテクチャ固有の定数や関数を持つことがあります。これらは通常、src/pkg/runtime/arch_*.h のようなファイルで定義されます。このコミットでは、appendCrossover をこのようなアーキテクチャ依存の定数として導入することで、将来的に特定のアーキテクチャで異なる最適なクロスオーバーポイントが見つかった場合に、容易に調整できるようにしています。

技術的詳細

このコミットの主要な変更点は、src/pkg/runtime/slice.c 内の runtime·appendstr 関数における文字列コピーのロジックです。

runtime·appendstr 関数は、append([]byte, string) の内部実装を担っています。変更前は、文字列の内容をバイトスライスにコピーする際に、常に runtime·memmove を使用していました。

// 変更前 (slice.c)
runtime·memmove(ret.array + ret.len, y.str, y.len);

このコミットでは、この部分に条件分岐が追加され、コピーする文字列の長さ (w) が appendCrossover という定数以下の場合には、memmove を呼び出す代わりに、シンプルな while ループによるバイトごとのコピーを行うように変更されました。

// 変更後 (slice.c)
w = y.len;
p = ret.array+ret.len;
q = y.str;
if(w <= appendCrossover) {
    while(w-- > 0)
        *p++ = *q++;
} else {
    runtime·memmove(p, q, w);
}

appendCrossover 定数

appendCrossover は、各アーキテクチャのヘッダーファイル (src/pkg/runtime/arch_386.h, src/pkg/runtime/arch_amd64.h, src/pkg/runtime/arch_arm.h) で定義されています。このコミットの時点では、すべてのアーキテクチャで 16 に設定されています。

// arch_386.h, arch_amd64.h, arch_arm.h (変更後)
enum {
    thechar = 'X', // '8', '6', '5' for 386, amd64, arm respectively
    BigEndian = 0,
    CacheLineSize = 64, // 32 for arm
    appendCrossover = 16 // 新しく追加された定数
};

これは、16バイト以下の文字列のコピーにはバイトごとのループが、16バイトを超える文字列のコピーには runtime·memmove が使用されることを意味します。コミットメッセージのベンチマーク結果が示すように、この 16 という値は、特に短い文字列のパフォーマンスを大幅に改善する上で効果的なクロスオーバーポイントとして経験的に決定されたものです。

runtime·appendslice の変更

src/pkg/runtime/slice.c の runtime·appendslice 関数にも同様の変更が加えられています。この関数は、スライスを別のスライスに追加する際の内部実装を担っています。以前はハードコードされた 16 という値で条件分岐していましたが、これも appendCrossover 定数を使用するように変更されました。

// 変更前 (slice.c)
// TODO: make 16 an architecture-dependent constant.
if(w <= 16) { // 16 empirically tested as approximate crossover on amd64.
    // ...
}

// 変更後 (slice.c)
if(w <= appendCrossover) {
    // ...
}

これにより、スライス追加操作における小さなコピーの最適化も、appendCrossover 定数によって一元的に管理されるようになります。

ベンチマークの追加

src/pkg/runtime/append_test.go には、append([]byte, string) のパフォーマンスを測定するための新しいベンチマーク関数が追加されています。これらは、異なる長さの文字列（1バイト、4バイト、8バイト、16バイト、32バイト）を繰り返し追加するシナリオをシミュレートし、最適化の効果を定量的に評価するために使用されます。

// src/pkg/runtime/append_test.go (追加)
func benchmarkAppendStr(b *testing.B, str string) { ... }
func BenchmarkAppendStr1Byte(b *testing.B) { ... }
func BenchmarkAppendStr4Bytes(b *testing.B) { ... }
func BenchmarkAppendStr8Bytes(b *testing.B) { ... }
func BenchmarkAppendStr16Bytes(b *testing.B) { ... }
func BenchmarkAppendStr32Bytes(b *testing.B) { ... }

これらのベンチマークは、コミットメッセージに記載されているパフォーマンス改善の数値の根拠となっています。

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

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

1. src/pkg/runtime/append_test.go:

   • benchmarkAppendStr 関数とそのバリエーション (BenchmarkAppendStr1Byte など) が追加され、append([]byte, string) のパフォーマンスを測定するための新しいベンチマークが導入されました。

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

   • 各アーキテクチャのヘッダーファイルに appendCrossover = 16 という新しい定数が追加されました。

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

   • runtime·appendslice 関数内のハードコードされた 16 という値が appendCrossover に置き換えられました。
   • runtime·appendstr 関数において、文字列の長さが appendCrossover 以下の場合に runtime·memmove の代わりにバイトごとのコピーを行う条件分岐が追加されました。

コアとなるコードの解説

src/pkg/runtime/append_test.go の変更

// 新しく追加されたベンチマークヘルパー関数
func benchmarkAppendStr(b *testing.B, str string) {
	b.StopTimer() // タイマーを一時停止
	x := make([]byte, 0, N) // 容量Nのバイトスライスを初期化
	b.StartTimer() // タイマーを再開
	for i := 0; i < b.N; i++ {
		x = x[0:0] // スライスをリセット（長さ0にするが、容量は保持）
		for j := 0; j < N; j++ {
			x = append(x, str...) // 指定された文字列を繰り返し追加
		}
	}
}

// 各文字列長に対応するベンチマーク関数
func BenchmarkAppendStr1Byte(b *testing.B) {
	benchmarkAppendStr(b, "1")
}

func BenchmarkAppendStr4Bytes(b *testing.B) {
	benchmarkAppendStr(b, "1234")
}

// ... 他の長さのベンチマーク関数も同様

これらのベンチマークは、append([]byte, string) 操作の実際のパフォーマンスを測定するために設計されています。b.StopTimer() と b.StartTimer() を使用して、スライスの初期化やリセットといったセットアップ時間を測定から除外しています。x = x[0:0] は、スライスの長さを0にリセットしますが、基盤となる配列の容量は保持するため、再割り当てのオーバーヘッドを最小限に抑えつつ、繰り返し append 操作の純粋なコストを測定できます。

src/pkg/runtime/arch_*.h の変更

// 例: src/pkg/runtime/arch_amd64.h
enum {
	thechar = '6',
	BigEndian = 0,
	CacheLineSize = 64,
	appendCrossover = 16 // この行が追加された
};

この変更は、appendCrossover という定数を各アーキテクチャのヘッダーファイルに導入したものです。これにより、append 操作の最適化における「クロスオーバーポイント」が、アーキテクチャ固有の設定として管理されるようになります。現在のところ、すべてのアーキテクチャで 16 に設定されていますが、将来的に特定のアーキテクチャで異なる最適な値が見つかった場合に、この定数を変更するだけで対応できるようになります。

src/pkg/runtime/slice.c の変更

runtime·appendslice 関数の変更

// 変更前: if(w <= 16)
// 変更後: if(w <= appendCrossover)
if(w <= appendCrossover) { // 以前はハードコードされた16だった
	if(p <= q || w <= p-q) // No overlap.
		while(w-- > 0)
			*p++ = *q++;
	else // Overlap.
		runtime·memmove(p, q, w);
} else {
	runtime·memmove(p, q, w);
}

この変更は、runtime·appendslice 関数（スライスをスライスに追加する際の内部処理）において、小さなコピーの最適化の閾値をハードコードされた 16 から、新しく定義された appendCrossover 定数に置き換えたものです。これにより、スライス追加の最適化も一元的に管理されるようになります。

runtime·appendstr 関数の変更

// runtime·appendstr 関数の一部
// ... (前略) ...

// 変更前: runtime·memmove(ret.array + ret.len, y.str, y.len);

// 変更後:
// Small appends can avoid the overhead of memmove.
w = y.len; // コピーするバイト数 (文字列の長さ)
p = ret.array+ret.len; // コピー先のポインタ (スライスの現在の末尾)
q = y.str; // コピー元のポインタ (文字列のデータ)
if(w <= appendCrossover) { // 文字列の長さがクロスオーバーポイント以下の場合
	while(w-- > 0) // バイトごとに手動でコピー
		*p++ = *q++;
} else { // 文字列の長さがクロスオーバーポイントを超える場合
	runtime·memmove(p, q, w); // memmove を使用してブロックコピー
}
ret.len += y.len; // スライスの長さを更新
FLUSH(&ret);

これがこのコミットの最も重要な変更点です。runtime·appendstr 関数は、append([]byte, string) の実際のコピー処理を行います。

• w = y.len; でコピーするバイト数（文字列の長さ）を取得します。
• p はコピー先のバイトスライスの末尾へのポインタ、q はコピー元の文字列データへのポインタです。
• if(w <= appendCrossover) の条件分岐が追加されました。
  • もし文字列の長さ w が appendCrossover (現在のところ16) 以下であれば、while(w-- > 0) *p++ = *q++; というシンプルなループを使って、バイトごとにデータをコピーします。この直接的なバイトコピーは、memmove の呼び出しオーバーヘッドや内部の複雑なロジックを回避できるため、非常に小さなデータサイズではより高速になります。
  • もし文字列の長さ w が appendCrossover を超える場合は、従来通り runtime·memmove(p, q, w); を呼び出して、最適化されたブロックコピーを利用します。これは、大きなデータサイズでは memmove の方が効率的であるためです。

この条件分岐により、Goランタイムは文字列の長さに応じて最適なコピー戦略を選択できるようになり、特に短い文字列の append 操作のパフォーマンスが大幅に向上しました。

関連リンク

• Go言語の append 関数に関する公式ドキュメント: https://pkg.go.dev/builtin#append
• Go言語のスライスに関するブログ記事: https://go.dev/blog/slices
• Go言語の文字列に関するブログ記事: https://go.dev/blog/strings
• Goのランタイムソースコード (GitHub): https://github.com/golang/go/tree/master/src/runtime

参考にした情報源リンク

• コミットメッセージ内のGerrit Change-ID: https://golang.org/cl/7459044 (これはGoのコードレビューシステムへのリンクであり、詳細な議論や変更履歴が含まれている可能性があります。)
• Go言語のソースコード (特に src/pkg/runtime/slice.c, src/pkg/runtime/arch_*.h, src/pkg/runtime/append_test.go)
• 一般的なメモリコピー最適化の概念 (クロスオーバーポイント、memmove の特性など) に関する知識。
• Goのベンチマークの書き方に関する知識。
• GoのランタイムがC言語で実装されている部分があることに関する知識。