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

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

このコミットは、Go言語の標準ライブラリであるregexpパッケージのベンチマークテストを追加するものです。具体的には、test/bench/go1/regexp_test.goという新しいファイルが追加され、様々な正規表現パターンと入力サイズに対するregexp.Match関数のパフォーマンスを測定するためのベンチマークが定義されています。

コミット

commit d526e5e79ca7182f1e6c88514bfa58c0e70b7d9e
Author: Rob Pike <r@golang.org>
Date:   Tue Mar 12 16:50:10 2013 -0700

    go/test/bench/go1: add regexp test
    
    R=golang-dev, bradfitz
    CC=golang-dev
    https://golang.org/cl/7480047

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

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

元コミット内容

go/test/bench/go1: add regexp test

このコミットは、Go言語のテストスイート内のベンチマークディレクトリ（test/bench/go1）に正規表現のベンチマークテストを追加するものです。

変更の背景

Go言語の正規表現パッケージ（regexp）は、テキスト処理において非常に重要なコンポーネントです。そのパフォーマンスは、Goアプリケーション全体の速度に大きな影響を与える可能性があります。このコミットが作成された2013年当時、Go言語はまだ比較的新しい言語であり、標準ライブラリの最適化と安定化が継続的に行われていました。

正規表現エンジンのパフォーマンスは、使用される正規表現パターン（単純なものから複雑なものまで）、入力文字列の長さ、そしてマッチングの成功/失敗によって大きく変動します。そのため、様々なシナリオにおける正規表現エンジンの挙動を詳細に測定し、潜在的なパフォーマンスボトルネックを特定することは、ライブラリの改善にとって不可欠です。

このコミットは、regexpパッケージのパフォーマンス特性を把握し、将来的な最適化の基準となるデータを提供することを目的として、ベンチマークテストを追加しました。これにより、Go開発者は正規表現エンジンの変更がパフォーマンスに与える影響を定量的に評価できるようになります。

前提知識の解説

Go言語のベンチマークテスト

Go言語には、標準ライブラリのtestingパッケージにベンチマークテストの機能が組み込まれています。これにより、開発者はコードのパフォーマンスを簡単に測定できます。

  • ベンチマーク関数の定義: ベンチマーク関数はBenchmarkXxx(*testing.B)というシグネチャを持ちます。testing.B型はベンチマークのコンテキストを提供します。
  • b.N: ベンチマーク関数内のループはb.N回実行されます。b.Nの値は、ベンチマーク実行時にGoテストフレームワークによって動的に調整され、統計的に有意な結果が得られるように十分な回数が実行されます。
  • b.ResetTimer(): このメソッドは、ベンチマークの計測を開始する前に呼び出されます。これにより、セットアップコードの実行時間が計測に含まれないようにします。
  • b.SetBytes(n int64): このメソッドは、ベンチマークが処理するバイト数を設定します。これにより、結果として「X MB/s」のようなスループットのメトリクスがレポートされます。これは、I/O操作やデータ処理のベンチマークで特に有用です。
  • go test -bench=.: このコマンドを実行することで、現在のディレクトリとそのサブディレクトリにあるすべてのベンチマークテストが実行されます。

Go言語の正規表現パッケージ (regexp)

Go言語の標準ライブラリには、正規表現を扱うためのregexpパッケージが用意されています。

  • regexp.MustCompile(expr string): この関数は、与えられた正規表現文字列をコンパイルし、*regexp.Regexpオブジェクトを返します。コンパイルに失敗した場合はパニック（panic）を引き起こします。これは、正規表現がプログラムの起動時に一度だけコンパイルされ、その後の実行でエラーが発生しないことが保証されている場合に便利です。
  • (*regexp.Regexp).Match(b []byte) bool: このメソッドは、コンパイルされた正規表現が与えられたバイトスライスbにマッチするかどうかをチェックし、結果をブール値で返します。

シード固定の乱数生成

ベンチマークテストにおいて、入力データがランダムに生成される場合、その再現性は非常に重要です。rand.Seed(0)のようにシードを固定することで、ベンチマークを複数回実行しても常に同じ乱数シーケンスが生成され、結果の比較可能性が保証されます。これにより、コードの変更がパフォーマンスに与える影響を正確に評価できます。

