Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Go言語の標準ライブラリ image/jpeg パッケージにおけるパフォーマンス改善を目的としています。具体的には、JPEG画像のDCT (Discrete Cosine Transform) ブロックを表現するデータ型を [64]int から [64]int32 に変更し、さらにエンコーダ内のスクラッチバッファの再利用を行うことで、エンコード処理の高速化とスタック使用量の削減を実現しています。

コミット

commit daf43ba476ac29c9c15b59169a9458900efa0e1d
Author: Nigel Tao <nigeltao@golang.org>
Date:   Tue Oct 30 11:10:08 2012 +1100

    image/jpeg: change block from [64]int to [64]int32.
    
    On 6g/linux:
    benchmark                     old ns/op    new ns/op    delta
    BenchmarkFDCT                      4606         4241   -7.92%
    BenchmarkIDCT                      4187         3923   -6.31%
    BenchmarkDecodeBaseline         3154864      3170224   +0.49%
    BenchmarkDecodeProgressive      4072812      4017132   -1.37%
    BenchmarkEncode                39406920     34596760  -12.21%
    
    Stack requirements before (from 'go tool 6g -S'):
    (scan.go:37) TEXT    (*decoder).processSOS+0(SB),$1352-32
    (writer.go:448) TEXT    (*encoder).writeSOS+0(SB),$5344-24
    
    after:
    (scan.go:37) TEXT    (*decoder).processSOS+0(SB),$1064-32
    (writer.go:448) TEXT    (*encoder).writeSOS+0(SB),$2520-24
    
    Also, in encoder.writeSOS, re-use the yBlock scratch buffer for Cb and
    Cr. This reduces the stack requirement slightly, but also avoids an
    unlucky coincidence where a BenchmarkEncode stack split lands between
    encoder.writeByte and bufio.Writer.WriteByte, which occurs very often
    during Huffman encoding and is otherwise disasterous for the final
    benchmark number. FWIW, the yBlock re-use *without* the s/int/int32/
    change does not have a noticable effect on the benchmarks.
    
    R=r
    CC=golang-dev, rsc
    https://golang.org/cl/6823043

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

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

元コミット内容

image/jpeg: change block from [64]int to [64]int32.

このコミットは、JPEG画像の処理において、DCTブロックのデータ型を [64]int から [64]int32 に変更します。これにより、ベンチマーク結果ではFDCTとIDCTのパフォーマンスが向上し、特にエンコード処理が大幅に高速化（-12.21%）しています。また、デコーダとエンコーダのスタック使用量も削減されています。

さらに、encoder.writeSOS 関数内で yBlock スクラッチバッファをCbおよびCrコンポーネントの処理に再利用することで、スタック要件をさらに削減し、ハフマン符号化中に頻繁に発生するスタック分割によるパフォーマンス低下を回避しています。

変更の背景

この変更の背景には、Go言語の image/jpeg パッケージのパフォーマンス最適化があります。特に、JPEGエンコード/デコード処理は計算負荷が高く、効率的なメモリ使用とCPUキャッシュの活用が重要です。

コミットメッセージに示されているように、[64]int から [64]int32 への変更は、主に以下の理由で行われました。

  1. パフォーマンスの向上: int 型はGoが実行されるアーキテクチャに依存し、32ビットシステムでは32ビット、64ビットシステムでは64ビットのサイズを持ちます。JPEGのDCT係数は通常、-2048から2047の範囲に収まることが多く、32ビット整数 (int32) で十分表現可能です。64ビットシステムで int が64ビットとして扱われる場合、int32 に変更することで、メモリフットプリントが半分になり、CPUキャッシュの効率が向上する可能性があります。これにより、データアクセスが高速化され、全体的な処理速度が向上します。ベンチマーク結果が示すように、FDCT、IDCT、そして特にエンコード処理で顕著な改善が見られます。
  2. スタック使用量の削減: int から int32 への変更は、スタック上に確保される変数のサイズを削減します。これにより、関数の呼び出し時に必要なスタック領域が減少し、特に再帰的な処理や多くのローカル変数を扱う関数において、スタックオーバーフローのリスクを低減し、全体的なメモリ効率を向上させます。コミットメッセージの go tool 6g -S の出力は、このスタック使用量の削減を明確に示しています。
  3. スタック分割の回避: Goのランタイムは、必要に応じてゴルーチンのスタックを動的に拡張する「スタック分割 (stack split)」というメカニズムを持っています。しかし、このスタック分割はオーバーヘッドを伴います。特に、encoder.writeByte と bufio.Writer.WriteByte の間でスタック分割が発生すると、ハフマン符号化のような頻繁に呼び出される処理において、パフォーマンスに壊滅的な影響を与える可能性があります。yBlock の再利用と int32 への変更は、スタック使用量を減らすことで、このような不運なスタック分割の発生を回避し、ベンチマークの安定性と実際のパフォーマンスを向上させることを目的としています。

