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

このコミットは、Go言語の実験的なHTMLパーサーライブラリ exp/html/atom における、文字列（アトム）のルックアップ処理の高速化とメモリ使用量の削減を目的としたものです。具体的には、アトムのルックアップに「完全クックーハッシュ」を導入し、アトム文字列の格納方法を最適化することで、パフォーマンスとメモリ効率を大幅に向上させています。

コミット

commit 192550592a24a8ba1e826d11f0426e5889c1a0af
Author: Russ Cox <rsc@golang.org>
Date:   Sat Jun 2 22:43:11 2012 -0400

    exp/html/atom: faster Lookup with smaller tables
    
    Use perfect cuckoo hash, to avoid binary search.
    Define Atom bits as offset+len in long string instead
    of enumeration, to avoid string headers.
    
    Before: 1909 string bytes + 6060 tables = 7969 total data
    After: 1406 string bytes + 2048 tables = 3454 total data
    
    benchmark          old ns/op    new ns/op    delta
    BenchmarkLookup        83878        64681  -22.89%
    
    R=nigeltao, r
    CC=golang-dev
    https://golang.org/cl/6262051

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

https://github.com/golang/go/commit/192550592a24a8ba1e826d11f0426e5889c1a0af

元コミット内容

exp/html/atom: faster Lookup with smaller tables

このコミットは、exp/html/atom パッケージにおける Lookup 関数の高速化と、関連するデータテーブルのメモリフットプリント削減を目的としています。具体的には、以下の変更が行われました。

完全クックーハッシュの導入: 以前のバイナリサーチベースのルックアップを廃止し、完全クックーハッシュを使用することで、ルックアップ時間を改善しました。
アトム文字列の格納方法の最適化: Atom 型の値を、単なる列挙型ではなく、長い単一の文字列 (atomText) 内のオフセットと長さとして定義するように変更しました。これにより、個々の文字列ヘッダーのオーバーヘッドを削減し、メモリ効率を高めました。

結果として、データサイズは7969バイトから3454バイトへと大幅に削減され、BenchmarkLookup の実行時間は22.89%改善されました。

HTMLパーサーは、HTMLドキュメント内の要素名や属性名といった特定の文字列を頻繁に処理します。これらの文字列は数が限られており、繰り返し出現することが多いため、文字列そのものを扱うよりも、それらを一意の整数値（アトム）にマッピングして処理する「アトム化（Atomization）」という手法が一般的に用いられます。これにより、文字列比較のオーバーヘッドを削減し、処理速度を向上させることができます。

このコミットが行われる前は、exp/html/atom パッケージでは、アトム文字列から対応する Atom 値を検索する Lookup 関数がバイナリサーチを使用していました。バイナリサーチはソートされたデータに対して効率的ですが、要素数が増えるにつれて検索時間が対数的に増加します（O(log N)）。また、アトム文字列自体は個別のGoの文字列としてメモリに格納されており、それぞれの文字列が持つヘッダー情報（ポインタ、長さなど）がメモリオーバーヘッドとなっていました。

HTMLパーサーのようなパフォーマンスが重視されるコンポーネントでは、アトムのルックアップは非常に頻繁に行われる操作であるため、その効率は全体のパフォーマンスに大きく影響します。このコミットの背景には、Lookup 関数のさらなる高速化と、アトム関連データのメモリ使用量の削減という明確な目標がありました。特に、Go言語の標準ライブラリとして成熟していく過程で、パフォーマンスとリソース効率の最適化は重要な課題となります。

前提知識の解説

1. アトム化 (Atomization)

アトム化とは、プログラム内で頻繁に登場する特定の文字列を、一意の整数値（アトム）にマッピングする最適化手法です。例えば、HTMLの要素名 "div" や "span"、属性名 "class" や "id" などは、ドキュメント内で何度も出現します。これらの文字列を毎回比較する代わりに、それぞれを atom.Div や atom.Span といった整数値に変換し、比較や処理を整数値で行うことで、文字列操作のオーバーヘッドを削減し、パフォーマンスを向上させます。アトムは通常、コンパイル時に固定されたセットとして定義されます。

