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

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

このコミットは、Go言語の標準ライブラリ src/pkg/compress/flate/deflate.go に関連するものです。このファイルは、DEFLATE圧縮アルゴリズムの実装の一部であり、特に圧縮処理におけるトークン（リテラルやマッチ）の管理方法を扱っています。DEFLATEは、Zlib、gzip、PNGなどの多くの圧縮フォーマットで利用されている、ロスレスデータ圧縮アルゴリズムです。

コミット

このコミットは、compress/flate パッケージ内のDEFLATE圧縮器において、出力トークンをキューに入れる方法を、スライスとカウンター（d.tokens[d.ti] と d.ti++）を使用する方式から、Go言語の組み込み関数 append を使用する方式へと変更するものです。これにより、コードの簡潔性、安全性、およびGoのイディオムへの準拠が向上します。

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

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

元コミット内容

compress/flate: use append instead of slice+counter.

R=rsc, nigeltao
CC=golang-dev
https://golang.org/cl/5561056

変更の背景

Go言語のスライスは、動的な配列のようなデータ構造であり、その操作には append 関数が推奨されます。append は、スライスの容量が不足した場合に自動的に新しい基底配列を割り当てて要素を追加するため、開発者は手動での容量管理やインデックスの追跡から解放されます。

このコミット以前のコードでは、d.tokens というスライスを事前に maxFlateBlockTokens の容量で確保し、d.ti というカウンター変数を使って現在の要素数を管理し、手動でインデックスアクセス (d.tokens[d.ti] = ...; d.ti++) を行っていました。この方法は、スライスの容量を常に意識し、d.ti が容量を超えないように注意する必要がありました。

変更の背景には、以下の点が考えられます。

  1. コードの簡潔性と可読性の向上: append を使用することで、要素の追加ロジックがより簡潔になり、d.ti のような補助的なカウンター変数を不要にできます。これにより、コードが読みやすくなり、意図が明確になります。
  2. Goのイディオムへの準拠: Go言語では、スライスに要素を追加する際には append を使用するのが一般的で推奨されるイディオムです。この変更は、コードベース全体で一貫したスタイルを促進します。
  3. 潜在的なバグの削減: 手動でインデックスを管理する場合、インデックスがスライスの境界を超えてしまう（out-of-bounds）バグを導入するリスクがあります。append はこのような問題を内部的に処理するため、より安全です。
  4. パフォーマンスの最適化: append は、スライスの容量が不足した場合に効率的な再割り当て戦略（通常は容量を2倍にする）を採用しています。手動での再割り当てロジックを記述するよりも、多くの場合で append の方が最適化されています。この特定のケースでは、maxFlateBlockTokens という固定容量が事前にわかっているため、パフォーマンス上の大きな違いはないかもしれませんが、コードの保守性という点でメリットがあります。

前提知識の解説

Go言語のスライス

Go言語のスライスは、同じ型の要素のシーケンスを表すデータ構造です。スライスは、基底となる配列への参照、長さ（len）、および容量（cap）の3つの要素で構成されます。

  • 長さ (Length): スライスに含まれる要素の数。len(s) で取得できます。
  • 容量 (Capacity): スライスの基底配列が保持できる要素の最大数。cap(s) で取得できます。スライスを拡張する際に、この容量を超えると新しい基底配列が割り当てられます。

append 関数

append はGoの組み込み関数で、スライスに要素を追加するために使用されます。 newSlice = append(oldSlice, elem1, elem2, ...) のように使用します。 append は、元のスライスの容量が不足している場合、より大きな容量を持つ新しい基底配列を割り当て、既存の要素をコピーし、新しい要素を追加した新しいスライスを返します。容量が十分な場合は、既存の基底配列の末尾に要素を追加し、スライスの長さを更新した新しいスライスを返します（この場合、多くは元のスライスと同じ基底配列を指します）。

compress/flate パッケージとDEFLATEアルゴリズム

compress/flate パッケージは、Go言語でDEFLATE圧縮および解凍を実装するためのものです。DEFLATEは、LZ77アルゴリズムとハフマン符号化を組み合わせたロスレスデータ圧縮アルゴリズムです。

  • LZ77: 繰り返し出現するバイトシーケンス（マッチ）を、以前に出現したシーケンスへの参照（長さとオフセット）に置き換えることでデータを圧縮します。
  • ハフマン符号化: 出現頻度の高いシンボルには短いビット列を、出現頻度の低いシンボルには長いビット列を割り当てることで、データをさらに圧縮します。

