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

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

このコミットは、Go言語のgo/scannerパッケージにおけるスキャン処理のパフォーマンスを約17%向上させることを目的としています。主な変更点は、Scan APIのセマンティクスを調整し、トークンのリテラル文字列の返却方法を最適化したこと、およびtoken.Lookup APIが[]byteではなくstring引数を受け取るように変更したことです。これらの変更は、長らく未解決だったTODO項目に対応するものであり、文字列の生成回数を減らすことでスキャナーの効率を高めています。また、パフォーマンス改善を測定するためのベンチマークも追加されました。

コミット

commit 3fc327b33bede4445ff01072b8cc91c88fbd10fa
Author: Robert Griesemer <gri@golang.org>
Date:   Wed Jan 11 14:20:32 2012 -0800

    go/scanner: 17% faster scanning
    
    - Changed the Scan API semantics slightly:
    The token literal string is only returned
    if the token is a literal, comment, semicolon,
    or illegal character. In all other cases, the
    token literal value is determined by the token
    value.
    
    Clients that care about the token literal value
    when not present can always use the following
    piece of code:
    
    pos, tok, lit := scanner.Scan()
    if lit == "" {
       lit = tok.String()
    }
    
    - Changed token.Lookup API to use a string instead
    of a []byte argument.
    
    - Both these changes were long-standing TODOs.
    
    - Added BenchmarkScan.
    
    This change permits a faster implementation of Scan
    with much fewer string creations:
    
    benchmark                old ns/op    new ns/op    delta
    scanner.BenchmarkScan        74404        61457  -17.40%
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/5532076

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

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

元コミット内容

go/scannerパッケージのスキャン処理を17%高速化する変更です。

主な変更点は以下の通りです。

  • Scan APIのセマンティクスがわずかに変更されました。トークンのリテラル文字列は、トークンがリテラル、コメント、セミコロン、または不正な文字である場合にのみ返されるようになりました。それ以外の場合、トークンのリテラル値はトークン値によって決定されます。
  • token.Lookup APIが[]byte引数ではなくstring引数を使用するように変更されました。
  • これらの変更は、長らく未解決だったTODO項目でした。
  • BenchmarkScanが追加されました。

これらの変更により、文字列の生成回数が大幅に減少し、Scanの実装が高速化されました。 ベンチマーク結果: scanner.BenchmarkScan 旧: 74404 ns/op 新: 61457 ns/op 差分: -17.40%

変更の背景

このコミットの背景には、Go言語のコンパイラやツールチェインの基盤となる字句解析（スキャン）処理のパフォーマンス最適化という明確な目的があります。

  1. パフォーマンスのボトルネック解消: 字句解析は、ソースコードをトークンに分解するプロセスであり、コンパイルプロセスの初期段階で頻繁に実行されます。この部分の効率が悪いと、コンパイル時間全体に大きな影響を与えます。特に、文字列の生成はメモリ割り当てとガベージコレクションのオーバーヘッドを伴うため、頻繁に行われるとパフォーマンスのボトルネックになりがちです。コミットメッセージにある「much fewer string creations」（はるかに少ない文字列生成）という記述は、この問題意識を明確に示しています。

  2. 長年のTODOの解決: コミットメッセージには「Both these changes were long-standing TODOs.」と明記されており、Scan APIのセマンティクスとtoken.Lookupの引数型に関する改善が、以前から計画されていた課題であったことがわかります。これは、設計上の改善点や既知の非効率性が認識されており、それが今回修正されたことを意味します。

  3. APIの整合性と効率化: token.Lookupが[]byteを受け取っていたことは、Goの文字列とバイトスライスの扱いの慣習から見ても、非効率的であった可能性があります。Goでは文字列は不変であり、バイトスライスから文字列への変換はコピーを伴います。頻繁な変換はオーバーヘッドとなるため、APIが直接stringを受け取るようにすることで、不要な変換を避けることができます。

  4. ベンチマークによる効果の検証: パフォーマンス改善を謳う変更には、その効果を客観的に測定する手段が不可欠です。BenchmarkScanの追加は、変更が実際に意図した効果をもたらしたことを確認し、将来的な回帰を防ぐための重要なステップです。

これらの背景から、このコミットはGo言語のツールチェインの基盤部分における堅牢性と効率性を高めるための、計画的かつ重要な最適化であったと言えます。

前提知識の解説

