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

このコミットは、Go言語の標準ライブラリ compress/flate パッケージ内の decompressor 構造体のメモリフットプリントを削減し、それによってパフォーマンスを向上させることを目的としています。具体的には、decompressor 構造体内の大きな配列フィールドを、配列へのポインタに変更し、これらの配列をヒープに別途割り当てるように修正しています。

コミット

commit c7873ff2a64982a4fa4f3c9177d4ec80f66e7db6
Author: Ryan Hitchman <hitchmanr@gmail.com>
Date:   Thu Nov 1 13:57:24 2012 -0400

    compress/flate: shrink decompressor struct for better performance
    
    Helps with issue 2703.
    
    R=dave, minux.ma, rsc
    CC=golang-dev
    https://golang.org/cl/5536078

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

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

元コミット内容

このコミットは、src/pkg/compress/flate/inflate.go ファイルに対して行われました。

変更の概要は以下の通りです。

decompressor 構造体内の bits および codebits フィールドの型を、固定サイズの配列 [N]int から、配列へのポインタ *[N]int に変更しました。
NewReader および NewReaderDict 関数内で decompressor 構造体を初期化する際に、変更されたポインタフィールド (bits と codebits) に対して new を使用してヒープ上に新しい配列を割り当て、そのポインタをフィールドに設定するようにしました。

この変更の主な背景は、decompressor 構造体のサイズを縮小し、それによってGoの compress/flate パッケージのパフォーマンスを向上させることです。コミットメッセージには「Helps with issue 2703」と記載されていますが、2012年当時の具体的な「issue 2703」の内容は、現在のGoのIssueトラッカーでは直接特定できませんでした（現在の「issue 2703」は別の脆弱性に関するものです）。しかし、文脈から判断すると、このIssueは decompressor 構造体のメモリ使用量や、それに起因するパフォーマンス上の問題に関連していたと考えられます。

decompressor 構造体は、Flate（Deflate）圧縮データを解凍する際に使用される主要なデータ構造です。この構造体内に大きな配列が直接埋め込まれていると、以下のような問題が発生する可能性があります。

メモリフットプリントの増大: decompressor オブジェクトが作成されるたびに、その中に含まれる大きな配列も一緒にメモリを消費します。これにより、特に多数の decompressor インスタンスが同時に存在する場合、全体のメモリ使用量が増大します。
キャッシュ効率の低下: CPUのキャッシュは、アクセス頻度の高いデータを高速に処理するために使用されます。大きな構造体は、CPUキャッシュに収まりきらない可能性が高く、データアクセス時にキャッシュミスが発生しやすくなります。キャッシュミスは、CPUがメインメモリからデータをフェッチする必要があるため、パフォーマンスの低下を招きます。
アロケーションコスト: 大きな構造体をスタックに割り当てる場合、スタックフレームが大きくなり、スタックオーバーフローのリスクが増加する可能性があります。また、ヒープに割り当てる場合でも、大きなオブジェクトのアロケーションは小さなオブジェクトよりもコストがかかることがあります。

これらの問題を解決するために、decompressor 構造体自体を小さく保ちつつ、必要に応じて大きなデータ（この場合はハフマン符号化に使用される配列）をヒープに別途割り当てるアプローチが採用されました。

前提知識の解説

Flate (Deflate) 圧縮

Flateは、ZlibライブラリやPNG画像フォーマットなどで広く使用されているデータ圧縮アルゴリズムです。LZ77アルゴリズムとハフマン符号化を組み合わせたもので、データ内の繰り返しパターンを効率的に削減し、さらに頻出するシンボルを短いビット列で表現することで高い圧縮率を実現します。

ハフマン符号化 (Huffman Coding)

ハフマン符号化は、データ圧縮に用いられる可変長符号化の一種です。データ内の各シンボルの出現頻度に基づいて、頻度の高いシンボルには短いビット列を、頻度の低いシンボルには長いビット列を割り当てます。これにより、データ全体のビット数を削減し、圧縮を実現します。Flate圧縮では、リテラル/長さ符号と距離符号の2種類のハフマン符号が使用されます。

Go言語の配列とポインタ

