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

このコミットは、Go言語の標準ライブラリ compress/flate パッケージにおけるDEFLATE圧縮処理の最適化に関するものです。具体的には、圧縮処理中に使用されるハッシュテーブル（hashHeadとhashPrev）のインデックス管理方法を変更することで、メモリへの書き込み回数を減らし、メモリ負荷（memory pressure）を軽減することを目的としています。この最適化は、追加の算術演算を伴うトレードオフの上に成り立っています。

コミット

• コミットハッシュ: d7e34051fcbd61a2f603b00f98d2bb3ca16c105d
• 作者: Ivan Krasin krasin@golang.org
• コミット日時: Mon Jan 23 09:19:39 2012 -0500

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

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

元コミット内容

compress/flate: reduce memory pressure at cost of additional arithmetic operation.

R=rsc
CC=golang-dev
https://golang.org/cl/5555070

変更の背景

DEFLATE圧縮アルゴリズムでは、過去のデータ（ウィンドウ）を参照して繰り返しパターンを見つけ、それを短い参照で置き換えることで圧縮を行います。この参照を効率的に行うために、ハッシュテーブルが使用されます。圧縮処理が進むにつれて、この「ウィンドウ」はスライドしていきます。

従来のGoのcompress/flate実装では、ウィンドウがスライドするたびに、ハッシュテーブル（hashHeadとhashPrev）内の古いインデックス値を新しいウィンドウの相対位置に合わせて調整する必要がありました。これは、テーブル全体を走査し、各エントリからwindowSizeを減算するというループ処理によって行われていました。

このループ処理は、特に大きなウィンドウサイズを使用する場合や、頻繁にウィンドウがスライドする場合に、大量のメモリ書き込み操作を発生させます。メモリへの書き込みはCPUキャッシュの無効化を引き起こし、パフォーマンスに影響を与える可能性があります。このコミットの背景には、この「メモリ負荷（memory pressure）」を軽減し、圧縮性能を向上させるという目的がありました。

前提知識の解説

DEFLATEアルゴリズム

DEFLATEは、LZ77アルゴリズムとハフマン符号化を組み合わせた可逆データ圧縮アルゴリズムです。

• LZ77 (Lempel-Ziv 1977): 繰り返し出現するバイト列を、そのバイト列が過去に出現した位置（オフセット）と長さ（マッチ長）で置き換えることで圧縮します。この過去のデータが格納されている領域を「スライディングウィンドウ」と呼びます。
• ハフマン符号化: LZ77によって生成されたリテラルバイト（圧縮されなかったバイト）と、オフセット・長さのペアを、出現頻度に基づいて可変長のビット列に符号化することで、さらに圧縮率を高めます。

スライディングウィンドウとハッシュチェーン

DEFLATEの実装では、LZ77のマッチ検索を高速化するためにハッシュテーブルが用いられます。

• スライディングウィンドウ: 圧縮対象のデータの一部を保持するバッファです。新しいデータが読み込まれると、ウィンドウはスライドし、最も古いデータが捨てられます。
• ハッシュテーブル: 入力データの特定の長さのシーケンス（通常は3バイトなど）をハッシュ値に変換し、そのハッシュ値に対応するウィンドウ内の位置を記録します。
• ハッシュチェーン: 同じハッシュ値を持つ複数の位置が存在する場合、それらの位置をリンクリストのように繋ぐことで、効率的に過去のマッチ候補を検索できるようにします。hashHead配列は各ハッシュ値の最新のマッチ位置を指し、hashPrev配列は各位置の前のマッチ位置を指します。

メモリ負荷 (Memory Pressure)

メモリ負荷とは、システムがメモリを効率的に利用できていない状態、またはメモリへのアクセスが頻繁に発生し、CPUのパフォーマンスを阻害している状態を指します。具体的には、以下のような状況で発生します。

• キャッシュミス: CPUがデータにアクセスしようとした際に、そのデータが高速なCPUキャッシュに存在せず、低速なメインメモリから読み込む必要がある場合に発生します。
• ライトバック: メモリへの書き込みが頻繁に行われると、キャッシュラインがダーティになり、メインメモリへの書き込み（ライトバック）が頻繁に発生します。これもパフォーマンス低下の原因となります。
• ガベージコレクション: Goのようなガベージコレクタを持つ言語では、メモリ割り当てと解放が頻繁に行われると、ガベージコレクションの頻度が増え、アプリケーションの一時停止（STW: Stop The World）を引き起こす可能性があります。

