[インデックス 13920] ファイルの概要
このコミットは、Go言語の標準ライブラリであるcompress/flateパッケージ内のデコンプレッサー（解凍器）の構造体から、ヒストリバッファを分離する変更を加えています。具体的には、decompressor構造体内に直接配列として持っていたヒストリバッファhist [maxHist]byteを、ポインタ*[maxHist]byteに変更し、ヒープ上に別途確保するように修正されました。この変更により、デコンプレッサーのパフォーマンスが向上したことがベンチマーク結果で示されています。
コミット
commit 6efa648853c14aec9d01821f9620401173c1c62b
Author: Nigel Tao <nigeltao@golang.org>
Date: Mon Sep 24 17:58:08 2012 +1000
compress/flate: move the history buffer out of the decompressor struct.
I'm not exactly sure why there's a performance gain, but it seems like
an easy win. Maybe it's a cache line thing. Maybe it's that
unsafe.Sizeof(decompressor{}) drops to below unmappedzero, so that
checkref/checkoffset don't need to insert TESTB instructions. Maybe
it's less noise for the conservative garbage collector. Maybe it's
something else.
compress/flate benchmarks:
BenchmarkDecodeDigitsSpeed1e4 378628 349906 -7.59%
BenchmarkDecodeDigitsSpeed1e5 3481976 3204898 -7.96%
BenchmarkDecodeDigitsSpeed1e6 34419500 31750660 -7.75%
BenchmarkDecodeDigitsDefault1e4 362317 335562 -7.38%
BenchmarkDecodeDigitsDefault1e5 3290032 3107624 -5.54%
BenchmarkDecodeDigitsDefault1e6 30542540 28937480 -5.26%
BenchmarkDecodeDigitsCompress1e4 362803 335158 -7.62%
BenchmarkDecodeDigitsCompress1e5 3294512 3114526 -5.46%
BenchmarkDecodeDigitsCompress1e6 30514940 28927090 -5.20%
BenchmarkDecodeTwainSpeed1e4 412818 389521 -5.64%
BenchmarkDecodeTwainSpeed1e5 3475780 3288908 -5.38%
BenchmarkDecodeTwainSpeed1e6 33629640 31931420 -5.05%
BenchmarkDecodeTwainDefault1e4 369736 348850 -5.65%
BenchmarkDecodeTwainDefault1e5 2861050 2721383 -4.88%
BenchmarkDecodeTwainDefault1e6 27120120 25862050 -4.64%\
BenchmarkDecodeTwainCompress1e4 372057 350822 -5.71%
BenchmarkDecodeTwainCompress1e5 2855109 2718664 -4.78%
BenchmarkDecodeTwainCompress1e6 26987010 26336030 -2.41%
image/png benchmarks:
BenchmarkDecodeGray 1841839 1802251 -2.15%
BenchmarkDecodeNRGBAGradient 7115318 6933280 -2.56%
BenchmarkDecodeNRGBAOpaque 6135892 6013284 -2.00%
BenchmarkDecodePaletted 1153313 1114302 -3.38%
BenchmarkDecodeRGB 5619404 5511190 -1.93%
R=rsc, r
CC=golang-dev
https://golang.org/cl/6533048
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/6efa648853c14aec9d01821f9620401173c1c62b
元コミット内容
compress/flate: デコンプレッサー構造体からヒストリバッファを移動。
パフォーマンス向上に繋がった正確な理由は不明だが、簡単な改善策として有効である。キャッシュラインの問題かもしれない。あるいは、unsafe.Sizeof(decompressor{})がunmappedzero以下になり、checkref/checkoffsetがTESTB命令を挿入する必要がなくなったためかもしれない。あるいは、保守的なガベージコレクタにとってノイズが減ったためかもしれない。あるいは、他の理由かもしれない。
compress/flateベンチマーク結果:
（上記コミット内容に記載のベンチマーク結果を省略）
image/pngベンチマーク結果:
（上記コミット内容に記載のベンチマーク結果を省略）
変更の背景
この変更の主な背景は、compress/flateパッケージにおけるデコンプレッション（解凍）処理のパフォーマンス向上です。コミットメッセージに明記されているように、ヒストリバッファをdecompressor構造体から分離することで、ベンチマークにおいて顕著なパフォーマンス改善（最大で約8%の高速化）が確認されました。
コミットの作者であるNigel Tao氏は、このパフォーマンス向上の正確な原因についていくつかの仮説を立てています。
- キャッシュラインの最適化:
decompressor構造体のサイズが小さくなることで、CPUのキャッシュラインに収まりやすくなり、データアクセスが効率化された可能性。 unsafe.Sizeofと命令挿入の削減:decompressor構造体のサイズが特定の閾値（unmappedzero）を下回ったことで、Goランタイムが参照チェックやオフセットチェックのために挿入するTESTB命令（メモリ領域がマップされているかを確認する命令）が不要になった可能性。これにより、実行時のオーバーヘッドが減少したと考えられます。- ガベージコレクタの負荷軽減: ヒストリバッファが構造体から分離され、ヒープ上に独立して確保されることで、保守的なガベージコレクタが構造体全体をスキャンする際の「ノイズ」が減り、より効率的に動作できるようになった可能性。
これらの仮説は、Goランタイムの内部動作、メモリ管理、CPUキャッシュの振る舞いに関する深い洞察に基づいています。いずれにせよ、この変更は具体的なパフォーマンス向上という結果をもたらしたため、採用されました。
前提知識の解説
Go言語のcompress/flateパッケージ
compress/flateは、Go言語の標準ライブラリの一部であり、DEFLATEアルゴリズム（RFC 1951で定義）に基づくデータ圧縮および解凍機能を提供します。DEFLATEは、LZ77アルゴリズムとハフマン符号化を組み合わせたもので、Zlib、gzip、PNGなどの多くのファイル形式で利用されています。このパッケージは、特にio.Readerおよびio.Writerインターフェースを通じてストリームベースの圧縮・解凍をサポートします。
decompressor構造体
decompressor構造体は、compress/flateパッケージ内でDEFLATE形式のデータを解凍する際の内部状態を管理するために使用されます。これには、入力ストリーム、出力バッファ、ハフマンツリー、そして過去の出力データを保持するヒストリバッファなどが含まれます。解凍処理は、この構造体のフィールドを更新しながら進行します。
ヒストリバッファ (hist)
DEFLATEアルゴリズムのLZ77部分では、圧縮効率を高めるために、既に出力されたデータ（ヒストリ）の中から一致するパターンを見つけて、そのパターンへの参照（距離と長さ）を符号化します。解凍時には、この参照を元にヒストリバッファからデータをコピーして元のデータを再構築します。したがって、ヒストリバッファは解凍処理において非常に重要な役割を果たします。maxHistは、このバッファの最大サイズ（通常は32KB）を定義します。
Goにおけるポインタと値型、メモリ割り当て
- 値型 (Value Type): Goにおいて、配列や構造体はデフォルトで値型です。これは、変数がそのデータ自体を直接保持することを意味します。例えば、
var arr [1024]byteと宣言すると、arrは1024バイトのメモリを直接占有します。関数に値型を渡すと、その値のコピーが作成されます。 - ポインタ型 (Pointer Type): ポインタは、メモリ上の特定のアドレスを指す変数です。
var ptr *[1024]byteと宣言すると、ptrは1024バイトの配列そのものではなく、その配列が格納されているメモリのアドレスを保持します。実際の配列データは、new([1024]byte)のようにヒープ上に別途割り当てられます。 - スタックとヒープ:
- スタック: 関数呼び出しやローカル変数など、生存期間が短いデータが格納されるメモリ領域です。高速なアクセスが可能ですが、サイズに制限があります。
- ヒープ: プログラムの実行中に動的に割り当てられるメモリ領域です。生存期間が長く、大きなデータを格納できますが、スタックに比べてアクセスが遅く、ガベージコレクションの対象となります。
- エスケープ解析: Goコンパイラは、変数がスタックに割り当てられるべきか、ヒープに「エスケープ」して割り当てられるべきかを自動的に判断します。変数が関数のスコープ外で参照される可能性がある場合、ヒープに割り当てられます。
CPUキャッシュライン
CPUは、メインメモリからデータを読み込む際に、一度にまとまったブロック（キャッシュライン）単位でデータをキャッシュに読み込みます。キャッシュラインのサイズは通常64バイト程度です。データがキャッシュラインに収まっていると、CPUは高速にアクセスできますが、データが複数のキャッシュラインにまたがっていたり、頻繁に異なるキャッシュラインのデータにアクセスしたりすると、キャッシュミスが発生し、パフォーマンスが低下します。構造体のサイズがキャッシュラインに収まるかどうかは、パフォーマンスに大きな影響を与える可能性があります。
ガベージコレクタ (GC)
Goのガベージコレクタは、プログラムが不要になったメモリを自動的に解放するシステムです。GoのGCは「並行（concurrent）」かつ「保守的（conservative）」な側面を持つことがあります。
- 保守的GC: ポインタではないように見えるメモリ上の値が、実際にはポインタである可能性がある場合に、それをポインタとして扱うことで、誤って使用中のメモリを解放してしまうことを防ぎます。これにより、GCはより安全になりますが、不要なメモリを保持し続ける「リーク」が発生する可能性もわずかにあります。大きな値型が構造体内に含まれていると、GCがスキャンする範囲が広がり、オーバーヘッドが増加する可能性があります。
技術的詳細
このコミットの技術的な核心は、decompressor構造体のhistフィールドの型を[maxHist]byte（値型配列）から*[maxHist]byte（配列へのポインタ）に変更した点にあります。
変更前:
type decompressor struct {
// ...
hist [maxHist]byte // Output history, buffer.
// ...
}
この定義では、decompressor構造体のインスタンスが作成されると、maxHistバイト（通常32KB）の配列が構造体の一部として直接メモリに割り当てられます。もしdecompressor構造体がスタックに割り当てられる場合、この大きな配列もスタック上に確保されることになります。
変更後:
type decompressor struct {
// ...
hist *[maxHist]byte // Output history, buffer.
// ...
}
この変更により、decompressor構造体自体はmaxHistバイトの配列を直接保持せず、その配列へのポインタ（通常8バイト）のみを保持するようになります。実際のmaxHistバイトの配列データは、new([maxHist]byte)によってヒープ上に別途割り当てられ、そのアドレスがhistフィールドに格納されます。
この変更がもたらす可能性のある影響は以下の通りです。
decompressor構造体のサイズ削減:decompressor構造体自体のメモリサイズが大幅に小さくなります（32KB + α から ポインタサイズ + α へ）。これにより、構造体がCPUのキャッシュラインに収まりやすくなり、キャッシュミスが減少する可能性があります。これは、コミットメッセージで言及されている「キャッシュラインの問題」に直接関連します。- スタックオーバーフローのリスク軽減: もし
decompressor構造体がスタックに割り当てられる場合、大きなヒストリバッファがスタックを圧迫し、スタックオーバーフローを引き起こすリスクがありました。ポインタに変更することで、スタック上のサイズが小さくなり、このリスクが軽減されます。実際のヒストリバッファはヒープに割り当てられるため、スタックの深さには影響しません。 - ガベージコレクタの効率化:
decompressor構造体が小さくなることで、ガベージコレクタが構造体をスキャンする際のオーバーヘッドが減少する可能性があります。特に保守的なGCの場合、構造体内の大きな値型配列は、GCがスキャンすべきメモリ領域を広げ、不要なメモリを保持し続ける原因となることがあります。ポインタに変更することで、GCは構造体内のポインタだけを追跡すればよくなり、ヒストリバッファ自体は独立したヒープオブジェクトとして管理されるため、GCの効率が向上する可能性があります。 unsafe.SizeofとTESTB命令: Goランタイムは、特定のサイズのオブジェクトに対して、メモリが適切にマップされているかを確認するためのTESTB命令を挿入することがあります。decompressor構造体のサイズが小さくなることで、この命令の挿入が不要になる閾値を下回った可能性があり、これにより実行時の命令数が減少し、パフォーマンスが向上したと考えられます。
コードの変更点としては、NewReaderとNewReaderDict関数内で、f.hist = new([maxHist]byte)という行が追加され、ヒストリバッファが明示的にヒープに割り当てられるようになりました。また、NewReaderDictではf.setDict(dict)の呼び出し順序が変更されていますが、これはヒストリバッファの初期化が先に行われるようにするためと考えられます。
コアとなるコードの変更箇所
--- a/src/pkg/compress/flate/inflate.go
+++ b/src/pkg/compress/flate/inflate.go
@@ -212,7 +212,7 @@ type decompressor struct {
codebits [numCodes]int
// Output history, buffer.
- hist [maxHist]byte
+ hist *[maxHist]byte
hp int // current output position in buffer
hw int // have written hist[0:hw] already
hfull bool // buffer has filled at least once
@@ -693,6 +693,7 @@ func makeReader(r io.Reader) Reader {\n func NewReader(r io.Reader) io.ReadCloser {\n var f decompressor\n f.r = makeReader(r)\n+\tf.hist = new([maxHist]byte)\n \tf.step = (*decompressor).nextBlock\n \treturn &f\n }\n@@ -704,8 +705,9 @@ func NewReader(r io.ReadCloser, dict []byte) io.ReadCloser {\n // to read data compressed by NewWriterDict.\n func NewReaderDict(r io.Reader, dict []byte) io.ReadCloser {\n \tvar f decompressor\n-\tf.setDict(dict)\n \tf.r = makeReader(r)\n+\tf.hist = new([maxHist]byte)\n \tf.step = (*decompressor).nextBlock\n+\tf.setDict(dict)\n \treturn &f\n }\n```
## コアとなるコードの解説
このコミットにおけるコアとなるコードの変更は、`src/pkg/compress/flate/inflate.go`ファイル内の以下の3点です。
1. **`decompressor`構造体の`hist`フィールドの型変更**:
```diff
- hist [maxHist]byte
+ hist *[maxHist]byte
```
これは最も重要な変更点です。`decompressor`構造体の`hist`フィールドが、固定サイズのバイト配列`[maxHist]byte`から、その配列へのポインタ`*[maxHist]byte`に変更されました。これにより、`decompressor`構造体自体が占めるメモリサイズが大幅に削減されます。実際のヒストリバッファのデータは、構造体内部ではなく、ヒープ上に別途割り当てられることになります。
2. **`NewReader`関数でのヒストリバッファの初期化**:
```diff
func NewReader(r io.Reader) io.ReadCloser {
var f decompressor
f.r = makeReader(r)
+ f.hist = new([maxHist]byte)
f.step = (*decompressor).nextBlock
return &f
}
```
`NewReader`関数は、新しいデコンプレッサーインスタンスを作成し、初期化します。`f.hist = new([maxHist]byte)`という行が追加され、ここで`maxHist`バイトの配列がヒープ上に新しく割り当てられ、そのポインタが`f.hist`に代入されます。これにより、デコンプレッサーが使用するヒストリバッファが適切に準備されます。
3. **`NewReaderDict`関数でのヒストリバッファの初期化と`setDict`の順序変更**:
```diff
func NewReaderDict(r io.Reader, dict []byte) io.ReadCloser {
var f decompressor
- f.setDict(dict)
f.r = makeReader(r)
+ f.hist = new([maxHist]byte)
f.step = (*decompressor).nextBlock
+ f.setDict(dict)
return &f
}
```
`NewReaderDict`関数は、辞書（dictionary）を使用してデコンプレッサーを初期化する際に使用されます。ここでも`f.hist = new([maxHist]byte)`が追加され、ヒストリバッファがヒープ上に割り当てられます。
また、`f.setDict(dict)`の呼び出し位置が`f.hist`の初期化後に移動しています。これは、辞書を設定する前にヒストリバッファが利用可能であることを保証するため、または辞書の設定がヒストリバッファの初期状態に依存する可能性があるためと考えられます。
これらの変更により、`decompressor`構造体はより軽量になり、ヒストリバッファはヒープ上で独立して管理されることで、前述のパフォーマンス向上の仮説（キャッシュ効率、GCの負荷軽減、`TESTB`命令の削減など）に繋がったと考えられます。
## 関連リンク
* Go Code Review 6533048: [https://golang.org/cl/6533048](https://golang.org/cl/6533048)
## 参考にした情報源リンク
* Go言語の公式ドキュメント (`compress/flate`パッケージ): [https://pkg.go.dev/compress/flate](https://pkg.go.dev/compress/flate)
* DEFLATE (RFC 1951): [https://www.rfc-editor.org/rfc/rfc1951](https://www.rfc-editor.org/rfc/rfc1951)
* Goにおけるメモリ割り当て（スタックとヒープ、エスケープ解析）に関する一般的な情報源
* CPUキャッシュの仕組みに関する一般的な情報源
* Goのガベージコレクタに関する一般的な情報源
* `unsafe.Sizeof`に関するGoのドキュメントまたは解説記事