Go言語において、配列は値型です。つまり、[N]T 型の変数を宣言すると、その配列の全要素がその変数の一部としてメモリに確保されます。構造体のフィールドとして配列を宣言した場合、その配列のメモリは構造体の一部として確保されます。

一方、ポインタはメモリアドレスを保持する型です。*T 型の変数は、T 型の値が格納されているメモリアドレスを指します。new(T) は、T 型のゼロ値を格納するのに十分なメモリを割り当て、そのメモリへのポインタを返します。

このコミットでは、decompressor 構造体内に直接大きな配列を埋め込むのではなく、配列へのポインタを埋め込むことで、構造体自体のサイズを大幅に削減しています。実際の配列データは、new を使ってヒープに別途割り当てられます。

キャッシュメモリとパフォーマンス

現代のCPUは、メインメモリよりもはるかに高速なキャッシュメモリを内蔵しています。CPUがデータにアクセスする際、まずキャッシュを調べ、データがキャッシュにあれば高速に処理できます（キャッシュヒット）。データがキャッシュになければ、メインメモリからデータをフェッチする必要があり、これは非常に時間がかかります（キャッシュミス）。

プログラムがアクセスするデータがCPUキャッシュに収まるように設計されていると、キャッシュヒット率が高まり、全体的なパフォーマンスが向上します。大きなデータ構造はキャッシュミスを引き起こしやすいため、構造体のサイズを小さくすることは、キャッシュ効率を改善し、パフォーマンスを向上させる上で重要な最適化手法の一つです。

技術的詳細

このコミットの技術的詳細な変更点は、decompressor 構造体の定義と、その初期化ロジックにあります。

`decompressor` 構造体の変更

変更前:

type decompressor struct {
	// ...
	bits     [maxLit + maxDist]int
	codebits [numCodes]int
	// ...
}

変更後:

type decompressor struct {
	// ...
	bits     *[maxLit + maxDist]int
	codebits *[numCodes]int
	// ...
}

ここで、maxLit, maxDist, numCodes は定数であり、これらの配列はそれぞれ int 型の要素を多数保持します。例えば、maxLit + maxDist は288 + 32 = 320、numCodes は19です。これらの配列が直接構造体に含まれると、decompressor 構造体は数百バイトのサイズになります。ポインタに変更することで、構造体内のこれらのフィールドが占めるメモリは、ポインタのサイズ（通常、64ビットシステムで8バイト）に削減されます。

`NewReader` および `NewReaderDict` 関数での初期化変更

変更前は、decompressor 構造体が宣言されると、その中に含まれる配列も自動的にゼロ値で初期化されていました。変更後、bits と codebits がポインタになったため、これらのポインタが指す先の配列を明示的に割り当てる必要があります。

// NewReader 関数内
func NewReader(r io.Reader) io.ReadCloser {
	var f decompressor
	// 変更前はここで配列が自動的に初期化されていた
	f.r = makeReader(r)
	f.hist = new([maxHist]byte) // hist は元々ポインタ
	f.step = (*decompressor).nextBlock
	return &f
}

// NewReaderDict 関数内
func NewReaderDict(r io.Reader, dict []byte) io.ReadCloser {
	var f decompressor
	// 変更前はここで配列が自動的に初期化されていた
	f.r = makeReader(r)
	f.hist = new([maxHist]byte) // hist は元々ポインタ
	f.step = (*decompressor).nextBlock
	f.setDict(dict)
	return &f
}

変更後:

// NewReader 関数内
func NewReader(r io.Reader) io.ReadCloser {
	var f decompressor
	f.bits = new([maxLit + maxDist]int) // 新しく追加
	f.codebits = new([numCodes]int)     // 新しく追加
	f.r = makeReader(r)
	f.hist = new([maxHist]byte)
	f.step = (*decompressor).nextBlock
	return &f
}

// NewReaderDict 関数内
func NewReaderDict(r io.Reader, dict []byte) io.ReadCloser {
	var f decompressor
	f.r = makeReader(r)
	f.hist = new([maxHist]byte)
	f.bits = new([maxLit + maxDist]int) // 新しく追加
	f.codebits = new([numCodes]int)     // 新しく追加
	f.step = (*decompressor).nextBlock
	f.setDict(dict)
	return &f
}

