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

このコミットは、Go言語の標準ライブラリであるimage/pngパッケージにおけるPNGデコード処理のパフォーマンス最適化を目的としています。特に、PNG画像のフィルタリング処理の一つであるPaethフィルタの適用方法が改善され、それに伴いデコード速度が向上しています。

コミット

commit dbcdce5866502aadc9b3e70e06c92d2afb22e1e1
Author: Nigel Tao <nigeltao@golang.org>
Date:   Wed May 30 21:38:46 2012 +1000

    image/png: optimize paeth some more.
    
    filterPaeth takes []byte arguments instead of byte arguments,
    which avoids some redudant computation of the previous pixel
    in the inner loop.
    
    Also eliminate a bounds check in decoding the up filter.
    
    benchmark                       old ns/op    new ns/op    delta
    BenchmarkDecodeGray               3139636      2812531  -10.42%
    BenchmarkDecodeNRGBAGradient     12341520     10971680  -11.10%
    BenchmarkDecodeNRGBAOpaque       10740780      9612455  -10.51%
    BenchmarkDecodePaletted           1819535      1818913   -0.03%
    BenchmarkDecodeRGB                8974695      8178070   -8.88%
    
    R=rsc
    CC=golang-dev
    https://golang.org/cl/6243061

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

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

元コミット内容

image/png: optimize paeth some more.

filterPaeth関数がbyte引数ではなく[]byte引数を取るように変更され、これにより内部ループでの前のピクセルの冗長な計算が回避されました。

また、upフィルタのデコードにおける境界チェックが削除されました。

ベンチマーク結果:

benchmark	old ns/op	new ns/op	delta
BenchmarkDecodeGray	3139636	2812531	-10.42%
BenchmarkDecodeNRGBAGradient	12341520	10971680	-11.10%
BenchmarkDecodeNRGBAOpaque	10740780	9612455	-10.51%
BenchmarkDecodePaletted	1819535	1818913	-0.03%
BenchmarkDecodeRGB	8974695	8178070	-8.88%

このコミットの主な背景は、Go言語のimage/pngパッケージにおけるPNGデコード処理のパフォーマンス改善です。PNG画像のデコードは、特に大きな画像や複雑なフィルタリングが適用された画像の場合、CPUリソースを多く消費する可能性があります。PaethフィルタはPNGのフィルタリング手法の中でも比較的計算コストが高い部類に入るため、その処理を最適化することで、全体のデコード時間を短縮し、より効率的な画像処理を実現することが目指されました。ベンチマーク結果が示すように、この最適化は特にグレースケール、NRGBA、RGB画像において顕著な効果をもたらしています。

前提知識の解説

PNG (Portable Network Graphics)

PNGは、可逆圧縮を特徴とするビットマップ画像フォーマットです。ウェブ上で広く利用されており、透明度（アルファチャンネル）をサポートし、画質の劣化なしに画像を保存できるため、ロゴやアイコン、スクリーンショットなどに適しています。

PNGフィルタリング

PNG画像は、圧縮効率を向上させるために、各行のピクセルデータに「フィルタリング」と呼ばれる前処理を適用します。これは、隣接するピクセル間の差分を符号化することで、より多くのゼロ値や小さな値を生成し、Deflate圧縮アルゴリズムによる圧縮率を高めることを目的としています。PNG仕様では以下の5種類のフィルタタイプが定義されています。

None (タイプ0): フィルタリングなし。
Sub (タイプ1): 現在のピクセルから左隣のピクセル値を引いた差分を格納します。
Up (タイプ2): 現在のピクセルから上隣のピクセル値を引いた差分を格納します。
Average (タイプ3): 現在のピクセルから、左隣と上隣のピクセル値の平均を引いた差分を格納します。
Paeth (タイプ4): 現在のピクセルから、左、上、左上の3つの隣接ピクセルから計算された予測値を引いた差分を格納します。

Paethフィルタアルゴリズム

