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

このコミットは、Go言語の標準ライブラリstringsパッケージにおいて、単一文字列の置換処理を高速化するための改善を導入しています。具体的には、Boyer-Moore文字列検索アルゴリズムを基盤とした新しいstringFinder型を導入し、strings.Replacerが単一の置換パターンを持つ場合にこの高速な検索ロジックを利用するように変更しています。これにより、特定のベンチマークにおいて最大で約50倍の速度向上が見られます。

コミット

commit 631a0e71c1eb1e85c3e745153a6575a82189ef3e
Author: Eric Roshan-Eisner <eric.d.eisner@gmail.com>
Date:   Fri Sep 28 12:34:18 2012 +1000

    strings: implement a faster single-string Replacer
    
    The string searching is implemented separately so other functions
    may make use of it in the future.
    
    benchmark                        old ns/op    new ns/op    delta
    BenchmarkSingleMaxSkipping          125889         2474  -98.03%
    BenchmarkSingleLongSuffixFail        16252         1996  -87.72%
    BenchmarkSingleMatch                260793       136266  -47.75%
    
    benchmark                         old MB/s     new MB/s  speedup
    BenchmarkSingleMaxSkipping           79.43      4041.57   50.88x
    BenchmarkSingleLongSuffixFail        61.65       501.81    8.14x
    BenchmarkSingleMatch                 57.52       110.08    1.91x
    
    R=nigeltao
    CC=golang-dev
    https://golang.org/cl/6545049

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

https://github.com/golang/go/commit/631a0e71c1eb1e85c3e745153a6575a82189ef3e

元コミット内容

strings: implement a faster single-string Replacer

The string searching is implemented separately so other functions
may make use of it in the future.

benchmark                        old ns/op    new ns/op    delta
BenchmarkSingleMaxSkipping          125889         2474  -98.03%
BenchmarkSingleLongSuffixFail        16252         1996  -87.72%
BenchmarkSingleMatch                260793       136266  -47.75%

benchmark                         old MB/s     new MB/s  speedup
BenchmarkSingleMaxSkipping           79.43      4041.57   50.88x
BenchmarkSingleLongSuffixFail        61.65       501.81    8.14x
BenchmarkSingleMatch                 57.52       110.08    1.91x

R=nigeltao
CC=golang-dev
https://golang.org/cl/6545049

変更の背景

Go言語のstringsパッケージには、文字列の置換を行うReplacer型が存在します。このReplacerは、複数の置換ルールを効率的に適用するために設計されていますが、単一の置換ルール（特に置換対象文字列が1バイトより長い場合）の場合でも、より汎用的なアルゴリズムが使用されていました。

文字列検索は、テキスト処理において非常に頻繁に行われる操作であり、その性能はアプリケーション全体のパフォーマンスに大きく影響します。特に、大規模なテキストデータに対して繰り返し置換操作を行う場合、検索アルゴリズムの効率がボトルネックとなることがあります。

このコミットの背景には、単一文字列の検索・置換において、より高速なアルゴリズムを導入することで、strings.Replacerの性能を向上させるという明確な目的がありました。コミットメッセージに記載されているベンチマーク結果が示すように、既存の実装には大幅な改善の余地があったことが伺えます。特にBenchmarkSingleMaxSkippingのような、パターンがテキスト中にほとんど出現しない、またはスキップが頻繁に発生するケースで顕著な性能向上が期待されました。

また、文字列検索ロジックをReplacerから分離し、独立したstringFinderとして実装することで、将来的に他のstringsパッケージ内の関数や、Go言語の他の部分でこの高速な検索機能を利用できるようにするという、再利用性の向上も意図されています。

前提知識の解説

Boyer-Moore文字列検索アルゴリズム

Boyer-Mooreアルゴリズムは、1977年にRobert S. BoyerとJ Strother Mooreによって考案された効率的な文字列検索アルゴリズムです。このアルゴリズムは、一般的にテキストの長さが長くなるほど、また検索パターンが長くなるほど、その効率性が際立ちます。

従来のナイーブな文字列検索アルゴリズムがテキストの先頭から1文字ずつパターンと比較していくのに対し、Boyer-Mooreアルゴリズムは以下の2つのヒューリスティック（経験則）を利用して、比較をスキップする量を最大化します。

