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

このコミットは、Go言語の標準ライブラリである go/scanner パッケージにおける字句解析（スキャン）処理のパフォーマンス最適化に関するものです。go/scanner パッケージは、Goのソースコードをトークン（識別子、キーワード、演算子、リテラルなど）のストリームに変換する役割を担っており、Goコンパイラやその他のツールチェーンの基盤となる重要なコンポーネントです。このコミットでは、特に一般的なケースにおけるスキャン処理の効率を向上させることを目的としています。

コミット

go/scanner パッケージにおいて、字句解析（スキャン）処理の速度を向上させるための最適化が行われました。これにより、いくつかの一般的なケースでのパフォーマンスが改善され、ベンチマークで約7%の高速化が確認されています。

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

https://github.com/golang/go/commit/3df0545a8b0f3ae1b7638474c986142fa9462c93

元コミット内容

commit 3df0545a8b0f3ae1b7638474c986142fa9462c93
Author: Robert Griesemer <gri@golang.org>
Date:   Tue Aug 14 11:26:30 2012 -0700

    go/scanner: faster scanning
    
    Optimize some common cases.
    
    benchmark            old ns/op    new ns/op    delta
    BenchmarkScanFile       718907       667960   -7.09%
    
    benchmark             old MB/s     new MB/s  speedup
    BenchmarkScanFile        23.03        25.51    1.11x
    
    R=r
    CC=golang-dev
    https://golang.org/cl/6454150
---
 src/pkg/go/scanner/scanner.go      | 38 ++++++++++++++++++++++++++++----------
 src/pkg/go/scanner/scanner_test.go | 26 +++++++++++++++++++++++++-
 2 files changed, 53 insertions(+), 11 deletions(-)

変更の背景

Go言語のコンパイラやツールは、ソースコードを処理する際に字句解析（スキャン）を頻繁に行います。このスキャン処理は、コンパイル時間の大部分を占める可能性があり、そのパフォーマンスは開発者の体験に直結します。特に、大規模なコードベースや頻繁なコンパイルが必要な開発環境では、スキャナーのわずかな速度向上でも全体的なビルド時間の短縮に大きく貢献します。

このコミットは、go/scanner パッケージの scan メソッド内で、文字の種類に応じたトークン識別のロジックを最適化することで、一般的なケースでのオーバーヘッドを削減し、スキャン速度を向上させることを目的としています。ベンチマーク結果が示すように、この最適化は実際に顕著なパフォーマンス改善をもたらしました。

前提知識の解説

字句解析（Lexical Analysis）とスキャナー（Scanner）

字句解析は、コンパイラの最初のフェーズであり、ソースコードを意味のある最小単位である「トークン」のストリームに変換するプロセスです。このプロセスを実行するプログラムは「字句解析器」または「スキャナー（Scanner）」と呼ばれます。例えば、var x = 10; というコードは、var (キーワード), x (識別子), = (演算子), 10 (整数リテラル), ; (区切り文字) といったトークンに分解されます。

go/scanner パッケージは、Go言語のソースコードをGo言語のトークンに変換するためのスキャナーを提供します。これは、Goコンパイラだけでなく、go vet や go fmt といった様々なGoツールで利用されています。

token.Lookup

token.Lookup 関数は、文字列（識別子）がGo言語の予約語（キーワード）であるかどうかを効率的に判断するために使用されます。内部的には、文字列とキーワードのマップを検索することで、該当するトークンタイプ（例: token.VAR, token.IF, token.FOR など）を返します。もし文字列がキーワードでなければ、token.IDENT（識別子）を返します。マップルックアップは一般的に高速ですが、頻繁に呼び出される場合、そのオーバーヘッドが累積してパフォーマンスボトルネックになる可能性があります。

insertSemi

