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

このコミットは、Go言語の標準ライブラリ compress/bzip2 パッケージにおけるデコード処理の高速化を目的としています。特に、ビット読み取りの最適化と、Move-to-Front (MTF) 変換で使用されるデータ構造の改善により、全体的なデコード性能が大幅に向上しています。ベンチマーク結果では、デコード速度が約25〜26%向上し、スループットが1.35〜1.36倍に改善されたことが示されています。

コミット

commit 394706b646c31ec129d0cdedc3b8eb09897322c0
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Mon Jun 3 20:38:00 2013 +0200

    compress/bzip2: faster decoding.
    
    benchmark                old ns/op    new ns/op    delta
    BenchmarkDecodeDigits     19451173     14347829  -26.24%
    BenchmarkDecodeTwain      57516800     42619978  -25.90%
    
    benchmark                 old MB/s     new MB/s  speedup
    BenchmarkDecodeDigits         2.22         3.01    1.36x
    BenchmarkDecodeTwain          2.17         2.93    1.35x
    
    R=golang-dev, dave, bradfitz, agl
    CC=golang-dev
    https://golang.org/cl/9915043

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

https://github.com/golang/go/commit/394706b646c31ec129d0cdcdedc3b8eb09897322c0

元コミット内容

compress/bzip2: faster decoding.

benchmark                old ns/op    new ns/op    delta
BenchmarkDecodeDigits     19451173     14347829  -26.24%
BenchmarkDecodeTwain      57516800     42619978  -25.90%

benchmark                 old MB/s     new MB/s  speedup
BenchmarkDecodeDigits         2.22         3.01    1.36x
BenchmarkDecodeTwain          2.17         2.93    1.35x

R=golang-dev, dave, bradfitz, agl
CC=golang-dev
https://golang.org/cl/9915043

変更の背景

compress/bzip2 パッケージは、Bzip2圧縮形式のデータをデコードするためのGo言語の標準ライブラリです。圧縮・解凍ライブラリの性能は、多くのアプリケーション、特にデータ転送やストレージを扱うシステムにおいて非常に重要です。デコード処理はCPUバウンドな操作であり、その効率はシステム全体のパフォーマンスに直結します。

このコミットの背景には、既存のBzip2デコーダの性能ボトルネックを解消し、より高速なデコードを実現するという明確な目標がありました。特に、ビット単位の読み取り操作や、Move-to-Front変換におけるデータ構造のアクセスパターンが、最適化の余地があると考えられました。ベンチマーク結果が示すように、この変更はデコード速度を大幅に向上させ、実用的なアプリケーションにおけるBzip2の利用効率を高めることに成功しています。

前提知識の解説

このコミットの変更内容を理解するためには、以下の技術的な概念を把握しておく必要があります。

1. Bzip2圧縮アルゴリズム:

   • Bzip2は、ブロックソート（Burrows-Wheeler Transform, BWT）、Move-to-Front (MTF) 変換、ランレングス符号化 (RLE)、ハフマン符号化を組み合わせたブロックベースの圧縮アルゴリズムです。
   • Burrows-Wheeler Transform (BWT): データを可逆的に変換し、同じ文字が連続して出現する傾向を高めます。これにより、後続の圧縮段階で高い圧縮率が得られます。
   • Move-to-Front (MTF) 変換: BWTの出力に対して適用されます。最近使用されたシンボルをリストの先頭に移動させることで、シンボルの出現頻度を偏らせ、小さな数値で表現されやすくします。これにより、ハフマン符号化の効率が向上します。
   • ハフマン符号化: MTF変換の出力に対して適用される可変長符号化手法です。出現頻度の高いシンボルには短いビット列を、低いシンボルには長いビット列を割り当てることで、データ全体のビット数を削減します。

2. ビットストリームの読み取り:

   • 圧縮データは通常、バイト単位ではなくビット単位で処理されます。デコーダは、入力ストリームから正確な数のビットを効率的に読み取る必要があります。この操作は非常に頻繁に行われるため、その性能がデコード速度に大きく影響します。