技術的詳細

このコミットで追加されたregexp_test.goファイルは、Goのregexpパッケージのパフォーマンスを測定するための包括的なベンチマークスイートを提供します。

  1. makeRegexpText(n int) []byte 関数:

    • この関数は、指定された長さnのバイトスライスを生成します。
    • rand.Seed(0)を呼び出すことで、乱数ジェネレータのシードを固定し、ベンチマークの再現性を保証します。
    • 生成されるテキストは、ランダムなASCII文字（0x20から0x7Eまで）で構成されます。
    • 約30回に1回の割合で改行文字（\n）が挿入されます。これにより、実際のテキストデータに近い、ある程度の構造を持つ入力がシミュレートされます。
    • regexpTextというグローバル変数を使用して、一度生成されたテキストをキャッシュし、同じ長さのテキストが再度要求された場合に再生成を避けることで、ベンチマークのセットアップ時間を短縮しています。

  2. benchmark(b *testing.B, re string, n int) 関数:

    • これは、個々のベンチマーク関数から呼び出されるヘルパー関数です。
    • regexp.MustCompile(re)で正規表現をコンパイルします。
    • makeRegexpText(n)でテスト対象のテキストを生成します。
    • b.ResetTimer()を呼び出して、正規表現のコンパイルとテキスト生成の時間を計測から除外します。
    • b.SetBytes(int64(n))を呼び出して、ベンチマークが処理するバイト数（入力テキストの長さ）を設定します。これにより、結果にスループット（例: MB/s）が表示されます。
    • b.N回ループし、r.Match(t)を呼び出して正規表現のマッチングを実行します。
    • if r.Match(t) { b.Fatal("match!") }という条件は、これらのベンチマークが「マッチしない」シナリオをテストしていることを示唆しています。正規表現が意図せずマッチした場合、ベンチマークは失敗します。これは、正規表現エンジンがマッチしないケースでどれだけ効率的に動作するかを測定するためによく行われる手法です。

  3. 正規表現定数:

    • easy0, easy1, medium, hardという4つの異なる複雑さの正規表現パターンが定義されています。
      • easy0 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ$": 非常に単純なリテラル文字列と行末アンカー。
      • easy1 = "A[AB]B[BC]C[CD]D[DE]E[EF]F[FG]G[GH]H[HI]I[IJ]J$": 文字クラスを含むが、比較的単純なパターン。
      • medium = "[XYZ]ABCDEFGHIJKLMNOPQRSTUVWXYZ$": 先頭に文字クラスを持つパターン。
      • hard = "[ -~]*ABCDEFGHIJKLMNOPQRSTUVWXYZ$": 任意の文字（スペースからチルダまで）の0回以上の繰り返しと、その後に続くリテラル文字列。これは、バックトラッキングが多く発生する可能性があり、正規表現エンジンにとって「ハード」なケースとなりやすいパターンです。

  4. 個々のベンチマーク関数:

    • BenchmarkRegexpMatchEasy0_32, BenchmarkRegexpMatchEasy0_1Kなどの関数が定義されています。
    • これらの関数は、benchmarkヘルパー関数を呼び出し、異なる正規表現パターンと入力テキストの長さ（32バイトと1KB）を組み合わせてテストします。
    • 32<<0は32バイト、1<<10は1024バイト（1KB）を意味します。

これらのベンチマークは、Goの正規表現エンジンが様々な複雑さのパターンと異なる入力サイズに対してどのようにスケールするかを評価するための堅牢なフレームワークを提供します。特に「ハード」なパターンは、エンジンのバックトラッキング性能や最適化の有効性を試すのに役立ちます。

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

このコミットでは、以下の新しいファイルが追加されています。

test/bench/go1/regexp_test.go

このファイルには、Goのregexpパッケージのベンチマークテストを定義するGoのソースコードが含まれています。

コアとなるコードの解説

追加されたregexp_test.goファイルは、Goのベンチマークテストの慣例に従って記述されています。