Go言語には、セミコロン自動挿入（Automatic Semicolon Insertion: ASI）という特徴的なルールがあります。これは、特定の状況下で改行の後に自動的にセミコロンが挿入されるというものです。go/scanner は、このASIルールを適切に処理するために、insertSemi というフラグを管理しています。このフラグは、現在のトークンの後にセミコロンを挿入すべきかどうかを示します。例えば、識別子、整数リテラル、break、continue、fallthrough、return などのトークンの後には、通常セミコロンが挿入されます。

ベンチマークの読み方

コミットメッセージに含まれるベンチマーク結果は、パフォーマンスの改善度合いを示しています。

• ns/op (nanoseconds per operation): 1回の操作にかかる平均時間（ナノ秒）。この値が小さいほど高速です。
• MB/s (megabytes per second): 1秒あたりに処理できるデータ量（メガバイト）。この値が大きいほど高速です。
• delta: 変更前後の ns/op の差分をパーセンテージで示したもの。負の値は高速化を示します。
• speedup: 変更前後の MB/s の比率。1より大きい値は高速化を示します。

このコミットでは、BenchmarkScanFile というベンチマークにおいて、1操作あたりの時間が約7.09%短縮され、処理速度が1.11倍に向上したことが示されています。

技術的詳細

このコミットの主要な最適化は、src/pkg/go/scanner/scanner.go ファイル内の Scanner.Scan メソッド（またはその内部で呼び出されるロジック）に集中しています。特に、現在の文字 s.ch に基づいてトークンを識別する switch ステートメントが変更されました。

1. 識別子/キーワードの処理の最適化

以前は、isLetter(ch) という汎用的な関数で文字がアルファベットであるかを判断し、その後 s.scanIdentifier() で識別子全体をスキャンし、token.Lookup(lit) でそれがキーワードであるかを調べていました。

// 変更前
case isLetter(ch):
    lit = s.scanIdentifier()
    tok = token.Lookup(lit)
    switch tok {
    case token.IDENT, token.BREAK, token.CONTINUE, token.FALLTHROUGH, token.RETURN:
        insertSemi = true
    }

この変更では、文字の種類をより具体的に区別することで、token.Lookup の呼び出し回数を減らしています。

• 小文字で始まる識別子/キーワード ('a' <= ch && ch <= 'z'): Go言語のキーワードはすべて小文字で始まり、かつ2文字以上の長さを持っています（例: for, if, var）。単一文字の識別子（例: i, j, x）は、Go言語のキーワードにはなりえません。この最適化では、まず s.scanIdentifier() で識別子全体をスキャンした後、len(lit) > 1 のチェックを追加しています。もし識別子の長さが1文字であれば、それは確実にキーワードではないため、token.Lookup(lit) の呼び出しをスキップし、直接 tok = token.IDENT と設定します。これにより、不要なマップルックアップを回避し、パフォーマンスを向上させます。

  // 変更後 (小文字で始まる場合)
  case 'a' <= ch && ch <= 'z':
      lit = s.scanIdentifier()
      if len(lit) > 1 { // キーワードは1文字より長いので、ここでLookupを避ける
          tok = token.Lookup(lit)
          switch tok {
          case token.IDENT, token.BREAK, token.CONTINUE, token.FALLTHROUGH, token.RETURN:
              insertSemi = true
          }
      } else {
          insertSemi = true
          tok = token.IDENT
      }
  

• 大文字またはアンダースコアで始まる識別子 ('A' <= ch && ch <= 'Z' || ch == '_'): Go言語では、大文字で始まる識別子やアンダースコアで始まる識別子は、常に通常の識別子であり、キーワードになることはありません。したがって、これらのケースでは token.Lookup を呼び出す必要がありません。直接 tok = token.IDENT と設定し、insertSemi = true を設定することで、無駄な処理を省いています。

  // 変更後 (大文字またはアンダースコアで始まる場合)
  case 'A' <= ch && ch <= 'Z' || ch == '_':
      insertSemi = true
      tok = token.IDENT
      lit = s.scanIdentifier()
  

