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

このコミットは、Goランタイムにおけるバイトスライスのappend操作のパフォーマンス改善を目的としています。特に、小さなバイト列の追加（append）において、既存のmemmove関数を使用する代わりに、より効率的な手動コピーロジックを導入することで、オーバーヘッドを削減し、パフォーマンスを向上させています。

コミット

commit 8cfed59941655f6a77af065f0196dff6450f52a7
Author: Rob Pike <r@golang.org>
Date:   Fri Mar 1 14:31:26 2013 -0800

    runtime: special-case small byte appends.
    Update #3679.
    
    BenchmarkAppend1Byte            484          199  -58.88%
    BenchmarkAppend4Bytes           829          286  -65.50%
    BenchmarkAppend8Bytes           484          365  -24.59%
    BenchmarkAppend16Bytes          484          498   +2.89%
    BenchmarkAppend32Bytes          486          484   -0.41%
    
    R=iant, dave, rsc
    CC=golang-dev
    https://golang.org/cl/7443047

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

https://github.com/golang/go/commit/8cfed59941655f6a77af065f0196dff6450f52a7

元コミット内容

このコミットの元のメッセージは以下の通りです。

runtime: special-case small byte appends.
Update #3679.

BenchmarkAppend1Byte            484          199  -58.88%
BenchmarkAppend4Bytes           829          286  -65.50%
BenchmarkAppend8Bytes           484          365  -24.59%
BenchmarkAppend16Bytes          484          498   +2.89%
BenchmarkAppend32Bytes          486          484   -0.41%

R=iant, dave, rsc
CC=golang-dev
https://golang.org/cl/7443047

このメッセージは、小さなバイト列の追加を特別扱いすることで、ランタイムのパフォーマンスを改善したことを示しています。ベンチマーク結果も併記されており、特に1バイト、4バイト、8バイトの追加において顕著なパフォーマンス向上が見られます。

変更の背景

Go言語の組み込み関数であるappendは、スライスに要素を追加するために広く使われます。特にバイトスライス（[]byte）は、ネットワークI/O、ファイル操作、文字列処理など、様々な場面で頻繁に利用されます。

従来のappendの実装では、要素のコピーにmemmoveのような汎用的なメモリ移動関数が使用されていました。memmoveは、任意のサイズのメモリブロックを効率的に移動するために最適化されていますが、非常に小さなサイズのコピー（例えば1バイトや数バイト）の場合、関数呼び出しのオーバーヘッドや、memmove内部の複雑なロジック（アライメント、キャッシュライン最適化など）が、実際のデータコピーにかかる時間よりも大きくなる可能性があります。

このコミットの背景には、Go issue #3679が存在します。このissueでは、特に小さなバイトスライスへのappend操作が遅いというパフォーマンス上の問題が指摘されていました。例えば、bytes.Bufferのような型で頻繁に1バイトずつデータを追加するようなシナリオでは、このオーバーヘッドが累積し、アプリケーション全体のパフォーマンスに影響を与える可能性がありました。

この問題に対処するため、開発チームは、小さなバイト列の追加に特化した最適化を導入することを決定しました。これにより、memmoveのオーバーヘッドを回避し、より直接的なバイトコピーを行うことで、パフォーマンスのボトルネックを解消しようとしました。

前提知識の解説

このコミットを理解するためには、以下のGo言語およびシステムプログラミングの概念を理解しておく必要があります。

1. Goスライス (Slice): Goのスライスは、配列のセグメントを参照するデータ構造です。内部的には、ポインタ（基底配列の先頭要素へのポインタ）、長さ（len）、容量（cap）の3つの要素で構成されます。

   • len: スライスに含まれる要素の数。
   • cap: スライスが参照する基底配列の容量。スライスが再割り当てなしで保持できる最大要素数。 append関数は、スライスの容量が足りない場合、より大きな基底配列を新しく割り当て、既存の要素を新しい配列にコピーしてから新しい要素を追加します。容量が足りている場合は、既存の基底配列の末尾に直接要素を追加します。

2. append関数: Goの組み込み関数appendは、スライスに要素を追加します。そのシグネチャはappend(s []T, elems ...T) []Tのようになります。内部的には、ランタイムのruntime·appendslice（または関連する関数）が呼び出されます。

3. memmove関数: memmoveは、C言語の標準ライブラリ関数であり、メモリブロックをコピーするために使用されます。memcpyと異なり、memmoveはコピー元とコピー先のメモリ領域がオーバーラップしている場合でも正しく動作することを保証します。これは、append操作において、既存のスライスデータと追加されるデータが同じ基底配列内でオーバーラップする可能性があるため重要です。memmoveは通常、アセンブリ言語で高度に最適化されており、CPUのSIMD命令（SSE, AVXなど）やキャッシュ最適化を利用して高速なコピーを実現します。

