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

このコミットは、Go言語のimage/jpegパッケージにおけるJPEG画像のハフマンデコード処理のパフォーマンスとメモリ効率を大幅に改善することを目的としています。具体的には、ハフマンデコードにルックアップテーブルを導入し、JPEG特有のバイトスタッフィングに対応するため、bufio.Readerの使用を廃止してデコーダが独自のバイトバッファリングを行うように変更しています。これにより、デコード速度が向上し、huffman構造体のメモリフットプリントが削減されました。

コミット

commit 4ecf0b103a3c0a21af9f397420c317a2f742103c
Author: Nigel Tao <nigeltao@golang.org>
Date:   Thu Jun 19 11:39:03 2014 +1000

    image/jpeg: use a look-up table to speed up Huffman decoding. This
    requires a decoder to do its own byte buffering instead of using
    bufio.Reader, due to byte stuffing.
    
    benchmark                      old MB/s     new MB/s     speedup
    BenchmarkDecodeBaseline        33.40        50.65        1.52x
    BenchmarkDecodeProgressive     24.34        31.92        1.31x
    
    On 6g, unsafe.Sizeof(huffman{}) falls from 4872 to 964 bytes, and
    the decoder struct contains 8 of those.
    
    LGTM=r
    R=r, nightlyone
    CC=bradfitz, couchmoney, golang-codereviews, raph
    https://golang.org/cl/109050045

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

https://github.com/golang/go/commit/4ecf0b103a3c0a21af9f397420c317a2f742103c

元コミット内容

image/jpeg: use a look-up table to speed up Huffman decoding. This
requires a decoder to do its own byte buffering instead of using
bufio.Reader, due to byte stuffing.

benchmark                      old MB/s     new MB/s     speedup
BenchmarkDecodeBaseline        33.40        50.65        1.52x
BenchmarkDecodeProgressive     24.34        31.92        1.31x

On 6g, unsafe.Sizeof(huffman{}) falls from 4872 to 964 bytes, and
the decoder struct contains 8 of those.

LGTM=r
R=r, nightlyone
CC=bradfitz, couchmoney, golang-codereviews, raph
https://golang.org/cl/109050045

変更の背景

JPEG画像のデコードにおいて、ハフマン符号のデコードは計算コストの高い処理の一つです。従来のGo言語のimage/jpegパッケージでは、ハフマンデコードがビットストリームから1ビットずつ読み取る比較的単純なアルゴリズムで実装されており、これがパフォーマンスのボトルネックとなっていました。特に、JPEGデータストリームには「バイトスタッフィング」という特殊なメカニズムが存在し、bufio.Readerのような汎用的なバッファリングリーダーでは、このバイトスタッフィングを適切に処理することが困難でした。

バイトスタッフィングとは、データ中にマーカーバイト（0xFF）と誤認される可能性のある0xFFバイトが出現した場合に、その直後に0x00バイトを挿入してエスケープするJPEGの仕様です。デコード時にはこの0x00バイトを読み飛ばす必要がありますが、bufio.Readerはバイトスタッフィングを意識しないため、デコーダ側で追加の複雑な処理が必要となり、効率が低下していました。

このコミットは、これらの課題を解決し、JPEGデコードの全体的なパフォーマンスを向上させることを目的としています。具体的には、ハフマンデコードを高速化するためにルックアップテーブルを導入し、バイトスタッフィングを効率的に処理するためにカスタムのバイトバッファリング機構を実装することで、デコード速度の向上とメモリ使用量の削減を実現しています。

前提知識の解説

JPEG形式の概要

JPEG (Joint Photographic Experts Group) は、主に写真などの自然画像を圧縮するための標準的な画像形式です。非可逆圧縮方式を採用しており、高い圧縮率と良好な画質を両立させます。JPEGのデコードプロセスは、主に以下のステップを含みます。

1. データストリームの解析: JPEGファイルは、マーカーと呼ばれる特別なバイトシーケンスで区切られたセグメントで構成されます。各セグメントは、画像に関するメタデータ（例: 画像の幅、高さ、色空間、量子化テーブル、ハフマンテーブルなど）や、圧縮された画像データを含みます。
2. 量子化解除 (Dequantization): 圧縮されたデータは、離散コサイン変換 (DCT) 係数として表現され、量子化されています。デコード時には、量子化テーブルを使用してこれらの係数を元のスケールに戻します。
3. 逆離散コサイン変換 (IDCT): 量子化解除されたDCT係数を空間ドメインのピクセルデータに変換します。
4. ハフマンデコード (Huffman Decoding): JPEGの圧縮データは、ハフマン符号化によってさらに圧縮されています。これは可変長符号化の一種で、出現頻度の高いデータには短い符号を、低いデータには長い符号を割り当てることで、データ量を削減します。デコード時には、ビットストリームからハフマン符号を読み取り、対応する元のデータ（DCT係数）に復元します。
5. 色空間変換: 通常、JPEGデータはYCbCr色空間で格納されているため、表示のためにRGB色空間に変換されます。

