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

このコミットは、Go言語の標準ライブラリであるstringsパッケージ内のbyteStringReplacer型におけるWriteStringメソッドのパフォーマンス改善に関するものです。具体的には、文字列置換処理において発生していた不要なメモリ割り当てを削減し、ベンチマークで50%以上の高速化を達成しています。

変更されたファイルは以下の2つです。

• src/pkg/strings/replace.go: byteStringReplacer.WriteStringメソッドの実装が変更されました。
• src/pkg/strings/replace_test.go: BenchmarkWriteStringという新しいベンチマークが追加され、変更による性能向上が測定されました。

コミット

commit 1ca10de35d289346468a9c5b26475265c375eb95
Author: Rui Ueyama <ruiu@google.com>
Date:   Thu Jun 19 11:22:50 2014 -0700

    strings: reduce allocation in byteStringReplacer.WriteString
    
    Use WriteString instead of allocating a byte slice as a
    buffer. This was a TODO.
    
    benchmark               old ns/op    new ns/op    delta
    BenchmarkWriteString        40139        19991  -50.20%
    
    LGTM=bradfitz
    R=golang-codereviews, bradfitz
    CC=golang-codereviews
    https://golang.org/cl/107190044

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

https://github.com/golang/go/commit/1ca10de35d289346468a9c5b26475265c375eb95

元コミット内容

strings: reduce allocation in byteStringReplacer.WriteString

Use WriteString instead of allocating a byte slice as a
buffer. This was a TODO.

benchmark               old ns/op    new ns/op    delta
BenchmarkWriteString        40139        19991  -50.20%

LGTM=bradfitz
R=golang-codereviews, bradfitz
CC=golang-codereviews
https://golang.org/cl/107190044

変更の背景

このコミットの背景には、Go言語のstringsパッケージにおける文字列置換処理のパフォーマンス最適化があります。以前のbyteStringReplacer.WriteStringメソッドの実装では、置換処理を行う際に一時的なバイトスライス（[]byte）をバッファとして割り当てていました。このバッファへの割り当てと書き込み、そして最終的なio.Writerへのフラッシュという一連の操作が、特に大量の文字列置換を行う場合にオーバーヘッドとなっていました。

コミットメッセージにある「This was a TODO.」という記述から、この非効率なメモリ割り当ては開発者によって認識されており、将来的な改善点としてマークされていたことがわかります。io.WriteStringを直接利用することで、この不要なバッファ割り当てを排除し、より効率的な書き込みパスを利用することが目的でした。ベンチマーク結果が示すように、この変更により処理時間が大幅に短縮され、特にパフォーマンスが重視される場面でのstrings.Replacerの利用が改善されました。

前提知識の解説

このコミットの変更内容を理解するためには、以下のGo言語の概念と標準ライブラリの知識が必要です。

1. io.Writerインターフェース: io.Writerは、Go言語におけるデータ書き込みの基本的なインターフェースです。Write([]byte) (n int, err error)メソッドを定義しており、バイトスライスを受け取ってデータを書き込みます。ファイル、ネットワーク接続、メモリバッファなど、様々な出力先に統一的な方法でデータを書き込むことを可能にします。

2. io.StringWriterインターフェース: io.StringWriterは、io.Writerを拡張したインターフェースで、WriteString(s string) (n int, err error)メソッドを定義しています。このインターフェースを実装する型は、バイトスライスではなく直接文字列を受け取って書き込むことができます。これにより、文字列からバイトスライスへの変換（メモリ割り当てを伴う可能性がある）を回避し、より効率的な書き込みが可能になります。bytes.Bufferやos.Fileなどがこのインターフェースを実装しています。

3. strings.Replacer: strings.Replacerは、複数の文字列置換を効率的に行うための型です。一度strings.NewReplacerで置換ルールを定義すると、そのルールに基づいて文字列の置換を高速に実行できます。内部的には、置換対象の文字列を効率的に検索し、対応する置換文字列に置き換えるためのデータ構造（このコミットで変更されたbyteStringReplacerなど）を持っています。

4. メモリ割り当てとガベージコレクション (GC): Go言語では、makeやnewなどの関数を使ってメモリを割り当てます。割り当てられたメモリはヒープ上に配置され、不要になったメモリはガベージコレクタによって自動的に解放されます。しかし、頻繁なメモリ割り当てはGCの負荷を増加させ、プログラムのパフォーマンスに悪影響を与える可能性があります。特に、ループ内で一時的なバッファを繰り返し割り当てるようなパターンは、GCの頻度を高め、レイテンシの増加やスループットの低下を招くことがあります。このコミットは、まさにこのような不要なメモリ割り当てを削減することを目的としています。