悪い文字ルール (Bad Character Rule):
- パターンをテキスト上で右から左へ比較していきます。
- 不一致が発生した場合、テキスト中の不一致文字がパターン中にどこにあるかを調べます。
- もし不一致文字がパターン中に存在しない場合、パターン全体を不一致文字の次まで安全にシフトできます。
- もし不一致文字がパターン中に存在する場合、パターン中のその文字の最も右の出現位置が、テキスト中の不一致文字と一致するようにパターンをシフトします。
- これにより、不一致文字に基づいて、パターンを大きくスキップできる可能性があります。
良い接尾辞ルール (Good Suffix Rule):
- パターンをテキスト上で右から左へ比較し、パターンの一部（接尾辞）が一致したが、その前の文字で不一致が発生した場合に適用されます。
- 一致した接尾辞がパターン内の他の場所で出現するかどうかを調べます。
- もし出現する場合、その出現位置がテキスト中の現在の位置と一致するようにパターンをシフトします。
- もし出現しない場合、一致した接尾辞のプレフィックス（接頭辞）がパターン全体のプレフィックスと一致するかどうかを調べ、その一致に基づいてパターンをシフトします。
- このルールは、パターンの一部が一致したという情報に基づいて、より大きなシフトを可能にします。

Boyer-Mooreアルゴリズムは、これらのルールを組み合わせて、より大きなシフト量を計算し、その最大値だけパターンをシフトします。これにより、テキスト中の多くの文字を比較することなくスキップできるため、平均的には非常に高速な検索を実現します。最悪計算量はO(mn)（mはパターン長、nはテキスト長）ですが、平均的にはO(n/m)に近い性能を発揮します。

Go言語の`strings`パッケージ

Go言語の標準ライブラリstringsパッケージは、UTF-8でエンコードされた文字列を操作するための基本的な機能を提供します。これには、文字列の結合、分割、検索、置換、大文字・小文字変換などが含まれます。

strings.Replacer: 複数のoldとnewのペアを指定して、文字列内の部分文字列を一括で置換するための型です。NewReplacer関数で作成され、Replaceメソッドで置換を実行します。内部的には、置換ルールの数や置換対象文字列の特性に応じて、異なる最適化されたアルゴリズム（例: 単一バイト置換、複数バイト置換、汎用的なAho-Corasickアルゴリズムなど）を使い分けています。

技術的詳細

このコミットの技術的な核心は、Boyer-MooreアルゴリズムをGo言語で実装し、それをstrings.Replacerの単一文字列置換ケースに統合した点にあります。

`stringFinder`構造体

新しく導入されたstringFinder構造体は、Boyer-Mooreアルゴリズムの実装をカプセル化しています。

type stringFinder struct {
	// pattern is the string that we are searching for in the text.
	pattern string

	// badCharSkip[b] contains the distance between the last byte of pattern
	// and the rightmost occurrence of b in pattern. If b is not in pattern,
	// badCharSkip[b] is len(pattern).
	badCharSkip [256]int

	// goodSuffixSkip[i] defines how far we can shift the matching frame given
	// that the suffix pattern[i+1:] matches, but the byte pattern[i] does
	// not.
	goodSuffixSkip []int
}

pattern: 検索対象のパターン文字列。
badCharSkip: 悪い文字ルールを実装するためのテーブル。256要素の配列で、各バイト値bに対して、パターン中のbの最も右の出現位置からパターンの末尾までの距離を格納します。パターン中にbが存在しない場合は、パターン長が格納されます。
goodSuffixSkip: 良い接尾辞ルールを実装するためのテーブル。パターン長と同じサイズの[]intスライスで、各インデックスiに対して、pattern[i+1:]が一致した場合のシフト量を格納します。

`makeStringFinder`関数

makeStringFinder関数は、与えられたパターン文字列に基づいてstringFinderのインスタンスを初期化します。この関数内で、badCharSkipテーブルとgoodSuffixSkipテーブルが構築されます。

badCharSkipテーブルの構築:
- まず、すべてのエントリをパターン長で初期化します。これは、パターン中に存在しない文字が見つかった場合に、パターン全体をスキップできることを意味します。
- 次に、パターンの各文字について、その文字がパターンの末尾からどれだけ離れているかを計算し、badCharSkipテーブルに格納します。これにより、不一致文字が見つかった際に、その文字がパターン中に存在する場合の適切なシフト量が決定されます。
goodSuffixSkipテーブルの構築:
- このテーブルの構築は2つのパスで行われます。
- 第一パス: パターンの各接尾辞について、その接尾辞がパターンのプレフィックスとして出現する場合のシフト量を計算します。
- 第二パス: パターンの各接尾辞について、その接尾辞がパターン内の他の場所で出現する場合のシフト量を計算します。これにより、より複雑なケースでの最適なシフト量が決定されます。longestCommonSuffixヘルパー関数が使用され、2つの文字列の最長共通接尾辞の長さを計算します。

`stringFinder.next`メソッド

stringFinder.next(text string) intメソッドは、Boyer-Mooreアルゴリズムの実際の検索ロジックを実装しています。