このコミットを理解するためには、以下のGo言語の概念とコンパイラの基礎知識が必要です。

  1. 字句解析（Lexical Analysis / Scanning）:

    • コンパイラの最初の段階であり、ソースコードの文字列を意味のある最小単位である「トークン（Token）」のストリームに変換するプロセスです。
    • 例えば、var x = 10;というコードは、var（キーワード）、x（識別子）、=（演算子）、10（整数リテラル）、;（区切り文字）といったトークンに分解されます。
    • go/scannerパッケージは、Go言語のソースコードを字句解析するための機能を提供します。

  2. トークン（Token）:

    • 字句解析によって生成される、プログラムの最小単位です。
    • 各トークンは、その「種類」（例: 識別子、キーワード、演算子、リテラル）と、場合によってはその「値」（リテラル文字列）を持ちます。
    • go/tokenパッケージは、Go言語のトークン型（token.Token）や、トークンの位置情報（token.Pos）などを定義しています。

  3. go/scannerパッケージ:

    • Go言語のソースコードをスキャンし、トークンを生成する機能を提供します。
    • 主要な関数はScan()で、これはソースコードから次のトークンを読み取り、その位置、トークンタイプ、およびリテラル文字列を返します。

  4. go/tokenパッケージ:

    • Go言語のトークンに関する定数やユーティリティ関数を提供します。
    • token.Token型は、Go言語のすべてのキーワード、演算子、区切り文字、リテラルなどを列挙したものです。
    • token.Lookup()関数は、与えられた文字列（またはバイトスライス）がGoのキーワードであるかどうかを調べ、対応するトークンタイプを返します。キーワードでなければ識別子（token.IDENT）を返します。

  5. Go言語におけるstringと[]byte:

    • string: Go言語の文字列型は不変（immutable）です。一度作成されると内容を変更できません。文字列は内部的にUTF-8エンコードされたバイト列として表現されます。
    • []byte: バイトスライスは可変（mutable）なバイトのシーケンスです。
    • 変換のコスト: []byteからstringへの変換、またはその逆の変換は、通常、データのコピーを伴います。これは、特に大きなデータや頻繁な変換の場合に、メモリ割り当てとCPUサイクルを消費するオーバーヘッドとなります。パフォーマンスが重要なコンテキストでは、この変換コストを最小限に抑えることが求められます。

  6. ベンチマーク（Benchmarking）:

    • Go言語には、コードのパフォーマンスを測定するための組み込みのベンチマークツールがあります。
    • go test -bench=.コマンドで実行され、特定の操作にかかる時間（ns/op: ナノ秒/操作）やメモリ割り当て（B/op: バイト/操作）などを測定します。
    • このコミットで追加されたBenchmarkScanは、go/scannerのScanメソッドの効率を測定するために使用されます。

これらの知識を持つことで、コミットがなぜ、どのようにしてパフォーマンスを向上させたのかを深く理解することができます。特に、文字列の不必要な生成を避けるという最適化の原則が、このコミットの核心にあります。

技術的詳細

このコミットの技術的詳細は、主にgo/scannerパッケージのScanメソッドのセマンティクス変更と、go/tokenパッケージのLookup関数の引数型変更の2点に集約されます。これらは、Go言語の字句解析における文字列生成のオーバーヘッドを削減し、全体的なスキャン速度を向上させることを目的としています。

1. Scan APIのセマンティクス変更

変更前: Scan()メソッドは、常にトークンのリテラル文字列（lit）を返していました。たとえそれがキーワードや演算子のように、そのトークンタイプ自体が意味を持つ場合でも、対応する文字列が生成されていました。例えば、ifキーワードをスキャンした場合でも、litには"if"という文字列が格納されていました。

変更後: Scan()メソッドは、以下の場合にのみリテラル文字列を返します。

  • リテラル（token.IDENT、token.INT、token.FLOAT、token.IMAG、token.CHAR、token.STRING）
  • コメント（token.COMMENT）
  • セミコロン（token.SEMICOLON）: ソースコードに明示的に存在する場合、または改行やEOFによって挿入された場合（"\n"）。
  • 不正な文字（token.ILLEGAL）: その不正な文字自体がリテラルとして返されます。

上記以外の場合（例: キーワード、演算子、区切り文字など）、Scan()は空のリテラル文字列（""）を返します。これらのトークンの値は、token.Token型自体によって決定されます。

パフォーマンスへの影響: この変更の最大の利点は、不要な文字列生成を大幅に削減できることです。キーワードや演算子など、その種類自体が意味を持つトークンに対しては、対応する文字列をヒープに割り当てる必要がなくなります。これにより、メモリ割り当ての回数が減り、ガベージコレクションの頻度も低下するため、スキャン処理全体の速度が向上します。