ハフマン符号化とデコード

ハフマン符号化は、データ圧縮によく用いられるエントロピー符号化の一種です。各シンボル（この場合はDCT係数）に、その出現頻度に基づいて可変長のビット列（ハフマンコード）を割り当てます。頻繁に出現するシンボルには短いコードが、稀にしか出現しないシンボルには長いコードが割り当てられます。

ハフマンデコードは、ビットストリームからビットを順次読み取り、現在のビット列がどのハフマンコードに一致するかを判断して元のシンボルを復元するプロセスです。単純な実装では、1ビットずつ読み取りながらハフマンツリーを辿ることでデコードを行いますが、これは多くのCPUサイクルを消費する可能性があります。

バイトスタッフィング (Byte Stuffing)

JPEGデータストリームでは、0xFFバイトは通常、セグメントの開始や終了を示すマーカーバイトとして使用されます。しかし、画像データ自体の中に0xFFバイトが出現する可能性もあります。この場合、データ中の0xFFバイトがマーカーと誤認されることを防ぐために、その直後に0x00バイトを挿入してエスケープします。これがバイトスタッフィングです。

例:

• データ ... 0xFF 0xD8 ... (SOIマーカー)
• データ ... 0xFF 0x00 ... (データ中の0xFFがエスケープされたもの)

デコード時には、0xFF 0x00というシーケンスを読み取った場合、0x00バイトを読み飛ばして、元のデータは0xFFであったと解釈する必要があります。この処理は、一般的なI/Oバッファリングライブラリ（例: Goのbufio.Reader）では直接サポートされていないため、デコーダが独自に処理する必要があります。

Go言語のimage/jpegパッケージ

Go言語の標準ライブラリには、JPEG画像のエンコードとデコードを扱うimage/jpegパッケージが含まれています。このパッケージは、JPEGの仕様に準拠した画像の読み書き機能を提供します。コミット前の実装では、bufio.Readerを使用して入力ストリームをバッファリングし、ハフマンデコードはビット単位で処理されていました。

ルックアップテーブル (Look-up Table)

ルックアップテーブルは、計算コストの高い処理を高速化するためのデータ構造です。事前に計算された結果をテーブルに格納しておき、実行時には入力値に対応する結果をテーブルから直接参照することで、計算を省略します。ハフマンデコードにおいては、ビットストリームの先頭から数ビットを読み取り、そのビット列に対応するハフマンコードの長さとデコードされた値をルックアップテーブルに格納しておくことで、ツリーを辿る処理を大幅に削減できます。

技術的詳細

このコミットの主要な変更点は、ハフマンデコードの高速化と、バイトスタッフィングへの対応のためのカスタムバイトバッファリングの導入です。

ハフマンデコーダの変更 (huffman.go)

1. huffman構造体の変更:

   • 従来のl, val, size, code, minCode, maxCode, valIndexといったフィールドに加えて、lut (look-up table) フィールドが追加されました。
   • lutは[1 << lutSize]uint16型で、lutSizeは8に設定されています。これは、ビットストリームの先頭8ビットをルックアップキーとして使用することを意味します。
   • lutの各エントリはuint16型で、上位8ビットがデコードされた値、下位8ビットが1 + コード長（または、ルックアップテーブルの範囲を超える場合は0）を表します。
   • minCode, maxCode, valIndexの型がintからint32に変更され、メモリフットプリントの削減に貢献しています。コミットメッセージにあるように、huffman{}構造体のサイズが4872バイトから964バイトに大幅に減少しました。これは、decoder構造体が8つのhuffmanインスタンスを持つため、全体的なメモリ使用量に大きな影響を与えます。

2. processDHT関数の変更:

   • DHT (Define Huffman Table) マーカーを処理する際に、新しいhuffman構造体のlutフィールドを構築するロジックが追加されました。
   • このロジックは、各ハフマンコードの長さと値に基づいて、ビットストリームの先頭lutSizeビットに対応するデコード結果をlutに事前計算して格納します。