2. 数値リテラルのスキャン最適化

数値リテラルをスキャンする際の文字判定も最適化されました。以前は digitVal(ch) < 10 という関数呼び出しを使用していましたが、これは文字が数字であるかを判断するためのものです。

// 変更前 (数値リテラル)
case digitVal(ch) < 10:
    insertSemi = true
    tok, lit = s.scanNumber(false)

// 変更前 (小数点以下の数値)
case '.':
    if digitVal(s.ch) < 10 {
        insertSemi = true
        tok, lit = s.scanNumber(true)
    } else if s.ch == '.' {
        // ...
    }

これを '0' <= ch && ch <= '9' という直接的な文字コード範囲チェックに置き換えることで、関数呼び出しのオーバーヘッドをなくし、より高速な判定を実現しています。

// 変更後 (数値リテラル)
case '0' <= ch && ch <= '9':
    insertSemi = true
    tok, lit = s.scanNumber(false)

// 変更後 (小数点以下の数値)
case '.':
    if '0' <= s.ch && s.ch <= '9' {
        insertSemi = true
        tok, lit = s.scanNumber(true)
    } else if s.ch == '.' {
        // ...
    }

3. default ケースでの文字処理の改善

switch ステートメントの default ケースは、どの特定のケースにもマッチしなかった文字を処理します。以前は、マッチしなかった文字はすべて「不正な文字」としてエラー処理されていました。

// 変更前 (default ケース)
default:
    s.error(s.file.Offset(pos), fmt.Sprintf("illegal character %#U", ch))
    insertSemi = s.insertSemi // preserve insertSemi info
    tok = token.ILLEGAL
    lit = string(ch)

この変更では、default ケース内で isLetter(ch) を再度チェックしています。これは、Unicode文字など、ASCII範囲外の文字で isLetter が true を返すものの、上記の 'a' <= ch && ch <= 'z' や 'A' <= ch && ch <= 'Z' || ch == '_' の直接的なASCII範囲チェックでは捕捉されなかった文字を適切に識別子として処理するためのフォールバックメカニズムと考えられます。これにより、より堅牢な字句解析が可能になります。

// 変更後 (default ケース)
default:
    if isLetter(ch) { // 捕捉しきれなかった文字がアルファベットの場合
        // handle any letters we might have missed
        insertSemi = true
        tok = token.IDENT
        s.scanIdentifier()
    } else { // それ以外は不正な文字
        s.error(s.file.Offset(pos), fmt.Sprintf("illegal character %#U", ch))
        insertSemi = s.insertSemi // preserve insertSemi info
        tok = token.ILLEGAL
        lit = string(ch)
    }

4. ベンチマークの追加と修正

src/pkg/go/scanner/scanner_test.go には、BenchmarkScanFile という新しいベンチマークが追加されました。このベンチマークは、scanner.go ファイル自体を読み込み、その内容をスキャンすることで、より現実的なシナリオでのスキャナーのパフォーマンスを測定します。これにより、実際のコードベースに対する変更の影響を正確に評価できるようになりました。

また、既存の BenchmarkScan 関数のループ方向が for i := b.N - 1; i >= 0; i-- から for i := 0; i < b.N; i++ に変更されています。これは機能的な違いはほとんどありませんが、ベンチマークの慣習やキャッシュの振る舞いにわずかな影響を与える可能性があります。

これらの変更により、go/scanner はより効率的に動作し、Goコンパイラ全体のパフォーマンス向上に貢献しています。

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

src/pkg/go/scanner/scanner.go

