[インデックス 16336] ファイルの概要
このコミットは、Go言語の標準ライブラリ compress/flate パッケージ内の forwardCopy 関数を最適化し、特に重複するメモリ領域でのコピー操作のパフォーマンスを向上させることを目的としています。flate パッケージは、DEFLATE圧縮アルゴリズムの実装を提供しており、これはZlib、gzip、PNGなどの多くのデータ圧縮フォーマットの基盤となっています。
コミット
commit 28882bbd339ac72b06e0b022311a30a7eef89e46
Author: Keith Randall <khr@golang.org>
Date: Sat May 18 15:28:27 2013 -0700
compress/flate: faster version of forwardCopy
benchmark old ns/op new ns/op delta
BenchmarkDecodeDigitsSpeed1e4 197767 203490 +2.89%
BenchmarkDecodeDigitsSpeed1e5 1873969 1912761 +2.07%
BenchmarkDecodeDigits1e6 18922760 19021056 +0.52%
BenchmarkDecodeDigitsDefault1e4 194975 197054 +1.07%
BenchmarkDecodeDigitsDefault1e5 1704262 1719988 +0.92%
BenchmarkDecodeDigitsDefault1e6 16618354 16351957 -1.60%
BenchmarkDecodeDigitsCompress1e4 195281 194626 -0.34%
BenchmarkDecodeDigitsCompress1e5 1694364 1702372 +0.47%
BenchmarkDecodeDigitsCompress1e6 16463347 16492126 +0.17%
BenchmarkDecodeTwainSpeed1e4 200653 200127 -0.26%
BenchmarkDecodeTwainSpeed1e5 1861385 1759632 -5.47%
BenchmarkDecodeTwainSpeed1e6 18255769 17186679 -5.86%
BenchmarkDecodeTwainDefault1e4 189080 185157 -2.07%
BenchmarkDecodeTwainDefault1e5 1559222 1461465 -6.27%
BenchmarkDecodeTwainDefault1e6 14792125 13879051 -6.17%
BenchmarkDecodeTwainCompress1e4 188881 185151 -1.97%
BenchmarkDecodeTwainCompress1e5 1537031 1456945 -5.21%
BenchmarkDecodeTwainCompress1e6 14805972 13405094 -9.46%
BenchmarkPaeth 4 4 -0.89%
BenchmarkDecodeGray 964679 937244 -2.84%
BenchmarkDecodeNRGBAGradient 3753769 3646416 -2.86%
BenchmarkDecodeNRGBAOpaque 3165856 2981300 -5.83%
BenchmarkDecodePaletted 713950 691984 -3.08%
BenchmarkDecodeRGB 3051718 2924260 -4.18%
R=nigeltao, bradfitz
CC=golang-dev, raph
https://golang.org/cl/9425046
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/28882bbd339ac72b06e0b022311a30a7eef89e46
元コミット内容
このコミットは、compress/flate パッケージ内の forwardCopy 関数の実装を改善し、特にメモリ領域が重複する場合のコピー操作の効率を高めるものです。コミットメッセージには、変更前後のベンチマーク結果が詳細に記載されており、特に BenchmarkDecodeTwain や BenchmarkDecodeNRGBAOpaque など、特定のデコードシナリオで顕著なパフォーマンス向上が見られます。
変更の背景
DEFLATE圧縮アルゴリズムのデコードプロセスでは、以前に出力されたデータの一部を現在の位置にコピーする「バックリファレンス」または「LZ77マッチ」と呼ばれる操作が頻繁に発生します。この際、コピー元とコピー先のメモリ領域が重複することがあります。例えば、"ababab"という文字列を生成する際に、"ab"をコピー元として、その直後に"ab"をコピーし、さらにその直後に"ab"をコピーするといったケースです。
Go言語の組み込み copy 関数は、memmove のように動作し、コピー元とコピー先が重複する場合でも正しく動作しますが、その実装は一般的なケースに最適化されています。しかし、DEFLATEデコードにおける重複コピーのパターンは非常に特殊であり、より効率的なアルゴリズムが存在します。
このコミットの背景には、このようなDEFLATEデコード特有の重複コピー操作のパフォーマンスボトルネックを解消し、Go言語の compress/flate パッケージ全体のデコード速度を向上させるという目的があります。ベンチマーク結果が示すように、特に画像デコード（PNGなど、TwainやNRGBAOpaqueが関連する可能性のあるシナリオ）において、この最適化が大きな効果を発揮しています。
前提知識の解説
DEFLATE圧縮アルゴリズム
DEFLATEは、LZ77アルゴリズムとハフマン符号化を組み合わせた可逆データ圧縮アルゴリズムです。
- LZ77 (Lempel-Ziv 1977): データの繰り返しパターンを検出して、そのパターンを「長さ」と「距離」（バックリファレンス）で置き換えることで圧縮します。例えば、「ABCABCABC」は「ABC」を3回繰り返す、というように表現できます。この「距離」が、コピー元とコピー先が重複する原因となります。
- ハフマン符号化: LZ77によって生成されたシンボル（リテラルバイト、長さ、距離）を、出現頻度に基づいて可変長のビット列に符号化することで、さらに圧縮率を高めます。
DEFLATEのデコードプロセスでは、ハフマン符号を読み取り、それがリテラルバイトなのか、それとも長さと距離のペアなのかを判断します。長さと距離のペアの場合、デコーダは出力バッファ内の指定された「距離」だけ前の位置から、「長さ」分のバイトを現在の出力位置にコピーします。このコピー操作が forwardCopy の役割です。
メモリコピーと重複領域
一般的なメモリコピー関数（例: C言語の memcpy や memmove）は、コピー元とコピー先のメモリ領域の重複をどのように扱うかによって動作が異なります。
memcpy: コピー元とコピー先が重複しないことを前提とします。重複した場合の動作は未定義です。memmove: コピー元とコピー先が重複しても正しく動作することを保証します。内部的には、重複の状況に応じてコピーの方向（前方から後方、または後方から前方）を調整します。
Go言語の組み込み copy 関数は memmove と同様に安全に重複領域を扱えます。しかし、DEFLATEデコードにおける重複コピーは、常に「コピー元がコピー先よりも前にある」という特定のパターン（前方重複）であり、このパターンに特化した最適化が可能です。
ベンチマーク
ソフトウェア開発において、特定のコード変更がパフォーマンスに与える影響を定量的に評価するためにベンチマークが用いられます。Go言語には、go test -bench コマンドで実行できる組み込みのベンチマーク機能があります。ベンチマーク結果は通常、操作あたりの時間（ns/op）や、操作あたりのメモリ割り当て（B/op）、割り当て回数（allocs/op）などで示されます。
このコミットのベンチマーク結果は、ns/op（ナノ秒/操作）で示されており、値が小さいほど高速であることを意味します。delta は変更前後のパフォーマンス変化率を示し、負の値はパフォーマンス向上、正の値はパフォーマンス低下を意味します。
技術的詳細
変更前の forwardCopy 関数は、単純に src スライスから dst スライスへバイトを1つずつコピーしていました。これは、重複がない場合や、重複があっても非常に短いコピー長の場合には問題ありませんが、DEFLATEデコードで頻繁に発生する「コピー元がコピー先よりも前にある重複」のケースでは、より効率的なアプローチが可能です。
新しい forwardCopy の実装は、この前方重複の特性を利用しています。
- 非重複ケースの最適化:
if dst <= srcの条件で、コピー元がコピー先よりも後にあるか、または完全に重複しない場合（つまり、通常のcopy関数で問題ない場合）は、Goの組み込みcopy関数をそのまま使用します。これは、組み込みcopyが高度に最適化されているためです。 - 前方重複ケースの最適化:
dst > srcの場合、つまりコピー元がコピー先よりも前にある前方重複のケースです。この場合、コピーされるデータは、コピー元から始まるパターンが繰り返される形になります。k := dst - src: これは、コピー元とコピー先のオフセットの差であり、繰り返されるパターンの初期の長さを示します。copy(mem[dst:dst+k], mem[src:src+k]): まず、この初期パターンをコピーします。- ループ内で
kを倍にしながらコピーを繰り返すことで、指数関数的にコピーされるデータの量を増やしていきます。これにより、短いコピーを多数繰り返すよりも、効率的に長いデータをコピーできます。これは、いわゆる「ダフィングのデバイス (Duff's Device)」に似た最適化戦略であり、ループアンローリングやブロックコピーを効率的に行うためのテクニックです。
この最適化により、特に長い繰り返しパターンを持つデータ（例: 画像の単色領域や、特定のデータパターン）のデコードにおいて、forwardCopy の呼び出しが大幅に高速化されます。
コアとなるコードの変更箇所
src/pkg/compress/flate/copy.go
--- a/src/pkg/compress/flate/copy.go
+++ b/src/pkg/compress/flate/copy.go
@@ -6,12 +6,27 @@ package flate
// forwardCopy is like the built-in copy function except that it always goes
// forward from the start, even if the dst and src overlap.
-func forwardCopy(dst, src []byte) int {
- if len(src) > len(dst) {
- src = src[:len(dst)]
+// It is equivalent to:
+// for i := 0; i < n; i++ {
+// mem[dst+i] = mem[src+i]
+// }
+func forwardCopy(mem []byte, dst, src, n int) {
+ if dst <= src {
+ copy(mem[dst:dst+n], mem[src:src+n])
+ return
}
- for i, x := range src {
- dst[i] = x
+ for {
+ if dst >= src+n {
+ copy(mem[dst:dst+n], mem[src:src+n])
+ return
+ }
+ // There is some forward overlap. The destination
+ // will be filled with a repeated pattern of mem[src:src+k].
+ // We copy one instance of the pattern here, then repeat.
+ // Each time around this loop k will double.
+ k := dst - src
+ copy(mem[dst:dst+k], mem[src:src+k])
+ n -= k
+ dst += k
}
- return len(src)
}
src/pkg/compress/flate/copy_test.go
forwardCopy のシグネチャ変更に伴い、テストケースの呼び出しも更新されています。
--- a/src/pkg/compress/flate/copy_test.go
+++ b/src/pkg/compress/flate/copy_test.go
@@ -30,10 +30,12 @@ func TestForwardCopy(t *testing.T) {
}\n\tfor _, tc := range testCases {
b := []byte("0123456789")
-\t\tdst := b[tc.dst0:tc.dst1]
-\t\tsrc := b[tc.src0:tc.src1]
-\t\tn := forwardCopy(dst, src)
-\t\tgot := string(dst[:n])
+\t\tn := tc.dst1 - tc.dst0
+\t\tif tc.src1-tc.src0 < n {
+\t\t\tn = tc.src1 - tc.src0
+\t\t}
+\t\tforwardCopy(b, tc.dst0, tc.src0, n)
+\t\tgot := string(b[tc.dst0 : tc.dst0+n])
\t\tif got != tc.want {
\t\t\tt.Errorf("dst=b[%d:%d], src=b[%d:%d]: got %q, want %q",
\t\t\t\ttc.dst0, tc.dst1, tc.src0, tc.src1, got, tc.want)
src/pkg/compress/flate/inflate.go
decompressor.copyHist メソッド内で forwardCopy の呼び出しが新しいシグネチャに合わせて更新されています。
--- a/src/pkg/compress/flate/inflate.go
+++ b/src/pkg/compress/flate/inflate.go
@@ -511,7 +511,7 @@ func (f *decompressor) copyHist() bool {
if x := len(f.hist) - p; n > x {
n = x
}
-\t\tforwardCopy(f.hist[f.hp:f.hp+n], f.hist[p:p+n])
+\t\tforwardCopy(f.hist[:], f.hp, p, n)
p += n
f.hp += n
f.copyLen -= n
コアとなるコードの解説
forwardCopy 関数の変更
変更前:
func forwardCopy(dst, src []byte) int {
if len(src) > len(dst) {
src = src[:len(dst)]
}
for i, x := range src {
dst[i] = x
}
return len(src)
}
このバージョンは、src スライスから dst スライスへバイトを1つずつコピーする非常にシンプルな実装でした。range ループを使用しているため、バイトごとのコピーとなり、パフォーマンス上のボトルネックとなる可能性がありました。また、dst と src がスライスとして渡されるため、呼び出し元で適切なスライス範囲を計算する必要がありました。
変更後:
func forwardCopy(mem []byte, dst, src, n int) {
if dst <= src {
copy(mem[dst:dst+n], mem[src:src+n])
return
}
for {
if dst >= src+n {
copy(mem[dst:dst+n], mem[src:src+n])
return
}
// There is some forward overlap. The destination
// will be filled with a repeated pattern of mem[src:src+k].
// We copy one instance of the pattern here, then repeat.
// Each time around this loop k will double.
k := dst - src
copy(mem[dst:dst+k], mem[src:src+k])
n -= k
dst += k
}
}
新しい forwardCopy は、以下のように動作します。
- シグネチャの変更:
mem []byte, dst, src, n intとなり、コピー対象の全体メモリmemと、その中のオフセットdst(コピー先開始位置)、src(コピー元開始位置)、n(コピー長) を直接受け取るようになりました。これにより、呼び出し元でのスライス作成のオーバーヘッドが減り、関数内部で効率的なスライス操作が可能になります。 - 非重複/後方重複の最適化:
if dst <= srcの条件は、コピー元がコピー先よりも後にあるか、または完全に重複しないケースをカバーします。この場合、Goの組み込みcopy関数が最も効率的であるため、これを利用します。 - 前方重複の最適化:
dst > srcの場合、つまりコピー元がコピー先よりも前にある前方重複のケースです。この状況では、コピーされるデータは、コピー元から始まるパターンが繰り返される形になります。k := dst - src: これは、コピー元とコピー先のオフセットの差であり、繰り返されるパターンの初期の長さを示します。例えば、src=0, dst=2であればk=2となり、2バイトのパターンが繰り返されます。copy(mem[dst:dst+k], mem[src:src+k]): まず、この初期パターンをコピーします。- ループ内で、コピーされたパターン自体をコピー元として利用し、コピー長
nが尽きるまでkを倍にしながらコピーを繰り返します。これにより、指数関数的にコピーされるデータの量を増やし、効率的なブロックコピーを実現します。これは、DEFLATEデコードにおけるバックリファレンスのコピーに特化した非常に効率的なアルゴリズムです。
copy_test.go の変更
forwardCopy のシグネチャ変更に合わせて、テストコードも更新されています。特に、tc.dst1 - tc.dst0 でコピー長 n を計算し、forwardCopy(b, tc.dst0, tc.src0, n) のように、全体バッファ b とオフセット、長さを渡す形式に変更されています。これにより、テストが新しい関数シグネチャと動作に適合していることを確認できます。
inflate.go の変更
decompressor.copyHist メソッドは、DEFLATEデコード中に履歴バッファ（f.hist）からデータをコピーする際に forwardCopy を使用します。このコミットでは、forwardCopy のシグネチャ変更に合わせて、呼び出しが forwardCopy(f.hist[:], f.hp, p, n) に更新されています。f.hist[:] は f.hist の基底配列全体を渡し、f.hp と p がそれぞれコピー先とコピー元のオフセット、n がコピー長となります。これにより、inflate パッケージが新しい最適化された forwardCopy 関数を正しく利用できるようになります。
関連リンク
- Go言語の
compress/flateパッケージのドキュメント: https://pkg.go.dev/compress/flate - DEFLATE (Wikipedia): https://ja.wikipedia.org/wiki/DEFLATE
- LZ77 (Wikipedia): https://ja.wikipedia.org/wiki/LZ77%E3%81%8A%E3%82%88%E3%81%B3LZ78
- ハフマン符号 (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
- Go言語の
copy関数に関する議論やドキュメント - DEFLATEアルゴリズムに関する技術文書 (RFC 1951など)
- Duff's Device (Wikipedia): https://en.wikipedia.org/wiki/Duff%27s_Device (直接のDuff's Deviceではないが、同様の最適化思想)
- Go言語のベンチマークに関するドキュメント: https://pkg.go.dev/testing (特に
Benchmark関数について) - Go言語のコードレビューシステム (Gerrit) の変更リスト: https://golang.org/cl/9425046 (コミットメッセージに記載されているリンク)