3. Go言語のデータ構造とメモリ管理:

   • スライス ([]T): Go言語における可変長シーケンスです。内部的には、配列へのポインタ、長さ、容量を持ちます。スライスへのアクセスは、基盤となる配列への間接参照を伴います。
   • 配列 ([N]T): Go言語における固定長シーケンスです。コンパイル時にサイズが決定され、通常はスタックに直接割り当てられるか、ヒープに割り当てられても連続したメモリブロックを占有します。スライスに比べて、間接参照が少なく、キャッシュ効率が良い場合があります。
   • ヒープアロケーションとガベージコレクション (GC): スライスのように動的にサイズが変更されるデータ構造は、ヒープにメモリを割り当てることが多く、その結果、ガベージコレクションの対象となります。GCの頻度や時間は、アプリケーションのパフォーマンスに影響を与える可能性があります。固定長配列を使用することで、ヒープアロケーションを減らし、GCのオーバーヘッドを削減できる場合があります。

技術的詳細

このコミットにおけるデコード高速化の主要な技術的アプローチは以下の2点です。

1. ビットリーダーの最適化 (bit_reader.go, huffman.go):

   • TryReadBit() の導入: bitReader 構造体に TryReadBit() という新しいメソッドが追加されました。このメソッドは、内部バッファにビットが残っている場合にのみビットを読み取り、成功したかどうかを示す ok フラグを返します。これにより、ビットがバッファに存在するかどうかのチェックと読み取りを単一の操作で効率的に行えます。
   • ハフマンデコードでの活用: ハフマンデコードは、圧縮データからシンボルを復元するために、非常に頻繁にビットを1つずつ読み取る必要があります。以前は ReadBit() メソッドが直接呼び出されていましたが、これは内部バッファが空の場合に refill() 処理（入力ストリームからの読み込みとエラーチェック）をトリガーする可能性がありました。
   • 新しい実装では、まず TryReadBit() を試みます。これにより、バッファにビットが残っている限り、refill() の呼び出しや関連するエラーチェックのオーバーヘッドを回避できます。TryReadBit() が失敗した場合（バッファが空の場合）にのみ、従来の ReadBit() を呼び出してバッファを補充し、ビットを読み取ります。この「高速パス」の導入により、頻繁なビット読み取り操作のレイテンシが削減され、全体的なデコード速度が向上します。

2. Move-to-Front (MTF) デコーダのデータ構造最適化 (move_to_front.go):

   • スライスから固定長配列への変更: moveToFrontDecoder 構造体内の symbols, next, prev フィールドが、可変長スライス ([]byte, []uint8) から固定長配列 ([256]byte, [256]uint8) に変更されました。
   • なぜ256か？: Bzip2のMTF変換は、256種類のシンボル（バイト値0〜255）を扱います。したがって、これらの配列の最大サイズは常に256です。
   • 性能上の利点:
     • ヒープアロケーションの削減: 固定長配列は、通常、スタックに直接割り当てられるか、ヒープに割り当てられても連続したメモリブロックを占有します。これにより、デコーダの初期化時や実行中に動的なメモリ割り当て（ヒープアロケーション）が不要になり、ガベージコレクションの頻度とオーバーヘッドが削減されます。
     • キャッシュ効率の向上: 固定長配列はメモリ上で連続して配置されるため、CPUのキャッシュに乗りやすくなります。これにより、データアクセス時のキャッシュミスが減少し、メモリからのデータ読み込みが高速化されます。
     • 間接参照の削減: スライスは基盤となる配列へのポインタを介してアクセスされますが、固定長配列は直接アクセスできるため、間接参照のオーバーヘッドがわずかに削減されます。
   • len フィールドの追加: MTFデコーダが実際に使用するシンボル数が256未満の場合に対応するため、len int フィールドが追加され、配列の有効な長さを追跡するようになりました。これにより、配列の固定サイズと、実際に使用されるシンボル数の柔軟性を両立させています。

これらの変更は、デコード処理のホットパスにおけるCPUサイクルとメモリアクセスの効率を向上させることで、ベンチマークで示された顕著な性能向上を実現しています。

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

