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

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

このコミットは、Go言語の実験的なHTMLパーサーライブラリ（exp/html）において、トークナイザーがタグトークンに対して文字列ではなく「アトム」（整数値）を返すように変更するものです。これにより、HTML要素のタグ名を文字列比較する代わりに、より高速な整数比較が可能になり、パーサーのパフォーマンスが向上します。

コミット

commit cd21eff70520a433f6ee67819e539b2ebe043120
Author: Nigel Tao <nigeltao@golang.org>
Date:   Thu Jun 7 13:05:35 2012 +1000

    exp/html: make the tokenizer return atoms for tag tokens.
    
    This is part 1 of a 2 part changelist. Part 2 contains the mechanical
    change to parse.go to compare atoms (ints) instead of strings.
    
    The overall effect of the two changes are:
    benchmark                      old ns/op    new ns/op    delta
    BenchmarkParser                  4462274      4058254   -9.05%
    BenchmarkRawLevelTokenizer        913202       912917   -0.03%
    BenchmarkLowLevelTokenizer       1268626      1267836   -0.06%
    BenchmarkHighLevelTokenizer      1947305      1968944   +1.11%
    
    R=rsc
    CC=andybalholm, golang-dev, r
    https://golang.org/cl/6305053

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

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

元コミット内容

exp/html: トークナイザーがタグトークンに対してアトムを返すようにする。

これは2部構成の変更リストのパート1です。パート2では、parse.goで文字列の代わりにアトム（整数）を比較するための機械的な変更が含まれます。

これら2つの変更の全体的な効果は以下の通りです： ベンチマーク 旧 ns/op 新 ns/op 差分 BenchmarkParser 4462274 4058254 -9.05% BenchmarkRawLevelTokenizer 913202 912917 -0.03% BenchmarkLowLevelTokenizer 1268626 1267836 -0.06% BenchmarkHighLevelTokenizer 1947305 1968944 +1.11%

変更の背景

この変更の主な背景は、HTMLパーサーのパフォーマンス向上です。HTMLドキュメントを解析する際、タグ名（例: <div>, <p>, <a>）は頻繁に出現します。これらのタグ名を文字列として比較することは、文字ごとの比較が必要となるため、計算コストが高い処理です。特に大規模なHTMLドキュメントや、多数のタグを含むドキュメントを処理する場合、このオーバーヘッドは無視できません。

Go言語のexp/htmlパッケージは、HTML5の仕様に準拠したパーサーを提供することを目指しており、その効率性は非常に重要です。このコミットは、タグ名の比較を最適化することで、パーサー全体の処理速度を向上させることを目的としています。具体的には、文字列の比較を、より高速な整数値の比較に置き換える「文字列インターニング」の概念を導入しています。

コミットメッセージに示されているベンチマーク結果は、この変更が特にBenchmarkParserにおいて約9%の性能向上をもたらしたことを示しており、その効果が実証されています。これは、HTMLパーシングのようなI/Oバウンドな処理において、CPUの計算効率を改善することがいかに重要であるかを示しています。

前提知識の解説

HTMLパーシングの基本

HTMLパーシングは、HTMLドキュメントを読み込み、その構造をコンピュータが理解できる形式（通常はDOMツリー）に変換するプロセスです。このプロセスは通常、以下の段階に分けられます。

  1. トークナイズ（字句解析）: 入力されたHTML文字列を、意味のある最小単位である「トークン」に分割します。例えば、<p>は開始タグトークン、Helloはテキストトークン、</p>は終了タグトークンといった具合です。
  2. ツリー構築（構文解析）: トークナイザーから受け取ったトークンを基に、HTMLドキュメントの階層構造を表すDOMツリーを構築します。

このコミットは、主にトークナイズの段階、特にタグトークンの処理に焦点を当てています。

文字列インターニング（String Interning）と「アトム」（Atom）