2. ハッシュ関数 (Hash Function)

ハッシュ関数は、任意の長さの入力データ（この場合は文字列）を受け取り、固定長の出力（ハッシュ値）を生成する関数です。良いハッシュ関数は、異なる入力に対して異なるハッシュ値を生成する傾向があり、ハッシュ値から元のデータを推測することは困難です。ハッシュ値は、ハッシュテーブルでのデータ検索や、データの整合性チェックなどに利用されます。

このコミットでは、FNV (Fowler-Noll-Vo) ハッシュ関数が使用されています。FNVハッシュは、シンプルで高速な非暗号学的ハッシュ関数であり、特にハッシュテーブルのキー生成に適しています。FNVハッシュは、入力バイト列を順に処理し、現在のハッシュ値にXOR演算と乗算を繰り返すことでハッシュ値を更新していきます。

3. ハッシュテーブル (Hash Table)

ハッシュテーブル（またはハッシュマップ）は、キーと値のペアを格納するデータ構造です。キーをハッシュ関数に通してハッシュ値を計算し、そのハッシュ値をインデックスとして配列（バケット）に値を格納します。これにより、平均的にはO(1)の定数時間で要素の挿入、削除、検索が可能になります。

しかし、異なるキーが同じハッシュ値を生成する「ハッシュ衝突」が発生する可能性があります。ハッシュ衝突の解決には、チェイニング（同じバケットに複数の要素をリストで格納）やオープンアドレス法（衝突した場合に別のバケットを探す）などの手法があります。

4. クックーハッシュ (Cuckoo Hashing)

クックーハッシュは、オープンアドレス法の一種で、ハッシュ衝突の解決に特徴的なアプローチを取るハッシュテーブルのアルゴリズムです。通常のハッシュテーブルが1つのハッシュ関数を使用するのに対し、クックーハッシュは通常2つ以上の独立したハッシュ関数を使用します。

要素を挿入する際、まず最初のハッシュ関数で計算された位置に要素を配置しようとします。もしその位置が空いていればそこに格納します。もし既に別の要素が存在していれば、既存の要素を「追い出し」（クックー鳥が他の鳥の巣に卵を産むように）、追い出された要素は2番目のハッシュ関数で計算された別の位置に移動しようとします。このプロセスは、要素が空いている位置を見つけるか、または無限ループに陥るまで繰り返されます。無限ループに陥った場合は、テーブル全体を再構築（リハッシュ）する必要があります。

クックーハッシュの主な利点は、最悪ケースでもO(1)の検索時間を保証できる点です。これは、各要素が常に2つの可能な位置のいずれかに存在するため、検索は最大で2回のハッシュ計算と2回のメモリ参照で完了するからです。

5. 完全クックーハッシュ (Perfect Cuckoo Hashing)

完全クックーハッシュは、通常のクックーハッシュの特殊なケースであり、特に静的なデータセット（挿入や削除がほとんどなく、事前に全ての要素が分かっているデータセット）に対して非常に強力です。完全クックーハッシュでは、事前にデータセットが与えられたときに、**衝突が一切発生しないようなハッシュ関数（またはハッシュ関数の組み合わせ）**を見つけ出します。これにより、リハッシュの必要がなく、常にO(1)の検索時間を保証できます。

このコミットでは、gen.go というコード生成ツールが、全てのアトム文字列に対して衝突のない最適なハッシュ関数 (hash0) と、それに対応するルックアップテーブル (table) を生成しています。これにより、実行時にはハッシュ衝突を心配することなく、非常に高速なアトムルックアップが可能になります。

技術的詳細

このコミットの核となる技術的変更は、exp/html/atom パッケージにおけるアトムのルックアップメカニズムを、従来のバイナリサーチから完全クックーハッシュへと移行した点です。これに伴い、アトムの内部表現も最適化されています。

1. 完全クックーハッシュによるルックアップの高速化