3. decodeHuffman関数の変更:

   • ハフマンデコードのメインロジックが変更され、ルックアップテーブルを使用した高速パスが導入されました。
   • まず、d.bits.n（バッファリングされたビット数）がlutSize（8ビット）以上あるかを確認します。
   • もし十分なビットがあれば、h.lut[(d.bits.a>>uint32(d.bits.n-lutSize))&0xff]という式でルックアップテーブルを参照します。これにより、ビットストリームの先頭8ビットに対応するデコード結果（値とコード長）を直接取得できます。
   • ルックアップテーブルで結果が見つかった場合（v != 0）、その結果を使用して高速にデコードを完了します。
   • ルックアップテーブルで結果が見つからない場合（コード長がlutSizeを超える場合など）、または十分なビットがない場合は、従来の1ビットずつ読み取る「slowPath」にフォールバックします。

4. ensureNBits関数の変更:

   • ビットストリームから必要なビット数を確保するこの関数は、バイトスタッフィングを考慮したd.readByteStuffedByte()を呼び出すように変更されました。これにより、bufio.Readerを使用せずに、デコーダ自身がバイトスタッフィングを処理できるようになります。

カスタムバイトバッファリングの導入 (reader.go)

1. decoder構造体の変更:

   • bufio.Readerの代わりに、bytesという新しいフィールドがdecoder構造体に追加されました。
   • bytesは、buf ([4096]byteの固定長バッファ)、i, j (バッファ内の読み取り/書き込みポインタ)、nUnreadable (アンリード可能なバイト数) を持ちます。これは、bufio.Readerと同様のバッファリング機能を提供しますが、バイトスタッフィングの処理に特化しています。

2. 新しいバイト読み込みヘルパー関数の追加:

   • fill(): d.bytes.bufを基になるio.Readerからバイトで満たします。bufio.Readerのfillに相当しますが、アンリードのために最後の2バイトをバッファの先頭に移動するロジックが含まれています。
   • readByte(): バッファから次の1バイトを読み取ります。バイトスタッフィングは考慮しません。
   • readByteStuffedByte(): バイトスタッフィングを考慮して次の1バイトを読み取ります。0xFF 0x00シーケンスを検出した場合、0x00を読み飛ばして0xFFを返します。これは、JPEGデコードにおいて非常に重要な関数です。
   • unreadByteStuffedByte(): readByteStuffedByte()で読み取ったバイトをバッファに戻します。ハフマンルックアップテーブルがオーバーシュートして余分なバイトを読み取ってしまった場合に、そのバイトを元に戻すために使用されます。
   • readFull(p []byte): io.ReadFullと同様に、指定されたバイト数だけ読み取ります。カスタムバッファを使用するように変更されました。
   • ignore(n int): 指定されたバイト数だけ読み飛ばします。カスタムバッファを使用するように変更されました。

3. bufio.Readerの削除:

   • decoder.decode関数からbufio.Readerの初期化と使用が完全に削除され、カスタムバッファリング機構に置き換えられました。

その他の変更 (scan.go, writer.go, reader_test.go)

• scan.goでは、ハフマンデコードの呼び出し箇所が新しいdecodeHuffman関数とhuffman構造体の変更に合わせて更新されました。また、d.b（古いビットバッファ）がd.bits（新しいビットバッファ）に置き換えられました。
• writer.goでは、コメントの修正のみが行われています。
• reader_test.goでは、不要な空行が削除されたのみで、機能的な変更はありません。

性能向上とメモリ削減

コミットメッセージに記載されているベンチマーク結果は、この変更の有効性を示しています。

• BenchmarkDecodeBaseline: 33.40 MB/s から 50.65 MB/s へ (1.52倍高速化)
• BenchmarkDecodeProgressive: 24.34 MB/s から 31.92 MB/s へ (1.31倍高速化)

これらの速度向上は、主にハフマンデコードにおけるルックアップテーブルの導入によるものです。また、huffman構造体のサイズが4872バイトから964バイトに削減されたことで、デコーダが複数のハフマンテーブルを持つ場合のメモリ使用量が大幅に削減されました。

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

このコミットにおけるコアとなるコードの変更は、主に以下のファイルに集中しています。

1. src/pkg/image/jpeg/huffman.go:

   • huffman構造体の定義変更（lutフィールドの追加、既存フィールドの型変更）。
   • processDHT関数におけるlutの構築ロジックの追加。
   • decodeHuffman関数におけるルックアップテーブルを使用した高速パスの導入と、フォールバックとしてのスローパスの維持。
   • ensureNBits関数がd.readByteStuffedByte()を呼び出すように変更。

