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

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

コミット

commit 994f59666f0f79379d3b48bae7c1fb3e2b0f8dc1
Author: Brad Fitzpatrick <bradfitz@golang.org>
Date:   Fri Mar 29 12:39:19 2013 -0700

    bytes: don't grow Buffer if capacity is available
    
    Also added a new benchmark from the same test:
    
    benchmark                           old ns/op    new ns/op    delta
    BenchmarkBufferNotEmptyWriteRead      2643698       709189  -73.17%
    
    Fixes #5154
    
    R=golang-dev, r, gri
    CC=golang-dev
    https://golang.org/cl/8164043

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

https://github.com/golang/go/commit/994f59666f0f79379d3b48bae7c1fb3e2b0f8dc1

元コミット内容

このコミットは、Go言語の標準ライブラリbytesパッケージ内のBuffer型において、既存の容量が利用可能な場合に不要なバッファの再割り当て（grow）を行わないように最適化するものです。これにより、特にWriteとRead操作が頻繁に繰り返されるシナリオでのパフォーマンスが大幅に向上します。

コミットメッセージには、以下の主要な変更点と成果が記載されています。

  • bytes.Bufferの最適化: バッファに十分な容量がある場合、新しいスライスを割り当てる代わりに、既存のデータを先頭にスライドさせることで再利用するように変更。
  • ベンチマークの追加: この最適化の効果を測定するために、BenchmarkBufferNotEmptyWriteReadという新しいベンチマークが追加されました。
  • パフォーマンス改善: 新しいベンチマークの結果として、BenchmarkBufferNotEmptyWriteReadの実行時間が約73.17%削減され、2,643,698 ns/opから709,189 ns/opへと大幅に改善されたことが示されています。
  • 関連Issueの修正: この変更は、GoのIssueトラッカーで報告されていた#5154を修正するものです。

変更の背景

このコミットの背景には、Go言語のbytes.Buffer型が特定の操作パターンにおいて非効率なメモリ割り当てを行っていたという問題があります。具体的には、Bufferがデータを書き込み（Write）し、その後読み込み（Read）してバッファの先頭部分が消費されるというサイクルを繰り返す場合、バッファの論理的な開始位置（b.off）が移動します。しかし、物理的な基盤となるスライス（b.buf）の容量は変わらないため、バッファの先頭に空き領域ができてしまいます。

従来のBufferの実装では、この空き領域が十分に活用されず、新しいデータが書き込まれる際に、たとえ既存の容量が残っていても、バッファが「いっぱい」であると判断して新しい、より大きなスライスを再割り当てしてしまうことがありました。これは、特に大量の小さなWrite/Read操作が繰り返されるような状況で、頻繁なメモリ再割り当てとデータコピーを引き起こし、パフォーマンスのボトルネックとなっていました。

Issue #5154は、この非効率性を具体的に指摘し、Bufferが既存の容量をより賢く利用し、不要な再割り当てを避けるべきであるという提案がなされていました。このコミットは、その問題に対する直接的な解決策として導入されました。

前提知識の解説

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

  1. Goのスライス (Slice):

    • Goのスライスは、配列の一部を参照する軽量なデータ構造です。スライスは「ポインタ（基盤配列の先頭要素への参照）」「長さ（len）」「容量（cap）」の3つの要素で構成されます。
    • lenはスライスが現在保持している要素の数を示し、capは基盤となる配列が保持できる要素の総数を示します。
    • スライスに要素を追加してlenがcapを超えると、Goランタイムはより大きな新しい基盤配列を割り当て、既存の要素を新しい配列にコピーします。この操作はコストが高いです。

  2. bytes.Buffer:

    • bytes.Bufferは、可変長のバイトシーケンスを扱うためのバッファです。io.Reader、io.Writer、io.ByteScanner、io.RuneScannerインターフェースを実装しており、バイトデータの読み書きに非常に便利です。
    • 内部的には、Bufferはバイトスライス（b.buf []byte）と、読み込みオフセット（b.off int）を保持しています。
    • b.bufはバッファの基盤となるストレージです。
    • b.offは、バッファの読み込み可能なデータの開始位置を示します。Read操作が行われるとb.offが増加し、Write操作が行われるとバッファの末尾にデータが追加されます。
    • BufferのLen()メソッドはlen(b.buf) - b.offで計算され、現在読み込み可能なバイト数を示します。
    • BufferのCap()メソッドはcap(b.buf)で計算され、基盤となるスライスの総容量を示します。

  3. Buffer.grow()メソッド:

    • Bufferにデータを書き込む際、現在の容量が不足している場合に呼び出される内部メソッドです。
    • このメソッドの主な目的は、nバイトの追加データを格納するために必要な容量を確保することです。
    • 通常、growは新しいスライスを割り当て、既存のデータをコピーすることで容量を増やします。このコミットの変更はこのgrowメソッド内にあります。

  4. メモリの再利用とスライド (Shifting):

    • スライスにおいて、先頭部分のデータが不要になった場合（例: Readによって消費された場合）、その領域は論理的には空きとなりますが、物理的にはメモリが解放されるわけではありません。
    • この空き領域を再利用する一般的な手法として、「スライド（またはシフト）」があります。これは、有効なデータをスライスの先頭にcopyすることで、先頭の空き領域を詰め、末尾に新しい空き領域を作り出す方法です。これにより、新しいスライスを割り当てることなく、既存の容量を最大限に活用できます。