このコミットで変更された主要なファイルとコードスニペットは以下の通りです。

1. src/pkg/compress/bzip2/bit_reader.go:

   • TryReadBit() メソッドの追加。

   --- a/src/pkg/compress/bzip2/bit_reader.go
   +++ b/src/pkg/compress/bzip2/bit_reader.go
   @@ -77,6 +77,14 @@ func (br *bitReader) ReadBit() bool {
    	return n != 0
    }
    
   +func (br *bitReader) TryReadBit() (bit byte, ok bool) {
   +\tif br.bits > 0 {
   +\t\tbr.bits--
   +\t\treturn byte(br.n>>br.bits) & 1, true
   +\t}\
   +\treturn 0, false
   +}
   +
    func (br *bitReader) Err() error {
    	return br.err
    }
   

2. src/pkg/compress/bzip2/huffman.go:

   • huffmanTree.Decode メソッドのレシーバをポインタに変更 (huffmanTree から *huffmanTree)。
   • TryReadBit() を使用するようにデコードロジックを変更。

   --- a/src/pkg/compress/bzip2/huffman.go
   +++ b/src/pkg/compress/bzip2/huffman.go
   @@ -33,14 +33,17 @@ const invalidNodeValue = 0xffff
    
    // Decode reads bits from the given bitReader and navigates the tree until a
    // symbol is found.
   -func (t huffmanTree) Decode(br *bitReader) (v uint16) {
   +func (t *huffmanTree) Decode(br *bitReader) (v uint16) {
     	nodeIndex := uint16(0) // node 0 is the root of the tree.
     
     	for {
     		node := &t.nodes[nodeIndex]
   -		bit := br.ReadBit()
   +		bit, ok := br.TryReadBit()
   +		if !ok && br.ReadBit() {
   +			bit = 1
   +		}
     		// bzip2 encodes left as a true bit.
   -		if bit {
   +		if bit != 0 {
     			// left
     			if node.left == invalidNodeValue {
     				return node.leftValue
   

3. src/pkg/compress/bzip2/move_to_front.go:

   • moveToFrontDecoder 構造体のフィールドをスライスから固定長配列に変更。
   • len フィールドの追加。
   • 関連する初期化およびループ処理の変更。

   --- a/src/pkg/compress/bzip2/move_to_front.go
   +++ b/src/pkg/compress/bzip2/move_to_front.go
   @@ -15,10 +15,11 @@ type moveToFrontDecoder struct {
     	// Rather than actually keep the list in memory, the symbols are stored
     	// as a circular, double linked list with the symbol indexed by head
     	// at the front of the list.
   -	symbols []byte
   -	next    []uint8
   -	prev    []uint8
   +	symbols [256]byte
   +	next    [256]uint8
   +	prev    [256]uint8
     	head    uint8
   +	len     int
     }
     
     // newMTFDecoder creates a move-to-front decoder with an explicit initial list
   @@ -28,12 +29,9 @@ func newMTFDecoder(symbols []byte) *moveToFrontDecoder {
     		panic("too many symbols")
     	}
     
   -	m := &moveToFrontDecoder{
   -		symbols: symbols,
   -		next:    make([]uint8, len(symbols)),
   -		prev:    make([]uint8, len(symbols)),
   -	}
   -
   +	m := new(moveToFrontDecoder)
   +	copy(m.symbols[:], symbols)
   +	m.len = len(symbols)
     	m.threadLinkedList()
     	return m
     }
   @@ -45,34 +43,29 @@ func newMTFDecoderWithRange(n int) *moveToFrontDecoder {
     		panic("newMTFDecoderWithRange: cannot have > 256 symbols")
     	}
     
   -	m := &moveToFrontDecoder{
   -		symbols: make([]uint8, n),
   -		next:    make([]uint8, n),
   -		prev:    make([]uint8, n),
   -	}
   -
   +	m := new(moveToFrontDecoder)
     	for i := 0; i < n; i++ {\n-		m.symbols[i] = byte(i)
   +		m.symbols[byte(i)] = byte(i)
     	}
   -\n+	m.len = n
     	m.threadLinkedList()
     	return m
     }
     
     // threadLinkedList creates the initial linked-list pointers.
     func (m *moveToFrontDecoder) threadLinkedList() {
   -	if len(m.symbols) == 0 {
   +	if m.len == 0 {
     		return
     	}
     
   -	m.prev[0] = uint8(len(m.symbols) - 1)
   +	m.prev[0] = uint8(m.len - 1)
     
   -	for i := 0; i < len(m.symbols)-1; i++ {
   +	for i := byte(0); int(i) < m.len-1; i++ {
     		m.next[i] = uint8(i + 1)
     		m.prev[i+1] = uint8(i)
     	}
     
   -	m.next[len(m.symbols)-1] = 0
   +	m.next[m.len-1] = 0
     }
     
     func (m *moveToFrontDecoder) Decode(n int) (b byte) {
   

4. src/pkg/compress/bzip2/bzip2_test.go:

   • 新しいベンチマークテストデータ (e.txt.bz2, Mark.Twain-Tom.Sawyer.txt.bz2) の追加。
   • benchmarkDecode ヘルパー関数の追加。
   • BenchmarkDecodeDigits と BenchmarkDecodeTwain ベンチマーク関数の追加。

   --- a/src/pkg/compress/bzip2/bzip2_test.go
   +++ b/src/pkg/compress/bzip2/bzip2_test.go
   @@ -155,3 +155,32 @@ const rand2Hex = "92d5652616ac444a4a04af1a8a3964aca0450d43d6cf233bd03233f4ba92f8
    
    const rand3BZ2Hex = "425a68393141592653593be669d00000327ffffffffffffffffffffffffffffffffffff7ffffffffffffffffffffffffffffffc002b3b2b1b6e2bae400004c00132300004c0d268c004c08c0130026001a008683234c0684c34008c230261a04c0260064d07a8d00034000d27a1268c9931a8d327a3427a41faa69ea0da264c1a34219326869b51b49a6469a3268c689fa53269a62794687a9a68f5189994c9e487a8f534fd49a3d34043629e8c93d04da4f4648d30d4f44d3234c4d3023d0840680984d309934c234d3131a000640984f536a6132601300130130c8d00d04d1841ea7a8d31a02609b40023460010c01a34d4c1a0d04d3069306810034d0d0d4c0046130d034d0131a9a64d321804c68003400098344c13000991808c0001a00000000098004d3d4da4604c47a13012140aadf8d673c922c607ef6212a8c0403adea4b28aee578900e653b9cdeb8d11e6b838815f3ebaad5a01c5408d84a332170aff8734d4e06612d3c2889f31925fb89e33561f5100ae89b1f7047102e729373d3667e58d73aaa80fa7be368a1cc2dadd81d81ec8e1b504bd772ca31d03649269b01ceddaca07bf3d4eba24de141be3f86f93601e03714c0f64654671684f9f9528626fd4e1b76753dc0c54b842486b8d59d8ab314e86ca818e7a1f079463cbbd70d9b79b283c7edc419406311022e4be98c2c1374df9cdde2d008ce1d00e5f06ad1024baf555631f70831fc1023034e62be7c4bcb648caf276963ffa20e96bb50377fe1c113da0db4625b50741c35a058edb009c6ee5dbf93b8a6b060eec568180e8db791b82aab96cbf4326ca98361461379425ba8dcc347be670bdba7641883e5526ae3d833f6e9cb9bac9557747c79e206151072f7f0071dff3880411846f66bf4075c7462f302b53cb3400a74cf35652ad5641ed33572fd54e7ed7f85f58a0acba89327e7c6be5c58cb71528b99df2431f1d0358f8d28d81d95292da631fb06701decabb205fac59ff0fb1df536afc681eece6ea658c4d9eaa45f1342aa1ff70bdaff2ddaf25ec88c22f12829a0553db1ec2505554cb17d7b282e213a5a2aa30431ded2bce665bb199d023840832fedb2c0c350a27291407ff77440792872137df281592e82076a05c64c345ffb058c64f7f7c207ef78420b7010520610f17e302cc4dfcfaef72a0ed091aab4b541eb0531bbe941ca2f792bf7b31ca6162882b68054a8470115bc2c19f2df2023f7800432b39b04d3a304e8085ba3f1f0ca5b1ba4d38d339e6084de979cdea6d0e244c6c9fa0366bd890621e3d30846f5e8497e21597b8f29bbf52c961a485dfbea647600da0fc1f25ce4d203a8352ece310c39073525044e7ac46acf2ed9120bae1b4f6f02364abfe343f80b... [truncated]
   
   const (
   	digits = iota
   	twain
   )
   
   var testfiles = []string{
   	// Digits is the digits of the irrational number e. Its decimal representation
   	// does not repeat, but there are only 10 posible digits, so it should be
   	// reasonably compressible.
   	digits: "testdata/e.txt.bz2",
   	// Twain is Project Gutenberg's edition of Mark Twain's classic English novel.
   	twain: "testdata/Mark.Twain-Tom.Sawyer.txt.bz2",
   }
   
   func benchmarkDecode(b *testing.B, testfile int) {
   	compressed, err := ioutil.ReadFile(testfiles[testfile])
   	if err != nil {
   		b.Fatal(err)
   	}
   	b.SetBytes(int64(len(compressed)))
   	for i := 0; i < b.N; i++ {
   		r := bytes.NewBuffer(compressed)
   		io.Copy(ioutil.Discard, NewReader(r))
   	}
   }
   
   func BenchmarkDecodeDigits(b *testing.B) { benchmarkDecode(b, digits) }
   func BenchmarkDecodeTwain(b *testing.B)  { benchmarkDecode(b, twain) }
   

コアとなるコードの解説

bit_reader.go の TryReadBit()

bitReader は、入力ストリームからビットを効率的に読み取るための構造体です。内部にビットバッファ (n と bits) を持ち、必要に応じて入力からバイトを読み込んでバッファを補充します。

TryReadBit() は、このバッファリングメカニズムを最大限に活用するための最適化です。

• if br.bits > 0: この条件は、現在バッファに読み取り可能なビットが残っているかどうかをチェックします。
• br.bits--: ビットが残っていれば、残りのビット数をデクリメントします。
• return byte(br.n>>br.bits) & 1, true: バッファ (br.n) から最上位ビットを抽出し、それを byte 型で返します。true は読み取りが成功したことを示します。
• return 0, false: バッファが空の場合、ビットを読み取らずに 0 と false を返します。

この関数は、バッファが空でない限り、refill() メソッドの呼び出し（これはI/O操作やエラーチェックを伴う可能性がある）を回避できるため、非常に高速なビット読み取りパスを提供します。

huffman.go の Decode メソッド

huffmanTree.Decode メソッドは、ハフマンツリーを辿ってビットストリームからシンボルをデコードします。このメソッドは、デコード処理の「ホットパス」であり、非常に頻繁に呼び出されます。

変更点：

1. レシーバの変更: func (t huffmanTree) Decode(...) から func (t *huffmanTree) Decode(...) へと、レシーバが値レシーバからポインタレシーバに変更されました。Decode メソッド自体は huffmanTree の状態を変更しませんが、ポインタレシーバを使用することで、メソッド呼び出し時の構造体のコピーが回避され、わずかながらパフォーマンスが向上する可能性があります。また、Goの慣習として、大きな構造体や、将来的に状態を変更する可能性がある構造体のメソッドにはポインタレシーバを使用することが推奨されます。
2. TryReadBit() の活用:

   		bit, ok := br.TryReadBit()
   		if !ok {
   			if br.ReadBit() {
   				bit = 1
   			} else {
   				bit = 0
   			}
   		}
   		// bzip2 encodes left as a true bit.
   		if bit != 0 {
   

   このコードブロックは、ビット読み取りの最適化の核心です。
   • まず br.TryReadBit() を呼び出し、バッファからビットを直接読み取ろうとします。
   • ok が false の場合（つまり、バッファが空で TryReadBit() が失敗した場合）、従来の br.ReadBit() を呼び出します。br.ReadBit() は必要に応じてバッファを補充し、読み取ったビットを bool 型で返します。
   • br.ReadBit() の結果（true または false）に基づいて、bit 変数（byte型）を 1 または 0 に設定します。
   • 最後に、if bit != 0 で読み取ったビットの値に基づいてハフマンツリーを辿ります。

このロジックにより、ほとんどの場合で高速な TryReadBit() パスが利用され、refill() 処理を伴う ReadBit() の呼び出しは、バッファが本当に空になった場合にのみ行われるようになります。

move_to_front.go の moveToFrontDecoder

moveToFrontDecoder は、Bzip2のMove-to-Front変換をデコードするための構造体です。この変換は、シンボルのリストを管理し、デコードされたシンボルをリストの先頭に移動させることで、後続のハフマン符号化の効率を高めます。

変更点：

• symbols, next, prev フィールド:
  • これらは、MTFリストのシンボルとそのリンクリスト構造を保持するための配列です。以前は []byte や []uint8 のスライスでしたが、[256]byte や [256]uint8 の固定長配列に変更されました。
  • Bzip2のMTF変換は常に256個の可能なシンボル（バイト値）を扱います。そのため、これらのデータ構造の最大サイズは常に256です。固定長配列を使用することで、これらのデータ構造のヒープアロケーションが完全に排除され、ガベージコレクションのオーバーヘッドが削減されます。また、メモリが連続して配置されるため、CPUキャッシュの効率が向上し、データアクセスが高速化されます。
• len フィールド:
  • int 型の len フィールドが追加されました。これは、MTFデコーダが実際に使用するシンボル数を追跡するために使用されます。Bzip2は、常に256個のシンボルすべてを使用するわけではないため、このフィールドは配列の固定サイズと、実際に使用されるシンボル数の間のギャップを埋めます。
• 初期化ロジックの変更:
  • newMTFDecoder および newMTFDecoderWithRange 関数は、新しい固定長配列の初期化に合わせて変更されました。make を使用してスライスを作成する代わりに、copy(m.symbols[:], symbols) のように配列の全体または一部をコピーしたり、直接配列要素に値を割り当てたりするようになりました。
• ループ処理の変更:
  • threadLinkedList のようなメソッド内のループは、len(m.symbols) の代わりに m.len を使用するように変更され、配列の有効な長さに合わせて処理が行われるようになりました。また、for i := byte(0); int(i) < m.len-1; i++ のように、インデックス変数 i を byte 型で宣言することで、配列のインデックスアクセスをより効率的に行えるようになっています。

これらの変更は、MTFデコード処理におけるメモリ割り当てとデータアクセスのオーバーヘッドを削減し、全体的なデコード性能に大きく貢献しています。

関連リンク

• Go言語の compress/bzip2 パッケージのドキュメント: https://pkg.go.dev/compress/bzip2
• Bzip2圧縮アルゴリズムに関するWikipedia記事: https://ja.wikipedia.org/wiki/Bzip2
• Burrows-Wheeler Transform (BWT) に関するWikipedia記事: https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%AD%E3%83%BC%E3%82%BA%E3%83%BB%E3%83%9B%E3%82%A4%E3%83%A9%E3%83%BC%E3%83%BB%E3%83%88%E3%83%A9%E3%83%B3%E3%82%B9%E3%83%95%E3%82%A9%E3%83%BC%E3%83%A0
• Move-to-Front Transform に関するWikipedia記事: https://en.wikipedia.org/wiki/Move-to-front_transform (日本語版は存在しないか、内容が少ない可能性があります)
• ハフマン符号化に関するWikipedia記事: https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E7%AC%A6%E5%8F%B7

参考にした情報源リンク

• Go言語のコミット履歴: https://github.com/golang/go/commits/master
• Go言語のコードレビューシステム (Gerrit): https://go.dev/cl/9915043 (コミットメッセージに記載されているCLリンク)
• Go言語のベンチマークに関するドキュメント: https://pkg.go.dev/testing#hdr-Benchmarks
• Go言語のメモリ管理とガベージコレクションに関する一般的な情報源 (例: Go公式ブログ、Go Conferenceの発表資料など)