前提知識の解説

JPEG画像フォーマット

JPEG (Joint Photographic Experts Group) は、主に写真などの自然画像を圧縮するための標準的な画像フォーマットです。非可逆圧縮方式を採用しており、高い圧縮率と比較的良好な画質を両立させます。JPEG圧縮の主要なステップには、色空間変換 (YCbCr)、ダウンサンプリング、DCT (離散コサイン変換)、量子化、ハフマン符号化などがあります。

  • YCbCr色空間: 人間の視覚特性に合わせて、輝度 (Y) と2つの色差 (Cb, Cr) に分離します。色差情報は輝度情報よりも解像度を下げても視覚的な影響が少ないため、ダウンサンプリングの対象となります。
  • DCT (Discrete Cosine Transform): 画像を8x8ピクセルのブロックに分割し、各ブロックの空間領域データを周波数領域データに変換します。これにより、人間の目には見えにくい高周波成分を効率的に除去できるようになります。
  • 量子化: DCTによって得られた周波数係数を、量子化テーブルと呼ばれる事前に定義された値で割って丸めます。これにより、多くの高周波成分がゼロになり、データ量を大幅に削減できます。このステップが非可逆圧縮の主要因です。
  • ハフマン符号化: 量子化された係数を、出現頻度の高いデータには短い符号を、低いデータには長い符号を割り当てることで、さらにデータ量を削減します。

Go言語の int と int32

  • int 型: Go言語の int 型は、実行環境のCPUアーキテクチャに依存する整数型です。32ビットシステムでは32ビット（約±20億）、64ビットシステムでは64ビット（約±900京）の範囲を表現できます。これは、ポインタのサイズと同じであることが保証されています。
  • int32 型: int32 型は、常に32ビット幅の符号付き整数型です。その範囲は -2,147,483,648 から 2,147,483,647 です。

JPEGのDCT係数は通常、この int32 の範囲に収まるため、64ビットシステムで int を使用すると、必要以上に大きなメモリを消費し、CPUキャッシュの効率を低下させる可能性があります。int32 を明示的に使用することで、メモリ使用量を最適化し、パフォーマンスを向上させることができます。

Go言語のスタックとスタック分割

Go言語のゴルーチンは、非常に軽量なスレッドのようなもので、独自のスタックを持っています。Goランタイムは、ゴルーチンのスタックが不足しそうになると、より大きなスタックを割り当ててデータをコピーする「スタック分割 (stack split)」というメカニズムを持っています。これは透過的に行われますが、その過程でオーバーヘッドが発生します。

特に、頻繁に呼び出される関数（例: ハフマン符号化中のバイト書き込み）の間にスタック分割が発生すると、そのオーバーヘッドが累積し、全体のパフォーマンスに悪影響を及ぼす可能性があります。スタック使用量を削減することは、スタック分割の発生頻度を減らし、パフォーマンスを安定させる上で有効な戦略です。

go tool 6g -S

go tool 6g -S は、Goコンパイラ 6g (Go 1.x 時代のamd64アーキテクチャ向けコンパイラ名) のオプションで、コンパイルされた関数のアセンブリコードとスタックフレームの情報を表示します。$1352-32 のような表記は、関数が使用するスタックフレームのサイズ（この場合1352バイト）と、引数に割り当てられたスタック領域のサイズ（32バイト）を示しています。この情報から、関数がどれくらいのスタックメモリを消費しているかを把握できます。

技術的詳細

int から int32 への型変更のメカニズムと効果

JPEGのDCTブロックは8x8の64個の係数から構成されます。これらの係数は、DCT変換と量子化の後、通常は小さな整数値になります。Go言語の image/jpeg パッケージでは、これらの係数を格納するために block 型が定義されていました。

