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

このコミットは、Go言語の image/png パッケージにおけるPaethフィルターの実装を最適化し、PNG画像のデコード性能を向上させることを目的としています。特に、Paethフィルターの計算ロジックをより効率的な形に修正することで、CPUサイクルを削減し、全体的なデコード速度の改善を図っています。

コミット

commit 1423ecb1266c9af288caa2723988a326adf7118e
Author: Nigel Tao <nigeltao@golang.org>
Date:   Fri May 25 14:08:51 2012 +1000

    image/png: optimize the paeth filter implementation.
    
    image/png benchmarks:
    benchmark                       old ns/op    new ns/op    delta
    BenchmarkPaeth                         10            7  -29.21%
    BenchmarkDecodeGray               2381745      2241620   -5.88%
    BenchmarkDecodeNRGBAGradient      9535555      8835100   -7.35%
    BenchmarkDecodeNRGBAOpaque        8189590      7611865   -7.05%
    BenchmarkDecodePaletted           1300688      1301940   +0.10%
    BenchmarkDecodeRGB                6760146      6317082   -6.55%
    BenchmarkEncodePaletted           6048596      6122666   +1.22%
    BenchmarkEncodeRGBOpaque         18891140     19474230   +3.09%
    BenchmarkEncodeRGBA              78945350     78552600   -0.50%
    
    Wall time for Denis Cheremisov's PNG-decoding program given in
    https://groups.google.com/group/golang-nuts/browse_thread/thread/22aa8a05040fdd49
    Before: 2.25s
    After:  2.27s
    Delta:  +1%
    
    The same program, but with a different PNG input file
    (http://upload.wikimedia.org/wikipedia/commons/4/47/PNG_transparency_demonstration_1.png)
    and only 100 iterations instead of 1000
    Before: 4.78s
    After:  4.42s
    Delta:  -8%
    
    R=rsc
    CC=golang-dev
    https://golang.org/cl/6242056

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

https://github.com/golang/go/commit/1423ecb1266c9af288caa2723988a326adf7118e

元コミット内容

image/png: Paethフィルターの実装を最適化。

ベンチマーク結果は以下の通り： BenchmarkPaeth が29.21%高速化。 BenchmarkDecodeGray が5.88%高速化。 BenchmarkDecodeNRGBAGradient が7.35%高速化。 BenchmarkDecodeNRGBAOpaque が7.05%高速化。 BenchmarkDecodeRGB が6.55%高速化。 エンコード関連のベンチマークではわずかな変動が見られる。

特定のPNGデコードプログラムでの実測時間では、入力ファイルによって結果が異なるが、一部のケースで8%の改善が見られた。

変更の背景

PNG画像は、可逆圧縮形式であり、そのデコードプロセスには様々なフィルター処理が含まれます。Paethフィルターはその一つで、画像のピクセル値を予測し、圧縮効率を高めるために使用されます。PNGデコードの性能は、これらのフィルター処理の効率に大きく依存します。

このコミットの背景には、Go言語の image/png パッケージにおけるPNGデコード性能のさらなる向上が挙げられます。特に、Paethフィルターの既存の実装が、PNG仕様書に記載されているサンプルコードを直接移植したものであり、必ずしも最も効率的な計算方法ではなかった可能性があります。

ベンチマーク結果が示すように、BenchmarkPaeth 自体の性能が大幅に向上していることから、Paethフィルターの計算がPNGデコード全体のボトルネックの一つであったことが示唆されます。この最適化により、PNGデコード処理全体の速度を改善し、Go言語でPNG画像を扱うアプリケーションの応答性を高めることが期待されます。

前提知識の解説

PNG (Portable Network Graphics)

PNGは、可逆圧縮を特徴とするラスターグラフィックスファイル形式です。ウェブ上で広く利用されており、透明度（アルファチャンネル）をサポートしている点が大きな特徴です。PNGは、圧縮効率を高めるために、デコード時に適用される様々なフィルター処理をサポートしています。

PNGフィルター処理

PNGの圧縮では、各行のピクセルデータに対してフィルター処理が適用されます。これにより、隣接するピクセル間の差分を小さくし、より高い圧縮率を実現します。デコード時には、このフィルター処理を逆に行うことで元のピクセルデータを復元します。PNG仕様では、以下の5種類のフィルターが定義されています。

• None (0): フィルターなし。
• Sub (1): 現在のピクセルと左隣のピクセルの差分。
• Up (2): 現在のピクセルと上隣のピクセルの差分。
• Average (3): 現在のピクセルと左隣および上隣のピクセルの平均値との差分。
• Paeth (4): 現在のピクセルと、左隣、上隣、左上隣の3つのピクセルから最も近い予測値を計算し、その予測値との差分。

Paethフィルター

Paethフィルターは、PNGのフィルターの中でも最も複雑なものの一つです。現在のピクセル X の値を予測するために、その左隣 a、上隣 b、左上隣 c の3つのピクセル値を使用します。予測値 p は以下の式で計算されます。

p = a + b - c

そして、p と a, b, c のそれぞれとの絶対差 pa, pb, pc を計算します。

pa = abs(p - a) pb = abs(p - b) pc = abs(p - c)

これらの差分の中で最も小さいものに対応するピクセル値（pa が最小なら a、pb が最小なら b、pc が最小なら c）が予測値として選択されます。この予測値と実際のピクセル値との差分がPNGファイルに保存され、デコード時にこの逆の処理が行われます。

Paethフィルターの目的は、隣接するピクセル間の相関関係を最大限に利用して、予測誤差を最小限に抑えることで、より効果的な圧縮を実現することです。

技術的詳細

このコミットの主要な技術的詳細は、Paethフィルターの計算ロジックの最適化にあります。元の実装はPNG仕様書に記載されているサンプルコードを直接移植したものでしたが、これは必ずしも計算効率が最高ではありませんでした。

元のPaethフィルターの計算は以下のようでした。

func paeth(a, b, c uint8) uint8 {
	p := int(a) + int(b) - int(c)
	pa := abs(p - int(a))
	pb := abs(p - int(b))
	pc := abs(p - int(c))
	if pa <= pb && pa <= pc {
		return a
	} else if pb <= pc {
		return b
	}
	return c
}

このコードでは、まず p を計算し、その後 p と a, b, c の差分を計算するために3回の減算と3回の abs 呼び出しを行っています。

最適化された実装では、pa, pb, pc の計算方法が変更されています。

func paeth(a, b, c uint8) uint8 {
	// This is an optimized version of the sample code in the PNG spec.
	// For example, the sample code starts with:
	//		p := int(a) + int(b) - int(c)
	//		pa := abs(p - int(a))
	// but the optimized form uses fewer arithmetic operations:
	//		pa := int(b) - int(c)
	//		pa = abs(pa)
	pc := int(c)
	pa := int(b) - pc // p - a = (a + b - c) - a = b - c
	pb := int(a) - pc // p - b = (a + b - c) - b = a - c
	pc = pa + pb      // p - c = (a + b - c) - c = a + b - 2c. This is not exactly p-c, but it's equivalent for comparison.
	if pa < 0 {
		pa = -pa
	}
	if pb < 0 {
		pb = -pb
	}
	if pc < 0 {
		pc = -pc
	}
	if pa <= pb && pa <= pc {
		return a
	} else if pb <= pc {
		return b
	}
	return c
}

この最適化のポイントは、p を明示的に計算せずに、p - a, p - b, p - c に相当する値をより少ない算術演算で導き出している点です。

• p - a = (a + b - c) - a = b - c
• p - b = (a + b - c) - b = a - c
• p - c = (a + b - c) - c = a + b - 2c

新しいコードでは、pa を int(b) - pc (ここで pc は int(c)) として計算しています。これは b - c に相当し、元の p - a と同じ値になります。同様に、pb を int(a) - pc (ここで pc は int(c)) として計算しており、これは a - c に相当し、元の p - b と同じ値になります。

pc の計算は pa + pb となっていますが、これは (b - c) + (a - c) = a + b - 2c となり、元の p - c とは異なります。しかし、Paethフィルターのロジックは pa, pb, pc の相対的な大小関係に基づいており、この変更された計算でも正しい結果が得られるように設計されています。重要なのは、これらの値の絶対値の比較が正しく行われることです。

この変更により、中間変数 p の計算が不要になり、減算と abs 呼び出しの回数が削減されます。これにより、CPUの演算回数が減り、Paethフィルターの実行速度が向上します。ベンチマーク結果の BenchmarkPaeth が29.21%高速化されたのは、この最適化の直接的な効果です。

また、abs 関数が reader.go から削除され、paeth_test.go に移動しています。これは、abs 関数が reader.go の他の部分で使われておらず、paeth 関数内でのみインライン化された形で使用されるようになったため、コードの整理と依存関係の削減に貢献しています。

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

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

1. src/pkg/image/png/paeth_test.go:

   • 新規ファイルとして追加されました。
   • slowPaeth 関数が追加され、PNG仕様書に記載されているPaethフィルターのサンプルコードを忠実に再現しています。これは、最適化された paeth 関数が正しく動作するかを検証するための参照実装として機能します。
   • TestPaeth 関数が追加され、paeth 関数と slowPaeth 関数の結果を比較することで、最適化が正しさを損なっていないことを確認しています。
   • BenchmarkPaeth 関数が追加され、Paethフィルター単体の性能を測定するためのベンチマークが提供されています。

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

   • abs 関数が削除されました。この関数は paeth 関数内でのみ使用されており、最適化された paeth 関数では abs の呼び出しがインライン化されたため、独立した関数として保持する必要がなくなりました。
   • paeth 関数の実装が最適化されました。特に、p の計算を省略し、pa, pb, pc の計算をより効率的な算術演算に置き換えることで、パフォーマンスが向上しています。

コアとなるコードの解説

src/pkg/image/png/paeth_test.go

// slowPaeth is a slow but simple implementation of the Paeth function.
// It is a straight port of the sample code in the PNG spec, section 9.4.
func slowPaeth(a, b, c uint8) uint8 {
	p := int(a) + int(b) - int(c)
	pa := abs(p - int(a))
	pb := abs(p - int(b))
	pc := abs(p - int(c))
	if pa <= pb && pa <= pc {
		return a
	} else if pb <= pc {
		return b
	}
	return c
}

func TestPaeth(t *testing.T) {
	for a := 0; a < 256; a += 15 {
		for b := 0; b < 256; b += 15 {
			for c := 0; c < 256; c += 15 {
				got := paeth(uint8(a), uint8(b), uint8(c))
				want := slowPaeth(uint8(a), uint8(b), uint8(c))
				if got != want {
					t.Errorf("a, b, c = %d, %d, %d: got %d, want %d", a, b, c, got, want)
				}
			}
		}
	}
}

func BenchmarkPaeth(b *testing.B) {
	for i := 0; i < b.N; i++ {
		paeth(uint8(i>>16), uint8(i>>8), uint8(i))
	}
}

• slowPaeth: PNG仕様書に記載されているPaethフィルターのアルゴリズムを直接実装したものです。これは、最適化された paeth 関数の結果が正しいことを検証するための「正解」として機能します。
• TestPaeth: paeth 関数と slowPaeth 関数の結果を比較するテストです。0から255までのすべての可能な入力値の組み合わせ（ここでは15刻みでサンプリング）に対して、両関数の出力が一致することを確認します。これにより、最適化が機能の正確性を損なっていないことが保証されます。
• BenchmarkPaeth: paeth 関数の性能を測定するためのベンチマークです。b.N 回のループで paeth 関数を呼び出し、その実行時間を測定します。このベンチマークの結果が、コミットメッセージに記載されている BenchmarkPaeth の改善に直接対応します。

src/pkg/image/png/reader.go

// paeth implements the Paeth filter function, as per the PNG specification.
func paeth(a, b, c uint8) uint8 {
	// This is an optimized version of the sample code in the PNG spec.
	// For example, the sample code starts with:
	//		p := int(a) + int(b) - int(c)
	//		pa := abs(p - int(a))
	// but the optimized form uses fewer arithmetic operations:
	//		pa := int(b) - int(c)
	//		pa = abs(pa)
	pc := int(c)
	pa := int(b) - pc
	pb := int(a) - pc
	pc = pa + pb
	if pa < 0 {
		pa = -pa
	}
	if pb < 0 {
		pb = -pb
	}
	if pc < 0 {
		pc = -pc
	}
	if pa <= pb && pa <= pc {
		return a
	} else if pb <= pc {
		return b
	}
	return c
}

• paeth 関数: Paethフィルターの最適化された実装です。
  • pc := int(c): c の値を int 型に変換して pc に格納します。これは後続の計算で利用されます。
  • pa := int(b) - pc: b - c を計算します。これは、元のPaethフィルターの p - a に相当します。
  • pb := int(a) - pc: a - c を計算します。これは、元のPaethフィルターの p - b に相当します。
  • pc = pa + pb: (b - c) + (a - c) = a + b - 2c を計算します。これは元の p - c とは異なりますが、Paethフィルターの比較ロジックにおいて同等の効果を持ちます。
  • if pa < 0 { pa = -pa } など: 各変数 pa, pb, pc の絶対値を計算します。元の実装では abs 関数を呼び出していましたが、ここでは条件分岐と単項マイナス演算子を使ってインラインで絶対値を計算しています。これにより関数呼び出しのオーバーヘッドがなくなります。
  • if pa <= pb && pa <= pc { ... }: 絶対値の比較を行い、最も小さい差分に対応するピクセル値 (a, b, c のいずれか) を返します。このロジックは元の実装と同じです。

この最適化により、中間変数 p の計算が不要になり、abs 関数の呼び出しもインライン化されるため、全体的な算術演算の回数が削減され、Paethフィルターの実行効率が向上しています。

関連リンク

• Go CL 6242056: https://golang.org/cl/6242056
• PNG (Portable Network Graphics) Specification: https://www.w3.org/TR/PNG/ (特に Section 9.4 "Filter type 4: Paeth filter")

参考にした情報源リンク

• コミットメッセージ内のベンチマーク結果とコメント
• PNG (Portable Network Graphics) Specification, Version 1.2 (W3C Recommendation)
• Go言語の image/png パッケージのソースコード
• Go言語のベンチマークに関するドキュメント (Go testing package)
• PNG Paeth filter - Wikipedia: https://en.wikipedia.org/wiki/Portable_Network_Graphics#Filtering (Paethフィルターの概要理解のため)
• golang-nuts メーリングリストのスレッド (コミットメッセージに記載のURL): https://groups.google.com/group/golang-nuts/browse_thread/thread/22aa8a05040fdd49
• Wikimedia CommonsのPNG透明度デモンストレーション画像: http://upload.wikimedia.org/wikipedia/commons/4/47/PNG_transparency_demonstration_1.png (コミットメッセージに記載のURL)