このコミットでは、ハッシュテーブルのインデックス調整に伴う大量のメモリ書き込みがメモリ負荷を高めているという問題意識がありました。

技術的詳細

このコミットの核心は、DEFLATE圧縮におけるスライディングウィンドウの管理方法を根本的に変更し、メモリ負荷を軽減することにあります。

従来のインデックス調整の問題点

従来のcompress/flateの実装では、圧縮ウィンドウがwindowSize分スライドするたびに、hashHeadとhashPrevという2つの大きな配列の全要素を更新していました。これらの配列には、ウィンドウ内の位置を示すインデックスが格納されています。ウィンドウがスライドすると、これらのインデックスは相対的にwindowSizeだけずれるため、各インデックスからwindowSizeを減算する必要がありました。

// 従来のコード（削除された部分）
for i, h := range d.hashHead {
    v := h - windowSize
    if v < -1 { // -1 は無効なインデックスを示す
        v = -1
    }
    d.hashHead[i] = v
}
for i, h := range d.hashPrev {
    v := h - windowSize
    if v < -1 {
        v = -1
    }
    d.hashPrev[i] = v
}

この処理は、hashHeadとhashPrevのサイズに比例して多くのメモリ書き込みを伴います。特にwindowSizeが大きい場合、これらの配列も大きくなるため、書き込み回数が増加し、CPUキャッシュの効率を低下させ、メモリ負荷を高めていました。

hashOffsetの導入による解決策

このコミットでは、hashOffsetという新しいフィールドをcompressor構造体に追加することで、この問題を解決しています。

// 新しく追加されたフィールド
hashOffset int

hashOffsetは、ハッシュテーブルに格納されているインデックス値と実際のウィンドウ内の位置との間の「ずれ」を表現します。ウィンドウがスライドするたびに、hashHeadとhashPrevの全要素を更新する代わりに、hashOffsetの値をwindowSizeだけ増加させるだけになります。

// 新しいコード
d.hashOffset += windowSize

これにより、大量のメモリ書き込みが、単一のhashOffset変数の更新という、はるかに少ない書き込みに置き換えられます。

トレードオフ：追加の算術演算

hashOffsetを導入したことによるトレードオフは、ハッシュテーブルからインデックス値を取得する際、またはハッシュテーブルにインデックス値を格納する際に、このhashOffsetを考慮した算術演算が必要になる点です。

• インデックスの格納時: 実際のウィンドウ内の位置（d.index）にhashOffsetを加算してハッシュテーブルに格納します。

  // 変更前: d.hashHead[d.hash] = d.index
  // 変更後: d.hashHead[d.hash] = d.index + d.hashOffset
  

• インデックスの取得時: ハッシュテーブルから取得したインデックス値からhashOffsetを減算して、実際のウィンドウ内の位置を計算します。

  // 変更前: if i = d.hashPrev[i&windowMask]; i < minIndex || i < 0 {
  // 変更後: if i = d.hashPrev[i&windowMask] - d.hashOffset; i < minIndex || i < 0 {
  

  同様に、d.chainHeadを使用する箇所でもd.hashOffsetが考慮されます。

  // 変更前: if d.chainHead >= minIndex && ... d.findMatch(d.index, d.chainHead, ...
  // 変更後: if d.chainHead-d.hashOffset >= minIndex && ... d.findMatch(d.index, d.chainHead-d.hashOffset, ...
  

この変更により、ウィンドウがスライドするたびに行われていた大規模なメモリ書き込みが削減され、代わりに個々のハッシュテーブルアクセス時に少量の算術演算が追加されることになります。一般的に、メモリ書き込みはCPUサイクルを多く消費し、キャッシュ効率に影響を与えるため、算術演算の追加は全体的なパフォーマンス向上に寄与すると考えられます。

hashOffsetの初期化

initDeflate関数では、hashOffsetが1で初期化されています。これは、インデックス0が特別な意味を持つ（無効なインデックスとして扱われる）ため、実際のインデックスとhashOffsetを加算した結果が0にならないようにするための工夫と考えられます。

// 新しいコード
d.hashOffset = 1

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

変更はすべて src/pkg/compress/flate/deflate.go ファイル内で行われています。