4. Goランタイム (Runtime): Goランタイムは、Goプログラムの実行を管理するシステムです。ガベージコレクション、スケジューリング、メモリ管理、プリミティブな操作（スライス操作、マップ操作など）の実装など、Goプログラムの低レベルな動作を司ります。src/pkg/runtimeディレクトリには、これらのランタイムのC（またはGoアセンブリ）コードが含まれています。

5. ベンチマーク (Benchmark): Goには、go test -bench=.コマンドで実行できる組み込みのベンチマーク機能があります。ベンチマークは、特定のコードのパフォーマンスを測定するために使用され、通常は操作あたりの時間（ns/op）や、操作あたりのメモリ割り当て（B/op）、割り当て回数（allocs/op）などを報告します。このコミットメッセージに記載されているベンチマーク結果は、変更前と変更後のパフォーマンスを比較したものです。

技術的詳細

このコミットの核心は、src/pkg/runtime/slice.cファイル内のruntime·appendslice関数の変更にあります。この関数は、Goのappend組み込み関数が内部的に呼び出すランタイム関数であり、スライスに別のスライス（または可変引数）の要素を追加するロジックを処理します。

変更前は、追加される要素のコピーに一律でruntime·memmoveが使用されていました。

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

ここで、ret.array + ret.len*wはコピー先のメモリ開始アドレス（既存スライスの末尾）、y.arrayはコピー元のメモリ開始アドレス（追加されるスライスの先頭）、y.len*wはコピーするバイト数（追加される要素数 * 要素サイズ）です。

このコミットでは、このruntime·memmoveの呼び出しを、コピーするバイト数（w、つまりy.len * t->elem->size）に基づいて条件分岐させるように変更しました。

// 変更後の一部
p = ret.array+ret.len*w; // コピー先アドレス
q = y.array;             // コピー元アドレス
w *= y.len;              // コピーするバイト数

// TODO: make 16 an architecture-dependent constant.
if(w <= 16) { // 16 empirically tested as approximate crossover on amd64.
    if(p <= q || w <= p-q) { // No overlap.
        while(w-- > 0)
            *p++ = *q++;
    } else { // Overlap. Copy backwards.
        p += w;
        q += w;
        while(w-- > 0)
            *--p = *--q;
    }
} else {
    runtime·memmove(p, q, w);
}

この変更のポイントは以下の通りです。

1. 閾値の導入: コピーするバイト数wが16バイト以下の場合に、特別な処理を行うようにしています。コメントにあるように、この「16」という値は、amd64アーキテクチャ上で経験的に最適なクロスオーバーポイント（memmoveよりも手動コピーが速くなる境界）としてテストされたものです。これは、小さなコピーではmemmoveのセットアップコストや内部ロジックが相対的に大きくなるためです。

2. 手動コピーの導入:

   • 非オーバーラップケース: p <= q || w <= p-qという条件は、コピー元とコピー先のメモリ領域がオーバーラップしていない、またはオーバーラップしていても前方コピーで問題ないケースを判定します。この場合、while(w-- > 0) *p++ = *q++;というシンプルなループで、バイトを先頭から順にコピーします。これは最も直接的で効率的なバイトコピー方法です。
   • オーバーラップケース: elseブロックは、コピー元とコピー先がオーバーラップしており、かつ前方コピーではデータが破壊される可能性があるケース（例えば、append(x[1:], x...)のように、コピー元がコピー先よりも後方にある場合）を処理します。この場合、p += w; q += w; while(w-- > 0) *--p = *--q;というループで、バイトを末尾から逆順にコピーします。これにより、データが破壊されることなく正しくコピーされます。これはmemmoveが内部的に行うオーバーラップ処理と同様のロジックです。

3. memmoveの継続利用: 16バイトを超える大きなコピーの場合、引き続きruntime·memmoveを使用します。これは、memmoveが大きなメモリブロックのコピーにおいて、CPUの最適化された命令セット（SIMDなど）を最大限に活用できるため、手動ループよりも高速であるためです。

この最適化により、特に頻繁に発生する小さなバイト列のappend操作（例: bytes.Buffer.WriteByteなど）のパフォーマンスが大幅に向上しました。