文字列インターニングとは、プログラム内で同じ文字列リテラルや文字列値が複数回出現する場合に、それらをメモリ上で一意のインスタンスとして管理する最適化手法です。これにより、以下の利点が得られます。

  • メモリ効率の向上: 同じ文字列が複数存在する場合でも、メモリ上には1つのコピーしか存在しないため、メモリ使用量を削減できます。
  • 比較の高速化: 文字列の内容を比較する代わりに、文字列が格納されているメモリアドレス（ポインタ）や、その文字列に割り当てられた一意の整数値（ID）を比較するだけで済むため、比較処理が非常に高速になります。これは、文字ごとの比較よりもはるかに効率的です。

**「アトム」（Atom）**は、コンパイラやプログラミング言語の文脈で、文字列インターニングされた文字列、または「シンボル」と同義で使われることがあります。特に、Lisp、Scheme、Julia、Rubyなどの言語では、変数名、関数名、キーワードなどの識別子を効率的に扱うために「シンボル」や「アトム」というデータ型が用いられます。これらは実質的にインターニングされた文字列であり、一意の整数値として内部的に表現されます。

このコミットでは、HTMLタグ名（例: "div", "p", "a"）を「アトム」として扱うことで、文字列インターニングの恩恵を受け、タグ名の比較を高速化しています。具体的には、各タグ名に一意の整数IDを割り当て、比較時にはこの整数IDを用いることで、文字列比較のオーバーヘッドを排除しています。

Go言語におけるexpパッケージ

Go言語の標準ライブラリには、安定版のAPIが含まれていますが、新しい機能や実験的なAPIはexp（experimental）パッケージとして提供されることがあります。exp/htmlもその一つで、HTML5パーサーの初期開発段階で利用されていました。expパッケージのコードは、将来的に標準ライブラリに統合されるか、あるいは破棄される可能性があります。このコミットは、exp/htmlパッケージの内部的な最適化であり、その後のGo言語の進化において、このアプローチが標準的なHTMLパーサーに採用されていきました。

技術的詳細

このコミットの核心は、HTMLタグ名を文字列として扱う代わりに、atom.Atom型という整数値として扱うように変更することです。

  1. atomパッケージの導入: src/pkg/exp/html/atomという新しいパッケージが導入され、HTMLの標準的なタグ名や属性名に対応する一意の整数値（アトム）を定義・管理します。このパッケージは、文字列からアトムへのマッピング（Lookup関数など）や、アトムから文字列への変換（Stringメソッドなど）を提供します。

  2. Node構造体へのDataAtomフィールドの追加: src/pkg/exp/html/node.goファイルにおいて、HTMLドキュメントのノードを表すNode構造体に、DataAtom atom.Atomという新しいフィールドが追加されました。

    • Dataフィールドは引き続き元の文字列形式のタグ名を保持しますが、DataAtomフィールドは、そのタグ名に対応するアトム（整数値）を保持します。
    • これにより、タグ名が既知のHTML要素である場合、DataAtomに非ゼロの値が設定され、文字列比較の代わりにこの整数値を利用できるようになります。

  3. Token構造体へのDataAtomフィールドの追加: src/pkg/exp/html/token.goファイルにおいて、トークナイザーが生成するトークンを表すToken構造体にも、DataAtom atom.Atomフィールドが追加されました。

    • トークナイザーは、タグ名を解析する際に、そのタグ名に対応するアトムをDataAtomフィールドに設定します。これにより、パーサーはトークンを受け取った時点で、すでにアトム化されたタグ名を利用できます。

  4. トークナイザーの変更: src/pkg/exp/html/token.go内のTokenizer.Token()メソッドが変更され、StartTagTokenおよびEndTagTokenを生成する際に、タグ名文字列をatom.Lookup関数でアトムに変換し、Token.DataAtomフィールドに設定するようになりました。もしタグ名が既知のアトムでない場合は、DataAtomはゼロ（無効なアトム）に設定されます。

  5. パーサーの変更（準備段階）: このコミットは「2部構成の変更リストのパート1」と明記されており、parse.go内のタグ名比較を文字列からアトムに切り替える「機械的な変更」はパート2で行われることが示されています。しかし、このコミットでもparse.go内のNodeやTokenの初期化時にDataAtomフィールドが考慮されるよう、一部の変更が加えられています（例: TODO: also set DataAtom.というコメントが追加されている箇所）。また、parse_test.goでは、テストケースのコンテキストノードを生成する際にatom.Lookupを使用してDataAtomを設定する変更が見られます。