--- a/src/pkg/go/scanner/scanner.go
+++ b/src/pkg/go/scanner/scanner.go
@@ -572,14 +572,25 @@ scanAgain:
 	// determine token value
 	insertSemi := false
 	switch ch := s.ch; {
-	case isLetter(ch):
+	case 'a' <= ch && ch <= 'z':
+		// literals start with a lower-case letter
 		lit = s.scanIdentifier()
-		tok = token.Lookup(lit)
-		switch tok {
-		case token.IDENT, token.BREAK, token.CONTINUE, token.FALLTHROUGH, token.RETURN:
+		if len(lit) > 1 {
+			// keywords are longer than one letter - avoid lookup otherwise
+			tok = token.Lookup(lit)
+			switch tok {
+			case token.IDENT, token.BREAK, token.CONTINUE, token.FALLTHROUGH, token.RETURN:
+				insertSemi = true
+			}
+		} else {
 			insertSemi = true
+			tok = token.IDENT
 		}
-	case digitVal(ch) < 10:
+	case 'A' <= ch && ch <= 'Z' || ch == '_':
+		insertSemi = true
+		tok = token.IDENT
+		lit = s.scanIdentifier()
+	case '0' <= ch && ch <= '9':
 		insertSemi = true
 		tok, lit = s.scanNumber(false)
 	default:
@@ -612,7 +623,7 @@ scanAgain:
 		case ':':
 			tok = s.switch2(token.COLON, token.DEFINE)
 		case '.':
-			if digitVal(s.ch) < 10 {
+			if '0' <= s.ch && s.ch <= '9' {
 				insertSemi = true
 				tok, lit = s.scanNumber(true)
 			} else if s.ch == '.' {
@@ -704,10 +715,17 @@ scanAgain:
 		case '|':
 			tok = s.switch3(token.OR, token.OR_ASSIGN, '|', token.LOR)
 		default:
-			s.error(s.file.Offset(pos), fmt.Sprintf("illegal character %#U", ch))
-			insertSemi = s.insertSemi // preserve insertSemi info
-			tok = token.ILLEGAL
-			lit = string(ch)
+			if isLetter(ch) {
+				// handle any letters we might have missed
+				insertSemi = true
+				tok = token.IDENT
+				s.scanIdentifier()
+			} else {
+				s.error(s.file.Offset(pos), fmt.Sprintf("illegal character %#U", ch))
+				insertSemi = s.insertSemi // preserve insertSemi info
+				tok = token.ILLEGAL
+				lit = string(ch)
+			}
 		}
 	}
 	if s.mode&dontInsertSemis == 0 {

src/pkg/go/scanner/scanner_test.go

--- a/src/pkg/go/scanner/scanner_test.go
+++ b/src/pkg/go/scanner/scanner_test.go
@@ -6,6 +6,7 @@ package scanner
 
 import (
 	"go/token"
+	"io/ioutil"
 	"os"
 	"path/filepath"
 	"runtime"
@@ -705,7 +706,7 @@ func BenchmarkScan(b *testing.B) {
 	file := fset.AddFile("", fset.Base(), len(source))
 	var s Scanner
 	b.StartTimer()
-	for i := b.N - 1; i >= 0; i-- {
+	for i := 0; i < b.N; i++ {
 		s.Init(file, source, nil, ScanComments)
 		for {
 			_, tok, _ := s.Scan()
@@ -715,3 +716,26 @@ func BenchmarkScan(b *testing.B) {
 		}
 	}
 }
+
+func BenchmarkScanFile(b *testing.B) {
+	b.StopTimer()
+	const filename = "scanner.go"
+	src, err := ioutil.ReadFile(filename)
+	if err != nil {
+		panic(err)
+	}
+	fset := token.NewFileSet()
+	file := fset.AddFile(filename, fset.Base(), len(src))
+	b.SetBytes(int64(len(src)))
+	var s Scanner
+	b.StartTimer()
+	for i := 0; i < b.N; i++ {
+		s.Init(file, src, nil, ScanComments)
+		for {
+			_, tok, _ := s.Scan()
+			if tok == token.EOF {
+				break
+			}
+		}
+	}
+}

コアとなるコードの解説

src/pkg/go/scanner/scanner.go の変更点

• switch ch := s.ch; ブロック内の変更:
  • case 'a' <= ch && ch <= 'z': の追加:
    • 以前の isLetter(ch) という汎用的なチェックを、小文字のアルファベットに特化した範囲チェックに分割しました。
    • lit = s.scanIdentifier() で識別子をスキャンした後、if len(lit) > 1 という条件を追加しています。これは、Go言語のキーワードが常に2文字以上であるという事実を利用した最適化です。もしスキャンされた識別子が1文字であれば、それはキーワードではないことが確定するため、高コストな token.Lookup(lit) の呼び出しをスキップし、直接 tok = token.IDENT と設定することでパフォーマンスを向上させています。
  • case 'A' <= ch && ch <= 'Z' || ch == '_': の追加:
    • 大文字のアルファベットまたはアンダースコアで始まる識別子に特化した新しいケースです。Go言語では、これらの文字で始まる識別子は常に通常の識別子であり、キーワードにはなりません。そのため、token.Lookup を呼び出すことなく、直接 tok = token.IDENT と設定し、insertSemi = true を設定しています。
  • case '0' <= ch && ch <= '9': への変更:
    • 数値リテラルをスキャンする際の判定を、digitVal(ch) < 10 から '0' <= ch && ch <= '9' という直接的な文字コード範囲チェックに変更しました。これにより、関数呼び出しのオーバーヘッドが削減され、より効率的な数字判定が可能になります。
  • case '.': ブロック内の変更:
    • 浮動小数点数をスキャンする際の小数点以下の数字判定も、同様に digitVal(s.ch) < 10 から '0' <= s.ch && s.ch <= '9' に変更されています。
  • default: ブロック内の変更:
    • どの特定のケースにもマッチしなかった文字を処理する default ブロックに、if isLetter(ch) という条件が追加されました。これは、ASCII範囲外のUnicode文字など、isLetter 関数がアルファベットと判断するものの、上記のASCII範囲チェックでは捕捉されなかった文字を適切に識別子として処理するためのフォールバックロジックです。これにより、スキャナーの堅牢性が向上します。

src/pkg/go/scanner/scanner_test.go の変更点

• import "io/ioutil" の追加:
  • 新しく追加されるベンチマーク関数 BenchmarkScanFile でファイル読み込みを行うために io/ioutil パッケージがインポートされました。
• BenchmarkScan 関数のループ変更:
  • for i := b.N - 1; i >= 0; i-- から for i := 0; i < b.N; i++ へとループの方向が変更されました。これは主にコーディングスタイルや、ごくわずかなキャッシュの振る舞いの違いによるものですが、機能的な影響はほとんどありません。
• BenchmarkScanFile 関数の追加:
  • この新しいベンチマーク関数は、scanner.go ファイル自体を読み込み、その内容を go/scanner でスキャンします。
  • b.SetBytes(int64(len(src))) を呼び出すことで、ベンチマーク結果に処理されたバイト数を含めるように設定しています。これにより、MB/s のようなスループット指標も測定できるようになり、より実用的なパフォーマンス評価が可能になります。このベンチマークが、コミットメッセージに記載されているパフォーマンス改善の数値の根拠となっています。

これらの変更は、Go言語の字句解析器の効率を向上させ、Goコンパイラおよび関連ツールの全体的なパフォーマンスに貢献しています。

関連リンク

• Go言語の公式ドキュメント: https://go.dev/doc/
• go/scanner パッケージのドキュメント: https://pkg.go.dev/go/scanner
• go/token パッケージのドキュメント: https://pkg.go.dev/go/token
• Go言語のセミコロン自動挿入ルールに関する公式ブログ記事: https://go.dev/blog/semicolon

参考にした情報源リンク

• Go Gerrit Code Review (変更リスト): https://golang.org/cl/6454150
• GitHub上のコミットページ: https://github.com/golang/go/commit/3df0545a8b0f3ae1b7638474c986142fa9462c93