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

このコミットは、Go言語の実験的なHTMLパーサーライブラリ exp/html 内の atom パッケージにおけるパフォーマンス改善を目的としています。具体的には、HTMLのタグ名や属性キーといった頻繁に出現する文字列（アトム）のルックアップ処理を、従来のバイナリサーチからハッシュベースのルックアップに切り替えることで高速化を図っています。

変更された主要なファイルは以下の通りです。

• src/pkg/exp/html/atom/atom.go: アトムの定義と、文字列からアトムへの変換（ルックアップ）を行う主要なロジックが含まれています。このコミットでは、ルックアップ関数がハッシュベースのアルゴリズムを使用するように変更されました。
• src/pkg/exp/html/atom/atom_test.go: atom パッケージのテストファイルです。新しいベンチマークが追加され、ルックアップのパフォーマンス改善が測定されています。
• src/pkg/exp/html/atom/gen.go: atom パッケージで使用される定数やルックアップテーブルを生成するためのGoプログラムです。このコミットでは、ハッシュベースのルックアップに必要なハッシュ値やオフセットテーブルを生成するロジックが追加されました。
• src/pkg/exp/html/atom/table.go: gen.go によって生成される、アトムの文字列表現とそれに対応する整数値、およびハッシュ値やルックアップのための補助データが定義されているファイルです。このコミットにより、このファイルの内容が大幅に更新されました。

コミット

commit d2a6098e9c72fdb5acac0dd8992cd174155c1caa
Author: Nigel Tao <nigeltao@golang.org>
Date:   Fri Jun 1 09:36:05 2012 +1000

    exp/html/atom: faster, hash-based lookup.
    
    exp/html/atom benchmark:
    benchmark          old ns/op    new ns/op    delta
    BenchmarkLookup       199226        80770  -59.46%
    
    exp/html benchmark:
    benchmark                      old ns/op    new ns/op    delta
    BenchmarkParser                  4864890      4510834   -7.28%
    BenchmarkHighLevelTokenizer      2209192      1969684  -10.84%
    benchmark                       old MB/s     new MB/s  speedup
    BenchmarkParser                    16.07        17.33    1.08x
    BenchmarkHighLevelTokenizer        35.38        39.68    1.12x
    
    R=r
    CC=golang-dev
    https://golang.org/cl/6261054

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

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

元コミット内容

exp/html/atom: faster, hash-based lookup.

exp/html/atom benchmark:
benchmark          old ns/op    new ns/op    delta
BenchmarkLookup       199226        80770  -59.46%

exp/html benchmark:
benchmark                      old ns/op    new ns/op    delta
BenchmarkParser                  4864890      4510834   -7.28%
BenchmarkHighLevelTokenizer      2209192      1969684  -10.84%
benchmark                       old MB/s     new MB/s  speedup
BenchmarkParser                    16.07        17.33    1.08x
BenchmarkHighLevelTokenizer        35.38        39.68    1.12x

R=r
CC=golang-dev
https://golang.org/cl/6261054

変更の背景

このコミットの主な背景は、HTMLパーシングのパフォーマンス向上です。HTMLドキュメントを解析する際、タグ名（例: <div>, <p>) や属性キー（例: id, class）といった特定の文字列が非常に頻繁に出現します。これらの文字列を効率的に処理することは、パーサー全体の速度に大きく影響します。

exp/html/atom パッケージは、これらの頻出するHTML文字列を「アトム」と呼ばれる一意の整数コードにマッピングすることで、文字列の比較やメモリ割り当てのオーバーヘッドを削減することを目的としています。従来の atom パッケージでは、文字列から対応するアトムを検索する際に、文字列のバイナリサーチ（二分探索）を使用していました。しかし、この方法は文字列比較のコストが高く、特に大量のルックアップが発生するHTMLパーシングにおいてはボトルネックとなる可能性がありました。

コミットメッセージに示されているベンチマーク結果は、この変更の動機を明確に示しています。

• BenchmarkLookup の実行時間が約60%削減されています。これは、文字列からアトムへの変換処理が大幅に高速化されたことを意味します。
• BenchmarkParser と BenchmarkHighLevelTokenizer の実行時間もそれぞれ約7%と約10%削減されており、処理速度が向上しています。これは、アトムのルックアップ処理の高速化が、HTMLパーサー全体のパフォーマンスに良い影響を与えていることを示しています。