テキストの末尾からパターン長分だけ戻った位置から比較を開始します。
パターンとテキストを右から左へ1文字ずつ比較していきます。
一致する限り、比較位置を左へ移動します。
もしパターン全体が一致した場合（j < 0）、マッチした位置（i + 1）を返します。
不一致が発生した場合、badCharSkipテーブルとgoodSuffixSkipテーブルから計算されたシフト量の最大値だけ、検索位置iを右にシフトします。
検索位置がテキストの長さを超えた場合、パターンが見つからなかったとして-1を返します。

`singleStringReplacer`型

strings.Replacerが単一の置換パターンを持つ場合に、この高速なstringFinderを利用するための新しい内部型singleStringReplacerが導入されました。

type singleStringReplacer struct {
	finder *stringFinder
	value string // value is the new string that replaces that pattern when it's found.
}

finder: 実際の文字列検索を行うstringFinderのインスタンス。
value: 置換後の文字列。

NewReplacer関数内で、len(oldnew) == 2 && len(oldnew[0]) > 1（つまり、単一の置換ルールで、置換対象文字列が1バイトより長い場合）という条件が満たされた場合に、このsingleStringReplacerが使用されるように変更されました。

singleStringReplacerのReplaceメソッドとWriteStringメソッドは、内部でr.finder.next(s[i:])を呼び出してパターンを検索し、見つかった場合は置換後の文字列をバッファに追加またはio.Writerに書き込むというロジックで実装されています。

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

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

src/pkg/strings/export_test.go:
- テスト目的で、内部のstringFinderを外部から利用できるようにStringFind関数とDumpTables関数が追加されました。これにより、Boyer-Mooreアルゴリズムの内部状態（badCharSkipとgoodSuffixSkipテーブル）をテストから検証できるようになります。
src/pkg/strings/replace.go:
- NewReplacer関数に、単一文字列置換の最適化ロジックが追加されました。oldnew引数が2つ（つまり1つの置換ペア）で、かつ置換対象文字列の長さが1より大きい場合に、新しく導入されたsingleStringReplacerを使用するように分岐が追加されています。
- stringWriterIfaceインターフェースとgetStringWriterヘルパー関数が導入され、io.WriterがWriteStringメソッドを持つ場合にそれを利用し、そうでない場合はstringWriterラッパーを使用するようにリファクタリングされました。これは、WriteStringの呼び出しをより効率的に行うための変更です。
- singleStringReplacer型とそのコンストラクタmakeSingleStringReplacer、そしてReplaceメソッドとWriteStringメソッドが追加されました。これが、Boyer-Mooreアルゴリズムを利用した高速な単一文字列置換の主要な実装です。
src/pkg/strings/replace_test.go:
- TestReplacerにsingle string replacerのテストケースが追加され、新しい最適化が正しく機能することを確認しています。
- TestPickAlgorithmのテストケースが更新され、NewReplacer("12", "123")のようなケースで*strings.singleStringReplacerが選択されることを検証しています。
- benchmarkSingleString, BenchmarkSingleMaxSkipping, BenchmarkSingleLongSuffixFail, BenchmarkSingleMatchといった新しいベンチマーク関数が追加されました。これらは、単一文字列置換の性能を測定し、コミットメッセージに記載されている性能向上を実証するためのものです。
src/pkg/strings/search.go:
- 新規ファイルとして追加されました。 このファイルには、Boyer-Moore文字列検索アルゴリズムのGo言語実装であるstringFinder型、そのコンストラクタmakeStringFinder、そして検索を実行するnextメソッドが含まれています。また、longestCommonSuffixやmaxといったヘルパー関数も定義されています。このファイルは、文字列検索ロジックをstringsパッケージの他の部分から独立させる役割を担っています。
src/pkg/strings/search_test.go:
- 新規ファイルとして追加されました。 このファイルには、stringFinderの機能と正確性を検証するためのテストが含まれています。TestFinderNextは様々なパターンとテキストの組み合わせで検索結果を検証し、TestFinderCreationはbadCharSkipとgoodSuffixSkipテーブルが正しく構築されることを検証しています。

コアとなるコードの解説

`src/pkg/strings/search.go` (新規ファイル)

このファイルは、Boyer-Mooreアルゴリズムの独立した実装を提供します。

// stringFinder efficiently finds strings in a source text. It's implemented
// using the Boyer-Moore string search algorithm:
// http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
// http://www.cs.utexas.edu/~moore/publications/fstrpos.pdf (note: this aged
// document uses 1-based indexing)
type stringFinder struct {
	pattern        string
	badCharSkip    [256]int
	goodSuffixSkip []int
}