変更前: type block [blockSize]int (ここで blockSize は64) 変更後: type block [blockSize]int32

この変更がもたらす技術的な効果は以下の通りです。

  1. メモリフットプリントの削減: 64ビットシステムでは、int は8バイト（64ビット）を占めますが、int32 は4バイト（32ビット）を占めます。したがって、[64]int は 64 * 8 = 512 バイトを消費するのに対し、[64]int32 は 64 * 4 = 256 バイトを消費します。これにより、各DCTブロックのメモリ使用量が半分になります。
  2. CPUキャッシュ効率の向上: メモリフットプリントが削減されることで、より多くのDCTブロックがCPUのL1/L2キャッシュに収まるようになります。キャッシュヒット率が向上すると、メインメモリへのアクセス回数が減り、データ転送のボトルネックが緩和され、処理速度が向上します。これは、特にFDCTやIDCTのような数値計算が中心となる処理において顕著な効果を発揮します。
  3. スタック使用量の削減: block 型の変数が関数内でローカル変数として宣言される場合、そのメモリはスタック上に確保されます。int32 への変更により、スタック上に確保される block 変数のサイズが小さくなるため、関数のスタックフレームサイズが削減されます。これは、go tool 6g -S の出力で示されたスタック要件の減少に直接つながります。

yBlock スクラッチバッファの再利用

encoder.writeSOS 関数は、JPEGエンコードの主要なループであり、画像データを8x8ブロックに分割し、YCbCr変換、DCT、量子化、ハフマン符号化を行います。変更前は、輝度 (Y)、青色差 (Cb)、赤色差 (Cr) の各コンポーネントに対して個別のスクラッチバッファ (yBlock, cbBlock, crBlock) を用意していました。

コミットでは、yBlock と同様の block 型の単一のスクラッチバッファ b を導入し、これをY、Cb、Crのすべてのコンポーネントの処理に再利用するように変更しています。

変更前:

var (
    yBlock  block
    cbBlock [4]block
    crBlock [4]block
    cBlock  block
)
// ...
rgbaToYCbCr(rgba, p, &yBlock, &cbBlock[i], &crBlock[i])
prevDCY = e.writeBlock(&yBlock, 0, prevDCY)
// ...
scale(&cBlock, &cbBlock)
prevDCCb = e.writeBlock(&cBlock, 1, prevDCCb)
scale(&cBlock, &crBlock)
prevDCCr = e.writeBlock(&cBlock, 1, prevDCCr)

変更後:

var (
    b      block
    cb, cr [4]block // cbBlock, crBlock は残るが、cBlock は b に置き換えられる
)
// ...
rgbaToYCbCr(rgba, p, &b, &cb[i], &cr[i]) // yBlock が b に
prevDCY = e.writeBlock(&b, 0, prevDCY)   // yBlock が b に
// ...
scale(&b, &cb) // cBlock が b に
prevDCCb = e.writeBlock(&b, 1, prevDCCb) // cBlock が b に
scale(&b, &cr) // cBlock が b に
prevDCCr = e.writeBlock(&b, 1, prevDCCr) // cBlock が b に

この再利用の技術的利点は以下の通りです。

  1. スタック使用量のさらなる削減: 複数の block 型の変数を宣言する代わりに、単一の block 変数を使い回すことで、writeSOS 関数がスタック上で必要とするメモリ量をさらに削減します。これは、go tool 6g -S の出力で writer.go:448 のスタック要件が大幅に減少していることからも裏付けられます。
  2. スタック分割の回避: コミットメッセージで言及されているように、この最適化は「不運な偶然」によるスタック分割を回避する効果があります。encoder.writeByte と bufio.Writer.WriteByte の間でスタック分割が発生すると、ハフマン符号化の効率が著しく低下します。スタック使用量を最小限に抑えることで、Goランタイムがスタックを拡張する必要がある頻度を減らし、結果としてスタック分割によるパフォーマンスヒットを回避できます。これは、特に BenchmarkEncode の結果に大きく貢献しています。

ベンチマーク結果の分析