Paethフィルタは、PNGフィルタの中で最も洗練された予測フィルタの一つです。現在のピクセル値の予測値を、その左（a）、上（b）、左上（c）の3つの隣接ピクセルから計算します。具体的には、以下の式で3つの予測候補値pを計算し、その中でa, b, cのいずれかに最も近いものを選択します。

p = a + b - c

そして、pとa, b, cそれぞれの差の絶対値が最小となるものを選択し、その選択された隣接ピクセル（a, b, cのいずれか）を予測値として使用します。この予測値が現在のピクセルから引かれ、その差分がエンコードされます。この複雑な予測により、Paethフィルタは特にエッジやグラデーションを含む画像において高い圧縮率を達成できます。

Go言語の`image/png`パッケージ

Go言語の標準ライブラリには、imageパッケージとそのサブパッケージとしてimage/pngが含まれています。image/pngパッケージは、PNG形式の画像をGoプログラム内でエンコードおよびデコードするための機能を提供します。これにより、GoアプリケーションはPNG画像を簡単に読み書きできます。

パフォーマンス最適化の一般的な手法

Go言語におけるパフォーマンス最適化では、以下のような手法が一般的に用いられます。

冗長な計算の削減: 同じ計算を複数回行うことを避け、一度計算した結果を再利用する。
メモリ割り当ての最小化: ガベージコレクションのオーバーヘッドを減らすために、不要なメモリ割り当てを避ける。
境界チェックの削減: スライスアクセス時にGoランタイムが行う境界チェックは安全性を保証しますが、パフォーマンスに影響を与えることがあります。コンパイラが安全性を保証できる場合、これらのチェックは省略されることがあります。コードの書き方を工夫することで、コンパイラが境界チェックを最適化しやすくなる場合があります。

技術的詳細

このコミットは、主に以下の2つの技術的な改善によってPNGデコードのパフォーマンスを向上させています。

filterPaeth関数の引数変更と内部ループの最適化:
- 以前のfilterPaeth関数は、おそらくピクセル単位で処理を行い、その際に前のピクセル値を再計算するような冗長な処理が含まれていた可能性があります。
- この変更では、filterPaeth関数がbyte引数ではなく[]byte（バイトスライス）引数を受け取るように変更されました。これにより、関数内で現在の行のデータ（cdat）と前の行のデータ（pdat）全体にアクセスできるようになります。
- この変更により、内部ループで前のピクセル（cdat[i-bytesPerPixel]など）の値を効率的に参照できるようになり、冗長な計算が回避されました。特に、Paethフィルタの計算では左、上、左上のピクセルを参照するため、これらの値への効率的なアクセスが重要です。
upフィルタデコードにおける境界チェックの削除:
- reader.go内のftUp（Upフィルタ）のデコード処理において、ループの書き方が変更されました。具体的には、for i := 0; i < len(cdat); i++ { cdat[i] += pdat[i] }という形式から、for i, p := range pdat { cdat[i] += p }という形式に変更されています。
- rangeキーワードを使用することで、Goコンパイラはスライスpdatの範囲をより正確に推論できるようになり、ループ内のpdat[i]へのアクセスに対する不要な境界チェックを省略できる可能性が高まります。これにより、わずかながらも実行時のオーバーヘッドが削減されます。

これらの変更は、特にCPUバウンドなPNGデコード処理において、計算効率を高め、実行時間を短縮する効果をもたらしました。ベンチマーク結果は、これらの最適化が実際にデコード性能を向上させたことを明確に示しています。

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

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