// Copyright 2013 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package go1

import (
	"math/rand"
	"regexp"
	"testing"
)

// benchmark based on regexp/exec_test.go

var regexpText []byte

func makeRegexpText(n int) []byte {
	rand.Seed(0) // For reproducibility.
	if len(regexpText) >= n {
		return regexpText[:n]
	}
	regexpText = make([]byte, n)
	for i := range regexpText {
		if rand.Intn(30) == 0 {
			regexpText[i] = '\n'
		} else {
			regexpText[i] = byte(rand.Intn(0x7E+1-0x20) + 0x20)
		}
	}
	return regexpText
}

func benchmark(b *testing.B, re string, n int) {
	r := regexp.MustCompile(re)
	t := makeRegexpText(n)
	b.ResetTimer()
	b.SetBytes(int64(n))
	for i := 0; i < b.N; i++ {
		if r.Match(t) {
			b.Fatal("match!")
		}
	}
}

const (
	easy0  = "ABCDEFGHIJKLMNOPQRSTUVWXYZ$"
	easy1  = "A[AB]B[BC]C[CD]D[DE]E[EF]F[FG]G[GH]H[HI]I[IJ]J$"
	medium = "[XYZ]ABCDEFGHIJKLMNOPQRSTUVWXYZ$"
	hard   = "[ -~]*ABCDEFGHIJKLMNOPQRSTUVWXYZ$"
)

func BenchmarkRegexpMatchEasy0_32(b *testing.B)  { benchmark(b, easy0, 32<<0) }
func BenchmarkRegexpMatchEasy0_1K(b *testing.B)  { benchmark(b, easy0, 1<<10) }
func BenchmarkRegexpMatchEasy1_32(b *testing.B)  { benchmark(b, easy1, 32<<0) }
func BenchmarkRegexpMatchEasy1_1K(b *testing.B)  { benchmark(b, easy1, 1<<10) }
func BenchmarkRegexpMatchMedium_32(b *testing.B) { benchmark(b, medium, 1<<0) }
func BenchmarkRegexpMatchMedium_1K(b *testing.B) { benchmark(b, medium, 1<<10) }
func BenchmarkRegexpMatchHard_32(b *testing.B)   { benchmark(b, hard, 32<<0) }
func BenchmarkRegexpMatchHard_1K(b *testing.B)   { benchmark(b, hard, 1<<10) }
  • パッケージ宣言とインポート: package go1と宣言されており、math/rand（乱数生成）、regexp（正規表現）、testing（テストとベンチマークフレームワーク）がインポートされています。
  • makeRegexpText: ベンチマークの入力となるランダムなテキストを生成します。シード固定により再現性を確保し、改行文字を適度に含めることで現実的なテキストを模倣しています。
  • benchmark: 実際の正規表現マッチングのベンチマークロジックをカプセル化するヘルパー関数です。正規表現のコンパイル、テキスト生成、タイマーのリセット、処理バイト数の設定、そしてb.N回にわたるMatchメソッドの呼び出しを行います。b.Fatal("match!")は、このベンチマークが「マッチしない」ケースのパフォーマンスを測定していることを示します。
  • 正規表現定数: easy0からhardまでの4つの異なる複雑さの正規表現パターンが定義されており、これらがベンチマークの対象となります。
  • BenchmarkRegexpMatch*関数群: これらがGoのテストツールによって自動的に発見・実行される個々のベンチマークテストです。それぞれがbenchmarkヘルパー関数を呼び出し、特定の正規表現パターンと入力テキストの長さ（32バイトまたは1KB）を組み合わせてテストを実行します。これにより、様々なシナリオでのregexp.Matchのパフォーマンスが測定されます。

このコードは、Goのベンチマークテストのベストプラクティスに従っており、正規表現エンジンのパフォーマンス特性を詳細に分析するための堅牢な基盤を提供します。

関連リンク

参考にした情報源リンク

  • Go言語の公式ドキュメント
  • Go言語のベンチマークに関する一般的な情報源
  • 正規表現のパフォーマンスに関する一般的な知識