また、src/pkg/runtime/append_test.goには、この最適化の効果を測定するための新しいベンチマーク関数が追加されています。BenchmarkAppend1ByteからBenchmarkAppend32Bytesまでの関数は、それぞれ1バイト、4バイト、8バイト、16バイト、32バイトの追加操作のパフォーマンスを測定します。これらのベンチマーク結果がコミットメッセージに記載されており、最適化の有効性を示しています。

さらに、TestAppendOverlapという新しいテストケースも追加されています。これは、append(x[1:], x...)のように、コピー元とコピー先がオーバーラップする特殊なケースが正しく処理されることを確認するためのものです。このテストは、手動コピーロジックがmemmoveと同様にオーバーラップを正しく扱えることを保証します。

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

主要な変更はsrc/pkg/runtime/slice.cファイル内のruntime·appendslice関数です。

--- a/src/pkg/runtime/slice.c
+++ b/src/pkg/runtime/slice.c
@@ -79,6 +79,7 @@ runtime·appendslice(SliceType *t, Slice x, Slice y, Slice ret)
  intgo m;
  uintptr w;
  void *pc;
+ uintptr *p, *q; // 変更: p, q の型を uint8* から uintptr* に変更 (これはコミットメッセージのdiffと異なるが、実際のコードではuint8*が正しい)

  m = x.len+y.len;
  w = t->elem->size;
@@ -104,7 +105,25 @@ runtime·appendslice(SliceType *t, Slice x, Slice y, Slice ret)
  runtime·racewriterangepc(ret.array+ret.len*w, y.len*w, w, pc, runtime·appendslice);
  }

- runtime·memmove(ret.array + ret.len*w, y.array, y.len*w);
+ // A very common case is appending bytes. Small appends can avoid the overhead of memmove.
+ // We can generalize a bit here, and just pick small-sized appends.
+ p = ret.array+ret.len*w; // コピー先アドレス
+ q = y.array;             // コピー元アドレス
+ w *= y.len;              // コピーするバイト数
+ // TODO: make 16 an architecture-dependent constant.
+ if(w <= 16) { // 16 empirically tested as approximate crossover on amd64.
+  if(p <= q || w <= p-q) { // No overlap.
+   while(w-- > 0)
+    *p++ = *q++;
+  } else { // Overlap. Copy backwards.
+   p += w;
+   q += w;
+   while(w-- > 0)
+    *--p = *--q;
+  }
+ } else {
+  runtime·memmove(p, q, w);
+ }
  ret.len += y.len;
  FLUSH(&ret);
 }
@@ -121,7 +140,7 @@ runtime·appendstr(SliceType *t, Slice x, String y, Slice ret)
  m = x.len+y.len;

  if(m < x.len)
-  runtime·throw("append: slice overflow");
+  runtime·throw("append: string overflow"); // 変更: エラーメッセージの修正

  if(m > x.cap)
  growslice1(t, x, m, &ret);

また、src/pkg/runtime/append_test.goには、新しいベンチマークとテストケースが追加されています。

--- a/src/pkg/runtime/append_test.go
+++ b/src/pkg/runtime/append_test.go
@@ -19,6 +19,39 @@ func BenchmarkAppend(b *testing.B) {
  }
 }

+func benchmarkAppendBytes(b *testing.B, length int) {
+ b.StopTimer()
+ x := make([]byte, 0, N)
+ y := make([]byte, length)
+ b.StartTimer()
+ for i := 0; i < b.N; i++ {
+  x = x[0:0]
+  for j := 0; j < N; j++ {
+   x = append(x, y...)
+  }
+ }
+}
+
+func BenchmarkAppend1Byte(b *testing.B) {
+ benchmarkAppendBytes(b, 1)
+}
+
+func BenchmarkAppend4Bytes(b *testing.B) {
+ benchmarkAppendBytes(b, 4)
+}
+
+func BenchmarkAppend8Bytes(b *testing.B) {
+ benchmarkAppendBytes(b, 8)
+}
+
+func BenchmarkAppend16Bytes(b *testing.B) {
+ benchmarkAppendBytes(b, 16)
+}
+
+func BenchmarkAppend32Bytes(b *testing.B) {
+ benchmarkAppendBytes(b, 32)
+}
+
 func BenchmarkAppendSpecialCase(b *testing.B) {
  b.StopTimer()
  x := make([]int, 0, N)
@@ -50,3 +83,13 @@ func TestSideEffectOrder(t *testing.T) {
  t.Error("append failed: ", x[0], x[1])
  }
 }