これらの概念を理解することで、コミットがbytes.Bufferのパフォーマンスをどのように改善したのか、その技術的な詳細を深く掘り下げることができます。

技術的詳細

このコミットの技術的な核心は、bytes.Bufferの内部メソッドであるgrow(n int)のロジック変更にあります。growメソッドは、Bufferにnバイトの新しいデータを書き込むために必要な容量を確保する役割を担っています。

変更前のgrowメソッドは、主に以下の2つのケースを考慮していました。

  1. b.bufがnilの場合（初期状態）。
  2. 既存のb.bufの容量が不足している場合。

後者の場合、growは新しい、より大きなスライスをmakeSliceで割り当て、既存の有効なデータ（b.buf[b.off:]）を新しいスライスにコピーしていました。このプロセスは、たとえcap(b.buf)がlen(b.buf)よりも大きく、バッファの末尾に十分な空き容量がなくても、b.offが0でない限り、常に新しいスライス割り当てとコピーを伴う可能性がありました。

このコミットでは、growメソッドに新しい条件分岐が追加されました。

else if m+n <= cap(b.buf) {
    // We can slide things down instead of
    // allocating a new slice.
    copy(b.buf[:], b.buf[b.off:])
    buf = b.buf[:m]
}

ここで、mは現在の有効なデータ長（len(b.buf) - b.off）です。 この新しい条件は、以下の状況をチェックします。

  • m + n <= cap(b.buf): これは、「現在の有効なデータ長mと、これから書き込むデータ長nの合計が、基盤となるスライスb.bufの総容量cap(b.buf)以下である」ことを意味します。つまり、バッファ全体としては、新しいデータを格納するのに十分な物理的な容量がまだ残っているということです。

この条件が真である場合、以下の最適化が適用されます。

  1. copy(b.buf[:], b.buf[b.off:]):
    • これは、バッファ内の有効なデータ（b.buf[b.off:]）を、基盤となるスライスの先頭（b.buf[:]）にコピーする操作です。
    • これにより、b.offによって生じていた先頭の空き領域が詰められ、有効なデータがスライスの先頭に移動します。
    • 結果として、スライスの末尾に、新しいデータを書き込むための連続した空き領域が確保されます。
  2. buf = b.buf[:m]:
    • b.bufスライスを、有効なデータが移動した後の新しい論理的な長さに再スライスします。これにより、b.bufのlenがmとなり、capは元のcap(b.buf)のまま維持されます。

この変更により、Bufferは、物理的な容量がまだ残っているにもかかわらず、論理的なオフセットのために不要な再割り当てを行うことを避けられるようになりました。代わりに、既存のメモリ領域内でデータをスライドさせることで、メモリ割り当てのオーバーヘッドとデータコピーのコストを大幅に削減します。

この最適化は、特にWriteとReadが交互に、または頻繁に繰り返され、バッファの先頭が消費されることでb.offが頻繁に移動するようなシナリオで絶大な効果を発揮します。ベンチマーク結果が示すように、パフォーマンスが73%以上改善されたのは、この賢いメモリ再利用戦略によるものです。