以前の Lookup 関数は、アトムのハッシュ値に基づいてソートされた配列に対してバイナリサーチを実行していました。これはO(log N)の計算量を持つため、アトムの数が増えるにつれて検索時間が長くなります。

新しい実装では、gen.go というツールがコンパイル時に全てのアトム文字列を分析し、それらの文字列を格納するための最適な「完全クックーハッシュ」テーブルを生成します。このテーブルは、2つのハッシュ関数（実際には1つのFNVハッシュ関数から2つのインデックスを導出）を使用し、全てのアトムが衝突なく配置されるように設計されています。

Lookup 関数は、入力文字列 s に対してFNVハッシュを計算し、そのハッシュ値から2つの可能なテーブルインデックスを導き出します。そして、これら2つのインデックスのいずれかに目的のアトムが存在するかを直接チェックします。これにより、検索は常に定数時間（O(1)）で完了します。

2. アトム文字列のメモリ効率化

従来の Atom 型は、table という []string 型のスライスに格納された文字列のインデックスとして機能していました。Goの string 型は、内部的にはポインタと長さのペアで構成されており、個々の文字列がメモリ上に分散して格納されるため、多数の短い文字列を扱う場合に文字列ヘッダーのオーバーヘッドが無視できませんでした。

このコミットでは、Atom 型が uint32 に変更され、その32ビットが以下のようにエンコードされるようになりました。

上位ビット: atomText という単一の長い文字列内でのアトム名の開始オフセット。
下位8ビット: アトム名の長さ。

例えば、Atom = 0x123405 の場合、0x1234 がオフセット、0x05 が長さを示します。これにより、全てのアトム文字列が atomText という巨大な単一の文字列リテラルとしてメモリに連続して格納されるため、個々の文字列ヘッダーのオーバーヘッドが完全に排除されます。Atom.String() メソッドは、このオフセットと長さの情報を使って atomText から部分文字列を効率的に抽出します。

3. `gen.go` によるテーブル生成

この最適化の鍵となるのは、src/pkg/exp/html/atom/gen.go というGoプログラムです。このプログラムは、HTMLアトムのリスト（要素名、属性名など）を読み込み、以下の処理を行います。

最適なハッシュ関数の探索: 多数のランダムな初期ハッシュ値 (h0) を試行し、全てのアトムを衝突なく配置できるような完全クックーハッシュテーブルを構築できる h0 とテーブルサイズ (k) の組み合わせを見つけ出します。
文字列のレイアウト最適化: 全てのアトム文字列を結合して atomText という単一の長い文字列を生成します。この際、文字列の重複部分を検出して結合することで、atomText の長さを最小化しようと試みます（例: "apple" と "pleasure" があれば "appleasure" のように結合）。
table.go の生成: 見つけ出した最適な h0、maxAtomLen、そして生成されたルックアップテーブル (table) と atomText を含むGoのソースコード (table.go) を出力します。また、atom.go で使用される Atom 定数もこの gen.go によって生成されます。

このコンパイル時生成アプローチにより、実行時には複雑なハッシュ衝突解決ロジックが不要となり、非常に高速でメモリ効率の良いアトムルックアップが実現されます。

4. ベンチマーク結果の分析

コミットメッセージに記載されているベンチマーク結果は、この最適化の効果を明確に示しています。

benchmark          old ns/op    new ns/op    delta
BenchmarkLookup        83878        64681  -22.89%

old ns/op: 変更前の Lookup 関数が1回の操作にかかる平均時間（ナノ秒）。
new ns/op: 変更後の Lookup 関数が1回の操作にかかる平均時間（ナノ秒）。
delta: 性能改善率。-22.89% は、新しい実装が古い実装よりも約22.89%高速になったことを意味します。

この結果は、完全クックーハッシュの導入と文字列格納の最適化が、アトムルックアップのパフォーマンスに顕著な改善をもたらしたことを裏付けています。

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

このコミットによる主要なコード変更は、以下のファイルに集中しています。

