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

[インデックス 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アルゴリズムでは、データ圧縮のために、以前に出現したデータの繰り返し(履歴コピー)を利用します。デコード時には、この履歴コピーを効率的に再現する必要があります。元の実装では、この履歴コピーの処理がバイト単位のループで行われており、これがパフォーマンスのボトルネックとなっていました。

コミットメッセージに示されているベンチマーク結果は、この問題の深刻さを示しています。特に BenchmarkDecoderDefaultCompression100KBenchmarkDecoderBestCompression100K のような大きなデータサイズ(100KB)のベンチマークでは、旧バージョンと比較して ns/op (操作あたりのナノ秒) が大幅に減少しており、最大で56%以上の性能向上が達成されています。これは、デコードにかかる時間が半分以下になったことを意味します。

また、プロファイルデータは、変更前は compress/flate.(*decompressor).huffmanBlock がCPU時間の大部分(52.3%)を占めていたことを示しています。この関数内で履歴コピーの処理が行われていたため、ここが最適化の主要なターゲットとなりました。変更後には huffmanBlock の割合が20%に減少し、代わりに新しく導入された forwardCopycopyHist がプロファイルに現れていますが、全体のサンプル数(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/gzipimage/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デコーダにおける履歴コピーの処理方法の改善です。

  1. forwardCopy 関数の導入:

    • src/pkg/compress/flate/copy.go に新しく forwardCopy 関数が追加されました。
    • この関数は、Goの組み込み copy 関数とは異なり、コピー元とコピー先がオーバーラップしている場合でも、常に先頭から順にバイトをコピーします。これにより、履歴コピーの際にデータが正しく複製されることが保証されます。
    • 実装は単純なバイト単位のループですが、これがオーバーラップするスライス間のコピーを安全に行うためのGoにおける慣用的な方法です。
  2. copyHist メソッドの導入と huffmanBlock のリファクタリング:

    • src/pkg/compress/flate/inflate.go 内で、履歴コピーのロジックが huffmanBlock メソッドから新しく導入された copyHist メソッドに抽出されました。
    • 元の huffmanBlock メソッド内の履歴コピー処理は、バイト単位のループで、バッファの境界チェックやフラッシュ処理がループ内に散在していました。
    • copyHist メソッドは、forwardCopy を利用して、一度に可能な限り多くのバイトをコピーするように変更されました。これにより、ループのイテレーション回数が減り、バッファの境界処理がより効率的になりました。
    • copyHist は、コピーが完了したかどうか、または履歴バッファが満杯になったかどうかを報告するブール値を返します。これにより、huffmanBlockcopyHuff からの呼び出し元が、バッファのフラッシュなどの後続処理を適切に制御できるようになります。
    • 特に、copyHist 内で n := f.copyLen から始まり、len(f.hist) - f.hp (現在の書き込み位置からバッファの終わりまでの残り容量) と len(f.hist) - p (現在の読み込み位置からバッファの終わりまでの残り容量) の最小値を取ることで、一度の forwardCopy 呼び出しで可能な限り多くのデータをコピーしようとします。これにより、ループのオーバーヘッドが削減されます。
  3. copyHuff メソッドの簡素化:

    • copyHuff メソッドは、以前は履歴コピーのロジックを直接含んでいましたが、copyHist メソッドを呼び出すように簡素化されました。これにより、コードの重複が排除され、可読性と保守性が向上しました。

これらの変更により、特に大きなデータブロックのデコード時における履歴コピーの効率が大幅に向上し、結果として compress/flate パッケージ全体のデコード性能が改善されました。プロファイルデータが示すように、以前は huffmanBlock が支配的だったCPU使用率が分散され、より効率的な forwardCopycopyHist に処理が移ったことが確認できます。

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

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

  1. src/pkg/compress/flate/copy.go (新規追加)
  2. src/pkg/compress/flate/copy_test.go (新規追加)
  3. 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 の長さを超える場合、srcdst の長さに切り詰めています。これは、dst に収まる範囲でしかコピーできないためです。

src/pkg/compress/flate/inflate.go

このファイルでは、主に huffmanBlock メソッドと copyHuff メソッドが変更され、新しい copyHist メソッドが導入されました。

huffmanBlock メソッドの変更

 		f.copyLen, f.copyDist = length, dist
 		if f.copyHist() {
 			return
 		}
  • 以前は、huffmanBlock メソッド内で履歴コピーのロジックが直接、バイト単位のループで実装されていました。
  • 変更後、このロジックは f.copyLenf.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つの値の最小値です。
    1. f.copyLen: 残りのコピーすべきバイト数。
    2. len(f.hist) - f.hp: 現在の書き込み位置から履歴バッファの終端までの残り容量。
    3. len(f.hist) - p: 現在の読み込み位置から履歴バッファの終端までの残り容量。 この計算により、バッファの境界を越えない範囲で、かつコピーすべき残りのバイト数を超えない範囲で、最大限のバイト数を一度にコピーできます。
  • forwardCopy の利用: 計算された n を使って、forwardCopy 関数を呼び出し、実際にバイトをコピーします。これにより、オーバーラップするメモリ領域でも安全かつ効率的にコピーが行われます。
  • ポインタの更新: コピー後、p (読み込みポインタ) と f.hp (書き込みポインタ) を n だけ進め、f.copyLenn だけ減らします。
  • バッファ満杯のチェック: 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() を呼び出してハフマンブロックの処理を続行します。

これらの変更により、履歴コピーの処理がモジュール化され、バッファの境界処理がより効率的になり、結果としてデコード性能が大幅に向上しました。

関連リンク

参考にした情報源リンク