また、このコミットでは、bytes/buffer_test.goにTestBufferGrowthとBenchmarkBufferNotEmptyWriteReadが追加されています。

  • TestBufferGrowthは、WriteとReadを繰り返した後にバッファの容量が不必要に大きくなっていないことを検証するテストです。これは、Bufferが適切にコンパクト化されているかを確認します。
  • BenchmarkBufferNotEmptyWriteReadは、まさにこの最適化がターゲットとするシナリオ（WriteとReadの繰り返し）をシミュレートし、パフォーマンス改善を定量的に測定するためのものです。

さらに、bytes/export_test.goにBuffer.Cap()メソッドがエクスポートされており、テストコードからBufferの内部容量にアクセスできるようになっています。これは、TestBufferGrowthで容量の検証を行うために必要です。

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

変更は主にsrc/pkg/bytes/buffer.goのgrow関数にあります。

--- a/src/pkg/bytes/buffer.go
+++ b/src/pkg/bytes/buffer.go
@@ -87,6 +87,11 @@ func (b *Buffer) grow(n int) int {
 		var buf []byte
 		if b.buf == nil && n <= len(b.bootstrap) {
 			buf = b.bootstrap[0:]
+		} else if m+n <= cap(b.buf) {
+			// We can slide things down instead of
+			// allocating a new slice.
+			copy(b.buf[:], b.buf[b.off:])
+			buf = b.buf[:m]
 		} else {
 			// not enough space anywhere
 			buf = makeSlice(2*cap(b.buf) + n)

コアとなるコードの解説

上記の差分は、bytes.Bufferのgrowメソッドにおける変更を示しています。

  • 変更前: grow関数は、新しいデータを書き込むために必要な容量nを確保しようとします。 b.buf == nil && n <= len(b.bootstrap)の条件は、バッファがまだ初期化されておらず、かつブートストラップバッファ（小さな固定サイズの内部バッファ）で十分な場合にそれを使用するロジックです。 それ以外のケース（elseブロック）では、常にmakeSliceを呼び出して新しいスライスを割り当て、既存のデータをコピーしていました。これは、たとえcap(b.buf)が十分であっても、b.offが0でないためにバッファの先頭に空き領域がある場合でも、新しい割り当てが発生してしまうことを意味します。

  • 変更後: 新しいelse if m+n <= cap(b.buf)という条件が追加されました。

    • mは、現在のバッファの有効なデータ長（len(b.buf) - b.off）です。
    • m+nは、現在の有効なデータとこれから書き込むデータの合計長です。
    • cap(b.buf)は、基盤となるスライスの総容量です。

    この条件が真である場合、つまり「既存の基盤スライスの容量内に、現在の有効なデータと新しいデータの両方を収めることができる」場合、以下の最適化が行われます。

    1. copy(b.buf[:], b.buf[b.off:]):
      • b.buf[b.off:]は、バッファ内で現在有効なデータ部分（読み込みオフセットb.offから末尾まで）を指します。
      • b.buf[:]は、基盤となるスライス全体の先頭を指します。
      • このcopy操作により、有効なデータがスライスの先頭に移動し、b.offによって生じていた先頭の「読み込み済み」の空き領域が詰められます。これにより、スライスの末尾に連続した空き領域が確保されます。
    2. buf = b.buf[:m]:
      • b.bufを、有効なデータが移動した後の新しい論理的な長さに再スライスします。これにより、len(b.buf)がmとなり、cap(b.buf)は変更されません。
      • このbufは、grow関数が呼び出し元に返す、書き込み可能なスライスの一部となります。

この変更により、Bufferは、物理的な容量がまだ残っているにもかかわらず、論理的なオフセットのために不要なメモリ再割り当てとデータコピーを行うことを避け、既存のメモリ領域を効率的に再利用できるようになりました。これにより、特にWriteとReadが頻繁に繰り返されるシナリオでのパフォーマンスが劇的に向上します。

関連リンク

参考にした情報源リンク

  • Go言語の公式ドキュメント: bytesパッケージ
  • Go言語のソースコード: src/pkg/bytes/buffer.go
  • Go言語のIssueトラッカー: Issue #5154
  • Go言語のコードレビューシステム (Gerrit): CL 8164043
  • Go言語のスライスに関する解説記事 (例: Go Slices: usage and internals)
  • Go言語のベンチマークに関する解説記事