5. bytes.Buffer: bytes.Bufferは、可変長のバイトバッファを実装する型で、io.Writerインターフェースを実装しています。メモリ上にデータを効率的に蓄積し、必要に応じてバイトスライスや文字列として取り出すことができます。また、io.StringWriterも実装しているため、文字列を直接書き込むことができます。

技術的詳細

このコミットの主要な変更点は、stringsパッケージ内のbyteStringReplacer.WriteStringメソッドの実装を、一時的なバイトスライスバッファの利用から、io.StringWriterインターフェースを活用した直接書き込みへと変更したことです。

変更前の実装の課題:

変更前のWriteStringメソッドは、最大32KBの固定サイズのバイトスライスbufを内部バッファとして使用していました。

// 変更前のコードの一部
bufsize := 32 << 10 // 32KB
if len(s) < bufsize {
    bufsize = len(s)
}
buf := make([]byte, bufsize) // ここでバッファを割り当て
bi := buf[:0]

// ... ループ内で bi にバイトを追加し、bi が満杯になったり置換が発生したりすると w.Write(bi) でフラッシュ

この実装では、入力文字列sを走査し、置換が必要ない文字はbi（bufのサブスライス）に追加していました。biが満杯になるか、置換が発生するたびに、w.Write(bi)を呼び出してバッファの内容をio.Writerに書き出していました。置換が発生した場合は、置換後のバイトスライスnewをw.Write(new)で直接書き出していました。

このアプローチの主な問題点は以下の通りです。

• 不要なメモリ割り当て: make([]byte, bufsize)によって、常に一時的なバイトスライスバッファが割り当てられていました。たとえ置換が発生しない場合でも、このバッファは必要でした。
• 複数回のWrite呼び出し: 置換が発生するたびに、バッファの内容と置換後の文字列の2回w.Writeが呼び出される可能性がありました。これは、io.Writerの実装によってはオーバーヘッドとなることがあります。

変更後の実装の改善点:

変更後のWriteStringメソッドは、以下の戦略を採用することで、メモリ割り当てを削減し、効率を向上させました。

1. getStringWriterの導入:

   sw := getStringWriter(w)
   

   getStringWriterは内部ヘルパー関数であり、渡されたio.Writer wがio.StringWriterインターフェースも実装しているかどうかをチェックします。もし実装していれば、そのio.StringWriterのメソッドを返します。これにより、後続の書き込みでWriteString(string)メソッドを直接呼び出すことが可能になり、文字列からバイトスライスへの変換（およびそれに伴うメモリ割り当て）を回避できます。io.StringWriterを実装していない場合は、w.Write([]byte)にフォールバックするようなラッパーが返されると推測されます。

2. 直接書き込みへの移行:

   if last != i {
       nw, err := sw.WriteString(s[last:i])
       // ...
   }
   // ...
   last = i + 1
   nw, err := w.Write(r.new[b]) // 置換後のバイトは w.Write で書き込み
   // ...
   if last != len(s) {
       var nw int
       nw, err = sw.WriteString(s[last:])
       // ...
   }
   

   新しい実装では、入力文字列sを走査し、置換が必要な文字が見つかるまで、その間の部分文字列s[last:i]をsw.WriteStringを使って直接io.Writerに書き込みます。これにより、置換されない部分の文字列に対しては、一時的なバイトバッファを介さずに直接書き込むことが可能になりました。置換される文字については、r.new[b]（置換後のバイトスライス）をw.Writeで書き込みます。

この変更により、以下の利点が得られました。

• メモリ割り当ての削減: 一時的なバイトスライスバッファの割り当てが不要になったため、ヒープ割り当てが減少し、ガベージコレクションの頻度が低下します。
• io.StringWriterの活用: io.StringWriterを実装しているio.Writerに対しては、より効率的なWriteStringパスを利用できるようになりました。
• Write呼び出し回数の最適化: 置換されない連続した文字列は一度のWriteString呼び出しで処理されるため、Write呼び出しの回数が削減される可能性があります。