src/pkg/exp/html/atom/atom.go:
- Atom 型の定義が type Atom int から type Atom uint32 に変更されました。
- Atom.String() メソッドの実装が、table スライスからの文字列参照から、atomText からオフセットと長さで部分文字列を抽出するロジックに変更されました。
- Lookup 関数の実装が、バイナリサーチから完全クックーハッシュに基づくルックアップロジック（2つのハッシュ位置をチェック）に変更されました。
- hash 関数（旧ハッシュ関数）が削除され、新しい fnv ハッシュ関数と match ヘルパー関数が追加されました。
src/pkg/exp/html/atom/gen.go:
- このファイルは、table.go と table_test.go を生成するためのツールです。
- 以前の単純なハッシュとソートに基づくテーブル生成ロジックが、完全クックーハッシュテーブルを構築するための複雑なアルゴリズム（最適な h0 と k の探索、文字列のオーバーラップ結合）に置き換えられました。
- main 関数内で、test フラグに応じて table_test.go 用の testAtomList を生成する機能も追加されました。
src/pkg/exp/html/atom/table.go:
- このファイルは gen.go によって生成されるため、コミット前後で内容が大きく変化しています。
- 以前は var table = [...]string{...} と var hashes = [...]uint32{...} のように、個々のアトム文字列とそれらのハッシュ値が直接定義されていました。
- 変更後は、const hash0 = ...、const maxAtomLen = ...、var table = [...]Atom{...}（ハッシュテーブル自体）、そして const atomText = ...（全てのアトム文字列を結合した巨大な文字列リテラル）が定義されるようになりました。Atom 定数も、Atom = 0x... の形式でオフセットと長さを含む値として定義されています。
src/pkg/exp/html/atom/atom_test.go および src/pkg/exp/html/atom/table_test.go:
- テストコードも、新しいアトム表現とルックアップロジックに合わせて更新されています。特に BenchmarkLookup は、新しいテーブル構造に対応するように変更されています。

コアとなるコードの解説

`src/pkg/exp/html/atom/atom.go` の変更点

`Atom` 型の定義

// Before
type Atom int

// After
type Atom uint32

Atom 型が int から uint32 に変更されました。これは、アトムの値を単なるインデックスではなく、文字列のオフセットと長さをエンコードした複合的な情報として扱うためです。

`Atom.String()` メソッド

// Before
func (a Atom) String() string {
	if 0 <= a && a < Atom(len(table)) {
		return table[a]
	}
	return ""
}

// After
func (a Atom) String() string {
	start := uint32(a >> 8) // 上位ビットからオフセットを取得
	n := uint32(a & 0xff)   // 下位8ビットから長さを取得
	if start+n > uint32(len(atomText)) {
		return ""
	}
	return atomText[start : start+n] // atomTextから部分文字列を抽出
}

Atom 値が uint32 になったことで、String() メソッドは Atom 値をビットシフトとビットマスクで分解し、グローバルな atomText 文字列から対応する部分文字列を抽出するようになりました。これにより、個々のアトム文字列をメモリに持つ必要がなくなり、メモリ効率が向上します。

`fnv` ハッシュ関数

// fnv computes the FNV hash with an arbitrary starting value h.
func fnv(h uint32, s []byte) uint32 {
	for i := range s {
		h ^= uint32(s[i])
		h *= 16777619 // FNV prime
	}
	return h
}

FNV-1aハッシュアルゴリズムの実装です。h は初期ハッシュ値（hash0 定数）、s は入力バイト列です。各バイトを現在のハッシュ値とXORし、FNVプライム（16777619）で乗算することでハッシュ値を更新します。

`Lookup` 関数

// Before (simplified)
func Lookup(s []byte) Atom {
	// ... length checks ...
	hs := hash(s) // Calculate hash
	// Binary search for hs in 'hashes' array
	// ... then verify string match with 'table'
}