これらの結果から、開発者はアトムのルックアップメカニズムを改善することで、HTMLパーシングの効率を向上させようとしたことがわかります。ハッシュベースのルックアップは、平均的には定数時間（O(1)）で検索が可能であるため、バイナリサーチ（O(log N)）よりも高速な選択肢となります。

前提知識の解説

このコミットを理解するためには、以下の概念について知っておく必要があります。

1. アトム (Atom) とは: プログラミングにおいて「アトム」という言葉は、一意の識別子として機能するシンボルや文字列を指すことがあります。この文脈では、HTMLのタグ名（例: div, p）や属性名（例: id, class）など、頻繁に登場する特定の文字列を、より効率的に扱えるように整数値にマッピングしたものです。

   • 文字列の共有 (String Interning): 同じ文字列リテラルが複数回出現する場合でも、メモリ上ではその文字列のインスタンスを一つだけ作成し、それ以降は同じインスタンスを参照するようにする最適化手法です。アトム化は、この文字列共有の一種と考えることができます。これにより、メモリ使用量を削減し、文字列比較をポインタ（または整数）比較に置き換えることで高速化を図ります。
   • 整数比較の優位性: 文字列の比較は、文字ごとに比較を行うため、文字列の長さに比例した時間がかかります。一方、整数の比較はCPUの単一命令で完了することが多く、非常に高速です。アトムを使用することで、文字列の比較を整数の比較に置き換えることができ、パフォーマンスが向上します。

2. ハッシュテーブル (Hash Table) / ハッシュマップ (Hash Map): キーと値のペアを格納するデータ構造で、キーをハッシュ関数に通して得られるハッシュ値を使って、値を格納するメモリ上の位置を決定します。

   • ハッシュ関数: 任意のサイズの入力データ（この場合は文字列）を受け取り、固定サイズの出力（ハッシュ値、通常は整数）を生成する関数です。良いハッシュ関数は、異なる入力に対して異なるハッシュ値を生成する傾向があり、ハッシュ値の衝突（異なる入力が同じハッシュ値を生成すること）を最小限に抑えます。
   • ルックアップの高速性: ハッシュテーブルでは、キーのハッシュ値を計算し、そのハッシュ値が指すメモリ位置に直接アクセスすることで、平均的にはO(1)（定数時間）で要素を検索できます。これは、データ量が増えても検索時間がほとんど変わらないことを意味します。
   • ハッシュ衝突 (Hash Collision): 異なるキーが同じハッシュ値を生成してしまうことです。ハッシュ衝突が発生した場合、ハッシュテーブルは衝突解決のためのメカニズム（例: チェイニング、オープンアドレス法）を使用して、正しい要素を見つけ出す必要があります。このコミットでは、ハッシュ衝突が発生した場合に、元の文字列を比較して最終的な確認を行うことで対応しています。

3. バイナリサーチ (Binary Search) / 二分探索: ソートされた配列から特定の要素を探し出すための探索アルゴリズムです。配列の中央の要素と目的の要素を比較し、その結果に基づいて探索範囲を半分に絞り込んでいきます。このプロセスを繰り返すことで、探索時間を大幅に短縮できます。

   • 時間計算量: O(log N)（Nは要素数）。要素数が増えるにつれて探索時間は対数的に増加します。ハッシュテーブルのO(1)と比較すると、Nが大きくなるほどバイナリサーチの方が遅くなります。

このコミットは、従来のバイナリサーチによる文字列ルックアップの代わりに、ハッシュテーブルの原理を応用したハッシュベースのルックアップを導入することで、HTMLパーシングのボトルネックを解消しようとしています。

技術的詳細

このコミットの核心は、exp/html/atom パッケージにおける文字列からアトムへのルックアップメカニズムを、従来のバイナリサーチからハッシュベースのルックアップに移行した点にあります。

変更前のルックアップ (バイナリサーチ): 変更前は、Lookup 関数内で table という文字列スライスに対してバイナリサーチを行っていました。table はアトムの文字列表現がソートされた状態で格納されており、compare 関数（bytes.Compare に似たカスタム比較関数）を使用して検索対象の文字列と table 内の文字列を比較していました。この方法は、文字列比較のコストが直接パフォーマンスに影響するため、効率的ではありませんでした。

変更後のルックアップ (ハッシュベース): 新しいアプローチでは、以下の要素が導入されています。

