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

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

このコミットは、Go言語の正規表現エンジンであるregexp/syntaxパッケージ内のEmptyOpContext関数のパフォーマンス最適化に関するものです。この最適化は、CPUプロファイルでこの関数が数パーセントのCPU時間を消費していることが発見されたことに端を発しています。変更により、EmptyOpContextのベンチマークで約11.92%の改善が見られ、全体の正規表現ベンチマークにも0〜3%の改善をもたらすとされています。

コミット

commit 90351506d47dad652d9ee8cea56ffb5c50e0e953
Author: Brad Fitzpatrick <bradfitz@golang.org>
Date:   Thu Aug 29 14:31:10 2013 -0700

    regexp/syntax: optimize EmptyOpContext
    
    Minor. Saw this in a profile at few percent of CPU and was
    curious what it was. Improves overall regexp benchmarks
    anywhere from 0 to 3%, but they're a pain to run. You need to
    run them in isolation for long runs to get stable numbers.
    
    benchmark                  old ns/op    new ns/op    delta
    BenchmarkEmptyOpContext          537          473  -11.92%
    
    R=golang-dev, crawshaw
    CC=golang-dev
    https://golang.org/cl/13407043

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

https://github.com/golang/go/commit/90351506d47dad652d9ee8cea56ffb5c50e0e953

元コミット内容

regexp/syntax: optimize EmptyOpContext

Minor. Saw this in a profile at few percent of CPU and was
curious what it was. Improves overall regexp benchmarks
anywhere from 0 to 3%, but they're a pain to run. You need to
run them in isolation for long runs to get stable numbers.

benchmark                  old ns/op    new ns/op    delta
BenchmarkEmptyOpContext          537          473  -11.92%

R=golang-dev, crawshaw
CC=golang-dev
https://golang.org/cl/13407043

変更の背景

このコミットの背景には、Go言語の正規表現エンジンにおけるパフォーマンスのボトルネックの特定と解消があります。コミットメッセージによると、開発者がCPUプロファイルを実行した際に、regexp/syntaxパッケージ内のEmptyOpContext関数がCPU時間の数パーセントを消費していることを発見しました。これは、正規表現の実行においてこの関数が頻繁に呼び出され、その効率が全体のパフォーマンスに影響を与えていることを示唆しています。

EmptyOpContextは、正規表現における「ゼロ幅アサーション」（例えば、行頭、行末、単語境界など、文字を消費せずに位置の条件を評価する要素）の評価に重要な役割を果たします。この関数の最適化は、正規表現の全体的な実行速度を向上させることを目的としています。ベンチマーク結果が示すように、EmptyOpContext自体の実行時間は約12%短縮され、これにより正規表現全体のベンチマークもわずかながら改善されることが期待されました。

前提知識の解説

Go言語のregexpパッケージとregexp/syntax

Go言語の標準ライブラリには、正規表現を扱うためのregexpパッケージが提供されています。このパッケージは、Googleが開発したRE2エンジンに基づいており、その最大の特徴は「線形時間複雑度」を保証することです。これは、入力文字列の長さに比例してマッチング時間が決まることを意味し、他の多くの正規表現エンジンで問題となる「壊滅的バックトラッキング」（特定のパターンと入力の組み合わせで指数関数的に時間がかかる現象）を防ぎます。

regexp/syntaxパッケージは、regexpパッケージの内部で利用されるサブパッケージであり、正規表現の構文解析（パース）とコンパイルを担当します。正規表現文字列を抽象構文木（AST）に変換し、さらにそれを実行可能なバイトコードや状態機械にコンパイルするプロセスを管理します。

ゼロ幅アサーション（Zero-width Assertions）

正規表現には、特定の「位置」に条件を課す特殊な要素があります。これらは「ゼロ幅アサーション」と呼ばれ、入力文字列の文字を消費することなく、マッチングが行われる位置に関する条件を評価します。主なゼロ幅アサーションには以下のようなものがあります。

  • ^: 行の先頭、または文字列の先頭
  • $: 行の末尾、または文字列の末尾
  • \b: 単語境界（word boundary）
  • \B: 非単語境界（non-word boundary）
  • \A: 文字列の絶対的な先頭
  • \z: 文字列の絶対的な末尾

これらのアサーションは、例えば「単語の先頭にあるa」や「行末にある.」といった、文字そのものではなく、その文字が現れる「文脈」を定義するために使用されます。

EmptyOpとEmptyOpContext

regexp/syntaxパッケージにおいて、EmptyOpはゼロ幅アサーションの状態を表すビットマスク型の型です。例えば、EmptyBeginText、EmptyEndText、EmptyBeginLine、EmptyEndLine、EmptyWordBoundary、EmptyNoWordBoundaryといった定数が定義されており、これらをビットOR演算子（|）で組み合わせることで、複数のアサーションが同時に真である状態を表現します。