new([maxLit + maxDist]int) は、[maxLit + maxDist]int 型の新しい配列をヒープに割り当て、その配列へのポインタを返します。このポインタが f.bits に代入されます。同様に f.codebits も処理されます。

この変更により、decompressor 構造体自体は小さくなり、そのインスタンスがスタックに割り当てられたり、他の構造体の一部として埋め込まれたりする場合のメモリ効率が向上します。実際の配列データはヒープに割り当てられますが、Goのガベージコレクタがこれらのメモリを管理します。

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

src/pkg/compress/flate/inflate.go

--- a/src/pkg/compress/flate/inflate.go
+++ b/src/pkg/compress/flate/inflate.go
@@ -208,8 +208,8 @@ type decompressor struct {
 	h1, h2 huffmanDecoder
 
 	// Length arrays used to define Huffman codes.
-	bits     [maxLit + maxDist]int
-	codebits [numCodes]int
+	bits     *[maxLit + maxDist]int
+	codebits *[numCodes]int
 
 	// Output history, buffer.
 	hist  *[maxHist]byte
@@ -692,6 +692,8 @@ func makeReader(r io.Reader) Reader {
 // finished reading.
 func NewReader(r io.Reader) io.ReadCloser {
 	var f decompressor
+	f.bits = new([maxLit + maxDist]int)
+	f.codebits = new([numCodes]int)
 	f.r = makeReader(r)
 	f.hist = new([maxHist]byte)
 	f.step = (*decompressor).nextBlock
@@ -707,6 +709,8 @@ func NewReaderDict(r io.Reader, dict []byte) io.ReadCloser {
 	var f decompressor
 	f.r = makeReader(r)
 	f.hist = new([maxHist]byte)
+	f.bits = new([maxLit + maxDist]int)
+	f.codebits = new([numCodes]int)
 	f.step = (*decompressor).nextBlock
 	f.setDict(dict)
 	return &f

コアとなるコードの解説

`decompressor` 構造体のフィールド型変更

bits [maxLit + maxDist]int から bits *[maxLit + maxDist]int へ:
- bits フィールドは、ハフマン符号化の際に使用されるビット長を格納する配列です。この配列は、リテラル/長さ符号と距離符号の最大シンボル数に対応するサイズを持っています。
- 変更前は、この配列が decompressor 構造体の一部として直接メモリに配置されていました。
- 変更後は、配列そのものではなく、その配列へのポインタが構造体に格納されます。これにより、decompressor 構造体自体のサイズが、この配列のサイズ分だけ小さくなります。
codebits [numCodes]int から codebits *[numCodes]int へ:
- codebits フィールドも同様に、ハフマン符号化に関連するコードビットを格納する配列です。
- bits と同様に、この変更により decompressor 構造体のサイズが削減されます。

`NewReader` および `NewReaderDict` 関数での配列の動的割り当て

f.bits = new([maxLit + maxDist]int):
- new キーワードは、指定された型のゼロ値を格納するのに十分なメモリを割り当て、そのメモリへのポインタを返します。
- ここでは、[maxLit + maxDist]int 型の新しい配列がヒープに割り当てられ、その配列へのポインタが f.bits フィールドに代入されます。
f.codebits = new([numCodes]int):
- 同様に、[numCodes]int 型の新しい配列がヒープに割り当てられ、そのポインタが f.codebits フィールドに代入されます。

これらの変更により、decompressor 構造体のインスタンスはより小さくなり、CPUキャッシュへの収まりが良くなることで、データアクセスが高速化され、全体的なパフォーマンスが向上します。特に、多数の圧縮/解凍操作が行われるようなシナリオでは、この最適化が顕著な効果を発揮します。

参考にした情報源リンク

Go言語の公式ドキュメント (配列、ポインタ、new 関数に関する情報)
CPUキャッシュとパフォーマンスに関する一般的な情報
Deflate圧縮アルゴリズムとハフマン符号化に関する一般的な情報

comemo