1. ハッシュ関数 hash(s []byte): atom.go と gen.go の両方で定義されている、文字列（バイトスライス）から uint32 のハッシュ値を計算する関数です。この関数は、文字列の各バイトをシフト演算とXOR演算を組み合わせてハッシュ値に組み込んでいきます。

   func hash(s []byte) (h uint32) {
   	for i := 0; i < len(s); i++ {
   		h = h<<5 ^ h>>27 ^ uint32(s[i])
   	}
   	return h
   }
   

   このハッシュ関数は、Goの標準ライブラリや他のプロジェクトでも見られる一般的なハッシュアルゴリズムの一つです。

2. gen.go によるルックアップテーブルの生成: gen.go は、atom パッケージが使用する静的なルックアップテーブルを生成するプログラムです。このコミットにより、以下の新しいテーブルが生成されるようになりました。

   • table (変更前も存在): アトムの文字列表現を格納するスライス。変更前はアルファベット順にソートされていましたが、変更後は lhash (長さとハッシュ値を組み合わせた値) の昇順にソートされます。
   • hashes ([...]uint32): table に対応する各アトムのハッシュ値を格納するスライス。gen.go で生成されます。
   • loHi ([maxLen + 2]uint16): 各文字列長に対応する table および hashes スライス内の開始インデックスと終了インデックスを格納するテーブルです。これにより、特定の長さの文字列を検索する際に、検索範囲を効率的に絞り込むことができます。gen.go で生成されます。

3. Lookup 関数の変更: Lookup 関数は、以下の手順でアトムを検索します。

   • 入力文字列 s のハッシュ値 hs を計算します。
   • 入力文字列の長さ len(s) を使用して、loHi テーブルから検索範囲 [lo, hi) を取得します。これにより、同じ長さのアトムのみを対象に検索できます。
   • hashes スライスに対してバイナリサーチを行います。このバイナリサーチは、ハッシュ値 hs と hashes[mid] を比較します。
   • ハッシュ値が一致した場合 (hs == ht)、ハッシュ衝突の可能性があるため、string(s) == table[mid] を確認します。gen.go は、生成されるアトムのハッシュ値がすべて異なることを保証していますが、任意の入力文字列がアトムと同じハッシュ値を持つ可能性はあります。そのため、最終的な文字列比較が必要です。
   • 文字列も一致した場合、対応するアトムのインデックス mid を返します。
   • ハッシュ値が一致しない場合、バイナリサーチのロジックに従って検索範囲を絞り込みます。

ハッシュ衝突の扱い: gen.go は、生成されるすべてのアトムの文字列に対して、ハッシュ値がユニークであることを検証します。もし衝突が見つかった場合、gen.go はエラーを出力して終了します。これにより、table 内のアトム同士でハッシュ衝突が発生しないことが保証されます。しかし、Lookup 関数に渡される任意の文字列が、既存のアトムと同じハッシュ値を持つ可能性は依然として存在します。そのため、Lookup 関数ではハッシュ値が一致した後に、元の文字列同士の比較 (string(s) == table[mid]) を行うことで、誤ったアトムを返さないようにしています。

このハッシュベースのルックアップは、平均的には非常に高速であり、ベンチマーク結果が示すように、HTMLパーシング全体のパフォーマンス向上に貢献しています。

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

このコミットにおけるコアとなるコードの変更は、主に以下の3つのファイルに集中しています。

1. src/pkg/exp/html/atom/atom.go:

   • hash 関数が追加されました。これは、文字列のハッシュ値を計算するために使用されます。
   • Lookup 関数の実装が大幅に変更されました。
     • 従来の compare 関数を使用したバイナリサーチが削除され、代わりにハッシュ値と hashes テーブル、loHi テーブルを使用したハッシュベースのルックアップロジックが導入されました。
     • ハッシュ値が一致した場合の最終的な文字列比較が追加されました。
   • compare 関数が削除されました。

2. src/pkg/exp/html/atom/gen.go:

   • hash 関数が追加されました。atom.go のものと同一のロジックです。
   • lhash 関数が追加されました。これは、文字列の長さとハッシュ値を組み合わせた uint64 の値を計算します。この値は、アトムをソートするために使用されます。
   • byLhash 型が追加されました。これは sort.Interface を実装し、lhash 値に基づいて文字列スライスをソートできるようにします。
   • アトムのリストを lhash 値でソートするように変更されました (sort.Sort(byLhash(atoms)))。
   • ハッシュ衝突をチェックするロジックが追加されました。生成されるアトムのハッシュ値がユニークであることを保証します。
   • table.go に出力される内容が変更されました。
     • hashes スライス（各アトムのハッシュ値）の生成が追加されました。
     • loHi スライス（各文字列長に対応するルックアップ範囲）の生成が追加されました。
     • max 定数が maxLen に変更され、最大文字列長を表すようになりました。
     • Atom 定数の定義順序が、従来のアルファベット順から lhash 値のソート順に変更されました。