// After
func Lookup(s []byte) Atom {
	if len(s) == 0 || len(s) > maxAtomLen {
		return 0
	}
	h := fnv(hash0, s) // FNVハッシュを計算 (初期値はgen.goで生成されたhash0)

	// 1つ目のハッシュ位置をチェック
	// tableはgen.goで生成された完全クックーハッシュテーブル
	// h & uint32(len(table)-1) はハッシュ値をテーブルサイズでマスクしてインデックスを得る
	if a := table[h&uint32(len(table)-1)]; int(a&0xff) == len(s) && match(a.string(), s) {
		return a
	}

	// 2つ目のハッシュ位置をチェック (ハッシュ値を16ビット右シフトして別のインデックスを得る)
	if a := table[(h>>16)&uint32(len(table)-1)]; int(a&0xff) == len(s) && match(a.string(), s) {
		return a
	}
	return 0
}

func match(s string, t []byte) bool {
	// ... (文字列比較の実装) ...
}

Lookup 関数は、入力文字列 s のFNVハッシュを計算します。このハッシュ値から、テーブルのサイズでマスクすることで2つの異なるインデックス（h & uint32(len(table)-1) と (h>>16)&uint32(len(table)-1)）を生成します。これはクックーハッシュの2つのハッシュ関数に相当します。

それぞれのインデックス位置に格納されている Atom 値 a を取得し、そのアトムの長さが入力文字列 s の長さと一致するか (int(a&0xff) == len(s))、そして a.string() が s と完全に一致するか (match(a.string(), s)) をチェックします。一致すればその Atom 値を返します。どちらの場所にも見つからなければ、対応するアトムは存在しないと判断し、ゼロを返します。このプロセスは、最大2回のテーブル参照と文字列比較で完了するため、非常に高速です。

`src/pkg/exp/html/atom/table.go` の変更点

このファイルは gen.go によって生成されるため、手動で編集されることはありません。変更後の table.go は、以下のような構造を持ちます。

// generated by go run gen.go; DO NOT EDIT

package atom

const (
	// 各アトム名に対応するAtom定数。
	// 値はオフセットと長さをエンコードしたuint32形式。
	A                Atom = 0x1
	Abbr             Atom = 0x4
	// ...
)

const hash0 = 0x516c42b0 // gen.goで探索された最適な初期ハッシュ値
const maxAtomLen = 16    // 最長のアトム文字列の長さ

var table = [1<<9]Atom{ // 完全クックーハッシュテーブル
	// インデックス: Atom値 (オフセットと長さを含む)
	0x2:   0x1f03,  // nav
	0x3:   0x17507, // onabort
	// ...
}

