[インデックス 12999] ファイルの概要
このコミットは、Go言語の標準ライブラリ compress/flate
パッケージにおけるDEFLATEデコーディングのパフォーマンス最適化を目的としています。特に、履歴コピー(history-copy)デコーディングの効率を向上させることで、圧縮解除処理の速度を大幅に改善しています。ベンチマーク結果とプロファイルデータが示唆するように、特に大きなデータセットにおいて顕著な性能向上が見られます。
コミット
commit 4de15a5cdaf94b9e2269fb79008c8c862f355d2a
Author: Nigel Tao <nigeltao@golang.org>
Date: Tue May 1 10:51:34 2012 +1000
compress/flate: optimize history-copy decoding.
The forwardCopy function could be re-written in asm, and the copyHuff
method could probably be rolled into huffmanBlock and copyHist, but
I'm leaving those changes for future CLs.
compress/flate benchmarks:
benchmark old ns/op new ns/op delta
BenchmarkDecoderBestSpeed1K 385327 435140 +12.93%
BenchmarkDecoderBestSpeed10K 1245190 1062112 -14.70%
BenchmarkDecoderBestSpeed100K 8512365 5833680 -31.47%
BenchmarkDecoderDefaultCompression1K 382225 421301 +10.22%
BenchmarkDecoderDefaultCompression10K 867950 613890 -29.27%
BenchmarkDecoderDefaultCompression100K 5658240 2466726 -56.40%
BenchmarkDecoderBestCompression1K 383760 421634 +9.87%
BenchmarkDecoderBestCompression10K 867743 614671 -29.16%
BenchmarkDecoderBestCompression100K 5660160 2464996 -56.45%
image/png benchmarks:
benchmark old ns/op new ns/op delta
BenchmarkDecodeGray 2540834 2389624 -5.95%
BenchmarkDecodeNRGBAGradient 10052700 9534565 -5.15%
BenchmarkDecodeNRGBAOpaque 8704710 8163430 -6.22%
BenchmarkDecodePaletted 1458779 1325017 -9.17%
BenchmarkDecodeRGB 7183606 6794668 -5.41%
Wall time for Denis Cheremisov's PNG-decoding program given in
https://groups.google.com/group/golang-nuts/browse_thread/thread/22aa8a05040fdd49
Before: 3.07s
After: 2.32s
Delta: -24%
Before profile:
Total: 304 samples
159 52.3% 52.3% 251 82.6% compress/flate.(*decompressor).huffmanBlock
58 19.1% 71.4% 76 25.0% compress/flate.(*decompressor).huffSym
32 10.5% 81.9% 32 10.5% hash/adler32.update
16 5.3% 87.2% 22 7.2% bufio.(*Reader).ReadByte
16 5.3% 92.4% 37 12.2% compress/flate.(*decompressor).moreBits
7 2.3% 94.7% 7 2.3% hash/crc32.update
7 2.3% 97.0% 7 2.3% runtime.memmove
5 1.6% 98.7% 5 1.6% scanblock
2 0.7% 99.3% 9 3.0% runtime.copy
1 0.3% 99.7% 1 0.3% compress/flate.(*huffmanDecoder).init
After profile:
Total: 230 samples
59 25.7% 25.7% 70 30.4% compress/flate.(*decompressor).huffSym
45 19.6% 45.2% 45 19.6% hash/adler32.update
35 15.2% 60.4% 35 15.2% compress/flate.forwardCopy
20 8.7% 69.1% 151 65.7% compress/flate.(*decompressor).huffmanBlock
16 7.0% 76.1% 24 10.4% compress/flate.(*decompressor).moreBits
15 6.5% 82.6% 15 6.5% runtime.memmove
11 4.8% 87.4% 50 21.7% compress/flate.(*decompressor).copyHist
7 3.0% 90.4% 7 3.0% hash/crc32.update
6 2.6% 93.0% 9 3.9% bufio.(*Reader).ReadByte
4 1.7% 94.8% 4 1.7% runtime.slicearray
R=rsc, rogpeppe, dave
CC=golang-dev, krasin
https://golang.org/cl/6127064
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/4de15a5cdaf94b9e2269fb79008c8c862f355d2a
元コミット内容
compress/flate: optimize history-copy decoding.
The forwardCopy function could be re-written in asm, and the copyHuff
method could probably be rolled into huffmanBlock and copyHist, but
I'm leaving those changes for future CLs.
compress/flate benchmarks:
benchmark old ns/op new ns/op delta
BenchmarkDecoderBestSpeed1K 385327 435140 +12.93%
BenchmarkDecoderBestSpeed10K 1245190 1062112 -14.70%
BenchmarkDecoderBestSpeed100K 8512365 5833680 -31.47%
BenchmarkDecoderDefaultCompression1K 382225 421301 +10.22%
BenchmarkDecoderDefaultCompression10K 867950 613890 -29.27%
BenchmarkDecoderDefaultCompression100K 5658240 2466726 -56.40%
BenchmarkDecoderBestCompression1K 383760 421634 +9.87%
BenchmarkDecoderBestCompression10K 867743 614671 -29.16%
BenchmarkDecoderBestCompression100K 5660160 2464996 -56.45%
image/png benchmarks:
benchmark old ns/op new ns/op delta
BenchmarkDecodeGray 2540834 2389624 -5.95%
BenchmarkDecodeNRGBAGradient 10052700 9534565 -5.15%
BenchmarkDecodeNRGBAOpaque 8704710 8163430 -6.22%
BenchmarkDecodePaletted 1458779 1325017 -9.17%
BenchmarkDecodeRGB 7183606 6794668 -5.41%
Wall time for Denis Cheremisov's PNG-decoding program given in
https://groups.google.com/group/golang-nuts/browse_thread/thread/22aa8a05040fdd49
Before: 3.07s
After: 2.32s
Delta: -24%
Before profile:
Total: 304 samples
159 52.3% 52.3% 251 82.6% compress/flate.(*decompressor).huffmanBlock
58 19.1% 71.4% 76 25.0% compress/flate.(*decompressor).huffSym
32 10.5% 81.9% 32 10.5% hash/adler32.update
16 5.3% 87.2% 22 7.2% bufio.(*Reader).ReadByte
16 5.3% 92.4% 37 12.2% compress/flate.(*decompressor).moreBits
7 2.3% 94.7% 7 2.3% hash/crc32.update
7 2.3% 97.0% 7 2.3% runtime.memmove
5 1.6% 98.7% 5 1.6% scanblock
2 0.7% 99.3% 9 3.0% runtime.copy
1 0.3% 99.7% 1 0.3% compress/flate.(*huffmanDecoder).init
After profile:
Total: 230 samples
59 25.7% 25.7% 70 30.4% compress/flate.(*decompressor).huffSym
45 19.6% 45.2% 45 19.6% hash/adler32.update
35 15.2% 60.4% 35 15.2% compress/flate.forwardCopy
20 8.7% 69.1% 151 65.7% compress/flate.(*decompressor).huffmanBlock
16 7.0% 76.1% 24 10.4% compress/flate.(*decompressor).moreBits
15 6.5% 82.6% 15 6.5% runtime.memmove
11 4.8% 87.4% 50 21.7% compress/flate.(*decompressor).copyHist
7 3.0% 90.4% 7 3.0% hash/crc32.update
6 2.6% 93.0% 9 3.9% bufio.(*Reader).ReadByte
4 1.7% 94.8% 4 1.7% runtime.slicearray
R=rsc, rogpeppe, dave
CC=golang-dev, krasin
https://golang.org/cl/6127064
変更の背景
このコミットの主な背景は、Go言語の compress/flate
パッケージにおけるDEFLATEデコーディングのパフォーマンス改善です。特に、大きなデータセットの圧縮解除において、既存の実装が非効率であることがプロファイリングによって明らかになっていました。
DEFLATEアルゴリズムでは、データ圧縮のために、以前に出現したデータの繰り返し(履歴コピー)を利用します。デコード時には、この履歴コピーを効率的に再現する必要があります。元の実装では、この履歴コピーの処理がバイト単位のループで行われており、これがパフォーマンスのボトルネックとなっていました。
コミットメッセージに示されているベンチマーク結果は、この問題の深刻さを示しています。特に BenchmarkDecoderDefaultCompression100K
や BenchmarkDecoderBestCompression100K
のような大きなデータサイズ(100KB)のベンチマークでは、旧バージョンと比較して ns/op
(操作あたりのナノ秒) が大幅に減少しており、最大で56%以上の性能向上が達成されています。これは、デコードにかかる時間が半分以下になったことを意味します。
また、プロファイルデータは、変更前は compress/flate.(*decompressor).huffmanBlock
がCPU時間の大部分(52.3%)を占めていたことを示しています。この関数内で履歴コピーの処理が行われていたため、ここが最適化の主要なターゲットとなりました。変更後には huffmanBlock
の割合が20%に減少し、代わりに新しく導入された forwardCopy
や copyHist
がプロファイルに現れていますが、全体のサンプル数(CPU時間)は304から230に減少しており、全体的な効率が向上したことを裏付けています。
この最適化は、Go言語でPNG画像をデコードする際のパフォーマンスにも良い影響を与えています。image/png
パッケージのベンチマークでも、すべてのテストケースで数パーセントの改善が見られ、外部のPNGデコードプログラムのウォールタイムも24%短縮されています。これは、image/png
が内部で compress/flate
を利用しているため、基盤となる圧縮解除の高速化が直接的な恩恵をもたらした結果です。
前提知識の解説
DEFLATEアルゴリズム
DEFLATEは、ロスレスデータ圧縮アルゴリズムであり、LZ77アルゴリズムとハフマン符号化の組み合わせに基づいています。Gzip、PNG、ZIPなどの一般的なファイル形式で広く使用されています。
- LZ77 (Lempel-Ziv 1977): 繰り返し出現するバイト列を、以前に出現した同じバイト列への「参照」(オフセットと長さのペア)に置き換えることでデータを圧縮します。例えば、「ABCABCABC」という文字列は、「ABC」と「その3バイトを2回繰り返す」という形で表現できます。この「参照」が「履歴コピー」の概念に直結します。
- ハフマン符号化 (Huffman Coding): LZ77によって生成されたリテラルバイト(圧縮されていないデータ)と参照(オフセットと長さのペア)を、出現頻度に基づいて可変長のビット列に符号化します。出現頻度の高いシンボルには短いビット列を、低いシンボルには長いビット列を割り当てることで、全体のデータサイズを削減します。
compress/flate
パッケージ
Go言語の標準ライブラリ compress/flate
は、DEFLATE圧縮および圧縮解除の機能を提供します。このパッケージは、compress/gzip
や image/png
などの他の標準ライブラリの基盤としても使用されています。
履歴コピー (History-copy decoding)
DEFLATEデコードにおいて、圧縮されたデータストリームは、リテラルバイト(そのままのデータ)と、以前に出力されたデータの一部をコピーする指示(距離と長さ)で構成されます。この「以前に出力されたデータの一部をコピーする」操作が履歴コピーです。デコーダは、デコード中の出力バッファ(履歴バッファ)から指定された距離だけ遡り、指定された長さのバイト列を現在の位置にコピーします。
例えば、出力バッファが [A, B, C, D, E, F]
で、デコーダが「距離3、長さ3」のコピー指示を受け取った場合、現在の位置から3バイト前(C)から3バイト(C, D, E)をコピーし、出力は [A, B, C, D, E, F, C, D, E]
となります。
この操作の効率は、デコーダの全体的なパフォーマンスに大きく影響します。特に、コピー元とコピー先がオーバーラップする場合(例:[A, B, C, D]
から距離1、長さ3をコピーすると [A, B, C, D, B, C, D]
となる)、単純な copy
関数では正しく動作しないため、特別な処理が必要になります。
Go言語におけるスライスとメモリコピー
Go言語では、スライスは基盤となる配列への参照です。copy
関数は、ソーススライスからデスティネーションスライスへ要素をコピーしますが、ソースとデスティネーションがオーバーラップしている場合、その動作は未定義または期待通りにならない可能性があります。特に、ソースの開始位置がデスティネーションの開始位置よりも前にある場合、コピー中にソースデータが上書きされてしまい、誤った結果になることがあります。
このため、履歴コピーのようにオーバーラップする可能性のあるメモリ領域間でバイトをコピーする際には、バイト単位で順方向にコピーするカスタム関数が必要になります。
ベンチマークとプロファイリング
- ベンチマーク (Benchmarks): ソフトウェアの性能を測定するためのテストです。Go言語では、
go test -bench=.
コマンドでベンチマークを実行できます。ns/op
(nanoseconds per operation): 1回の操作にかかる平均ナノ秒数を示します。この値が小さいほど性能が良いことを意味します。delta
: 変更前後の性能変化率を示します。負の値は性能向上、正の値は性能低下を意味します。
- プロファイリング (Profiling): プログラムの実行中に、CPU使用率、メモリ使用量、関数呼び出し回数などを測定し、プログラムのどの部分が最も多くのリソースを消費しているかを特定する手法です。Go言語では、
pprof
ツールを使用してプロファイルデータを収集・分析できます。samples
: プロファイリング期間中にその関数が実行されていた回数(またはCPU時間)の相対的な指標です。%
: その関数が全体のCPU時間の何パーセントを占めているかを示します。- プロファイルデータは、性能ボトルネックを特定し、最適化のターゲットを絞り込むのに非常に役立ちます。
技術的詳細
このコミットの主要な技術的変更点は、DEFLATEデコーダにおける履歴コピーの処理方法の改善です。
-
forwardCopy
関数の導入:src/pkg/compress/flate/copy.go
に新しくforwardCopy
関数が追加されました。- この関数は、Goの組み込み
copy
関数とは異なり、コピー元とコピー先がオーバーラップしている場合でも、常に先頭から順にバイトをコピーします。これにより、履歴コピーの際にデータが正しく複製されることが保証されます。 - 実装は単純なバイト単位のループですが、これがオーバーラップするスライス間のコピーを安全に行うためのGoにおける慣用的な方法です。
-
copyHist
メソッドの導入とhuffmanBlock
のリファクタリング:src/pkg/compress/flate/inflate.go
内で、履歴コピーのロジックがhuffmanBlock
メソッドから新しく導入されたcopyHist
メソッドに抽出されました。- 元の
huffmanBlock
メソッド内の履歴コピー処理は、バイト単位のループで、バッファの境界チェックやフラッシュ処理がループ内に散在していました。 copyHist
メソッドは、forwardCopy
を利用して、一度に可能な限り多くのバイトをコピーするように変更されました。これにより、ループのイテレーション回数が減り、バッファの境界処理がより効率的になりました。copyHist
は、コピーが完了したかどうか、または履歴バッファが満杯になったかどうかを報告するブール値を返します。これにより、huffmanBlock
やcopyHuff
からの呼び出し元が、バッファのフラッシュなどの後続処理を適切に制御できるようになります。- 特に、
copyHist
内でn := f.copyLen
から始まり、len(f.hist) - f.hp
(現在の書き込み位置からバッファの終わりまでの残り容量) とlen(f.hist) - p
(現在の読み込み位置からバッファの終わりまでの残り容量) の最小値を取ることで、一度のforwardCopy
呼び出しで可能な限り多くのデータをコピーしようとします。これにより、ループのオーバーヘッドが削減されます。
-
copyHuff
メソッドの簡素化:copyHuff
メソッドは、以前は履歴コピーのロジックを直接含んでいましたが、copyHist
メソッドを呼び出すように簡素化されました。これにより、コードの重複が排除され、可読性と保守性が向上しました。
これらの変更により、特に大きなデータブロックのデコード時における履歴コピーの効率が大幅に向上し、結果として compress/flate
パッケージ全体のデコード性能が改善されました。プロファイルデータが示すように、以前は huffmanBlock
が支配的だったCPU使用率が分散され、より効率的な forwardCopy
や copyHist
に処理が移ったことが確認できます。
コアとなるコードの変更箇所
このコミットでは、以下の3つのファイルが変更されています。
src/pkg/compress/flate/copy.go
(新規追加)src/pkg/compress/flate/copy_test.go
(新規追加)src/pkg/compress/flate/inflate.go
(修正)
diff --git a/src/pkg/compress/flate/copy.go b/src/pkg/compress/flate/copy.go
new file mode 100644
index 0000000000..06e5d2e66d
--- /dev/null
+++ b/src/pkg/compress/flate/copy.go
@@ -0,0 +1,17 @@
+// Copyright 2012 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+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)]
+ }
+ for i, x := range src {
+ dst[i] = x
+ }
+ return len(src)
+}
diff --git /dev/null b/src/pkg/compress/flate/copy_test.go
new file mode 100644
index 0000000000..d13941cf1c
--- /dev/null
+++ b/src/pkg/compress/flate/copy_test.go
@@ -0,0 +1,42 @@
+// Copyright 2012 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package flate
+
+import (
+ "testing"
+)
+
+func TestForwardCopy(t *testing.T) {
+ testCases := []struct {
+ dst0, dst1 int
+ src0, src1 int
+ want string
+ }{
+ {0, 9, 0, 9, "012345678"},
+ {0, 5, 4, 9, "45678"},
+ {4, 9, 0, 5, "01230"},
+ {1, 6, 3, 8, "34567"},
+ {3, 8, 1, 6, "12121"},
+ {0, 9, 3, 6, "345"},
+ {3, 6, 0, 9, "012"},
+ {1, 6, 0, 9, "00000"},
+ {0, 4, 7, 8, "7"},
+ {0, 1, 6, 8, "6"},
+ {4, 4, 6, 9, ""},
+ {2, 8, 6, 6, ""},
+ {0, 0, 0, 0, ""},
+ }
+ for _, tc := range testCases {
+ b := []byte("012345678")
+ dst := b[tc.dst0:tc.dst1]
+ src := b[tc.src0:tc.src1]
+ n := forwardCopy(dst, src)
+ got := string(dst[:n])
+ if got != tc.want {
+ t.Errorf("dst=b[%d:%d], src=b[%d:%d]: got %q, want %q",
+ tc.dst0, tc.dst1, tc.src0, tc.src1, got, tc.want)
+ }
+ }
+}
diff --git a/src/pkg/compress/flate/inflate.go b/src/pkg/compress/flate/inflate.go
index 3f2042bfe9..a4be91b6f7 100644
--- a/src/pkg/compress/flate/inflate.go
+++ b/src/pkg/compress/flate/inflate.go
@@ -505,51 +505,49 @@ func (f *decompressor) huffmanBlock() {
return
}
- p := f.hp - dist
- if p < 0 {
- p += len(f.hist)
- }
- for i := 0; i < length; i++ {
- f.hist[f.hp] = f.hist[p]
- f.hp++
- p++
- if f.hp == len(f.hist) {
- // After flush continue copying out of history.
- f.copyLen = length - (i + 1)
- f.copyDist = dist
- f.flush((*decompressor).copyHuff)
- return
- }
- if p == len(f.hist) {
- p = 0
- }
+ f.copyLen, f.copyDist = length, dist
+ if f.copyHist() {
+ return
}
}
panic("unreached")
}
-func (f *decompressor) copyHuff() {
- length := f.copyLen
- dist := f.copyDist
- p := f.hp - dist
+// copyHist copies f.copyLen bytes from f.hist (f.copyDist bytes ago) to itself.
+// It reports whether the f.hist buffer is full.
+func (f *decompressor) copyHist() bool {
+ p := f.hp - f.copyDist
if p < 0 {
p += len(f.hist)
}
- for i := 0; i < length; i++ {
- f.hist[f.hp] = f.hist[p]
- f.hp++
- p++
+ for f.copyLen > 0 {
+ n := f.copyLen
+ if x := len(f.hist) - f.hp; n > x {
+ n = x
+ }
+ if x := len(f.hist) - p; n > x {
+ n = x
+ }
+ forwardCopy(f.hist[f.hp:f.hp+n], f.hist[p:p+n])
+ p += n
+ f.hp += n
+ f.copyLen -= n
if f.hp == len(f.hist) {
- f.copyLen = length - (i + 1)
+ // After flush continue copying out of history.
f.flush((*decompressor).copyHuff)
- return
+ return true
}
if p == len(f.hist) {
p = 0
}
}
-
- // Continue processing Huffman block.
+ return false
+}
+
+func (f *decompressor) copyHuff() {
+ if f.copyHist() {
+ return
+ }
f.huffmanBlock()
}
@@ -584,9 +582,9 @@ func (f *decompressor) dataBlock() {
f.copyData()
}
+// copyData copies f.copyLen bytes from the underlying reader into f.hist.
+// It pauses for reads when f.hist is full.
func (f *decompressor) copyData() {
- // Read f.dataLen bytes into history,
- // pausing for reads as history fills.
n := f.copyLen
for n > 0 {
m := len(f.hist) - f.hp
コアとなるコードの解説
src/pkg/compress/flate/copy.go
このファイルは新しく追加され、forwardCopy
関数を定義しています。
// 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)]
}
for i, x := range src {
dst[i] = x
}
return len(src)
}
- 目的: Goの組み込み
copy
関数は、コピー元とコピー先のスライスがオーバーラップしている場合に、期待通りの動作をしない可能性があります。特に、コピー元がコピー先よりも「前」にある場合、コピー中にコピー元のデータが上書きされてしまい、結果が不正になることがあります。forwardCopy
は、このような状況でも常に先頭から順にバイトをコピーすることで、正しい結果を保証します。 - 実装:
for i, x := range src
ループを使って、src
スライスの各バイトをdst
スライスの対応する位置に1バイトずつコピーしています。これにより、オーバーラップがあっても常に正しい順序でデータが転送されます。 len(src) > len(dst)
の処理:src
の長さがdst
の長さを超える場合、src
をdst
の長さに切り詰めています。これは、dst
に収まる範囲でしかコピーできないためです。
src/pkg/compress/flate/inflate.go
このファイルでは、主に huffmanBlock
メソッドと copyHuff
メソッドが変更され、新しい copyHist
メソッドが導入されました。
huffmanBlock
メソッドの変更
f.copyLen, f.copyDist = length, dist
if f.copyHist() {
return
}
- 以前は、
huffmanBlock
メソッド内で履歴コピーのロジックが直接、バイト単位のループで実装されていました。 - 変更後、このロジックは
f.copyLen
とf.copyDist
を設定し、新しく導入されたf.copyHist()
メソッドを呼び出す形に簡素化されました。 f.copyHist()
がtrue
を返した場合(履歴バッファが満杯になり、フラッシュが必要な場合)、huffmanBlock
はすぐにreturn
します。
copyHist
メソッドの新規追加
// copyHist copies f.copyLen bytes from f.hist (f.copyDist bytes ago) to itself.
// It reports whether the f.hist buffer is full.
func (f *decompressor) copyHist() bool {
p := f.hp - f.copyDist
if p < 0 {
p += len(f.hist)
}
for f.copyLen > 0 {
n := f.copyLen
if x := len(f.hist) - f.hp; n > x {
n = x
}
if x := len(f.hist) - p; n > x {
n = x
}
forwardCopy(f.hist[f.hp:f.hp+n], f.hist[p:p+n])
p += n
f.hp += n
f.copyLen -= n
if f.hp == len(f.hist) {
// After flush continue copying out of history.
f.flush((*decompressor).copyHuff)
return true
}
if p == len(f.hist) {
p = 0
}
}
return false
}
- 目的: 履歴バッファ
f.hist
内での履歴コピー操作を効率的に実行します。 p
の計算: コピー元の開始位置p
を計算します。f.hp
は現在の書き込み位置、f.copyDist
はコピーするデータの距離です。p
が負になる場合(リングバッファの終端を超えて遡る場合)、len(f.hist)
を加算してリングバッファの正しい位置に調整します。- メインループ:
f.copyLen
が0になるまでループを続けます。これは、コピーすべきバイトが残っている限り処理を繰り返すことを意味します。 n
の計算: 一度にコピーできるバイト数n
を決定します。これは、以下の3つの値の最小値です。f.copyLen
: 残りのコピーすべきバイト数。len(f.hist) - f.hp
: 現在の書き込み位置から履歴バッファの終端までの残り容量。len(f.hist) - p
: 現在の読み込み位置から履歴バッファの終端までの残り容量。 この計算により、バッファの境界を越えない範囲で、かつコピーすべき残りのバイト数を超えない範囲で、最大限のバイト数を一度にコピーできます。
forwardCopy
の利用: 計算されたn
を使って、forwardCopy
関数を呼び出し、実際にバイトをコピーします。これにより、オーバーラップするメモリ領域でも安全かつ効率的にコピーが行われます。- ポインタの更新: コピー後、
p
(読み込みポインタ) とf.hp
(書き込みポインタ) をn
だけ進め、f.copyLen
をn
だけ減らします。 - バッファ満杯のチェック:
f.hp == len(f.hist)
の場合、履歴バッファが満杯になったことを意味します。この場合、f.flush((*decompressor).copyHuff)
を呼び出してバッファをフラッシュし、true
を返して呼び出し元に処理を中断するよう伝えます。 return false
: ループが終了し、すべてのバイトがコピーされた場合、false
を返します。
copyHuff
メソッドの変更
func (f *decompressor) copyHuff() {
if f.copyHist() {
return
}
f.huffmanBlock()
}
- 以前は、
copyHuff
メソッドも履歴コピーのロジックを直接含んでいましたが、copyHist
メソッドの導入により、その役割が簡素化されました。 - 現在では、単に
f.copyHist()
を呼び出し、それがtrue
を返した場合(バッファが満杯でフラッシュが必要な場合)はreturn
します。そうでない場合は、f.huffmanBlock()
を呼び出してハフマンブロックの処理を続行します。
これらの変更により、履歴コピーの処理がモジュール化され、バッファの境界処理がより効率的になり、結果としてデコード性能が大幅に向上しました。
関連リンク
- Go CL 6127064: https://golang.org/cl/6127064
- Denis Cheremisov's PNG-decoding program discussion: https://groups.google.com/group/golang-nuts/browse_thread/thread/22aa8a05040fdd49
参考にした情報源リンク
- DEFLATE (Wikipedia): https://ja.wikipedia.org/wiki/DEFLATE
- ハフマン符号 (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言語の
copy
関数とスライスのオーバーラップに関する議論 (Stack Overflowなど): https://stackoverflow.com/questions/tagged/go+slice+copy (一般的な情報源として) - Go言語のベンチマークとプロファイリングに関する公式ドキュメント: https://go.dev/doc/diagnostics (一般的な情報源として)
- Go言語
compress/flate
パッケージのソースコード: https://pkg.go.dev/compress/flate (コミット時点のバージョンとは異なる可能性がありますが、一般的な構造理解のため)