src/pkg/image/png/paeth.go (新規作成):
- paeth関数とfilterPaeth関数が新しく定義され、Paethフィルタのロジックがこのファイルに集約されました。
- paeth関数は単一のピクセルに対するPaethフィルタの計算を行います。
- filterPaeth関数は、行全体のデータに対してPaethフィルタを適用します。
src/pkg/image/png/paeth_test.go (変更):
- 新しく定義されたfilterPaeth関数のテストケースが追加されました。
- slowFilterPaethという、よりシンプルだが非効率なfilterPaethの実装がテスト用に用意され、最適化されたfilterPaethの出力と比較することで、正確性が検証されています。
- TestPaethDecode関数が追加され、ランダムなデータを用いてfilterPaethの動作が検証されています。
src/pkg/image/png/reader.go (変更):
- 以前このファイル内に直接実装されていたpaeth関数が削除されました。
- decodeメソッド内のフィルタリング処理において、ftPaeth（Paethフィルタ）のケースで、以前のインラインループ処理が削除され、新しく定義されたfilterPaeth関数が呼び出されるように変更されました。
- ftUp（Upフィルタ）のケースにおけるループの記述が、for i := 0; i < len(cdat); i++ { cdat[i] += pdat[i] } から for i, p := range pdat { cdat[i] += p } に変更されました。

コアとなるコードの解説

`src/pkg/image/png/paeth.go`

このファイルは、Paethフィルタリングのロジックをカプセル化するために新しく作成されました。

func paeth(a, b, c uint8) uint8:
- この関数は、PNG仕様で定義されているPaethフィルタの計算ロジックを実装しています。
- aは左のピクセル、bは上のピクセル、cは左上のピクセルを表します。
- コメントにもあるように、PNG仕様のサンプルコードよりも算術演算の回数を減らすように最適化されています。具体的には、p = int(a) + int(b) - int(c) のような中間変数を使わず、直接差分を計算し、絶対値を取ることで効率化を図っています。
- 最終的に、pa, pb, pcの絶対値が最小となるものに基づいて、a, b, cのいずれかのピクセル値を返します。
func filterPaeth(cdat, pdat []byte, bytesPerPixel int):
- この関数は、現在の行のデータcdatと前の行のデータpdatに対してPaethフィルタを適用します。
- bytesPerPixelは、1ピクセルあたりのバイト数（例: RGBAなら4）を示します。
- 外側のループはbytesPerPixelの数だけ繰り返され、各バイトチャネル（例: R, G, B, A）ごとに処理を行います。
- 内側のループは、各バイトチャネル内のピクセルデータを走査します。
- この関数が[]byte引数を受け取ることで、ループ内でcdat[j-bytesPerPixel]やpdat[j]といった隣接ピクセルへのアクセスが効率的に行われ、以前のreader.go内のインライン実装で発生していた可能性のある冗長な計算が削減されています。
- cdat[j] = uint8(a) の行で、デコードされたピクセル値がcdatに書き込まれます。

`src/pkg/image/png/reader.go`

このファイルは、PNGデコードの主要なロジックを含んでいます。

paeth関数の削除:
- 以前このファイル内に直接定義されていたpaeth関数が削除され、paeth.goに移動されました。これにより、コードの関心分離が図られ、モジュール性が向上しました。
ftPaethケースの変更:
- decodeメソッド内のフィルタリング処理のcase ftPaeth:ブロックが大幅に簡素化されました。
- 以前は、Paethフィルタのロジックがこのブロック内にインラインで記述されていましたが、それが削除され、新しく定義されたfilterPaeth(cdat, pdat, bytesPerPixel)の呼び出しに置き換えられました。これにより、コードの可読性が向上し、Paethフィルタのロジックがpaeth.goに一元化されました。
ftUpケースのループ変更:
- case ftUp:ブロック内のループが、for i := 0; i < len(cdat); i++ { cdat[i] += pdat[i] } から for i, p := range pdat { cdat[i] += p } に変更されました。
- この変更は、機能的には同じですが、rangeキーワードを使用することで、Goコンパイラがループのイテレーションとスライスアクセスをより効率的に最適化できるようになります。特に、境界チェックの省略に繋がり、わずかながらもパフォーマンス向上に寄与します。

これらの変更により、PNGデコード処理、特にPaethフィルタの適用がより効率的になり、全体的なデコード速度が向上しました。

参考にした情報源リンク

Go Gerrit Code Review - image/png: optimize paeth some more.: https://golang.org/cl/6243061

comemo