3. src/pkg/exp/html/atom/table.go:

   • gen.go の変更に伴い、このファイルの内容が完全に再生成されました。
   • Atom 定数の定義順序が変更され、値もそれに合わせて変更されました。
   • max 定数が maxLen に変更されました。
   • table スライスの内容と順序が変更されました。
   • hashes スライスと loHi スライスが新しく追加されました。

これらの変更により、アトムのルックアップ処理が根本的に改善され、HTMLパーシングのパフォーマンスが向上しました。

コアとなるコードの解説

ここでは、変更された主要なコード部分について、その役割と動作を詳しく解説します。

src/pkg/exp/html/atom/atom.go

func hash(s []byte) (h uint32)

func hash(s []byte) (h uint32) {
	for i := 0; i < len(s); i++ {
		h = h<<5 ^ h>>27 ^ uint32(s[i])
	}
	return h
}

この関数は、入力されたバイトスライス s のハッシュ値を計算します。

• h<<5: 現在のハッシュ値 h を左に5ビットシフトします。これにより、ハッシュ値のビットが循環的に移動し、各バイトがハッシュ値の異なる位置に影響を与えるようになります。
• h>>27: h を右に27ビットシフトします。これは h<<5 と合わせて、32ビットのハッシュ値内でビットを循環させるための一般的な手法です（5 + 27 = 32）。
• ^ uint32(s[i]): 現在のハッシュ値と、入力バイト s[i] を uint32 にキャストした値とのXOR演算を行います。XORは、ビットのパターンを混ぜ合わせることで、ハッシュ値の均一性を高めます。

この組み合わせにより、入力文字列の各バイトがハッシュ値全体に影響を与え、異なる文字列が異なるハッシュ値を生成する可能性が高まります。

func Lookup(s []byte) Atom

func Lookup(s []byte) Atom {
	if len(s) == 0 || len(s) > maxLen {
		return 0
	}
	if len(s) == 1 {
		// ... (1バイトのアトムの特殊処理)
	}

	hs := hash(s) // 入力文字列のハッシュ値を計算

	// loHi テーブルを使って、入力文字列の長さsに対応する検索範囲[lo, hi)を取得
	lo := Atom(loHi[len(s)])
	hi := Atom(loHi[len(s)+1])

	for lo < hi {
		mid := (lo + hi) / 2
		ht := hashes[mid] // 中間点のアトムのハッシュ値を取得

		if hs == ht {
			// ハッシュ値が一致した場合、文字列自体も一致するか確認（ハッシュ衝突の可能性）
			t := table[mid]
			for i, si := range s {
				if si != t[i] {
					return 0 // 文字列が一致しない場合は、衝突と判断し0を返す
				}
			}
			return mid // ハッシュ値と文字列が一致した場合、アトムを返す
		} else if hs > ht {
			lo = mid + 1 // 検索範囲を後半に絞る
		} else {
			hi = mid // 検索範囲を前半に絞る
		}
	}
	return 0 // 見つからなかった場合
}

この関数は、文字列 s に対応する Atom を検索します。

1. 長さによるフィルタリング: まず、入力文字列の長さが0または maxLen を超える場合は、無効なアトムとして0を返します。また、1バイトの文字列については、oneByteAtoms という専用のテーブルを使って高速にルックアップします。
2. ハッシュ値の計算: 入力文字列 s のハッシュ値 hs を hash 関数で計算します。
3. 検索範囲の特定: loHi テーブルは、各文字列長に対応する table および hashes スライス内の開始インデックスと終了インデックスを格納しています。len(s) をキーとして loHi から lo と hi を取得することで、検索対象を同じ長さのアトムに限定し、検索効率を高めます。
4. ハッシュ値によるバイナリサーチ: lo と hi で定義された範囲内で、hashes スライスに対してバイナリサーチを行います。このバイナリサーチは、入力文字列のハッシュ値 hs と、hashes スライスの中間点のアトムのハッシュ値 ht を比較します。
5. ハッシュ衝突の解決: hs == ht となった場合、ハッシュ値が一致したことを意味しますが、これはハッシュ衝突の可能性があります。そのため、table[mid] に格納されている実際の文字列 t と入力文字列 s をバイトごとに比較し、完全に一致するかどうかを確認します。
   • 完全に一致すれば、正しいアトムが見つかったと判断し、そのインデックス mid を返します。
   • 一致しなければ、それはハッシュ衝突であり、目的のアトムではないため、0を返します。