+
+func TestAppendOverlap(t *testing.T) {
+ x := []byte("1234")
+ x = append(x[1:], x...) // p > q in runtime·appendslice.
+ got := string(x)
+ want := "2341234"
+ if got != want {
+  t.Errorf("overlap failed: got %q want %q", got, want)
+ }
+}

コアとなるコードの解説

runtime·appendslice関数は、Goのappend組み込み関数の内部実装です。この関数は、スライスxにスライスyの要素を追加し、結果をretスライスに格納します。

変更の核心は、追加されるデータのサイズw（バイト単位）が16バイト以下の場合に、runtime·memmoveの代わりに手動でバイトコピーを行うロジックです。

1. ポインタの初期化: p = ret.array+ret.len*w; は、コピー先の開始アドレスを計算します。これは、既存のretスライスの現在の長さの直後、つまり新しい要素が追加されるべき位置です。 q = y.array; は、コピー元の開始アドレスを計算します。これは、追加されるスライスyの先頭です。 w *= y.len; は、コピーする合計バイト数を計算します。これは、追加される要素の数（y.len）に各要素のサイズ（t->elem->size、これはwに初期化されている）を掛けたものです。

2. サイズによる条件分岐: if(w <= 16): ここで、コピーするバイト数が16バイト以下であるかをチェックします。この16バイトという閾値は、memmoveの関数呼び出しオーバーヘッドや内部ロジックの複雑さを考慮し、経験的に決定されたものです。小さなコピーでは、memmoveの汎用性が逆にオーバーヘッドとなるため、よりシンプルな手動コピーが有利になります。

3. オーバーラップの検出と処理: if(p <= q || w <= p-q): この条件は、コピー元とコピー先のメモリ領域がオーバーラップしているかどうか、そしてオーバーラップしている場合に前方コピーで安全かどうかを判断します。

   • p <= q: コピー先アドレスpがコピー元アドレスq以下である場合、つまりコピー先がコピー元と同じかそれよりも前にある場合、前方コピー（*p++ = *q++;）は安全です。

   • w <= p-q: コピーするバイト数wが、コピー先アドレスpとコピー元アドレスqの差（p-q）以下である場合、これも前方コピーで安全です。これは、コピー元がコピー先よりも後方にあるが、コピーするデータがコピー元を上書きする前にコピーが完了するため、オーバーラップによる破壊が発生しないケースです。

   • 非オーバーラップ/安全な前方コピー: 上記の条件が真の場合、while(w-- > 0) *p++ = *q++;というループで、qからpへバイトを1つずつコピーし、ポインタをインクリメントします。これは最も直接的なバイトコピーです。

   • オーバーラップ/後方コピーが必要なケース: elseブロックに入った場合、コピー元とコピー先がオーバーラップしており、かつ前方コピーではデータが破壊される可能性があることを意味します（例: q < p < q + w）。この場合、p += w; q += w;でポインタをコピーするブロックの末尾に移動させ、while(w-- > 0) *--p = *--q;というループで、末尾から先頭に向かってバイトを1つずつコピーし、ポインタをデクリメントします。これにより、データが破壊されることなく正しくコピーされます。

4. memmoveの利用: else { runtime·memmove(p, q, w); }：コピーするバイト数が16バイトを超える場合、引き続きruntime·memmoveが使用されます。これは、memmoveが大きなメモリブロックのコピーにおいて、CPUの最適化された命令セット（SIMDなど）を最大限に活用できるため、手動ループよりも高速であるためです。

この変更により、特に小さなバイト列のappend操作において、memmoveの呼び出しオーバーヘッドと複雑な内部ロジックを回避し、より効率的なバイトコピーパスを提供することで、パフォーマンスが大幅に向上しました。コミットメッセージのベンチマーク結果がこの効果を明確に示しています。

関連リンク

• Go issue #3679: https://github.com/golang/go/issues/3679 (このコミットが解決した問題のトラッキング)
• Go CL 7443047: https://golang.org/cl/7443047 (このコミットのGerritコードレビューページ)

参考にした情報源リンク

• Go言語の公式ドキュメント: スライス (https://go.dev/blog/slices-intro)
• memmove関数のドキュメントや解説 (例: man memmove、C言語の標準ライブラリに関する資料)
• Goランタイムのソースコード (src/runtime/slice.go, src/runtime/memmove_*.sなど)
• Goのベンチマークに関するドキュメント (https://go.dev/doc/articles/go_benchmarking.html)
• Goのbytes.Bufferの内部実装 (頻繁にappendが使われる例として)
• Goのissueトラッカー (https://github.com/golang/go/issues)
• GoのGerritコードレビューシステム (https://go.googlesource.com/go/+/refs/heads/master)