コミットメッセージに示されているように、クライアントコードは、リテラル文字列が必要な場合にif lit == "" { lit = tok.String() }というコードスニペットを使用して、トークンタイプから文字列を再構築できます。これは、必要な場合にのみ文字列を生成するという「遅延評価」の原則に基づいています。

2. token.Lookup APIの引数型変更

変更前: token.Lookup関数は、[]byte型の引数を受け取っていました。

func Lookup(ident []byte) Token

変更後: token.Lookup関数は、string型の引数を受け取るように変更されました。

func Lookup(ident string) Token

パフォーマンスへの影響: Go言語では、[]byteからstringへの変換は、通常、新しい文字列をヒープに割り当ててバイトスライスの内容をコピーする操作を伴います。token.Lookupは識別子（変数名、関数名など）がキーワードであるかをチェックするために頻繁に呼び出される可能性があります。変更前は、スキャナーがソースコードから読み取った[]byteをtoken.Lookupに渡す際に、毎回stringへの変換（コピー）が発生していました。

変更後は、token.Lookupが直接stringを受け取るため、スキャナー内部で識別子をstringとして保持し、そのstringを直接Lookupに渡すことで、不要な[]byteからstringへの変換コストを削減できます。これは、特に識別子が多いコードをスキャンする際に顕著なパフォーマンス改善をもたらします。

3. BenchmarkScanの追加

このコミットでは、go/scanner/scanner_test.goにBenchmarkScanという新しいベンチマーク関数が追加されました。これにより、Scanメソッドのパフォーマンスを継続的に測定し、将来の変更がスキャン速度に与える影響を監視できるようになります。コミットメッセージに記載されたベンチマーク結果（17.40%の高速化）は、この新しいベンチマークによって得られたものです。