2. src/pkg/image/jpeg/reader.go:

   • decoder構造体からbufio.Reader関連のフィールドを削除し、カスタムバイトバッファリング用のbytesフィールドを追加。
   • fill(), readByte(), readByteStuffedByte(), unreadByteStuffedByte(), readFull(), ignore()といったカスタムバイトバッファリングおよびバイトスタッフィング処理のためのヘルパー関数の追加。
   • decode関数からbufio.Readerの使用を削除し、カスタムバッファリングに切り替え。

3. src/pkg/image/jpeg/scan.go:

   • ハフマンデコードの呼び出し箇所が、新しいhuffman構造体とdecodeHuffman関数のシグネチャに合わせて更新。
   • ビットバッファリングの参照がd.bからd.bitsに変更。

コアとなるコードの解説

huffman構造体とルックアップテーブル (lut)

type huffman struct {
	// length is the number of codes in the tree.
	nCodes int32
	// lut is the look-up table for the next lutSize bits in the bit-stream.
	// The high 8 bits of the uint16 are the encoded value. The low 8 bits
	// are 1 plus the code length, or 0 if the value is too large to fit in
	// lutSize bits.
	lut [1 << lutSize]uint16 // lutSize is 8, so [256]uint16
	// vals are the decoded values, sorted by their encoding.
	vals [maxNCodes]uint8 // maxNCodes is 256
	// minCodes[i] is the minimum code of length i, or -1 if there are no
	// codes of that length.
	minCodes [maxCodeLength]int32 // maxCodeLength is 16
	// maxCodes[i] is the maximum code of length i, or -1 if there are no
	// codes of that length.
	maxCodes [maxCodeLength]int32
	// valsIndices[i] is the index into vals of minCodes[i].
	valsIndices [maxCodeLength]int32
}

huffman構造体に追加されたlutフィールドは、ハフマンデコードの高速化の鍵です。lutSizeが8であるため、lutは256エントリの配列となります。各エントリlut[i]は、ビットストリームの先頭8ビットがiである場合に、その8ビットでデコードできるハフマンコードの情報を含みます。

• uint16の上位8ビット (v >> 8) は、デコードされたシンボル値です。
• uint16の下位8ビット (v & 0xff) は、1 + コード長を表します。これにより、コード長が0になることを防ぎ、0を「ルックアップテーブルでデコードできない」という特殊な値として使用できます。

processDHT関数でこのlutが構築されます。例えば、コード長が3ビットのハフマンコード010が値Xに対応する場合、ビットストリームの先頭8ビットが010xxxxxとなるすべてのパターン（01000000から01011111まで）について、lutの対応するエントリにXと1+3（コード長）が格納されます。

decodeHuffman関数の高速パス

func (d *decoder) decodeHuffman(h *huffman) (uint8, error) {
	// ... (error handling for uninitialized table)

	if d.bits.n < 8 { // Check if at least 8 bits are available for lookup
		if err := d.ensureNBits(8); err != nil {
			// ... (error handling and fall back to slowPath)
			goto slowPath
		}
	}
	// Fast path: use the look-up table
	if v := h.lut[(d.bits.a>>uint32(d.bits.n-lutSize))&0xff]; v != 0 {
		n := (v & 0xff) - 1 // Extract code length
		d.bits.n -= int32(n)
		d.bits.m >>= n
		return uint8(v >> 8), nil // Extract decoded value
	}

slowPath:
	// ... (Original slow path: 1-bit at a time decoding)
}

このコードスニペットは、decodeHuffman関数の高速パスを示しています。

1. d.bits.n < 8で、現在バッファリングされているビット数が8ビット未満であるかを確認します。もし不足していれば、ensureNBits(8)を呼び出して8ビットを確保しようとします。このensureNBitsは、後述のカスタムバイトバッファリングとバイトスタッフィング処理を利用します。
2. h.lut[(d.bits.a>>uint32(d.bits.n-lutSize))&0xff]の部分がルックアップテーブルの参照です。
   • d.bits.aはビットアキュムレータ（読み込んだビットが格納されている）。
   • d.bits.nはアキュムレータ内の未読ビット数。
   • (d.bits.a>>uint32(d.bits.n-lutSize))は、アキュムレータから先頭lutSizeビット（8ビット）を抽出します。
   • &0xffは、その8ビットをインデックスとして使用するためのマスクです。
3. v != 0は、ルックアップテーブルに有効なエントリが存在するかを確認します。
4. 有効なエントリが見つかった場合、n := (v & 0xff) - 1でコード長を抽出し、uint8(v >> 8)でデコードされたシンボル値を抽出します。
5. d.bits.n -= int32(n)とd.bits.m >>= nで、読み取ったビット数だけビットバッファの状態を更新します。