これらの変更により、HTMLパーサーはタグ名の比較を文字列ベースから整数ベースに移行するための基盤が構築され、結果としてベンチマークで示されたようなパフォーマンス向上が実現されました。

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

src/pkg/exp/html/node.go

  • NodeTypeの型がintからuint32に変更されました。
  • Node構造体にDataAtom atom.Atomフィールドが追加されました。
  • Node.clone()メソッドで、クローンされるノードにDataAtomもコピーされるようになりました。
--- a/src/pkg/exp/html/node.go
+++ b/src/pkg/exp/html/node.go
@@ -4,8 +4,12 @@
 
 package html
 
+import (
+	"exp/html/atom"
+)
+
 // A NodeType is the type of a Node.
-type NodeType int
+type NodeType uint32
 
 const (
 	ErrorNode NodeType = iota
@@ -25,7 +29,8 @@ var scopeMarker = Node{Type: scopeMarkerNode}\n // A Node consists of a NodeType and some Data (tag name for element nodes,\n // content for text) and are part of a tree of Nodes. Element nodes may also\n // have a Namespace and contain a slice of Attributes. Data is unescaped, so\n-// that it looks like "a<b" rather than "a&lt;b".\n+// that it looks like "a<b" rather than "a&lt;b". For element nodes, DataAtom\n+// is the atom for Data, or zero if Data is not a known tag name.\n //\n // An empty Namespace implies a "http://www.w3.org/1999/xhtml" namespace.\n // Similarly, "math" is short for "http://www.w3.org/1998/Math/MathML", and\n@@ -34,6 +39,7 @@ type Node struct {\n 	Parent    *Node\n 	Child     []*Node\n 	Type      NodeType\n+	DataAtom  atom.Atom\n 	Data      string\n 	Namespace string\n 	Attr      []Attribute\n@@ -83,9 +89,10 @@ func reparentChildren(dst, src *Node) {\n // The clone has no parent and no children.\n func (n *Node) clone() *Node {\n 	m := &Node{\n-\t\tType: n.Type,\n-\t\tData: n.Data,\n-\t\tAttr: make([]Attribute, len(n.Attr)),\n+\t\tType:     n.Type,\n+\t\tDataAtom: n.DataAtom,\n+\t\tData:     n.Data,\n+\t\tAttr:     make([]Attribute, len(n.Attr)),\n 	}\n 	copy(m.Attr, n.Attr)\n 	return m

src/pkg/exp/html/parse.go

  • exp/html/atomパッケージがインポートされました。
  • addElement関数内で、Nodeの初期化時にDataAtomを設定するTODOコメントが追加されました。
  • parseImpliedToken関数内で、Tokenの初期化時にDataAtomを設定するTODOコメントが追加されました。
  • ParseFragment関数内で、ルートノードの初期化時にDataAtomを設定するTODOコメントが追加されました。
  • 属性のループ変数名がaからt0やt1、tに変更され、より明確になりました。
  • SVGタグ名の調整ロジックで、p.tok.DataAtomも設定されるようになりました。
--- a/src/pkg/exp/html/parse.go
+++ b/src/pkg/exp/html/parse.go
@@ -5,6 +5,7 @@
 package html
 
 import (
+	"exp/html/atom"
 	"io"
 	"strings"
 )
@@ -280,7 +281,7 @@ func (p *parser) addText(text string) {
 func (p *parser) addElement(tag string, attr []Attribute) {
 	p.addChild(&Node{
 		Type: ElementNode,
-		Data: tag,
+		Data: tag, // TODO: also set DataAtom.
 		Attr: attr,
 	})
 }
@@ -310,9 +311,9 @@ findIdenticalElements:
 			continue
 		}
 	compareAttributes:
-		for _, a := range n.Attr {
-			for _, b := range attr {
-				if a.Key == b.Key && a.Namespace == b.Namespace && a.Val == b.Val {
+		for _, t0 := range n.Attr {
+			for _, t1 := range attr {
+				if t0.Key == t1.Key && t0.Namespace == t1.Namespace && t0.Val == t1.Val {
 					// Found a match for this attribute, continue with the next attribute.
 					continue compareAttributes
 				}
@@ -676,13 +677,13 @@ func copyAttributes(dst *Node, src Token) {
 		return
 	}
 	attr := map[string]string{}
-	for _, a := range dst.Attr {
-		attr[a.Key] = a.Val
-	}
-	for _, a := range src.Attr {
-		if _, ok := attr[a.Key]; !ok {
-			dst.Attr = append(dst.Attr, a)
-			attr[a.Key] = a.Val
+	for _, t := range dst.Attr {
+		attr[t.Key] = t.Val
+	}
+	for _, t := range src.Attr {
+		if _, ok := attr[t.Key]; !ok {
+			dst.Attr = append(dst.Attr, t)
+			attr[t.Key] = t.Val
 		}
 	}
 }
@@ -843,9 +844,9 @@ func inBodyIM(p *parser) bool {
 		p.oe.pop()
 		p.acknowledgeSelfClosingTag()
 		if p.tok.Data == "input" {
-			for _, a := range p.tok.Attr {
-				if a.Key == "type" {
-					if strings.ToLower(a.Val) == "hidden" {
+			for _, t := range p.tok.Attr {
+				if t.Key == "type" {
+					if strings.ToLower(t.Val) == "hidden" {
 						// Skip setting framesetOK = false
 						return true
 					}
@@ -874,16 +875,16 @@ func inBodyIM(p *parser) bool {
 			action := ""
 			prompt := "This is a searchable index. Enter search keywords: "
 			attr := []Attribute{{Key: "name", Val: "isindex"}}
-			for _, a := range p.tok.Attr {
-				switch a.Key {
+			for _, t := range p.tok.Attr {
+				switch t.Key {
 				case "action":
-					action = a.Val
+					action = t.Val
 				case "name":
 					// Ignore the attribute.
 				case "prompt":
-					prompt = a.Val
+					prompt = t.Val
 				default:
-					attr = append(attr, a)
+					attr = append(attr, t)
 				}
 			}
 			p.acknowledgeSelfClosingTag()
@@ -1231,8 +1232,8 @@ func inTableIM(p *parser) bool {
 		case "style", "script":
 			return inHeadIM(p)
 		case "input":
-			for _, a := range p.tok.Attr {
-				if a.Key == "type" && strings.ToLower(a.Val) == "hidden" {
+			for _, t := range p.tok.Attr {
+				if t.Key == "type" && strings.ToLower(t.Val) == "hidden" {
 					p.addElement(p.tok.Data, p.tok.Attr)
 					p.oe.pop()
 					return true
@@ -1863,6 +1864,7 @@ func parseForeignContent(p *parser) bool {
 			// Adjust SVG tag names. The tokenizer lower-cases tag names, but
 			// SVG wants e.g. "foreignObject" with a capital second "O".
 			if x := svgTagNameAdjustments[p.tok.Data]; x != "" {
+				p.tok.DataAtom = a.Lookup([]byte(x))
 				p.tok.Data = x
 			}
 			adjustAttributeNames(p.tok.Attr, svgAttributeAdjustments)
@@ -1929,7 +1931,7 @@ func (p *parser) parseImpliedToken(t TokenType, data string, attr []Attribute) {\n 	realToken, selfClosing := p.tok, p.hasSelfClosingToken\n 	p.tok = Token{\n 		Type: t,\n-		Data: data,\n+		Data: data, // TODO: also set DataAtom.
 		Attr: attr,
 	}\n 	p.hasSelfClosingToken = false
@@ -2014,7 +2016,7 @@ func ParseFragment(r io.Reader, context *Node) ([]*Node, error) {\n 
 	root := &Node{\n 		Type: ElementNode,\n-		Data: "html",\n+		Data: "html", // TODO: also set DataAtom.
 	}\n 	p.doc.Add(root)\n 	p.oe = nodeStack{root}

src/pkg/exp/html/parse_test.go

  • exp/html/atomパッケージがインポートされました。
  • testParseCase関数内で、contextNodeを生成する際にDataAtomフィールドもatom.Lookupを使って設定されるようになりました。
--- a/src/pkg/exp/html/parse_test.go
+++ b/src/pkg/exp/html/parse_test.go
@@ -8,6 +8,7 @@ import (
 	"bufio"
 	"bytes"
 	"errors"
+	"exp/html/atom"
 	"flag"
 	"fmt"
 	"io"
@@ -320,8 +321,9 @@ func testParseCase(text, want, context string) (result parseTestResult, err erro\n 		}\n 	} else {\n 		contextNode := &Node{\n-\t\t\tType: ElementNode,\n-\t\t\tData: context,\n+\t\t\tType:     ElementNode,\n+\t\t\tDataAtom: atom.Lookup([]byte(context)),\n+\t\t\tData:     context,\n 		}\n 		nodes, err := ParseFragment(strings.NewReader(text), contextNode)\n 		if err != nil {

src/pkg/exp/html/token.go

  • TokenTypeの型がintからuint32に変更されました。
  • Token構造体にDataAtom atom.Atomフィールドが追加されました。
  • Tokenizer.Token()メソッド内で、StartTagTokenとEndTagTokenのDataAtomフィールドが、atom.Lookup関数を使って設定されるようになりました。タグ名が既知のアトムでない場合は0が設定されます。
--- a/src/pkg/exp/html/token.go
+++ b/src/pkg/exp/html/token.go
@@ -13,7 +13,7 @@ import (
 )
 
 // A TokenType is the type of a Token.
-type TokenType int
+type TokenType uint32
 
 const (
 	// ErrorToken means that an error occurred during tokenization.
@@ -66,11 +66,13 @@ type Attribute struct {
 // A Token consists of a TokenType and some Data (tag name for start and end
 // tags, content for text, comments and doctypes). A tag Token may also contain
 // a slice of Attributes. Data is unescaped for all Tokens (it looks like "a<b"
-// rather than "a&lt;b").
+// rather than "a&lt;b"). For tag Tokens, DataAtom is the atom for Data, or
+// zero if Data is not a known tag name.
 type Token struct {
-\tType TokenType\n-\tData string\n-\tAttr []Attribute\n+\tType     TokenType
+\tDataAtom atom.Atom
+\tData     string
+\tAttr     []Attribute
 }\n \n // tagString returns a string representation of a tag Token's Data and Attr.\n@@ -794,11 +796,19 @@ func (z *Tokenizer) Token() Token {\n \t\t\tkey, val, moreAttr = z.TagAttr()\n \t\t\tattr = append(attr, Attribute{"", atom.String(key), string(val)})\n \t\t}\n-\t\tt.Data = atom.String(name)\n+\t\tif a := atom.Lookup(name); a != 0 {\n+\t\t\tt.DataAtom, t.Data = a, a.String()\n+\t\t} else {\n+\t\t\tt.DataAtom, t.Data = 0, string(name)\n+\t\t}\n \t\tt.Attr = attr\n \tcase EndTagToken:\n \t\tname, _ := z.TagName()\n-\t\tt.Data = atom.String(name)\n+\t\tif a := atom.Lookup(name); a != 0 {\n+\t\t\tt.DataAtom, t.Data = a, a.String()\n+\t\t} else {\n+\t\t\tt.DataAtom, t.Data = 0, string(name)\n+\t\t}\n \t}\n \treturn t\n }\n```

## コアとなるコードの解説

このコミットの主要な変更は、HTMLパーサーの内部表現において、タグ名を従来の文字列（`string`）だけでなく、`atom.Atom`という新しい型（実体は`uint32`）で管理するようにした点です。

1.  **`Node`および`Token`構造体への`DataAtom`フィールドの追加**:
    *   `Node`はHTMLドキュメントの要素を表し、`Token`はトークナイザーが出力する最小単位を表します。
    *   これらの構造体に`DataAtom`フィールドが追加されたことで、タグ名が既知のHTML要素（例: `div`, `p`, `a`など）である場合、そのタグ名に対応する一意の整数値がこのフィールドに格納されます。
    *   これにより、タグ名の比較が必要な場面で、コストの高い文字列比較（文字ごとの比較）を行う代わりに、高速な整数比較が可能になります。

2.  **`token.go`におけるトークナイザーの変更**:
    *   `Tokenizer.Token()`メソッドは、HTMLの入力ストリームを読み込み、`Token`を生成する主要な関数です。
    *   このメソッド内で、`StartTagToken`や`EndTagToken`を生成する際に、タグ名（バイトスライスとして取得される）を`atom.Lookup()`関数に渡しています。
    *   `atom.Lookup()`は、与えられたタグ名文字列に対応するアトム（整数値）を返します。もしそのタグ名が事前に定義された既知のHTMLタグ名であれば、対応する非ゼロのアトムが返されます。そうでなければ、ゼロ（無効なアトム）が返されます。
    *   このアトムが`Token.DataAtom`フィールドに格納されます。同時に、元の文字列形式のタグ名は引き続き`Token.Data`フィールドに格納されます。これは、未知のタグ名や、デバッグ、表示目的で元の文字列が必要な場合に対応するためです。

3.  **`parse.go`における変更の準備**:
    *   このコミットは「パート1」であり、`parse.go`内で実際にアトムを使った比較に切り替える「機械的な変更」は「パート2」で行われると明記されています。
    *   しかし、このコミットでも、`addElement`や`parseImpliedToken`、`ParseFragment`といった関数内で`Node`や`Token`を生成する際に、`DataAtom`フィールドを設定するためのTODOコメントが追加されています。これは、将来の変更に備えたプレースホルダーです。
    *   また、SVGタグ名の調整ロジックでは、すでに`p.tok.DataAtom = a.Lookup([]byte(x))`という形でアトムが設定されるようになっています。これは、特定のタグ名に対しては先行してアトム化を適用していることを示しています。

このアプローチにより、HTMLパーサーは、頻繁に比較されるタグ名を効率的に処理できるようになり、特に大規模なHTMLドキュメントの解析において、顕著なパフォーマンス向上が期待できます。ベンチマーク結果が示すように、パーサー全体の速度が向上しているのは、このアトム化による最適化の直接的な効果です。

## 関連リンク

*   Go言語の公式ドキュメント: [https://golang.org/](https://golang.org/)
*   Go言語の`exp/html`パッケージ（当時の実験的なパッケージ）: 現在は`golang.org/x/net/html`に統合されています。
*   Go言語のコードレビューシステム（Gerrit）の変更リスト: [https://golang.org/cl/6305053](https://golang.org/cl/6305053)

## 参考にした情報源リンク

*   Wikipedia: [String interning](https://en.wikipedia.org/wiki/String_interning)
*   Compiler Design - Intermediate Code Generation (TutorialsPoint): [https://www.tutorialspoint.com/compiler_design/compiler_design_intermediate_code_generation.htm](https://www.tutorialspoint.com/compiler_design/compiler_design_intermediate_code_generation.htm)
*   What is an atom in compiler design? (Reddit discussion): [https://www.reddit.com/r/compilers/comments/102120/what_is_an_atom_in_compiler_design/](https://www.reddit.com/r/compilers/comments/102120/what_is_an_atom_in_compiler_design/)
*   Mozilla Developer Network: [Atoms](https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Internals/Atoms) (FirefoxのJavaScriptエンジンにおけるアトムの概念)