ベンチマーク結果が示すように、この最適化はWriteStringメソッドの実行時間を約50%削減するという顕著な効果をもたらしました。

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

src/pkg/strings/replace.go の func (r *byteStringReplacer) WriteString(w io.Writer, s string) (n int, err error) メソッドが変更されました。

--- a/src/pkg/strings/replace.go
+++ b/src/pkg/strings/replace.go
@@ -511,48 +511,32 @@ func (r *byteStringReplacer) Replace(s string) string {
 	return string(buf)
 }
 
-// WriteString maintains one buffer that's at most 32KB.  The bytes in
-// s are enumerated and the buffer is filled.  If it reaches its
-// capacity or a byte has a replacement, the buffer is flushed to w.
 func (r *byteStringReplacer) WriteString(w io.Writer, s string) (n int, err error) {
-	// TODO(bradfitz): use io.WriteString with slices of s instead.
-	bufsize := 32 << 10
-	if len(s) < bufsize {
-		bufsize = len(s)
-	}
-	buf := make([]byte, bufsize)
-	bi := buf[:0]
-
+	sw := getStringWriter(w)
+	last := 0
 	for i := 0; i < len(s); i++ {
 		b := s[i]
-		var new []byte
-		if r.old[b>>5]&uint32(1<<(b&31)) != 0 {
-			new = r.new[b]
-		} else {
-			bi = append(bi, b)
-		}
-		if len(bi) == cap(bi) || (len(bi) > 0 && len(new) > 0) {
-			nw, err := w.Write(bi)
-			n += nw
-			if err != nil {
-				return n, err
-			}
-			bi = buf[:0]
+		if r.old[b>>5]&uint32(1<<(b&31)) == 0 {
+			continue
 		}
-		if len(new) > 0 {
-			nw, err := w.Write(new)
+		if last != i {
+			nw, err := sw.WriteString(s[last:i])
 			n += nw
 			if err != nil {
 				return n, err
 			}
 		}
-	}
-	if len(bi) > 0 {
-		nw, err := w.Write(bi)
+		last = i + 1
+		nw, err := w.Write(r.new[b])
 		n += nw
 		if err != nil {
 			return n, err
 		}
 	}
-	return n, nil
+	if last != len(s) {
+		var nw int
+		nw, err = sw.WriteString(s[last:])
+		n += nw
+	}
+	return
 }

また、src/pkg/strings/replace_test.go に新しいベンチマークが追加されました。

--- a/src/pkg/strings/replace_test.go
+++ b/src/pkg/strings/replace_test.go
@@ -480,6 +480,15 @@ func BenchmarkHTMLEscapeOld(b *testing.B) {
 	}
 }
 
+func BenchmarkWriteString(b *testing.B) {
+	str := Repeat("I <3 to escape HTML & other text too.", 100)
+	buf := new(bytes.Buffer)
+	for i := 0; i < b.N; i++ {
+		htmlEscaper.WriteString(buf, str)
+		buf.Reset()
+	}
+}
+
 // BenchmarkByteByteReplaces compares byteByteImpl against multiple Replaces.
 func BenchmarkByteByteReplaces(b *testing.B) {
 	str := Repeat("a", 100) + Repeat("b", 100)

コアとなるコードの解説

src/pkg/strings/replace.go の変更

byteStringReplacer.WriteString メソッドは、io.Writer w に文字列 s を書き込みながら、定義された置換ルールに基づいて文字を置換する役割を担います。

変更前:

変更前の実装は、一時的なバイトスライス buf をバッファとして使用していました。

• buf := make([]byte, bufsize): 最大32KBのバイトスライスを割り当てます。これは、置換処理のたびにヒープ割り当てが発生する原因となります。
• bi := buf[:0]: bufの先頭を指すスライスbiを作成し、これに置換されない文字をappendで追加していきます。
• if len(bi) == cap(bi) || (len(bi) > 0 && len(new) > 0): biが満杯になるか、置換が発生した場合に、w.Write(bi)でバッファの内容をio.Writerにフラッシュしていました。
• if len(new) > 0: 置換後のバイトスライスnewがある場合は、w.Write(new)で直接書き込んでいました。

このアプローチは、バッファリングによってw.Writeの呼び出し回数を減らすことを意図していましたが、バッファ自体の割り当てと、置換が発生するたびにバッファのフラッシュと置換後の文字列の書き込みという2回のWrite呼び出しが発生する可能性があり、非効率でした。特に、io.Writerがio.StringWriterを実装している場合、文字列を直接書き込む方が効率的です。

変更後:

変更後の実装は、一時的なバイトスライスバッファの割り当てを排除し、io.StringWriterの活用と部分文字列の直接書き込みに焦点を当てています。

1. sw := getStringWriter(w):

   • この行が新しい実装の鍵となります。getStringWriterは内部関数であり、wがio.StringWriterインターフェースを実装しているかどうかを効率的にチェックします。
   • もしwがio.StringWriterを実装していれば、swはそのWriteStringメソッドを直接呼び出すことができるようになります。これにより、文字列からバイトスライスへの変換（[]byte(string)）を回避し、メモリ割り当てを削減できます。
   • wがio.StringWriterを実装していない場合でも、swはw.Write([]byte(s))のような形で文字列をバイトスライスに変換して書き込むフォールバックロジックを提供すると考えられます。

2. last := 0:

   • last変数は、最後に書き込みが完了した文字列のインデックスを追跡します。これにより、置換されない連続した部分文字列を効率的に抽出できます。

3. for i := 0; i < len(s); i++:

   • 入力文字列sを1文字ずつ走査します。

4. if r.old[b>>5]&uint32(1<<(b&31)) == 0:

   • 現在の文字bが置換対象でない場合、continueして次の文字に進みます。この条件は、strings.Replacerが内部的に使用する高速なルックアップテーブル（r.old）を利用して、文字が置換対象かどうかを判断しています。

5. if last != i:

   • 現在の文字s[i]が置換対象であり、かつlast（最後に書き込みが完了した位置）から現在の位置iまでの間に置換されない部分文字列が存在する場合（つまりlastとiが異なる場合）、その部分文字列s[last:i]をsw.WriteStringを使ってio.Writerに書き込みます。
   • これにより、置換されない連続した文字列は、一度のWriteString呼び出しで効率的に処理されます。

6. last = i + 1:

   • 置換対象の文字s[i]が処理された後、lastを次の文字の開始位置に更新します。

7. nw, err := w.Write(r.new[b]):

   • 置換対象の文字s[i]に対応する置換後のバイトスライスr.new[b]を、直接w.Writeを使ってio.Writerに書き込みます。

8. if last != len(s):

   • ループが終了した後、文字列の末尾までまだ書き込まれていない部分文字列s[last:]が存在する場合、それをsw.WriteStringを使って書き込みます。

この新しい実装は、置換されない部分文字列をまとめてWriteStringで処理し、置換される部分だけを個別にWriteで処理することで、メモリ割り当てとWrite呼び出しのオーバーヘッドを大幅に削減しています。特に、置換が少ない、または全くない文字列に対しては、非常に効率的なパスとなります。

src/pkg/strings/replace_test.go の変更

• BenchmarkWriteStringという新しいベンチマーク関数が追加されました。
• このベンチマークは、htmlEscaper（HTMLエスケープを行うstrings.Replacerのインスタンス）のWriteStringメソッドのパフォーマンスを測定します。
• bytes.Bufferをio.Writerとして使用し、長い文字列を繰り返し書き込むことで、実際の使用シナリオに近い条件でWriteStringの性能を評価しています。
• このベンチマークの追加により、変更がもたらしたパフォーマンス改善が数値として明確に示され、回帰テストとしても機能します。

関連リンク

• Go言語の変更リスト (CL): https://golang.org/cl/107190044

参考にした情報源リンク

• Go言語 io パッケージのドキュメント: https://pkg.go.dev/io
• Go言語 strings パッケージのドキュメント: https://pkg.go.dev/strings
• Go言語 bytes パッケージのドキュメント: https://pkg.go.dev/bytes
• Go言語におけるメモリ割り当てとガベージコレクションに関する一般的な情報 (例: Goの公式ブログや技術記事など)
  • Go Slices: usage and internals: https://go.dev/blog/slices
  • The Go garbage collector: https://go.dev/blog/go15gc
• io.StringWriter インターフェースに関する情報 (例: Goのソースコードや関連する議論)
  • io.StringWriter source code: https://cs.opensource.google/go/go/+/refs/tags/go1.22.3:src/io/io.go;l260
• strings.Builder (Go 1.10以降で導入された効率的な文字列構築): https://pkg.go.dev/strings#Builder (このコミットの時点では存在しないが、関連する概念として)