token 構造体

DEFLATE圧縮器は、入力データを処理する際に、リテラルバイト（そのままのバイト）またはマッチ（以前のデータへの参照）を「トークン」として表現します。 literalToken は単一のリテラルバイトを表し、matchToken はマッチの長さとオフセットを表します。これらのトークンは、圧縮されたデータブロックを形成するためにキューに格納されます。

maxFlateBlockTokens

これは、単一のDEFLATEブロックにキューイングできるトークンの最大数を定義する定数です。この定数は、圧縮器が一度に処理するデータのチャンクサイズを決定し、メモリ使用量とパフォーマンスのバランスを取るために重要です。

技術的詳細

このコミットの技術的な核心は、compressor 構造体の tokens フィールドの扱い方と、それに要素を追加するロジックの変更にあります。

変更前: compressor 構造体には tokens []token と ti int の2つのフィールドがありました。 tokens は make([]token, maxFlateBlockTokens, maxFlateBlockTokens+1) のように初期化され、maxFlateBlockTokens の長さと maxFlateBlockTokens+1 の容量を持っていました。 ti は tokens スライス内の現在の要素数を追跡するカウンターとして機能していました。 要素の追加は d.tokens[d.ti] = someToken; d.ti++ の形式で行われ、スライスのクリアは d.ti = 0 で行われていました。

変更後: compressor 構造体から ti int フィールドが削除されました。 tokens スライスは make([]token, 0, maxFlateBlockTokens+1) のように初期化されます。これは、長さが0で、容量が maxFlateBlockTokens+1 の空のスライスを作成することを意味します。 要素の追加はすべて d.tokens = append(d.tokens, someToken) の形式で行われます。append は新しいスライスを返すため、その結果を d.tokens に再代入する必要があります。 スライスのクリアは d.tokens = d.tokens[:0] で行われます。これは、既存の基底配列を再利用しつつ、スライスの長さを0にリセットする効率的な方法です。

なぜ maxFlateBlockTokens+1 の容量なのか？ make([]token, 0, maxFlateBlockTokens+1) のように容量を maxFlateBlockTokens+1 に設定しているのは、maxFlateBlockTokens 個のトークンがキューに格納された後、さらに1つのトークンを追加する可能性があるためです。これにより、append が新しい基底配列を割り当てることなく、既存の容量内で追加のトークンを処理できるようになります。これは、メモリ割り当てのオーバーヘッドを最小限に抑えるための最適化です。

この変更により、コードはよりGoらしい書き方になり、ti のような手動カウンターの管理に伴う複雑さや潜在的なエラーが排除されます。append 関数は、スライスの動的な成長を安全かつ効率的に処理するためのGoの標準的なメカニズムです。

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

変更は src/pkg/compress/flate/deflate.go ファイルに集中しています。