1. compressor構造体へのhashOffsetフィールドの追加:

   --- a/src/pkg/compress/flate/deflate.go
   +++ b/src/pkg/compress/flate/deflate.go
   @@ -70,9 +70,10 @@ type compressor struct {
    	// If hashHead[hashValue] is within the current window, then
    	// hashPrev[hashHead[hashValue] & windowMask] contains the previous index
    	// with the same hash value.
   -	chainHead int
   -	hashHead  []int
   -	hashPrev  []int
   +	chainHead  int
   +	hashHead   []int
   +	hashPrev   []int
   +	hashOffset int
   

2. fillDeflate関数でのインデックス調整ループの削除とhashOffsetの更新: ウィンドウがスライドする際に、hashHeadとhashPrevの全要素を更新していたループが削除され、代わりにd.hashOffsetをwindowSizeだけ増加させる処理が追加されました。

   --- a/src/pkg/compress/flate/deflate.go
   +++ b/src/pkg/compress/flate/deflate.go
   @@ -104,20 +105,7 @@ func (d *compressor) fillDeflate(b []byte) int {
    		} else {
    			d.blockStart = skipNever
    		}
   -		for i, h := range d.hashHead {
   -			v := h - windowSize
   -			if v < -1 {
   -				v = -1
   -			}
   -			d.hashHead[i] = v
   -		}
   -		for i, h := range d.hashPrev {
   -			v := h - windowSize
   -			if v < -1 {
   -				v = -1
   -			}
   -			d.hashPrev[i] = v
   -		}
   +		d.hashOffset += windowSize
    	}
    	n := copy(d.window[d.windowEnd:], b)
    	d.windowEnd += n
   

3. findMatch関数でのインデックス取得時のhashOffsetの適用: ハッシュチェーンを辿る際に、hashPrevから取得したインデックス値からhashOffsetを減算して実際のインデックスを計算するように変更されました。

   --- a/src/pkg/compress/flate/deflate.go
   +++ b/src/pkg/compress/flate/deflate.go
   @@ -188,7 +176,7 @@ func (d *compressor) findMatch(pos int, prevHead int, prevLength int, lookahead
    			// hashPrev[i & windowMask] has already been overwritten, so stop now.
    			break
    		}
   -		if i = d.hashPrev[i&windowMask]; i < minIndex || i < 0 {
   +		if i = d.hashPrev[i&windowMask] - d.hashOffset; i < minIndex || i < 0 {
    			break
    		}
    	}
   