6. 検索範囲の更新: hs と ht の比較結果に基づいて、lo または hi を更新し、検索範囲を絞り込みます。
7. 見つからない場合: ループが終了してもアトムが見つからなかった場合、0を返します。

src/pkg/exp/html/atom/gen.go

このファイルは、atom パッケージが使用する静的なデータ（table.go に出力される）を生成するためのツールです。

func hash(s string) (h uint32)

atom.go と同じロジックのハッシュ関数です。gen.go では文字列 (string) を引数にとります。

func lhash(s string) uint64

func lhash(s string) uint64 {
	return uint64(len(s))<<32 | uint64(hash(s))
}

この関数は、文字列の長さ (len(s)) を上位32ビットに、ハッシュ値 (hash(s)) を下位32ビットに結合した uint64 の値を生成します。この lhash 値は、アトムのリストをソートするために使用されます。これにより、同じ長さの文字列が近くに配置され、さらにハッシュ値の順序でソートされるため、Lookup 関数での検索効率が向上します。

type byLhash []string とそのメソッド

type byLhash []string

func (b byLhash) Len() int           { return len(b) }
func (b byLhash) Less(i, j int) bool { return lhash(b[i]) < lhash(b[j]) }
func (b byLhash) Swap(i, j int)      { b[i], b[j] = b[j], b[i] }

これは sort.Interface インターフェースを実装しており、lhash 値に基づいて文字列スライスをソートできるようにします。gen.go の main 関数内で sort.Sort(byLhash(atoms)) として使用され、アトムのリストが lhash 順にソートされます。

ハッシュ衝突のチェック

	// Check for hash collisions.
	m1 := map[uint64]int{}
	for i, h := range lhashes {
		h &= 1<<32 - 1 // ハッシュ値（下位32ビット）のみを抽出
		if j, ok := m1[h]; ok {
			fmt.Fprintf(os.Stderr, "hash collision at 0x%08x: %q, %q\\n", h, byInt[i], byInt[j])
			os.Exit(1) // 衝突が見つかった場合は終了
		}
		m1[h] = i
	}

この重要なセクションは、生成されるすべてのアトムのハッシュ値がユニークであることを保証します。

• lhashes スライス（各アトムの lhash 値）をイテレートします。
• 各 lhash 値から下位32ビット（純粋なハッシュ値）を抽出します。
• m1 というマップを使用して、これまでに処理したハッシュ値とそのインデックスを記録します。
• もし現在のハッシュ値が既にマップに存在する場合（つまり、異なるアトムが同じハッシュ値を持っている場合）、それはハッシュ衝突であるため、エラーメッセージを出力してプログラムを終了します。 このチェックにより、table 内のアトム同士でハッシュ衝突が発生しないことが保証され、Lookup 関数でのハッシュ値によるバイナリサーチがより効率的になります。

table.go の生成ロジック

gen.go は、table.go に出力される table、hashes、loHi などのGoコードを生成します。

• table スライスは、lhash 順にソートされたアトムの文字列を格納します。
• hashes スライスは、table スライスに対応する各アトムのハッシュ値を格納します。
• loHi スライスは、各文字列長 n に対して、table および hashes スライス内で長さ n のアトムが始まるインデックスを格納します。これは sort.Search を使用して効率的に計算されます。

これらの変更により、atom パッケージは、HTMLパーシングにおいて頻繁に発生する文字列ルックアップを、より高速なハッシュベースのメカニズムで実行できるようになりました。

関連リンク

• Go CL 6261054: https://golang.org/cl/6261054

参考にした情報源リンク

• go.dev: golang.org/x/net/html/atom package documentation: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQFnIP7b9iHoytYNJQDiet0msEsMSInynmMNTqEL0akoHogZRgOaGEulY29eEyNk6H-VWw3PnKcRGj9Xw12JhnzhAVfsG_PhZYjV-5GC2BVqGlZZj7MhwsEYqmDEakmRFh79Qd4pBhkspg==
  • このリンクは、golang.org/x/net/html/atom パッケージの目的と最適化に関する情報を提供しています。特に、文字列割り当ての削減と高速な比較の利点について言及しています。