const atomText = // 全てのアトム文字列を結合した単一の長い文字列リテラル
	"\x00a\x00b\x00i\x00p\x00q\x00s\x00u\x00br\x00em\x00dd\x00dl\x00dt\x00h1\x00h2\x00h3\x00h4\x00h5\x00h6\x00id\x00hr\x00ol\x00li\x00rp\x00rt\x00ul\x00td\x00th\x00tr\x00col\x00bdi\x00bdo\x00alt\x00for\x00dfn\x00del\x00dir\x00div\x00kbd\x00ins\x00img\x00nav\x00map\x00max\x00min\x00low\x00src\x00sub\x00sup\x00rel\x00pre\x00wbr\x00var\x00cite\x00code\x00cols\x00base\x00body\x00abbr\x00area\x00font\x00form\x00data\x00kind\x00icon\x00head\x00high\x00href\x00html\x00open\x00name\x00nobr\x00mark\x00menu\x00meta\x00lang\x00link\x00list\x00loop\x00samp\x00size\x00span\x00step\x00rows\x00ruby\x00ping\x00wrap\x00time\x00type\x00color\x00class\x00align\x00aside\x00async\x00audio\x00frame\x00embed\x00defer\x00inert\x00input\x00ismap\x00media\x00meter\x00muted\x00label\x00scope\x00sizes\x00shape\x00small\x00start\x00style\x00param\x00width\x00value\x00video\x00tbody\x00table\x00tfoot\x00title\x00thead\x00track\x00canvas\x00center\x00coords\x00border\x00button\x00accept\x00action\x00applet\x00figure\x00footer\x00dialog\x00keygen\x00iframe\x00itemid\x00hgroup\x00header\x00height\x00hidden\x00object\x00onblur\x00ondrag\x00ondrop\x00onload\x00onshow\x00onplay\x00option\x00output\x00method\x00legend\x00scoped\x00script\x00select\x00source\x00srcdoc\x00strong\x00poster\x00usemap\x00target\x00sandbox\x00caption\x00section\x00keytype\x00charset\x00checked\x00content\x00command\x00colspan\x00onclick\x00onclose\x00onabort\x00onfocus\x00onended\x00onerror\x00onkeyup\x00oninput\x00onreset\x00onpause\x00srclang\x00optimum\x00summary\x00rowspan\x00address\x00enctype\x00article\x00itemref\x00pattern\x00headers\x00default\x00details\x00dirname\x00preload\x00controls\x00colgroup\x00noscript\x00download\x00oncancel\x00onchange\x00frameset\x00hreflang\x00progress\x00ononline\x00dropzone\x00onscroll\x00onseeked\x00onselect\x00onsubmit\x00onresize\x00onunload\x00tabindex\x00readonly\x00seamless\x00fieldset\x00manifest\x00selected\x00multiple\x00disabled\x00required\x00reversed\x00datalist\x00datetime\x00autoplay\x00textarea\x00itemprop\x00itemtype\x00optgroup\x00onwaiting\x00oncanplay\x00onoffline\x00onseeking\x00accesskey\x00onkeydown\x00onsuspend\x00onstalled\x00onstorage\x00draggable\x00onmessage\x00onmouseup\x00translate\x00oninvalid\x00itemscope\x00onemptied\x00challenge\x00autofocus\x00onplaying\x00maxlength\x00ondragend\x00figcaption\x00blockquote\x00onpopstate\x00onmouseout\x00annotation\x00ondragover\x00onprogress\x00http-equiv\x00ondblclick\x00formaction\x00mediagroup\x00onpageshow\x00onpagehide\x00radiogroup\x00formmethod\x00novalidate\x00formtarget\x00onkeypress\x00spellcheck\x00crossorigin\x00oncuechange\x00ondragstart\x00ondragleave\x00ondragenter\x00onloadstart\x00placeholder\x00formenctype\x00onmousedown\x00onmousemove\x00onmouseover\x00contextmenu\x00autocomplete\x00onmousewheel\x00onafterprint\x00ontimeupdate\x00onratechange\x00onhashchange\x00onloadeddata\x00typemustmatch\x00oncontextmenu\x00onbeforeprint\x00accept-charset\x00formnovalidate\x00onvolumechange\x00onbeforeunload\x00contenteditable\x00ondurationchange\x00onloadedmetadata\x00oncanplaythrough"

この構造は、完全クックーハッシュの動作に必要な全ての静的データを提供します。table 配列は、Lookup 関数が直接参照するハッシュテーブルであり、各エントリには対応する Atom 値（オフセットと長さ）が格納されています。atomText は、全てのアトム文字列が連続して格納されたメモリ効率の良いデータブロックです。

参考にした情報源リンク

クックーハッシュ:
- Wikipedia (Cuckoo hashing): https://en.wikipedia.org/wiki/Cuckoo_hashing
- GeeksforGeeks (Cuckoo Hashing): https://www.geeksforgeeks.org/cuckoo-hashing/
FNVハッシュ関数:
- Wikipedia (Fowler–Noll–Vo hash function): https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
- Stack Overflow (What is the FNV hash algorithm?): https://stackoverflow.com/questions/1072190/what-is-the-fnv-hash-algorithm
Go言語の文字列内部表現:
- Go Slices: usage and internals: https://go.dev/blog/slices (文字列の内部表現についても触れられています)
アトム化の概念:
- Mozilla Developer Network (MDN) - Atom (WebAssembly): https://developer.mozilla.org/en-US/docs/WebAssembly/Understanding_the_text_format#atoms (WebAssemblyの文脈ですが、アトム化の概念が説明されています)
- WebKit - AtomString: https://webkit.org/blog/1034/atomstring/ (WebKitにおけるアトム文字列の概念)

comemo