これらの技術的な変更は、Go言語のコンパイラ基盤におけるマイクロ最適化の典型例であり、小さな変更が積み重なることで全体的なパフォーマンスに大きな影響を与えることを示しています。

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

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

  1. src/pkg/go/scanner/scanner.go:

    • Scan()関数のシグネチャが変更され、lit stringが明示的に返されるようになりました。 
      -func (S *Scanner) Scan() (token.Pos, token.Token, string) {
+func (S *Scanner) Scan() (pos token.Pos, tok token.Token, lit string) {
    • Scan()関数内で、lit変数の初期化と設定ロジックが変更されました。特定のトークンタイプ（リテラル、コメント、セミコロン、不正な文字）の場合にのみlitに値が代入され、それ以外の場合は空文字列のままとなります。
    • scanComment(), scanIdentifier(), scanChar(), scanString(), scanRawString()といったヘルパー関数が、以前は[]byteを返したり、Scan内で[]byteからstringへの変換を行っていた箇所が、直接stringを返すように変更されました。これにより、中間的な[]byteの生成とstringへの変換が削減されます。 
      -func (S *Scanner) scanComment() {
+func (S *Scanner) scanComment() string {
// ...
+	return string(S.src[offs:S.offset])
}

-func (S *Scanner) scanIdentifier() token.Token {
+func (S *Scanner) scanIdentifier() string {
// ...
-	return token.Lookup(S.src[offs:S.offset])
+	return string(S.src[offs:S.offset])
}

-func (S *Scanner) scanNumber(seenDecimalPoint bool) token.Token {
+func (S *Scanner) scanNumber(seenDecimalPoint bool) (token.Token, string) {
// ...
-	return tok
+	return tok, string(S.src[offs:S.offset])
}
    • stripCR関数がscanner.goからtoken.goに移動し、ScanRawString内で使用されるようになりました。

  2. src/pkg/go/token/token.go:

    • Lookup()関数のシグネチャが変更され、[]byte引数からstring引数を受け取るようになりました。 
      -func Lookup(ident []byte) Token {
+func Lookup(ident string) Token {
    • Lookup()関数内の実装も、string(ident)という変換が不要になり、直接identを使用するように変更されました。 
      -	if tok, is_keyword := keywords[string(ident)]; is_keyword {
+	if tok, is_keyword := keywords[ident]; is_keyword {
    • Lookup関数に関するTODOコメントが削除されました。

  3. src/pkg/go/scanner/scanner_test.go:

    • BenchmarkScanという新しいベンチマーク関数が追加されました。
    • TestScan関数内で、新しいScan APIのセマンティクスに合わせて、lit == ""の場合にtok.String()を使用してリテラル文字列を取得するロジックが追加されました。 
      		if lit == "" {
			// no literal value for non-literal tokens
			lit = tok.String()
		}

  4. src/cmd/cgo/gcc.go:

    • token.Lookupの呼び出し箇所が、新しいAPIシグネチャに合わせて[]byte(goid)からgoid（string型）に直接変更されました。これは、token.LookupのAPI変更の消費者側の修正です。 
      -			if token.Lookup([]byte(goid)).IsKeyword() {
+			if token.Lookup(goid).IsKeyword() {

これらの変更は、Go言語の字句解析器の内部動作を根本的に見直し、文字列の不必要なコピーと割り当てを排除することで、パフォーマンスを向上させています。

コアとなるコードの解説

このコミットのコアとなるコードの変更は、Go言語の字句解析器（スキャナー）がトークンを処理し、リテラル文字列を返す方法を根本的に最適化しています。

go/scanner/scanner.go の変更

最も重要な変更は、Scanner.Scan()メソッドとそのヘルパー関数における文字列（string）の扱い方です。

  1. Scan()メソッドのセマンティクス変更: 変更前は、Scan()は常にtoken.Pos, token.Token, stringの3つの値を返していました。このstringは、スキャンされたトークンのリテラル表現でした。しかし、キーワード（例: func, var）や演算子（例: +, -）のように、そのトークンタイプ自体が意味を持つ場合、対応する文字列を毎回生成して返すのは非効率的でした。 変更後は、Scan()はリテラル（識別子、数値、文字列、文字リテラル）、コメント、セミコロン、不正な文字の場合にのみ、対応するリテラル文字列を返します。それ以外のトークン（キーワード、演算子など）では、空文字列""を返します。 これにより、スキャナーは不要な文字列のヒープ割り当てとコピーを避けることができます。例えば、funcというキーワードをスキャンする際に、以前は"func"という文字列が生成されていましたが、変更後はtoken.FUNCというトークンタイプが返され、リテラル文字列は生成されません。

  2. ヘルパー関数の戻り値の変更: scanComment(), scanIdentifier(), scanChar(), scanString(), scanRawString()といった、実際にソースコードからリテラルを読み取る関数群の戻り値が、以前は[]byteを返したり、Scan内で[]byteからstringへの変換を行っていた箇所が、直接stringを返すように変更されました。 例えば、scanIdentifier()は以前token.Tokenを返していましたが、これは内部でtoken.Lookup([]byte)を呼び出していました。変更後はstringを直接返し、Scan()メソッド内でそのstringを使ってtoken.Lookup(string)を呼び出すようになりました。 この変更のポイントは、[]byteからstringへの変換を、本当に必要な場合にのみ、かつ一度だけ行うようにしたことです。Goでは[]byteからstringへの変換はメモリコピーを伴うため、この変換回数を減らすことがパフォーマンス向上に直結します。スキャナーはソースコードのバイトスライスを直接操作し、必要な部分をstringに変換して返すことで、中間的な[]byteの生成とそれに続くstringへの変換という二重のオーバーヘッドを回避しています。

go/token/token.go の変更

  1. Lookup()関数の引数型変更: token.Lookup()関数は、与えられた識別子がGoのキーワードであるかをチェックするために使用されます。以前は[]byte型の引数を受け取っていました。 
    func Lookup(ident []byte) Token
    このため、スキャナーがソースコードから読み取った識別子（[]byte）をLookupに渡すたびに、[]byteからstringへの変換（string(ident)）が内部的に行われていました。 変更後は、string型の引数を受け取るようになりました。 
    func Lookup(ident string) Token
    これにより、Scan()メソッド内で識別子をstringとして取得した後、そのstringを直接Lookupに渡すことができるようになり、不要な[]byteからstringへの変換コストが削減されます。これは、go/scanner側の変更と連携して、全体的な効率を高めています。

これらの変更は、Go言語の字句解析器が、ソースコードのバイト列からトークンを生成する過程で発生するメモリ割り当てとコピーのオーバーヘッドを最小限に抑えるための、非常に効果的な最適化です。特に、頻繁に呼び出されるScanメソッドの内部で、文字列の生成を抑制することで、コンパイル時間の短縮に貢献しています。

関連リンク

参考にした情報源リンク

  • Go言語の公式ドキュメント（go/scannerおよびgo/tokenパッケージ）
  • Go言語の文字列とバイトスライスに関する一般的な知識
  • コンパイラの字句解析に関する一般的な概念
  • Go言語のベンチマークに関する一般的な知識
  • コミットメッセージと差分（diff）の内容