4. initDeflate関数でのhashOffsetの初期化: compressorの初期化時にhashOffsetが1に設定されるようになりました。

   --- a/src/pkg/compress/flate/deflate.go
   +++ b/src/pkg/compress/flate/deflate.go
   @@ -207,7 +195,7 @@ func (d *compressor) initDeflate() {
    	d.hashHead = make([]int, hashSize)
    	d.hashPrev = make([]int, windowSize)
    	d.window = make([]byte, 2*windowSize)
   -	fillInts(d.hashHead, -1)
   +	d.hashOffset = 1
    	d.tokens = make([]token, maxFlateBlockTokens, maxFlateBlockTokens+1)
    	d.length = minMatchLength - 1
    	d.offset = 0
   

5. Loop内でのインデックス格納時および取得時のhashOffsetの適用:

   • 新しいハッシュチェーンエントリをhashHeadに格納する際に、d.indexにd.hashOffsetを加算するようになりました。
   • d.chainHeadを使用する条件式やfindMatch関数呼び出し時に、d.chainHeadからd.hashOffsetを減算して実際のインデックスを計算するようになりました。

   --- a/src/pkg/compress/flate/deflate.go
   +++ b/src/pkg/compress/flate/deflate.go
   @@ -263,7 +251,7 @@ Loop:
    		d.hash = (d.hash<<hashShift + int(d.window[d.index+2])) & hashMask
    		d.chainHead = d.hashHead[d.hash]
    		d.hashPrev[d.index&windowMask] = d.chainHead
   -		d.hashHead[d.hash] = d.index
   +		d.hashHead[d.hash] = d.index + d.hashOffset
    	}
    	prevLength := d.length
    	prevOffset := d.offset
   @@ -274,10 +262,10 @@ Loop:
    		minIndex = 0
    	}
    
   -	if d.chainHead >= minIndex &&
   +	if d.chainHead-d.hashOffset >= minIndex &&
    		(d.fastSkipHashing != skipNever && lookahead > minMatchLength-1 ||
    			d.fastSkipHashing == skipNever && lookahead > prevLength && prevLength < d.lazy) {
   -		if newLength, newOffset, ok := d.findMatch(d.index, d.chainHead, minMatchLength-1, lookahead); ok {
   +		if newLength, newOffset, ok := d.findMatch(d.index, d.chainHead-d.hashOffset, minMatchLength-1, lookahead); ok {
    			d.length = newLength
    			d.offset = newOffset
    		}
   @@ -310,7 +298,7 @@ Loop:
    					// Our chain should point to the previous value.
    					d.hashPrev[d.index&windowMask] = d.hashHead[d.hash]
    					// Set the head of the hash chain to us.
   -					d.hashHead[d.hash] = d.index
   +					d.hashHead[d.hash] = d.index + d.hashOffset
    				}
    			}
    		if d.fastSkipHashing == skipNever {
   

コアとなるコードの解説

このコミットの主要な変更は、compressor構造体にhashOffsetという新しいフィールドを導入し、ハッシュテーブル（hashHeadとhashPrev）のインデックス管理ロジックを根本的に変更した点にあります。

hashOffsetの役割

hashOffsetは、ハッシュテーブルに格納されているインデックス値と、実際の圧縮ウィンドウ内の位置との間のオフセット（ずれ）を管理します。

• インデックスの格納: 圧縮処理中に新しいマッチが見つかり、その位置（d.index）をハッシュテーブルに記録する際、実際のd.indexではなく、d.index + d.hashOffsetという「オフセットされた」値をhashHeadに格納します。

  d.hashHead[d.hash] = d.index + d.hashOffset
  d.hashPrev[d.index&windowMask] = d.chainHead // chainHeadもオフセットされた値
  

• インデックスの取得: ハッシュテーブルから過去のマッチ位置（d.chainHeadやd.hashPrevから取得される値）を取得する際、その値はオフセットされた値なので、実際のウィンドウ内の位置を得るためにはd.hashOffsetを減算する必要があります。

  if d.chainHead-d.hashOffset >= minIndex && ...
  if i = d.hashPrev[i&windowMask] - d.hashOffset; i < minIndex || i < 0 {
  

ウィンドウのスライドとhashOffsetの更新

最も重要な変更は、圧縮ウィンドウがスライドする際の処理です。 従来のコードでは、ウィンドウがwindowSize分スライドするたびに、hashHeadとhashPrevの全要素をループで走査し、各インデックスからwindowSizeを減算して更新していました。これは、これらの配列が非常に大きい場合（windowSizeに比例するため）、大量のメモリ書き込みを伴い、メモリ負荷の原因となっていました。

このコミットでは、この高コストなループ処理を完全に削除し、代わりにd.hashOffsetの値をwindowSizeだけ増加させるように変更しました。

d.hashOffset += windowSize

これにより、ハッシュテーブルの物理的な内容は変更されず、インデックスの「意味」だけがhashOffsetによって調整されることになります。メモリへの書き込みは、hashOffsetという単一の整数変数の更新のみに限定され、大幅に削減されます。

パフォーマンスへの影響

この変更は、メモリ書き込みの削減により、特に大きなウィンドウサイズを使用する圧縮シナリオにおいて、パフォーマンスの向上が期待されます。メモリ書き込みが減ることで、CPUキャッシュのヒット率が向上し、全体的な処理速度が速くなる可能性があります。

一方で、ハッシュテーブルへのアクセスごとにhashOffsetの加算または減算という追加の算術演算が必要になります。しかし、これらの算術演算は非常に高速であり、大規模なメモリ書き込みのコストと比較すると、無視できる程度のオーバーヘッドであると考えられます。結果として、この変更は「追加の算術演算のコストでメモリ負荷を軽減する」というコミットメッセージの意図を正確に反映しています。

関連リンク

• Go CL 5555070: https://golang.org/cl/5555070

参考にした情報源リンク

• DEFLATE (Wikipedia): https://ja.wikipedia.org/wiki/DEFLATE
• LZ77 (Wikipedia): https://ja.wikipedia.org/wiki/LZ77
• ハフマン符号 (Wikipedia): https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E7%AC%A6%E5%8F%B7
• CPUキャッシュ (Wikipedia): https://ja.wikipedia.org/wiki/CPU%E3%82%AD%E3%83%A3%E3%83%83%E3%82%B7%E3%83%A5
• Memory pressure (Google Search): https://www.google.com/search?q=memory+pressure
• Go言語のcompress/flateパッケージのソースコード (Go公式リポジトリ): https://github.com/golang/go/tree/master/src/compress/flate