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

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

このコミットは、Go言語の標準ライブラリであるcompress/flateパッケージ内のDeflate圧縮アルゴリズムにおいて、内部で使用されるハッシュテーブルのサイズを拡張することで、圧縮処理のパフォーマンスを向上させるものです。具体的には、ハッシュテーブルのサイズを決定するhashBits定数を15から17に増加させ、これによりハッシュテーブルのエントリ数が2^15（32,768）から2^17（131,072）へと4倍に拡大されました。この変更により、圧縮速度が0%から16%向上すると報告されています。

コミット

commit 565e140a16cb26fb878ee7554ca62c90ac9fa351
Author: Ivan Krasin <krasin@golang.org>
Date:   Tue Jan 24 13:52:45 2012 -0500

    compress/flate: increase the length of hash table from 1<<15 to 1<<17. 0%-16% speedup.
    
    R=rsc, imkrasin
    CC=golang-dev
    https://golang.org/cl/5569048
---
 src/pkg/compress/flate/deflate.go | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n
diff --git a/src/pkg/compress/flate/deflate.go b/src/pkg/compress/flate/deflate.go
index 5745336cc8..1e725890b7 100644
--- a/src/pkg/compress/flate/deflate.go
+++ b/src/pkg/compress/flate/deflate.go
@@ -27,7 +27,7 @@ const (
 	// stop things from getting too large.
 	maxFlateBlockTokens = 1 << 14
 	maxStoreBlockSize   = 65535
-	hashBits            = 15
+	hashBits            = 17
 	hashSize            = 1 << hashBits
 	hashMask            = (1 << hashBits) - 1
 	hashShift           = (hashBits + minMatchLength - 1) / minMatchLength

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

https://github.com/golang/go/commit/565e140a16cb26fb878ee7554ca62c90ac9fa351

元コミット内容

compress/flate: increase the length of hash table from 1<<15 to 1<<17. 0%-16% speedup.

R=rsc, imkrasin
CC=golang-dev
https://golang.org/cl/5569048

変更の背景

この変更の主な背景は、Go言語のcompress/flateパッケージにおけるデータ圧縮性能の向上です。Deflateアルゴリズムは、LZ77アルゴリズムとハフマン符号化を組み合わせたもので、LZ77の段階でデータの繰り返しパターン（マッチ）を効率的に見つけることが全体の圧縮速度に大きく影響します。

LZ77では、既に処理したデータの中から現在の入力シーケンスと一致する部分を探し、その位置と長さに置き換えることで圧縮を行います。この「一致する部分を探す」処理を高速化するために、ハッシュテーブルが用いられます。ハッシュテーブルは、特定のバイトシーケンス（通常は3バイトなど）をキーとして、そのシーケンスが以前に出現した位置を記録します。

従来のhashBits = 15では、ハッシュテーブルのサイズが2^15 = 32,768エントリでした。このサイズでは、特に長いデータや多様なパターンを持つデータにおいて、ハッシュ衝突（異なるバイトシーケンスが同じハッシュ値になること）が頻繁に発生する可能性がありました。ハッシュ衝突が発生すると、同じハッシュ値を持つエントリのリストを線形に探索する必要が生じ、これがパフォーマンスのボトルネックとなります。

hashBitsを17に増やすことで、ハッシュテーブルのサイズは2^17 = 131,072エントリとなり、従来の4倍に拡張されます。これにより、ハッシュ衝突の発生頻度が大幅に減少し、結果としてマッチ検索の効率が向上し、圧縮処理全体の速度が改善されるという背景があります。コミットメッセージにある「0%-16% speedup」は、この最適化がデータの内容によって異なる効果をもたらすことを示しています。

前提知識の解説

compress/flateパッケージ

Go言語の標準ライブラリに含まれるcompress/flateパッケージは、Deflateデータ形式の実装を提供します。Deflateは、ZlibやGzipなどの一般的な圧縮形式の基盤となるアルゴリズムであり、データ圧縮と伸長（解凍）の機能を提供します。

Deflateアルゴリズム

Deflateは、以下の2つの主要なアルゴリズムを組み合わせています。

  1. LZ77 (Lempel-Ziv 1977) アルゴリズム:

    • データ内の繰り返しパターンを検出・置換することで圧縮を行います。
    • 具体的には、既に処理したデータ（スライディングウィンドウと呼ばれる領域）の中から、現在の入力シーケンスと一致する最長の部分を探します。
    • 一致が見つかった場合、そのシーケンスを「(オフセット, 長さ)」のペアに置き換えます。オフセットはスライディングウィンドウ内の位置、長さは一致したシーケンスの長さです。
    • 一致が見つからない場合、そのバイトはそのまま出力されます。
    • このマッチ検索を高速化するために、ハッシュテーブルが重要な役割を果たします。

  2. ハフマン符号化 (Huffman Coding):

    • LZ77によって生成されたリテラルバイト（一致が見つからなかったバイト）と、(オフセット, 長さ)のペアを、出現頻度に基づいて可変長のビット列に符号化します。
    • 出現頻度の高いシンボルには短いビット列を、低いシンボルには長いビット列を割り当てることで、全体のデータサイズを削減します。

ハッシュテーブル (Hash Table) in LZ77

LZ77圧縮におけるハッシュテーブルは、過去に出現したバイトシーケンス（通常は最小マッチ長、例えば3バイト）を効率的に検索するためのデータ構造です。

  • 動作原理:

    1. 入力ストリームから一定の長さ（例: 3バイト）のシーケンスを読み取ります。
    2. そのシーケンスのハッシュ値を計算します。
    3. ハッシュテーブルのそのハッシュ値に対応するエントリを参照します。このエントリには、過去に同じハッシュ値を持つシーケンスが出現した位置（スライディングウィンドウ内のインデックス）が記録されています。
    4. 記録された位置から実際のバイトシーケンスを取り出し、現在のシーケンスと比較して一致するかどうかを確認します。
    5. 複数のシーケンスが同じハッシュ値を持つ場合（ハッシュ衝突）、それらのシーケンスは通常、リンクリスト（またはチェイン）として管理され、リストを辿って正確なマッチを探します。

  • ハッシュテーブルのサイズ:

    • ハッシュテーブルのサイズは、通常2^Nの形式で表され、NがhashBitsに相当します。
    • テーブルサイズが大きいほど、ハッシュ衝突の可能性が低くなり、マッチ検索が高速になります。
    • しかし、テーブルサイズが大きいほど、より多くのメモリを消費します。これは、圧縮アルゴリズムにおける速度とメモリ使用量のトレードオフの一例です。

hashBits定数

hashBitsは、ハッシュテーブルのサイズを決定するためのビット数を定義する定数です。この値がNである場合、ハッシュテーブルのサイズは1 << N（すなわち2^N）エントリとなります。

技術的詳細

このコミットにおける技術的詳細は、DeflateアルゴリズムのLZ77部分におけるハッシュテーブルの最適化に集約されます。

Deflateにおけるハッシュテーブルの役割の再確認

Deflate圧縮では、入力データをスキャンし、現在の位置から始まるバイトシーケンス（例えば、3バイト）が、既に処理された「スライディングウィンドウ」内に存在するかどうかを高速に検索する必要があります。この検索を効率的に行うために、ハッシュテーブルが使用されます。

  1. ハッシュ値の計算: 現在の3バイト（またはそれ以上の最小マッチ長）のシーケンスからハッシュ値を計算します。
  2. テーブル参照: 計算されたハッシュ値をインデックスとして、ハッシュテーブルを参照します。ハッシュテーブルの各エントリは、そのハッシュ値を持つシーケンスがスライディングウィンドウ内で最後に出現した位置を指します。
  3. マッチの探索: ハッシュテーブルから得られた位置から、実際のバイトシーケンスを比較し、現在のシーケンスとの一致を確認します。Deflateの実装では、通常、同じハッシュ値を持つ複数の候補（チェイン）を辿って、最長の一致を探します。

hashBitsの変更がもたらす影響

  • 変更前: hashBits = 15
    • hashSize = 1 << 15 = 32,768エントリ
    • hashMask = (1 << 15) - 1 = 32767 (ハッシュ値をテーブルサイズに収めるためのマスク)
  • 変更後: hashBits = 17
    • hashSize = 1 << 17 = 131,072エントリ
    • hashMask = (1 << 17) - 1 = 131071

この変更により、ハッシュテーブルのサイズが4倍に増加しました。このサイズ増加は以下の影響をもたらします。

  1. ハッシュ衝突の減少: ハッシュテーブルのエントリ数が増えることで、異なる入力シーケンスが同じハッシュ値にマッピングされる「ハッシュ衝突」の発生頻度が統計的に減少します。
  2. マッチ探索の高速化: ハッシュ衝突が減少すると、同じハッシュ値を持つエントリのリンクリスト（またはチェイン）の平均的な長さが短くなります。これにより、マッチ探索時にリストを辿る回数が減り、結果としてマッチ検索の処理時間が短縮されます。
  3. メモリ使用量の増加: ハッシュテーブルのサイズが4倍になるため、圧縮処理中に使用されるメモリ量が増加します。これは、速度とメモリ使用量の間の典型的なトレードオフです。このコミットでは、速度向上がメモリ増加のコストを上回ると判断されたことを示唆しています。
  4. 性能向上 (0%-16% speedup) の理由:
    • 圧縮対象のデータに繰り返しパターンが多い場合、ハッシュテーブルの効率が直接的に圧縮速度に影響します。テーブルが大きくなることで、より多くのマッチがより速く見つかるようになります。
    • 「0%-16%」という速度向上の幅は、入力データの特性に依存することを示しています。ランダムなデータや繰り返しが少ないデータでは効果が限定的である一方、テキストファイルやプログラムコードのように繰り返しパターンが多いデータでは顕著な効果が期待できます。

この最適化は、Deflateアルゴリズムのコア部分に手を加えることで、Go言語の圧縮ライブラリの全体的な効率を高めることを目的としています。

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

変更はsrc/pkg/compress/flate/deflate.goファイルの一箇所のみです。

--- a/src/pkg/compress/flate/deflate.go
+++ b/src/pkg/compress/flate/deflate.go
@@ -27,7 +27,7 @@ const (
 	// stop things from getting too large.
 	maxFlateBlockTokens = 1 << 14
 	maxStoreBlockSize   = 65535
-	hashBits            = 15
+	hashBits            = 17
 	hashSize            = 1 << hashBits
 	hashMask            = (1 << hashBits) - 1
 	hashShift           = (hashBits + minMatchLength - 1) / minMatchLength

コアとなるコードの解説

変更された行は、hashBitsという定数の定義です。

-	hashBits            = 15
+	hashBits            = 17
  • hashBits: この定数は、Deflateアルゴリズム内で使用されるハッシュテーブルのサイズを決定するためのビット数を定義しています。
  • 15から17への変更:
    • 元の値15は、ハッシュテーブルのサイズが2^15 = 32,768エントリであることを意味していました。
    • 新しい値17は、ハッシュテーブルのサイズが2^17 = 131,072エントリであることを意味します。
  • 関連する定数:
    • hashSize = 1 << hashBits: この行は、hashBitsの値に基づいて実際のハッシュテーブルのサイズを計算します。hashBitsが17になったことで、hashSizeは131072になります。
    • hashMask = (1 << hashBits) - 1: この行は、ハッシュ値をhashSizeの範囲内に収めるためのビットマスクを計算します。hashBitsが17になったことで、hashMaskは131071になります。
    • hashShift = (hashBits + minMatchLength - 1) / minMatchLength: この定数は、ハッシュ値を計算する際のビットシフト量に関連しており、hashBitsの変更に伴いその値も影響を受けます。

この単一の定数変更が、ハッシュテーブルの物理的なサイズを直接的に変更し、その結果としてDeflate圧縮アルゴリズムのマッチ検索効率に大きな影響を与え、最終的に圧縮速度の向上に繋がっています。

関連リンク

参考にした情報源リンク