コミットメッセージに示されたベンチマーク結果は、これらの変更の効果を定量的に示しています。

  • BenchmarkFDCT / BenchmarkIDCT: DCT変換と逆DCT変換のベンチマークです。int から int32 への変更によるメモリ効率の改善が直接的に寄与し、それぞれ約8%と6%の高速化を達成しています。
  • BenchmarkDecodeBaseline / BenchmarkDecodeProgressive: デコード処理のベンチマークです。わずかながら改善が見られますが、エンコードほど劇的ではありません。これは、デコード処理ではデータ読み込みやハフマン復号化のオーバーヘッドが大きく、DCTブロックの型変更による恩恵が相対的に小さいためと考えられます。
  • BenchmarkEncode: エンコード処理のベンチマークです。最も顕著な改善（-12.21%）が見られます。これは、int から int32 への変更によるDCT処理の高速化に加え、yBlock の再利用によるスタック使用量の削減と、それに伴うスタック分割の回避が複合的に作用した結果と考えられます。エンコード処理は、DCT変換、量子化、ハフマン符号化など、計算負荷の高いステップが連続するため、これらの最適化が全体に与える影響が大きくなります。

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

このコミットでは、主に src/pkg/image/jpeg/ ディレクトリ内の以下のファイルが変更されています。

  1. src/pkg/image/jpeg/dct_test.go: テストコード内で block 型の要素を int32 にキャストする変更。
    • b[r.Int()%len(b)] = r.Int31() % 256 (旧: r.Int())
    • b[i] = int32(dst[i] + 0.5) (旧: int(dst[i] + 0.5))
  2. src/pkg/image/jpeg/huffman.go: ハフマン符号化関連の関数で、int 型の変数を int32 に変更。
    • func (d *decoder) receiveExtend(t uint8) (int32, error) (旧: int)
    • s := int32(1) << t (旧: s := 1 << t)
    • x := int32(d.b.a>>uint8(d.b.n)) & (s - 1) (旧: x := int(d.b.a>>uint8(d.b.n)) & (s - 1))
  3. src/pkg/image/jpeg/idct.go: block 型の定義を int から int32 に変更。
    • type block [blockSize]int32 (旧: int)
  4. src/pkg/image/jpeg/reader.go: 量子化テーブルの読み込みで int 型を int32 に変更。
    • d.quant[tq][i] = int32(d.tmp[i+1]) (旧: int(d.tmp[i+1]))
  5. src/pkg/image/jpeg/scan.go: デコーダの processSOS 関数内で、様々な変数の型を int から int32 または uint から uint32 に変更。
    • zigStart, zigEnd, ah, al := int32(0), int32(blockSize-1), uint32(0), uint32(0) (旧: int, uint)
    • dc [nColorComponent]int32 (旧: int)
    • zig += int32(val0) (旧: int(val0))
    • dc = [nColorComponent]int32{} (旧: int{})
    • func (d *decoder) refine(b *block, h *huffman, zigStart, zigEnd, delta int32) error (旧: int)
    • z := int32(0) (旧: int)
    • zig, err = d.refineNonZeroes(b, zig, zigEnd, int32(val0), delta) (旧: int(val0))
    • func (d *decoder) refineNonZeroes(b *block, zig, zigEnd, nz, delta int32) (int32, error) (旧: int)
  6. src/pkg/image/jpeg/writer.go: エンコーダの writer.go で、div 関数、emitHuff 関数、emitHuffRLE 関数、writeBlock 関数、toYCbCr 関数、rgbaToYCbCr 関数、writeSOS 関数内の変数の型を int から int32 に変更し、writeSOS 関数内でスクラッチバッファの再利用ロジックを実装。
    • func div(a, b int32) int32 (旧: int)
    • func (e *encoder) emitHuff(h huffIndex, value int32) (旧: int)
    • func (e *encoder) emitHuffRLE(h huffIndex, runLength, value int32) (旧: int)
    • e.emitHuff(h, runLength<<4|int32(nBits)) (旧: int(nBits))
    • func (e *encoder) writeBlock(b *block, q quantIndex, prevDC int32) int32 (旧: int)
    • dc := div(b[0], 8*int32(e.quant[q][0])) (旧: 8 * int(e.quant[q][0]))
    • h, runLength := huffIndex(2*q+1), int32(0) (旧: int)
    • ac := div(b[unzig[zig]], 8*int32(e.quant[q][zig])) (旧: 8 * int(e.quant[q][zig]))
    • yBlock[8*j+i] = int32(yy) (旧: int(yy)) など、YCbCr変換結果の代入
    • prevDCY, prevDCCb, prevDCCr int32 (旧: int)
    • var ( b block; cb, cr [4]block ) (旧: yBlock block; cbBlock [4]block; crBlock [4]block; cBlock block)
    • rgbaToYCbCr(rgba, p, &b, &cb[i], &cr[i]) (旧: &yBlock, &cbBlock[i], &crBlock[i])
    • toYCbCr(m, p, &b, &cb[i], &cr[i]) (旧: &yBlock, &cbBlock[i], &crBlock[i])
    • prevDCY = e.writeBlock(&b, 0, prevDCY) (旧: &yBlock)
    • scale(&b, &cb) (旧: &cBlock, &cbBlock)
    • prevDCCb = e.writeBlock(&b, 1, prevDCCb) (旧: &cBlock)
    • scale(&b, &cr) (旧: &cBlock, &crBlock)
    • prevDCCr = e.writeBlock(&b, 1, prevDCCr) (旧: &cBlock)