func makeStringFinder(pattern string) *stringFinder {
	f := &stringFinder{
		pattern:        pattern,
		goodSuffixSkip: make([]int, len(pattern)),
	}
	last := len(pattern) - 1

	// Build bad character table.
	for i := range f.badCharSkip {
		f.badCharSkip[i] = len(pattern) // Default skip is pattern length
	}
	for i := 0; i < last; i++ {
		f.badCharSkip[pattern[i]] = last - i // Distance from last char of pattern
	}

	// Build good suffix table.
	lastPrefix := last
	for i := last; i >= 0; i-- {
		if HasPrefix(pattern, pattern[i+1:]) { // Check if suffix is also a prefix of pattern
			lastPrefix = i + 1
		}
		f.goodSuffixSkip[i] = lastPrefix + last - i
	}
	for i := 0; i < last; i++ {
		lenSuffix := longestCommonSuffix(pattern, pattern[1:i+1])
		if pattern[i-lenSuffix] != pattern[last-lenSuffix] {
			f.goodSuffixSkip[last-lenSuffix] = lenSuffix + last - i
		}
	}
	return f
}

func (f *stringFinder) next(text string) int {
	i := len(f.pattern) - 1 // Start comparison from the end of the pattern
	for i < len(text) {
		j := len(f.pattern) - 1 // Index for pattern
		for j >= 0 && text[i] == f.pattern[j] { // Compare backwards
			i--
			j--
		}
		if j < 0 {
			return i + 1 // Match found
		}
		// Shift based on max of bad character and good suffix rules
		i += max(f.badCharSkip[text[i]], f.goodSuffixSkip[j])
	}
	return -1 // No match
}

makeStringFinderは、Boyer-Mooreアルゴリズムのプリプロセスステップを実行し、badCharSkipとgoodSuffixSkipテーブルを構築します。これらのテーブルは、検索時にパターンをどれだけスキップできるかを決定するために使用されます。
nextメソッドは、実際の検索ループです。テキストを右から左へ比較し、不一致が発生した場合は、事前に計算されたスキップテーブルに基づいて検索位置を効率的に進めます。

`src/pkg/strings/replace.go`

このファイルでは、strings.Replacerが単一文字列置換のケースでstringFinderを利用するように変更されています。

func NewReplacer(oldnew ...string) *Replacer {
	// ... (既存のバリデーションとロジック)

	if len(oldnew) == 2 && len(oldnew[0]) > 1 {
		return &Replacer{r: makeSingleStringReplacer(oldnew[0], oldnew[1])}
	}

	// ... (既存のReplacer選択ロジック)
}

type singleStringReplacer struct {
	finder *stringFinder
	value string
}

func makeSingleStringReplacer(pattern string, value string) *singleStringReplacer {
	return &singleStringReplacer{finder: makeStringFinder(pattern), value: value}
}

func (r *singleStringReplacer) Replace(s string) string {
	var buf []byte
	i := 0
	for {
		match := r.finder.next(s[i:]) // Use stringFinder to find the next match
		if match == -1 {
			break
		}
		buf = append(buf, s[i:i+match]...) // Append text before match
		buf = append(buf, r.value...)      // Append replacement
		i += match + len(r.finder.pattern) // Advance index past replaced part
	}
	if buf == nil {
		return s // No replacements made
	}
	buf = append(buf, s[i:]...) // Append remaining text
	return string(buf)
}

func (r *singleStringReplacer) WriteString(w io.Writer, s string) (n int, err error) {
	sw := getStringWriter(w) // Get efficient string writer
	var i, wn int
	for {
		match := r.finder.next(s[i:])
		if match == -1 {
			break
		}
		wn, err = sw.WriteString(s[i : i+match]) // Write text before match
		n += wn
		if err != nil {
			return
		}
		wn, err = sw.WriteString(r.value) // Write replacement
		n += wn
		if err != nil {
			return
		}
		i += match + len(r.finder.pattern)
	}
	wn, err = sw.WriteString(s[i:]) // Write remaining text
	n += wn
	return
}

NewReplacerは、単一の置換パターンが与えられた場合に、makeSingleStringReplacerを呼び出してsingleStringReplacerのインスタンスを生成し、それをReplacerの内部実装として使用します。
singleStringReplacer.ReplaceとsingleStringReplacer.WriteStringは、stringFinder.nextを使用して置換対象のパターンを効率的に見つけ、見つかった場合は置換を実行します。これにより、従来の汎用的な置換アルゴリズムよりも大幅な性能向上が実現されます。

参考にした情報源リンク

Go CL 6545049: strings: implement a faster single-string Replacer: https://golang.org/cl/6545049
Boyer-Moore string search algorithm - Wikipedia: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
A Fast String Searching Algorithm (original paper by Boyer and Moore): http://www.cs.utexas.edu/~moore/publications/fstrpos.pdf
Go言語のstringsパッケージのソースコード (特にreplace.goとsearch.go): https://github.com/golang/go/tree/master/src/strings
Go言語のベンチマークに関するドキュメント: https://pkg.go.dev/testing#hdr-Benchmarks
Go言語のio.Writerインターフェースに関するドキュメント: https://pkg.go.dev/io#Writer

comemo