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

このコミットは、Go言語のcompress/flateパッケージにおけるinflate（DEFLATE圧縮データの伸長）処理のパフォーマンスを大幅に改善するものです。特に、ハフマン符号のデコード方法を最適化し、zlibの実装に似た単一テーブルルックアップ方式を導入することで、伸長速度が約50%向上しています。

コミット

commit ebf35167eed54afb75332f879351dffdc5615e5d
Author: Raph Levien <raph@google.com>
Date:   Fri Jan 18 15:09:42 2013 -0500

    compress/flate: Performance improvement for inflate
    
    Decode as much as possible of a Huffman symbol in a single table
    lookup (much like the zlib implementation), filling more bits
    (conservatively, so we don't consume past the end of the stream)
    when the code prefix indicates more bits are needed. This
    results in about a 50% performance gain in speed benchmarks.
    The following set is benchcmp done on a retina MacBook Pro:
    
    benchmark                            old MB/s     new MB/s  speedup
    BenchmarkDecodeDigitsSpeed1e4           28.41        42.79    1.51x
    BenchmarkDecodeDigitsSpeed1e5           30.18        47.62    1.58x
    BenchmarkDecodeDigitsSpeed1e6           30.81        48.14    1.56x
    BenchmarkDecodeDigitsDefault1e4         30.28        44.61    1.47x
    BenchmarkDecodeDigitsDefault1e5         32.18        51.94    1.61x
    BenchmarkDecodeDigitsDefault1e6         35.57        53.28    1.50x
    BenchmarkDecodeDigitsCompress1e4        30.39        44.83    1.48x
    BenchmarkDecodeDigitsCompress1e5        33.05        51.64    1.56x
    BenchmarkDecodeDigitsCompress1e6        35.69        53.04    1.49x
    BenchmarkDecodeTwainSpeed1e4            25.90        43.04    1.66x
    BenchmarkDecodeTwainSpeed1e5            29.97        48.19    1.61x
    BenchmarkDecodeTwainSpeed1e6            31.36        49.43    1.58x
    BenchmarkDecodeTwainDefault1e4          28.79        45.02    1.56x
    BenchmarkDecodeTwainDefault1e5          37.12        55.65    1.50x
    BenchmarkDecodeTwainDefault1e6          39.28        58.16    1.48x
    BenchmarkDecodeTwainCompress1e4         28.64        44.90    1.57x
    BenchmarkDecodeTwainCompress1e5         37.40        55.98    1.50x
    BenchmarkDecodeTwainCompress1e6         39.35        58.06    1.48x
    
    R=rsc, dave, minux.ma, bradfitz, nigeltao
    CC=golang-dev
    https://golang.org/cl/6872063

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

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

元コミット内容

compress/flate: Performance improvement for inflate
    
Decode as much as possible of a Huffman symbol in a single table
lookup (much like the zlib implementation), filling more bits
(conservatively, so we don't consume past the end of the stream)
when the code prefix indicates more bits are needed. This
results in about a 50% performance gain in speed benchmarks.
The following set is benchcmp done on a retina MacBook Pro:

benchmark                            old MB/s     new MB/s  speedup
BenchmarkDecodeDigitsSpeed1e4           28.41        42.79    1.51x
BenchmarkDecodeDigitsSpeed1e5           30.18        47.62    1.58x
BenchmarkDecodeDigitsSpeed1e6           30.81        48.14    1.56x
BenchmarkDecodeDigitsDefault1e4         30.28        44.61    1.47x
BenchmarkDecodeDigitsDefault1e5         32.18        51.94    1.61x
BenchmarkDecodeDigitsDefault1e6         35.57        53.28    1.50x
BenchmarkDecodeDigitsCompress1e4        30.39        44.83    1.48x
BenchmarkDecodeDigitsCompress1e5        33.05        51.64    1.56x
BenchmarkDecodeDigitsCompress1e6        35.69        53.04    1.49x
BenchmarkDecodeTwainSpeed1e4            25.90        43.04    1.66x
BenchmarkDecodeTwainSpeed1e5            29.97        48.19    1.61x
BenchmarkDecodeTwainSpeed1e6            31.36        49.43    1.58x
BenchmarkDecodeTwainDefault1e4          28.79        45.02    1.56x
BenchmarkDecodeTwainDefault1e5          37.12        55.65    1.50x
BenchmarkDecodeTwainDefault1e6          39.28        58.16    1.48x
BenchmarkDecodeTwainCompress1e4         28.64        44.90    1.57x
BenchmarkDecodeTwainCompress1e5         37.40        55.98    1.50x
BenchmarkDecodeTwainCompress1e6         39.35        58.06    1.48x

R=rsc, dave, minux.ma, bradfitz, nigeltao
CC=golang-dev
https://golang.org/cl/6872063

変更の背景

このコミットの主な目的は、Go言語のcompress/flateパッケージにおけるDEFLATEデータの伸長（inflate）性能を向上させることです。既存のハフマンデコード処理がボトルネックとなっており、特に大量のデータを扱う際にパフォーマンスの低下が顕著でした。コミットメッセージに示されているベンチマーク結果からもわかるように、この変更によって約1.5倍の速度向上が見込まれています。これは、データ圧縮・伸長が多用されるネットワーク通信やファイルI/Oにおいて、アプリケーション全体の応答性向上に直結する重要な改善です。

前提知識の解説

DEFLATE圧縮アルゴリズム

DEFLATEは、LZ77アルゴリズムとハフマン符号化を組み合わせた可逆データ圧縮アルゴリズムです。RFC 1951で定義されており、ZIP、gzip、PNGなどのファイル形式で広く利用されています。

• LZ77 (Lempel-Ziv 1977): 繰り返し出現するバイト列（シーケンス）を、以前に出現した同じシーケンスへの「参照」（長さと距離のペア）に置き換えることでデータを圧縮します。これにより、冗長なデータの繰り返しを効率的に削減します。
• ハフマン符号化 (Huffman Coding): LZ77によって生成されたリテラルバイト（圧縮されていないバイト）と長さ/距離のペアを、出現頻度に基づいて可変長のビット列に変換するエントロピー符号化の一種です。出現頻度の高いシンボルには短いビット列を、低いシンボルには長いビット列を割り当てることで、全体のデータサイズを削減します。DEFLATEでは、リテラル/長さ符号と距離符号の2種類のハフマンツリーが使用されます。

ハフマン符号のデコード

ハフマン符号は可変長であるため、デコードには特別な処理が必要です。ビットストリームからビットを読み込み、現在のビット列がどのハフマン符号に対応するかを判断します。

従来の単純なデコード方法では、ビットを1ビットずつ読み込み、ハフマンツリーを辿ってシンボルを特定します。しかし、これは多くのCPUサイクルを消費する可能性があります。

zlibのハフマンデコード実装

zlibは、DEFLATEアルゴリズムの最も広く使われている実装の一つです。zlibのハフマンデコードは、パフォーマンスを重視して最適化されています。その主要な最適化の一つが、**ルックアップテーブル（lookup table）**の使用です。

zlibのデコーダは、入力ビットストリームから一度に複数のビット（例えば、9ビットや10ビット）を読み込み、そのビット列をインデックスとしてルックアップテーブルを参照します。このテーブルのエントリには、対応するハフマンシンボル、そのシンボルのビット長、そして必要であれば次のルックアップテーブルへのポインタ（オーバーフローテーブルへのリンク）が含まれています。

• 単一テーブルルックアップ: 短いハフマン符号（テーブルのビット幅以下の長さの符号）は、1回のテーブル参照で直接デコードできます。
• オーバーフローテーブル: 長いハフマン符号（テーブルのビット幅を超える長さの符号）の場合、最初のルックアップでは部分的な情報しか得られません。テーブルエントリは、さらにビットを読み込んで別の（オーバーフロー）テーブルを参照する必要があることを示します。これにより、複数回のテーブル参照が必要になることもありますが、それでも1ビットずつツリーを辿るよりもはるかに高速です。

このアプローチにより、CPUの分岐予測ミスを減らし、キャッシュ効率を向上させ、全体的なデコード速度を大幅に向上させることができます。

技術的詳細

このコミットは、Goのcompress/flateパッケージのハフマンデコーダを、zlibの実装に倣ってルックアップテーブルベースの方式に移行することで、inflateのパフォーマンスを向上させています。

変更の核心は、huffmanDecoder構造体と、それを利用するhuffSymデコード関数にあります。

1. huffmanDecoder構造体の変更:

   • 従来のmin, max, limit, base, codesといった配列ベースの構造から、min, chunks, links, linkMaskというルックアップテーブルベースの構造に変わりました。
   • chunksは、固定ビット幅（huffmanChunkBits、このコミットでは9ビット）の初期ルックアップテーブルです。各エントリは、シンボルの値とビット長を含みます。
   • linksは、huffmanChunkBitsを超える長さのハフマン符号をデコードするためのオーバーフローテーブルへのポインタの配列です。
   • linkMaskは、オーバーフローテーブルのインデックス計算に使用されます。

2. init関数の変更:

   • ハフマン符号のビット長配列（bits）から、新しいhuffmanDecoder構造体（chunksとlinks）を構築するロジックが完全に書き直されました。
   • この関数は、各ビット長に対応するコードの数を数え、最小・最大ビット長を特定します。
   • huffmanChunkBitsを超える長さのコードが存在する場合、オーバーフローテーブル（links）が作成されます。
   • 各ハフマン符号について、その符号に対応するビット列を反転させ、ルックアップテーブルの適切な位置にシンボル情報（値とビット長）を格納します。短いコードは複数のエントリを占有し、長いコードはオーバーフローテーブルへのリンクを介して処理されます。

3. huffSymデコード関数の変更:

   • 従来の1ビットずつ読み込み、limitとbase配列を使ってシンボルを特定するループ処理から、新しいルックアップテーブルベースのデコードロジックに変わりました。
   • まず、入力ストリームからhuffmanChunkBits分のビットを読み込み、chunksテーブルを直接参照します。
   • 参照結果から、シンボルのビット長（n）と値（chunk >> huffmanValueShift）を取得します。
   • もしnがhuffmanChunkBitsより大きい場合（つまり、最初のルックアップでシンボルが完全に特定できなかった場合）、linksテーブル（オーバーフローテーブル）を参照して残りのビットをデコードします。
   • この「単一テーブルルックアップ」と「必要に応じて追加ビットを読み込む」アプローチにより、デコードに必要なCPU命令数が大幅に削減され、パフォーマンスが向上します。

4. fixedhuff.goとgen.goの導入:

   • DEFLATEアルゴリズムで定義されている固定ハフマン符号（Fixed Huffman Codes）は、事前に計算して静的に埋め込むことで、実行時の初期化コストを削減できます。
   • gen.goは、この固定ハフマン符号のルックアップテーブルを生成するためのGoプログラムです。go generateコマンドなどで実行され、fixedhuff.goというソースファイルを自動生成します。
   • fixedhuff.goには、fixedHuffmanDecoderというhuffmanDecoder型の変数が定義されており、これが固定ハフマン符号のデコードに使用される静的なルックアップテーブルとなります。これにより、実行時に毎回テーブルを構築する必要がなくなり、起動時性能が向上します。

これらの変更により、Goのcompress/flateパッケージは、zlibのような高性能なDEFLATE伸長処理を実現しています。

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

このコミットでは、以下の4つのファイルが変更されています。

1. src/pkg/compress/flate/fixedhuff.go (新規追加)

   • gen.goによって自動生成されるファイルで、固定ハフマン符号のデコードに使用される静的なhuffmanDecoderテーブルが定義されています。

2. src/pkg/compress/flate/flate_test.go (変更)

   • 主にテストコードの削除が行われています。以前のhuffmanDecoderのテストや、fixedHuffmanBitsなどの古い定数が削除されました。これは、新しいデコードロジックとテーブル構造に合わせたテストの再構築が必要になったためと考えられます。

3. src/pkg/compress/flate/gen.go (新規追加)

   • fixedhuff.goを生成するためのGoプログラムです。
   • huffmanDecoder構造体の定義の一部が、このファイルにもコピーされています（inflate.goと共有）。
   • main関数内で、固定ハフマン符号のビット長配列を定義し、huffmanDecoder.initを呼び出してテーブルを構築し、その結果をGoのソースコードとして標準出力に出力します。

4. src/pkg/compress/flate/inflate.go (変更)

   • DEFLATE伸長処理の主要なロジックが含まれるファイルです。
   • huffmanDecoder構造体の定義が大幅に変更され、ルックアップテーブルベースの新しい構造になりました。
   • huffmanDecoder.init関数の実装が、新しいテーブル構築ロジックに合わせて完全に書き直されました。
   • huffSym関数（ハフマンシンボルをデコードする関数）のロジックが、新しいルックアップテーブルを利用するように変更されました。

コアとなるコードの解説

src/pkg/compress/flate/inflate.goにおけるhuffmanDecoderとhuffSymの変更

変更前のhuffmanDecoder構造体（概念）:

type huffmanDecoder struct {
	min, max int
	limit    [maxCodeLen + 1]int // 各ビット長における最大コード値
	base     [maxCodeLen + 1]int // 各ビット長における最小コード値からのオフセット
	codes    []int               // シーケンス番号から出力コードへのマッピング
}

変更前は、limitとbase配列を使って、読み込んだビット列がどのビット長の範囲に属するかを判断し、codes配列から対応するシンボルを検索していました。これは、ビットを1ビットずつ読み込みながらツリーを辿るような、比較的線形的な検索アプローチでした。

変更後のhuffmanDecoder構造体:

const (
	huffmanChunkBits  = 9 // 初期ルックアップテーブルのビット幅
	huffmanNumChunks  = 1 << huffmanChunkBits // チャンク数 (512)
	huffmanCountMask  = 15 // ビット長を抽出するためのマスク
	huffmanValueShift = 4  // 値を抽出するためのシフト量
)

type huffmanDecoder struct {
	min      int                      // 最小コード長
	chunks   [huffmanNumChunks]uint32 // 初期ルックアップテーブル
	links    [][]uint32               // オーバーフローテーブルへのリンク
	linkMask uint32                   // リンクテーブルのマスク
}

新しいhuffmanDecoderは、zlibの設計思想を取り入れています。

• chunks: 入力ストリームから最初のhuffmanChunkBits（9ビット）を読み込み、この配列をインデックスとして参照します。各uint32エントリは、下位4ビットにシンボルのビット長、上位ビットにシンボルの値（またはオーバーフローテーブルへのオフセット）を格納します。
• links: huffmanChunkBitsを超える長さのハフマン符号をデコードするための補助的なルックアップテーブルです。

変更後のhuffSym関数（抜粋）:

func (f *decompressor) huffSym(h *huffmanDecoder) (int, error) {
	n := uint(h.min) // 最小ビット長から開始
	for {
		for f.nb < n { // 必要なビット数が足りない場合、さらにビットを読み込む
			if err := f.moreBits(); err != nil {
				return 0, err
			}
		}
		
		// 最初のルックアップ: 現在のバッファの先頭huffmanChunkBits分を使ってchunksテーブルを参照
		chunk := h.chunks[f.b&(huffmanNumChunks-1)]
		n = uint(chunk & huffmanCountMask) // チャンクからビット長を取得

		if n > huffmanChunkBits { // ビット長がhuffmanChunkBitsより大きい場合、オーバーフローテーブルを参照
			// chunksエントリの上位ビットからリンクテーブルのオフセットを取得し、
			// さらにバッファの残りのビットを使ってlinksテーブルを参照
			chunk = h.links[chunk>>huffmanValueShift][(f.b>>huffmanChunkBits)&h.linkMask]
			n = uint(chunk & huffmanCountMask) // オーバーフローテーブルから最終的なビット長を取得
		}
		
		if n <= f.nb { // 必要なビット数がバッファにある場合
			f.b >>= n   // バッファからビットを消費
			f.nb -= n
			return int(chunk >> huffmanValueShift), nil // シンボルの値を返す
		}
	}
	// ... エラーハンドリング ...
}

この新しいhuffSym関数は、まずhuffmanChunkBits分のビットを使ってchunksテーブルをルックアップします。

• もしシンボルがhuffmanChunkBits以下の長さであれば、1回のルックアップでシンボルが特定され、その値とビット長が返されます。
• もしシンボルがhuffmanChunkBitsより長い場合、chunksテーブルのエントリはオーバーフローテーブル（links）へのポインタを含んでいます。この場合、さらにビットを読み込み、linksテーブルをルックアップすることでシンボルを特定します。

この方式は、多くのハフマン符号が短いビット長を持つという特性を活かし、ほとんどのデコードを1〜2回のメモリ参照で完了させることで、大幅な高速化を実現しています。

src/pkg/compress/flate/gen.goの役割

gen.goは、Goのgo generateツールと組み合わせて使用されるコード生成スクリプトです。その主な目的は、DEFLATEの固定ハフマン符号のためのルックアップテーブルを事前に計算し、Goのソースコードとしてfixedhuff.goに出力することです。

// +build ignore

// This program generates fixedhuff.go
// Invoke as
//
//      go run gen.go |gofmt >fixedhuff.go

このコメントが示すように、gen.goは通常のビルドプロセスには含まれず、開発者が手動で実行するか、go generateを通じて実行されます。

main関数内では、固定ハフマン符号のビット長がRFC 1951に従って定義され、huffmanDecoder.initメソッドが呼び出されて、その固定符号に対応するchunksテーブルが構築されます。最終的に、この構築されたテーブルの内容がGoのコードとして整形され、標準出力に書き出されます。この出力がfixedhuff.goファイルとして保存されるわけです。

これにより、compress/flateパッケージがビルドされる際に、固定ハフマン符号のデコードテーブルがコンパイル済みのバイナリに静的に埋め込まれるため、実行時にテーブルを動的に構築するオーバーヘッドがなくなります。

関連リンク

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

参考にした情報源リンク

• RFC 1951 - DEFLATE Compressed Data Format Specification version 1.3: https://www.ietf.org/rfc/rfc1951.txt
• zlib Home Site: https://www.zlib.net/
• Huffman coding - Wikipedia: https://en.wikipedia.org/wiki/Huffman_coding
• DEFLATE - Wikipedia: https://en.wikipedia.org/wiki/DEFLATE
• Go compress/flate package documentation: https://pkg.go.dev/compress/flate
• (Web検索結果に基づく一般的なハフマンデコードとzlib実装に関する情報)

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

このコミットは、Go言語のcompress/flateパッケージにおけるinflate（DEFLATE圧縮データの伸長）処理のパフォーマンスを大幅に改善するものです。特に、ハフマン符号のデコード方法を最適化し、zlibの実装に似た単一テーブルルックアップ方式を導入することで、伸長速度が約50%向上しています。

コミット

commit ebf35167eed54afb75332f879351dffdc5615e5d
Author: Raph Levien <raph@google.com>
Date:   Fri Jan 18 15:09:42 2013 -0500

    compress/flate: Performance improvement for inflate
    
    Decode as much as possible of a Huffman symbol in a single table
    lookup (much like the zlib implementation), filling more bits
    (conservatively, so we don't consume past the end of the stream)
    when the code prefix indicates more bits are needed. This
    results in about a 50% performance gain in speed benchmarks.
    The following set is benchcmp done on a retina MacBook Pro:
    
    benchmark                            old MB/s     new MB/s  speedup
    BenchmarkDecodeDigitsSpeed1e4           28.41        42.79    1.51x
    BenchmarkDecodeDigitsSpeed1e5           30.18        47.62    1.58x
    BenchmarkDecodeDigitsSpeed1e6           30.81        48.14    1.56x
    BenchmarkDecodeDigitsDefault1e4         30.28        44.61    1.47x
    BenchmarkDecodeDigitsDefault1e5         32.18        51.94    1.61x
    BenchmarkDecodeDigitsDefault1e6         35.57        53.28    1.50x
    BenchmarkDecodeDigitsCompress1e4        30.39        44.83    1.48x
    BenchmarkDecodeDigitsCompress1e5        33.05        51.64    1.56x
    BenchmarkDecodeDigitsCompress1e6        35.69        53.04    1.49x
    BenchmarkDecodeTwainSpeed1e4            25.90        43.04    1.66x
    BenchmarkDecodeTwainSpeed1e5            29.97        48.19    1.61x
    BenchmarkDecodeTwainSpeed1e6            31.36        49.43    1.58x
    BenchmarkDecodeTwainDefault1e4          28.79        45.02    1.56x
    BenchmarkDecodeTwainDefault1e5          37.12        55.65    1.50x
    BenchmarkDecodeTwainDefault1e6          39.28        58.16    1.48x
    BenchmarkDecodeTwainCompress1e4         28.64        44.90    1.57x
    BenchmarkDecodeTwainCompress1e5         37.40        55.98    1.50x
    BenchmarkDecodeTwainCompress1e6         39.35        58.06    1.48x
    
    R=rsc, dave, minux.ma, bradfitz, nigeltao
    CC=golang-dev
    https://golang.org/cl/6872063

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

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

元コミット内容

compress/flate: Performance improvement for inflate
    
Decode as much as possible of a Huffman symbol in a single table
lookup (much like the zlib implementation), filling more bits
(conservatively, so we don't consume past the end of the stream)
when the code prefix indicates more bits are needed. This
results in about a 50% performance gain in speed benchmarks.
The following set is benchcmp done on a retina MacBook Pro:

benchmark                            old MB/s     new MB/s  speedup
BenchmarkDecodeDigitsSpeed1e4           28.41        42.79    1.51x
BenchmarkDecodeDigitsSpeed1e5           30.18        47.62    1.58x
BenchmarkDecodeDigitsSpeed1e6           30.81        48.14    1.56x
BenchmarkDecodeDigitsDefault1e4         30.28        44.61    1.47x
BenchmarkDecodeDigitsDefault1e5         32.18        51.94    1.61x
BenchmarkDecodeDigitsDefault1e6         35.57        53.28    1.50x
BenchmarkDecodeDigitsCompress1e4        30.39        44.83    1.48x
BenchmarkDecodeDigitsCompress1e5        33.05        51.64    1.56x
BenchmarkDecodeDigitsCompress1e6        35.69        53.04    1.49x
BenchmarkDecodeTwainSpeed1e4            25.90        43.04    1.66x
BenchmarkDecodeTwainSpeed1e5            29.97        48.19    1.61x
BenchmarkDecodeTwainSpeed1e6            31.36        49.43    1.58x
BenchmarkDecodeTwainDefault1e4          28.79        45.02    1.56x
BenchmarkDecodeTwainDefault1e5          37.12        55.65    1.50x
BenchmarkDecodeTwainDefault1e6          39.28        58.16    1.48x
BenchmarkDecodeTwainCompress1e4         28.64        44.90    1.57x
BenchmarkDecodeTwainCompress1e5         37.40        55.98    1.50x
BenchmarkDecodeTwainCompress1e6         39.35        58.06    1.48x

R=rsc, dave, minux.ma, bradfitz, nigeltao
CC=golang-dev
https://golang.org/cl/6872063

変更の背景

このコミットの主な目的は、Go言語のcompress/flateパッケージにおけるDEFLATEデータの伸長（inflate）性能を向上させることです。既存のハフマンデコード処理がボトルネックとなっており、特に大量のデータを扱う際にパフォーマンスの低下が顕著でした。コミットメッセージに示されているベンチマーク結果からもわかるように、この変更によって約1.5倍の速度向上が見込まれています。これは、データ圧縮・伸長が多用されるネットワーク通信やファイルI/Oにおいて、アプリケーション全体の応答性向上に直結する重要な改善です。

前提知識の解説

DEFLATE圧縮アルゴリズム

DEFLATEは、LZ77アルゴリズムとハフマン符号化を組み合わせた可逆データ圧縮アルゴリズムです。RFC 1951で定義されており、ZIP、gzip、PNGなどのファイル形式で広く利用されています。

• LZ77 (Lempel-Ziv 1977): 繰り返し出現するバイト列（シーケンス）を、以前に出現した同じシーケンスへの「参照」（長さと距離のペア）に置き換えることでデータを圧縮します。これにより、冗長なデータの繰り返しを効率的に削減します。
• ハフマン符号化 (Huffman Coding): LZ77によって生成されたリテラルバイト（圧縮されていないバイト）と長さ/距離のペアを、出現頻度に基づいて可変長のビット列に変換するエントロピー符号化の一種です。出現頻度の高いシンボルには短いビット列を、低いシンボルには長いビット列を割り当てることで、全体のデータサイズを削減します。DEFLATEでは、リテラル/長さ符号と距離符号の2種類のハフマンツリーが使用されます。

ハフマン符号のデコード

ハフマン符号は可変長であるため、デコードには特別な処理が必要です。ビットストリームからビットを読み込み、現在のビット列がどのハフマン符号に対応するかを判断します。

従来の単純なデコード方法では、ビットを1ビットずつ読み込み、ハフマンツリーを辿ってシンボルを特定します。しかし、これは多くのCPUサイクルを消費する可能性があります。

zlibのハフマンデコード実装

zlibは、DEFLATEアルゴリズムの最も広く使われている実装の一つです。zlibのハフマンデコードは、パフォーマンスを重視して最適化されています。その主要な最適化の一つが、**ルックアップテーブル（lookup table）**の使用です。

zlibのデコーダは、入力ビットストリームから一度に複数のビット（例えば、9ビットや10ビット）を読み込み、そのビット列をインデックスとしてルックアップテーブルを参照します。このテーブルのエントリには、対応するハフマンシンボル、そのシンボルのビット長、そして必要であれば次のルックアップテーブルへのポインタ（オーバーフローテーブルへのリンク）が含まれています。

• 単一テーブルルックアップ: 短いハフマン符号（テーブルのビット幅以下の長さの符号）は、1回のテーブル参照で直接デコードできます。
• オーバーフローテーブル: 長いハフマン符号（テーブルのビット幅を超える長さの符号）の場合、最初のルックアップでは部分的な情報しか得られません。テーブルエントリは、さらにビットを読み込んで別の（オーバーフロー）テーブルを参照する必要があることを示します。これにより、複数回のテーブル参照が必要になることもありますが、それでも1ビットずつツリーを辿るよりもはるかに高速です。

このアプローチにより、CPUの分岐予測ミスを減らし、キャッシュ効率を向上させ、全体的なデコード速度を大幅に向上させることができます。

技術的詳細

このコミットは、Goのcompress/flateパッケージのハフマンデコーダを、zlibの実装に倣ってルックアップテーブルベースの方式に移行することで、inflateのパフォーマンスを向上させています。

変更の核心は、huffmanDecoder構造体と、それを利用するhuffSymデコード関数にあります。

1. huffmanDecoder構造体の変更:

   • 従来のmin, max, limit, base, codesといった配列ベースの構造から、min, chunks, links, linkMaskというルックアップテーブルベースの構造に変わりました。
   • chunksは、固定ビット幅（huffmanChunkBits、このコミットでは9ビット）の初期ルックアップテーブルです。各エントリは、シンボルの値とビット長を含みます。
   • linksは、huffmanChunkBitsを超える長さのハフマン符号をデコードするためのオーバーフローテーブルへのポインタの配列です。
   • linkMaskは、オーバーフローテーブルのインデックス計算に使用されます。

2. init関数の変更:

   • ハフマン符号のビット長配列（bits）から、新しいhuffmanDecoder構造体（chunksとlinks）を構築するロジックが完全に書き直されました。
   • この関数は、各ビット長に対応するコードの数を数え、最小・最大ビット長を特定します。
   • huffmanChunkBitsを超える長さのコードが存在する場合、オーバーフローテーブル（links）が作成されます。
   • 各ハフマン符号について、その符号に対応するビット列を反転させ、ルックアップテーブルの適切な位置にシンボル情報（値とビット長）を格納します。短いコードは複数のエントリを占有し、長いコードはオーバーフローテーブルへのリンクを介して処理されます。

3. huffSymデコード関数の変更:

   • 従来の1ビットずつ読み込み、limitとbase配列を使ってシンボルを特定するループ処理から、新しいルックアップテーブルベースのデコードロジックに変わりました。
   • まず、入力ストリームからhuffmanChunkBits分のビットを読み込み、chunksテーブルを直接参照します。
   • 参照結果から、シンボルのビット長（n）と値（chunk >> huffmanValueShift）を取得します。
   • もしnがhuffmanChunkBitsより大きい場合（つまり、最初のルックアップでシンボルが完全に特定できなかった場合）、linksテーブル（オーバーフローテーブル）を参照して残りのビットをデコードします。
   • この「単一テーブルルックアップ」と「必要に応じて追加ビットを読み込む」アプローチにより、デコードに必要なCPU命令数が大幅に削減され、パフォーマンスが向上します。

4. fixedhuff.goとgen.goの導入:

   • DEFLATEアルゴリズムで定義されている固定ハフマン符号（Fixed Huffman Codes）は、事前に計算して静的に埋め込むことで、実行時の初期化コストを削減できます。
   • gen.goは、この固定ハフマン符号のルックアップテーブルを生成するためのGoプログラムです。go generateコマンドなどで実行され、fixedhuff.goというソースファイルを自動生成します。
   • fixedhuff.goには、fixedHuffmanDecoderというhuffmanDecoder型の変数が定義されており、これが固定ハフマン符号のデコードに使用される静的なルックアップテーブルとなります。これにより、実行時に毎回テーブルを構築する必要がなくなり、起動時性能が向上します。

これらの変更により、Goのcompress/flateパッケージは、zlibのような高性能なDEFLATE伸長処理を実現しています。

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

このコミットでは、以下の4つのファイルが変更されています。

1. src/pkg/compress/flate/fixedhuff.go (新規追加)

   • gen.goによって自動生成されるファイルで、固定ハフマン符号のデコードに使用される静的なhuffmanDecoderテーブルが定義されています。

2. src/pkg/compress/flate/flate_test.go (変更)

   • 主にテストコードの削除が行われています。以前のhuffmanDecoderのテストや、fixedHuffmanBitsなどの古い定数が削除されました。これは、新しいデコードロジックとテーブル構造に合わせたテストの再構築が必要になったためと考えられます。

3. src/pkg/compress/flate/gen.go (新規追加)

   • fixedhuff.goを生成するためのGoプログラムです。
   • huffmanDecoder構造体の定義の一部が、このファイルにもコピーされています（inflate.goと共有）。
   • main関数内で、固定ハフマン符号のビット長配列を定義し、huffmanDecoder.initを呼び出してテーブルを構築し、その結果をGoのソースコードとして標準出力に出力します。

4. src/pkg/compress/flate/inflate.go (変更)

   • DEFLATE伸長処理の主要なロジックが含まれるファイルです。
   • huffmanDecoder構造体の定義が大幅に変更され、ルックアップテーブルベースの新しい構造になりました。
   • huffmanDecoder.init関数の実装が、新しいテーブル構築ロジックに合わせて完全に書き直されました。
   • huffSym関数（ハフマンシンボルをデコードする関数）のロジックが、新しいルックアップテーブルを利用するように変更されました。

コアとなるコードの解説

src/pkg/compress/flate/inflate.goにおけるhuffmanDecoderとhuffSymの変更

変更前のhuffmanDecoder構造体（概念）:

type huffmanDecoder struct {
	min, max int
	limit    [maxCodeLen + 1]int // 各ビット長における最大コード値
	base     [maxCodeLen + 1]int // 各ビット長における最小コード値からのオフセット
	codes    []int               // シーケンス番号から出力コードへのマッピング
}

変更前は、limitとbase配列を使って、読み込んだビット列がどのビット長の範囲に属するかを判断し、codes配列から対応するシンボルを検索していました。これは、ビットを1ビットずつ読み込みながらツリーを辿るような、比較的線形的な検索アプローチでした。

変更後のhuffmanDecoder構造体:

const (
	huffmanChunkBits  = 9 // 初期ルックアップテーブルのビット幅
	huffmanNumChunks  = 1 << huffmanChunkBits // チャンク数 (512)
	huffmanCountMask  = 15 // ビット長を抽出するためのマスク
	huffmanValueShift = 4  // 値を抽出するためのシフト量
)

type huffmanDecoder struct {
	min      int                      // 最小コード長
	chunks   [huffmanNumChunks]uint32 // 初期ルックアップテーブル
	links    [][]uint32               // オーバーフローテーブルへのリンク
	linkMask uint32                   // リンクテーブルのマスク
}

新しいhuffmanDecoderは、zlibの設計思想を取り入れています。

• chunks: 入力ストリームから最初のhuffmanChunkBits（9ビット）を読み込み、この配列をインデックスとして参照します。各uint32エントリは、下位4ビットにシンボルのビット長、上位ビットにシンボルの値（またはオーバーフローテーブルへのオフセット）を格納します。
• links: huffmanChunkBitsを超える長さのハフマン符号をデコードするための補助的なルックアップテーブルです。

変更後のhuffSym関数（抜粋）:

func (f *decompressor) huffSym(h *huffmanDecoder) (int, error) {
	n := uint(h.min) // 最小ビット長から開始
	for {
		for f.nb < n { // 必要なビット数が足りない場合、さらにビットを読み込む
			if err := f.moreBits(); err != nil {
				return 0, err
			}
		}
		
		// 最初のルックアップ: 現在のバッファの先頭huffmanChunkBits分を使ってchunksテーブルを参照
		chunk := h.chunks[f.b&(huffmanNumChunks-1)]
		n = uint(chunk & huffmanCountMask) // チャンクからビット長を取得

		if n > huffmanChunkBits { // ビット長がhuffmanChunkBitsより大きい場合、オーバーフローテーブルを参照
			// chunksエントリの上位ビットからリンクテーブルのオフセットを取得し、
			// さらにバッファの残りのビットを使ってlinksテーブルを参照
			chunk = h.links[chunk>>huffmanValueShift][(f.b>>huffmanChunkBits)&h.linkMask]
			n = uint(chunk & huffmanCountMask) // オーバーフローテーブルから最終的なビット長を取得
		}
		
		if n <= f.nb { // 必要なビット数がバッファにある場合
			f.b >>= n   // バッファからビットを消費
			f.nb -= n
			return int(chunk >> huffmanValueShift), nil // シンボルの値を返す
		}
	}
	// ... エラーハンドリング ...
}

この新しいhuffSym関数は、まずhuffmanChunkBits分のビットを使ってchunksテーブルをルックアップします。

• もしシンボルがhuffmanChunkBits以下の長さであれば、1回のルックアップでシンボルが特定され、その値とビット長が返されます。
• もしシンボルがhuffmanChunkBitsより長い場合、chunksテーブルのエントリはオーバーフローテーブル（links）へのポインタを含んでいます。この場合、さらにビットを読み込み、linksテーブルをルックアップすることでシンボルを特定します。

この方式は、多くのハフマン符号が短いビット長を持つという特性を活かし、ほとんどのデコードを1〜2回のメモリ参照で完了させることで、大幅な高速化を実現しています。

src/pkg/compress/flate/gen.goの役割

gen.goは、Goのgo generateツールと組み合わせて使用されるコード生成スクリプトです。その主な目的は、DEFLATEの固定ハフマン符号のためのルックアップテーブルを事前に計算し、Goのソースコードとしてfixedhuff.goに出力することです。

// +build ignore

// This program generates fixedhuff.go
// Invoke as
//
//      go run gen.go |gofmt >fixedhuff.go

このコメントが示すように、gen.goは通常のビルドプロセスには含まれず、開発者が手動で実行するか、go generateを通じて実行されます。

main関数内では、固定ハフマン符号のビット長がRFC 1951に従って定義され、huffmanDecoder.initメソッドが呼び出されて、その固定符号に対応するchunksテーブルが構築されます。最終的に、この構築されたテーブルの内容がGoのコードとして整形され、標準出力に書き出されます。この出力がfixedhuff.goファイルとして保存されるわけです。

これにより、compress/flateパッケージがビルドされる際に、固定ハフマン符号のデコードテーブルがコンパイル済みのバイナリに静的に埋め込まれるため、実行時にテーブルを動的に構築するオーバーヘッドがなくなります。

関連リンク

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

参考にした情報源リンク

• RFC 1951 - DEFLATE Compressed Data Format Specification version 1.3: https://www.ietf.org/rfc/rfc1951.txt
• zlib Home Site: https://www.zlib.net/
• Huffman coding - Wikipedia: https://en.wikipedia.org/wiki/Huffman_coding
• DEFLATE - Wikipedia: https://en.wikipedia.org/wiki/DEFLATE
• Go compress/flate package documentation: https://pkg.go.dev/compress/flate
• (Web検索結果に基づく一般的なハフマンデコードとzlib実装に関する情報)