この高速パスにより、多くのハフマンコードは1回のルックアップと数回のビット操作でデコードできるようになり、大幅な速度向上が実現されます。

カスタムバイトバッファリングとバイトスタッフィング処理

reader.goで導入されたdecoder.bytes構造体と関連するヘルパー関数は、bufio.Readerの代替として機能し、特にJPEGのバイトスタッフィングを効率的に処理します。

type decoder struct {
	// ... other fields
	bits bits // The bit buffer for Huffman decoding
	// bytes is a byte buffer, similar to a bufio.Reader, except that it
	// has to be able to unread more than 1 byte, due to byte stuffing.
	// Byte stuffing is specified in section F.1.2.3.
	bytes struct {
		// buf[i:j] are the buffered bytes read from the underlying
		// io.Reader that haven't yet been passed further on.
		buf  [4096]byte
		i, j int
		// nUnreadable is the number of bytes to back up i after
		// overshooting. It can be 0, 1 or 2.
		nUnreadable int
	}
	// ... other fields
}

func (d *decoder) readByteStuffedByte() (x byte, err error) {
	// Fast path for when at least two bytes are in the buffer
	if d.bytes.i+2 <= d.bytes.j {
		x = d.bytes.buf[d.bytes.i]
		d.bytes.i++
		d.bytes.nUnreadable = 1
		if x != 0xff {
			return x, err
		}
		if d.bytes.buf[d.bytes.i] != 0x00 {
			return 0, errMissingFF00
		}
		d.bytes.i++
		d.bytes.nUnreadable = 2 // Read 2 bytes (0xFF and 0x00)
		return 0xff, nil         // Return 0xFF as the actual data byte
	}

	// Slow path: read byte by byte
	x, err = d.readByte()
	if err != nil {
		return 0, err
	}
	if x != 0xff {
		d.bytes.nUnreadable = 1
		return x, nil
	}

	x, err = d.readByte()
	if err != nil {
		d.bytes.nUnreadable = 1
		return 0, err
	}
	d.bytes.nUnreadable = 2
	if x != 0x00 {
		return 0, errMissingFF00
	}
	return 0xff, nil
}

func (d *decoder) unreadByteStuffedByte() {
	if d.bytes.nUnreadable == 0 {
		panic("jpeg: unreadByteStuffedByte call cannot be fulfilled")
	}
	d.bytes.i -= d.bytes.nUnreadable // Move read pointer back
	d.bytes.nUnreadable = 0
	if d.bits.n >= 8 { // If bits buffer has enough bits, also unread from there
		d.bits.a >>= 8
		d.bits.n -= 8
		d.bits.m >>= 8
	}
}

readByteStuffedByte関数は、JPEGのバイトスタッフィングを処理する核心部分です。

• バッファに十分なバイトがある場合、高速パスで0xFFの後に0x00が続くかをチェックします。
• 0xFF 0x00シーケンスが見つかった場合、0x00を読み飛ばし、実際のデータバイトとして0xFFを返します。この際、nUnreadableを2に設定し、2バイトを読み取ったことを記録します。
• unreadByteStuffedByte関数は、readByteStuffedByteで読み取ったバイトを「元に戻す」機能を提供します。これは、ハフマンデコードのルックアップテーブルが、必要なビット数よりも多く（例えば8ビット）を先読みしてしまい、その結果、バイト境界を越えて余分なバイトを読み取ってしまった場合に、その余分なバイトをバッファに戻すために使用されます。これにより、デコードの正確性が保証されます。

これらのカスタムバッファリングとバイトスタッフィング処理の導入により、image/jpegパッケージはJPEGの仕様に厳密に準拠しつつ、より効率的なデータ読み取りが可能になりました。

関連リンク

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

参考にした情報源リンク

• JPEG File Interchange Format (JFIF) Version 1.02: https://www.w3.org/Graphics/JPEG/jfif3.pdf
• ITU-T T.81 (JPEG) Information technology – Digital compression and coding of continuous-tone still images – Requirements and guidelines: https://www.itu.int/rec/T-REC-T.81-199210-I/en
• Huffman coding - Wikipedia: https://en.wikipedia.org/wiki/Huffman_coding
• JPEG Byte Stuffing Explanation: https://www.impulseadventure.com/photo/jpeg-huffman-coding.html (General explanation of JPEG Huffman and byte stuffing)
• Go bufio package documentation: https://pkg.go.dev/bufio
• Go image/jpeg package documentation: https://pkg.go.dev/image/jpeg