コアとなるコードの解説

image/jpeg/idct.go の block 型定義

const blockSize = 64 // A DCT block is 8x8.

type block [blockSize]int32 // 変更点: int から int32 へ

この変更は、JPEGのDCTブロック（8x8ピクセル、計64個の係数）を格納する配列の要素型を int から int32 に変更しています。これにより、64ビットシステムでのメモリ使用量が半分になり、CPUキャッシュの効率が向上します。これは、FDCTやIDCTといった数値計算が中心となる処理のパフォーマンスに直接影響を与えます。

image/jpeg/writer.go の writeSOS 関数におけるバッファ再利用

// 変更前:
// var (
// 	yBlock  block
// 	cbBlock [4]block
// 	crBlock [4]block
// 	cBlock  block
// 	prevDCY, prevDCCb, prevDCCr int
// )

// 変更後:
var (
	b      block // yBlock と cBlock の役割を兼ねる
	cb, cr [4]block // cbBlock と crBlock は残る
	prevDCY, prevDCCb, prevDCCr int32 // int から int32 へ
)

// ... (ループ内での使用箇所) ...

// 変更前:
// rgbaToYCbCr(rgba, p, &yBlock, &cbBlock[i], &crBlock[i])
// prevDCY = e.writeBlock(&yBlock, 0, prevDCY)
// scale(&cBlock, &cbBlock)
// prevDCCb = e.writeBlock(&cBlock, 1, prevDCCb)
// scale(&cBlock, &crBlock)
// prevDCCr = e.writeBlock(&cBlock, 1, prevDCCr)

// 変更後:
rgbaToYCbCr(rgba, p, &b, &cb[i], &cr[i]) // yBlock の代わりに b を使用
prevDCY = e.writeBlock(&b, 0, prevDCY)   // yBlock の代わりに b を使用
scale(&b, &cb) // cBlock の代わりに b を使用
prevDCCb = e.writeBlock(&b, 1, prevDCCb) // cBlock の代わりに b を使用
scale(&b, &cr) // cBlock の代わりに b を使用
prevDCCr = e.writeBlock(&b, 1, prevDCCr) // cBlock の代わりに b を使用

writeSOS 関数は、JPEGエンコードのメインループであり、各8x8ブロックの処理を行います。変更前は、輝度 (Y) 用の yBlock と、色差 (Cb, Cr) のスケーリング用の一時バッファ cBlock が個別に宣言されていました。この変更では、単一の block 型変数 b を導入し、これを yBlock と cBlock の両方の役割で再利用しています。

この再利用により、writeSOS 関数がスタック上で確保するメモリ量が削減されます。特に、ハフマン符号化中に頻繁に呼び出される encoder.writeByte と bufio.Writer.WriteByte の間でスタック分割が発生する「不運な偶然」を回避し、エンコード処理のパフォーマンスを安定させ、向上させる効果があります。

その他の型変更

上記以外にも、huffman.go、reader.go、scan.go、writer.go の各ファイルで、DCT係数や関連する計算結果を格納する変数、関数の引数、戻り値の型が int から int32 に、または uint から uint32 に変更されています。これらはすべて、メモリ効率の向上とスタック使用量の削減という目的のために行われています。例えば、receiveExtend 関数や refine 関数、writeBlock 関数などが影響を受けています。

関連リンク

参考にした情報源リンク