EmptyOpContext関数は、正規表現のマッチング中に、特定の「位置」におけるゼロ幅アサーションの真偽を評価するために使用されます。この関数は、その位置の直前の文字（r1）と直後の文字（r2）を引数として受け取ります。r1が-1の場合はテキストの先頭、r2が-1の場合はテキストの末尾を示します。EmptyOpContextは、これらの文字の組み合わせに基づいて、どのEmptyOpフラグが立つべきかを計算し、その結果をEmptyOp型の値として返します。

特に、単語境界（\b）や非単語境界（\B）の判定には、IsWordChar関数が用いられます。この関数は、与えられたルーン（Unicodeコードポイント）が「単語を構成する文字」（英数字やアンダースコアなど）であるかどうかを判定します。単語境界は、r1とr2のどちらか一方が単語文字で、もう一方が非単語文字である場合に成立します。

技術的詳細

このコミットの技術的詳細は、EmptyOpContext関数の内部ロジックの変更にあります。変更前は、複数のif文とIsWordChar関数の呼び出しを組み合わせてEmptyOpを構築していました。変更後は、switch文とboundaryというバイト型の変数、そしてビット演算をより効率的に利用することで、同じロジックをより高速に実行するように改善されています。

変更前のコードは、r1とr2それぞれに対して、テキストの境界、行の境界、そして単語文字であるかどうかのチェックを独立したif文で行っていました。特に単語境界の判定は、IsWordChar(r1) != IsWordChar(r2)という比較と、その結果に応じたEmptyWordBoundaryまたはEmptyNoWordBoundaryのビットOR演算で行われていました。

変更後のコードでは、まずop変数をEmptyNoWordBoundaryで初期化し、boundaryという新しい変数を導入しています。 r1とr2のそれぞれについて、switch文を使って以下の条件を評価します。

  1. IsWordChar(r): その文字が単語文字である場合、boundary変数を操作します。
    • r1が単語文字の場合、boundaryを1に設定します。
    • r2が単語文字の場合、boundaryをboundary ^ 1（XOR演算）します。これにより、r1とr2のIsWordCharの結果が異なる場合にのみboundaryが1になります。
  2. r == '\n': 改行文字である場合、EmptyBeginLineまたはEmptyEndLineをopにビットORします。
  3. r < 0: テキストの境界（-1）である場合、EmptyBeginText | EmptyBeginLineまたはEmptyEndText | EmptyEndLineをopにビットORします。

最後に、if boundary != 0（つまり、IsWordChar(r1)とIsWordChar(r2)の結果が異なる場合）に、op ^= (EmptyWordBoundary | EmptyNoWordBoundary)というビットXOR演算を行います。これは、EmptyWordBoundaryとEmptyNoWordBoundaryの両方のビットを反転させることで、EmptyNoWordBoundaryが設定されていればEmptyWordBoundaryに、EmptyWordBoundaryが設定されていればEmptyNoWordBoundaryに切り替える効果があります。初期値がEmptyNoWordBoundaryであるため、このXOR演算は、単語境界が存在する場合にEmptyNoWordBoundaryを解除し、EmptyWordBoundaryを設定する役割を果たします。

この変更により、条件分岐の構造が整理され、特に単語境界の判定ロジックがより効率的なビット演算に置き換えられたことで、パフォーマンスが向上したと考えられます。

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

src/pkg/regexp/syntax/prog.go の EmptyOpContext 関数が変更されました。