--- a/src/pkg/compress/flate/deflate.go
+++ b/src/pkg/compress/flate/deflate.go
@@ -82,9 +82,8 @@ type compressor struct {
 	blockStart    int  // window index where current tokens start
 	byteAvailable bool // if true, still need to process window[index-1].
 
-\t// queued output tokens: tokens[:ti]
+\t// queued output tokens
 \ttokens []token
-\tti     int
 \n \t// deflate state
 \tlength         int
 @@ -196,12 +195,11 @@ func (d *compressor) initDeflate() {
 \td.hashPrev = make([]int, windowSize)\n \td.window = make([]byte, 2*windowSize)\n \td.hashOffset = 1\n-\td.tokens = make([]token, maxFlateBlockTokens, maxFlateBlockTokens+1)\n+\td.tokens = make([]token, 0, maxFlateBlockTokens+1)\n \td.length = minMatchLength - 1\n \td.offset = 0\n \td.byteAvailable = false\n \td.index = 0\n-\td.ti = 0
 \td.hash = 0\n \td.chainHead = -1\n }\n@@ -233,15 +231,14 @@ Loop:\n \t\t\t\t// Flush current output block if any.\n \t\t\t\tif d.byteAvailable {\n \t\t\t\t\t// There is still one pending token that needs to be flushed\n-\t\t\t\t\td.tokens[d.ti] = literalToken(uint32(d.window[d.index-1]))\n-\t\t\t\t\td.ti++\n+\t\t\t\t\td.tokens = append(d.tokens, literalToken(uint32(d.window[d.index-1])))\n \t\t\t\t\td.byteAvailable = false\n \t\t\t\t}\n-\t\t\t\tif d.ti > 0 {\n-\t\t\t\t\tif d.err = d.writeBlock(d.tokens[0:d.ti], d.index, false); d.err != nil {\n+\t\t\t\tif len(d.tokens) > 0 {\n+\t\t\t\t\tif d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {\n \t\t\t\t\t\treturn\n \t\t\t\t\t}\n-\t\t\t\t\td.ti = 0\n+\t\t\t\t\td.tokens = d.tokens[:0]\n \t\t\t\t}\n \t\t\t\tbreak Loop\n \t\t\t}\n@@ -275,11 +272,10 @@ Loop:\n \t\t\t// There was a match at the previous step, and the current match is\n \t\t\t// not better. Output the previous match.\n \t\t\tif d.fastSkipHashing != skipNever {\n-\t\t\t\td.tokens[d.ti] = matchToken(uint32(d.length-minMatchLength), uint32(d.offset-minOffsetSize))\n+\t\t\t\td.tokens = append(d.tokens, matchToken(uint32(d.length-minMatchLength), uint32(d.offset-minOffsetSize)))\n \t\t\t} else {\n-\t\t\t\td.tokens[d.ti] = matchToken(uint32(prevLength-minMatchLength), uint32(prevOffset-minOffsetSize))\n+\t\t\t\td.tokens = append(d.tokens, matchToken(uint32(prevLength-minMatchLength), uint32(prevOffset-minOffsetSize)))\n \t\t\t}\n-\t\t\td.ti++\n \t\t\t// Insert in the hash table all strings up to the end of the match.\n \t\t\t// index and index-1 are already inserted. If there is not enough\n \t\t\t// lookahead, the last two strings are not inserted into the hash\n@@ -313,12 +309,12 @@ Loop:\n \t\t\t\t\td.hash = (int(d.window[d.index])<<hashShift + int(d.window[d.index+1]))\n \t\t\t\t}\n \t\t\t}\n-\t\t\tif d.ti == maxFlateBlockTokens {\n+\t\t\tif len(d.tokens) == maxFlateBlockTokens {\n \t\t\t\t// The block includes the current character\n \t\t\t\tif d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {\n \t\t\t\t\treturn\n \t\t\t\t}\n-\t\t\t\td.ti = 0\n+\t\t\t\td.tokens = d.tokens[:0]\n \t\t\t}\n \t\t} else {\n \t\t\tif d.fastSkipHashing != skipNever || d.byteAvailable {\n@@ -326,13 +322,12 @@ Loop:\n \t\t\t\tif d.fastSkipHashing != skipNever {\n \t\t\t\t\ti = d.index\n \t\t\t\t}\n-\t\t\t\td.tokens[d.ti] = literalToken(uint32(d.window[i]))\n-\t\t\t\td.ti++\n-\t\t\t\tif d.ti == maxFlateBlockTokens {\n+\t\t\t\td.tokens = append(d.tokens, literalToken(uint32(d.window[i])))\n+\t\t\t\tif len(d.tokens) == maxFlateBlockTokens {\n \t\t\t\t\tif d.err = d.writeBlock(d.tokens, i+1, false); d.err != nil {\n \t\t\t\t\t\treturn\n \t\t\t\t\t}\n-\t\t\t\t\td.ti = 0\n+\t\t\t\t\td.tokens = d.tokens[:0]\n \t\t\t\t}\n \t\t\t}\n \t\t\td.index++

コアとなるコードの解説

compressor 構造体からの ti フィールドの削除

-\tti     int

compressor 構造体から ti フィールドが削除されました。これは、append 関数がスライスの長さを内部的に管理するため、手動でインデックスを追跡する必要がなくなったためです。

initDeflate 関数での tokens スライスの初期化変更

-\td.tokens = make([]token, maxFlateBlockTokens, maxFlateBlockTokens+1)
+\td.tokens = make([]token, 0, maxFlateBlockTokens+1)
-\td.ti = 0

initDeflate 関数内で、d.tokens の初期化方法が変更されました。 変更前は、maxFlateBlockTokens の長さと maxFlateBlockTokens+1 の容量を持つスライスを作成していました。 変更後は、長さが0で容量が maxFlateBlockTokens+1 の空のスライスを作成しています。これにより、append を使用して要素を追加する準備が整います。 また、d.ti = 0 の行も削除されました。

トークン追加ロジックの変更

以下の箇所で、d.tokens[d.ti] = ...; d.ti++ のパターンが d.tokens = append(d.tokens, ...) に変更されています。

  • リテラルトークンの追加 (行 236):

    -\t\t\t\t\td.tokens[d.ti] = literalToken(uint32(d.window[d.index-1]))
-\t\t\t\t\td.ti++
+\t\t\t\t\td.tokens = append(d.tokens, literalToken(uint32(d.window[d.index-1])))

    d.byteAvailable が true の場合、保留中のリテラルトークンを tokens スライスに追加します。

  • マッチトークンの追加 (行 278, 281):

    -\t\t\t\t\td.tokens[d.ti] = matchToken(uint32(d.length-minMatchLength), uint32(d.offset-minOffsetSize))
+\t\t\t\t\td.tokens = append(d.tokens, matchToken(uint32(d.length-minMatchLength), uint32(d.offset-minOffsetSize)))

    -\t\t\t\t\td.tokens[d.ti] = matchToken(uint32(prevLength-minMatchLength), uint32(prevOffset-minOffsetSize))
+\t\t\t\t\td.tokens = append(d.tokens, matchToken(uint32(prevLength-minMatchLength), uint32(prevOffset-minOffsetSize)))

    マッチが見つかった場合、そのマッチを表すトークンを tokens スライスに追加します。

  • リテラルトークンの追加 (行 329):

    -\t\t\t\t\td.tokens[d.ti] = literalToken(uint32(d.window[i]))
-\t\t\t\t\td.ti++
+\t\t\t\t\td.tokens = append(d.tokens, literalToken(uint32(d.window[i])))

    ハッシュスキップやバイトが利用可能な場合、リテラルトークンを tokens スライスに追加します。

スライスの長さチェックとクリアロジックの変更

以下の箇所で、d.ti を使用したスライスの長さチェックとクリアロジックが len(d.tokens) と d.tokens = d.tokens[:0] に変更されています。

  • ブロックの書き出しとスライスのクリア (行 240, 245):

    -\t\t\t\tif d.ti > 0 {
+\t\t\t\tif len(d.tokens) > 0 {

    -\t\t\t\t\tif d.err = d.writeBlock(d.tokens[0:d.ti], d.index, false); d.err != nil {
+\t\t\t\t\tif d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {

    -\t\t\t\t\td.ti = 0
+\t\t\t\t\td.tokens = d.tokens[:0]

    d.tokens に要素がある場合、writeBlock 関数に d.tokens スライス全体を渡し、その後 d.tokens = d.tokens[:0] でスライスをクリアします。

  • ブロックの書き出しとスライスのクリア (行 317, 322):

    -\t\t\t\tif d.ti == maxFlateBlockTokens {
+\t\t\t\tif len(d.tokens) == maxFlateBlockTokens {

    -\t\t\t\t\td.ti = 0
+\t\t\t\t\td.tokens = d.tokens[:0]

    tokens スライスの長さが maxFlateBlockTokens に達した場合、ブロックを書き出し、スライスをクリアします。

  • ブロックの書き出しとスライスのクリア (行 332, 337):

    -\t\t\t\t\tif d.ti == maxFlateBlockTokens {
+\t\t\t\t\tif len(d.tokens) == maxFlateBlockTokens {

    -\t\t\t\t\td.ti = 0
+\t\t\t\t\td.tokens = d.tokens[:0]

    同様に、tokens スライスの長さが maxFlateBlockTokens に達した場合の処理です。

これらの変更により、コードはよりGoのイディオムに沿ったものとなり、スライスの操作がより安全で簡潔になりました。

関連リンク

参考にした情報源リンク