--- a/src/pkg/regexp/syntax/prog.go
+++ b/src/pkg/regexp/syntax/prog.go
@@ -56,23 +56,26 @@ const (
 // Passing r2 == -1 indicates that the position is
 // at the end of the text.
 func EmptyOpContext(r1, r2 rune) EmptyOp {
-\tvar op EmptyOp
-\tif r1 < 0 {\n-\t\top |= EmptyBeginText | EmptyBeginLine
-\t}\n-\tif r1 == \'\\n\' {\n+\tvar op EmptyOp = EmptyNoWordBoundary
+\tvar boundary byte
+\tswitch {\n+\tcase IsWordChar(r1):\n+\t\tboundary = 1
+\tcase r1 == \'\\n\':\n \t\top |= EmptyBeginLine
+\tcase r1 < 0:\n+\t\top |= EmptyBeginText | EmptyBeginLine
 \t}\n-\tif r2 < 0 {\n-\t\top |= EmptyEndText | EmptyEndLine
-\t}\n-\tif r2 == \'\\n\' {\n+\tswitch {\n+\tcase IsWordChar(r2):\n+\t\tboundary ^= 1
+\tcase r2 == \'\\n\':\n \t\top |= EmptyEndLine
+\tcase r2 < 0:\n+\t\top |= EmptyEndText | EmptyEndLine
 \t}\n-\tif IsWordChar(r1) != IsWordChar(r2) {\n-\t\top |= EmptyWordBoundary
-\t} else {\n-\t\top |= EmptyNoWordBoundary
+\tif boundary != 0 { // IsWordChar(r1) != IsWordChar(r2)
+\t\top ^= (EmptyWordBoundary | EmptyNoWordBoundary)
 \t}\n \treturn op
 }

また、src/pkg/regexp/syntax/prog_test.go に BenchmarkEmptyOpContext が追加されました。

--- a/src/pkg/regexp/syntax/prog_test.go
+++ b/src/pkg/regexp/syntax/prog_test.go
@@ -103,3 +103,14 @@ func TestCompile(t *testing.T) {\n \t\t}\n \t}\n }\n+\n+func BenchmarkEmptyOpContext(b *testing.B) {\n+\tfor i := 0; i < b.N; i++ {\n+\t\tvar r1 rune = -1\n+\t\tfor _, r2 := range \"foo, bar, baz\\nsome input text.\\n\" {\n+\t\t\tEmptyOpContext(r1, r2)\n+\t\t\tr1 = r2\n+\t\t}\n+\t\tEmptyOpContext(r1, -1)\n+\t}\n+}

コアとなるコードの解説

変更されたEmptyOpContext関数は、主に単語境界の判定ロジックを改善しています。

変更前:

変更前のコードでは、op変数を初期化せずに、複数のif文で条件をチェックし、該当するEmptyOpフラグをビットORで追加していました。特に単語境界の判定は以下のようになっていました。

if IsWordChar(r1) != IsWordChar(r2) {
	op |= EmptyWordBoundary
} else {
	op |= EmptyNoWordBoundary
}

これは、IsWordChar(r1)とIsWordChar(r2)の結果が異なる場合にEmptyWordBoundaryを設定し、そうでない場合にEmptyNoWordBoundaryを設定するという、排他的な条件分岐でした。

変更後:

変更後のコードでは、以下の点が異なります。

  1. opの初期化: var op EmptyOp = EmptyNoWordBoundary

    • op変数をEmptyNoWordBoundaryで初期化しています。これは、デフォルトでは単語境界ではないと仮定し、後で単語境界であると判明した場合にこのフラグを反転させるというアプローチを取るためです。

  2. boundary変数の導入: var boundary byte

    • boundaryというバイト型の変数を導入し、単語文字の判定結果を一時的に保持します。

  3. switch文による条件分岐の整理:

    • r1とr2それぞれに対してswitch文を使用し、条件分岐をより構造化しています。
    • case IsWordChar(r1): boundary = 1
      • r1が単語文字の場合、boundaryを1に設定します。
    • case IsWordChar(r2): boundary ^= 1
      • r2が単語文字の場合、boundaryをboundaryと1のXOR（排他的論理和）で更新します。
      • このXOR演算がポイントです。
        • もしr1が単語文字でr2も単語文字なら: boundaryは1 ^ 1 = 0
        • もしr1が単語文字でr2が非単語文字なら: boundaryは1 ^ 0 = 1
        • もしr1が非単語文字でr2が単語文字なら: boundaryは0 ^ 1 = 1
        • もしr1が非単語文字でr2も非単語文字なら: boundaryは0 ^ 0 = 0
      • 結果として、boundaryが1になるのは、IsWordChar(r1)とIsWordChar(r2)の結果が異なる場合（つまり単語境界が存在する場合）のみです。

  4. 単語境界の最終判定: if boundary != 0 { op ^= (EmptyWordBoundary | EmptyNoWordBoundary) }

    • boundaryが0でない（つまり単語境界が存在する）場合、opに対してEmptyWordBoundary | EmptyNoWordBoundaryのビットXOR演算を行います。
    • EmptyWordBoundaryとEmptyNoWordBoundaryは互いに排他的なフラグであり、ビットマスクとしては00010000と00100000のような形になります（実際の値は異なる可能性がありますが、重要なのは互いに異なるビット位置にあること）。
    • opがEmptyNoWordBoundaryで初期化されているため、このXOR演算はEmptyNoWordBoundaryを解除し、代わりにEmptyWordBoundaryを設定する効果があります。例えば、opがX | EmptyNoWordBoundaryだった場合、op ^ (EmptyWordBoundary | EmptyNoWordBoundary)はX | EmptyWordBoundaryになります。

この変更により、単語境界の判定ロジックがより簡潔になり、特にIsWordCharの呼び出し結果をboundary変数で効率的に管理し、最終的なEmptyOpの構築にビットXOR演算を用いることで、パフォーマンスが向上したと考えられます。

追加されたBenchmarkEmptyOpContextは、EmptyOpContext関数のパフォーマンスを測定するためのベンチマークテストです。これにより、変更が実際に性能向上に寄与したことを数値的に確認できます。

関連リンク

参考にした情報源リンク