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

このコミットは、Go言語の標準ライブラリである net/textproto パッケージ内の ReadMIMEHeader 関数におけるメモリ割り当てを削減することを目的としています。具体的には、HTTPヘッダーなどのMIMEヘッダーを読み込む際のパフォーマンスを向上させるために、不要な小さなメモリ割り当てを減らす最適化が行われました。

コミット

commit 16c3f82ed45931775565b8945bcdcd88183dedb6
Author: Brad Fitzpatrick <bradfitz@golang.org>
Date:   Tue Jul 2 22:37:19 2013 -0700

    net/textproto: reduce allocations in ReadMIMEHeader
    
    ReadMIMEHeader is used by net/http, net/mail, and
    mime/multipart.
    
    Don't do so many small allocations. Calculate up front
    how much we'll probably need.
    
    benchmark                  old ns/op    new ns/op    delta
    BenchmarkReadMIMEHeader         8433         7467  -11.45%
    
    benchmark                 old allocs   new allocs    delta
    BenchmarkReadMIMEHeader           23           14  -39.13%
    
    benchmark                  old bytes    new bytes    delta
    BenchmarkReadMIMEHeader         1705         1343  -21.23%
    
    R=golang-dev, r, iant, adg
    CC=golang-dev
    https://golang.org/cl/8179043

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

https://github.com/golang/go/commit/16c3f82ed45931775565b8945bcdcd88183dedb6

元コミット内容

net/textproto: reduce allocations in ReadMIMEHeader

ReadMIMEHeader は net/http, net/mail, mime/multipart で使用されています。

多くの小さな割り当てを行わないようにします。事前にどれくらいのメモリが必要になるかを計算します。

ベンチマーク結果: BenchmarkReadMIMEHeader

• ns/op (操作あたりのナノ秒): 8433 -> 7467 (-11.45% 改善)
• allocs (割り当て回数): 23 -> 14 (-39.13% 改善)
• bytes (割り当てバイト数): 1705 -> 1343 (-21.23% 改善)

変更の背景

net/textproto パッケージの ReadMIMEHeader 関数は、HTTPヘッダーやメールヘッダー、MIMEマルチパートのヘッダーなど、様々なテキストベースのプロトコルヘッダーを解析するために広く利用されています。この関数は、ヘッダーの各行を読み込み、キーと値のペアに分割して MIMEHeader マップに格納します。

従来の ReadMIMEHeader の実装では、ヘッダーの各行や各値が読み込まれるたびに、小さな文字列やスライスが動的に割り当てられていました。このような多数の小さなメモリ割り当ては、ガベージコレクションの頻度を増加させ、結果としてアプリケーションのパフォーマンスに悪影響を与える可能性があります。特に、大量のヘッダーを処理するサーバーアプリケーションなどでは、このオーバーヘッドが顕著になります。

このコミットの目的は、このような不要な小さなメモリ割り当てを削減し、ReadMIMEHeader 関数の実行効率を向上させることです。具体的には、ヘッダーの読み込みを開始する前に、必要なメモリ量を事前に予測し、一度に大きなメモリブロックを割り当てることで、後続の小さな割り当てを回避しようとしています。これにより、ガベージコレクションの負荷を軽減し、全体的な処理速度を向上させることが期待されます。ベンチマーク結果が示すように、操作あたりの時間、割り当て回数、割り当てバイト数の全てにおいて顕著な改善が見られています。

前提知識の解説

Go言語のメモリ割り当てとガベージコレクション

Go言語は自動メモリ管理（ガベージコレクション、GC）を採用しています。プログラムがメモリを必要とすると、ヒープ領域からメモリが割り当てられます。不要になったメモリはガベージコレクタによって自動的に解放されます。

• 小さな割り当てのコスト: Goのガベージコレクタは非常に効率的ですが、非常に小さなオブジェクトが頻繁に割り当てられ、すぐに不要になるようなパターンは、GCのオーバーヘッドを増加させる可能性があります。これは、GCがヒープをスキャンして到達可能なオブジェクトを特定し、不要なオブジェクトを解放する際に、オブジェクトの数が多いほど処理量が増えるためです。
• スライスと容量 (Capacity): Goのスライスは、内部的に配列を参照するデータ構造です。スライスには「長さ (length)」と「容量 (capacity)」があります。長さはスライスに含まれる要素の数、容量はスライスが参照する基底配列の最大サイズです。append 関数を使ってスライスに要素を追加する際、容量が足りなくなると、Goランタイムはより大きな新しい基底配列を割り当て、既存の要素をコピーします。この再割り当てとコピーの操作はコストがかかります。
• make 関数による事前割り当て: make([]T, length, capacity) の形式でスライスを作成すると、指定された容量を持つ基底配列が事前に割り当てられます。これにより、後続の append 操作で再割り当てが発生する回数を減らすことができます。

net/textproto パッケージと MIMEHeader

net/textproto パッケージは、MIME (Multipurpose Internet Mail Extensions) やHTTPなどのテキストベースのプロトコルを扱うための低レベルな機能を提供します。

• Reader 構造体: このパッケージの Reader は、bufio.Reader をラップし、プロトコル固有の読み込みメソッド（例: 行の読み込み、ヘッダーの読み込み）を提供します。
• ReadMIMEHeader() 関数: この関数は、入力ストリームからMIMEヘッダーブロックを読み込み、それを MIMEHeader 型のマップとして返します。MIMEヘッダーは通常、Key: Value の形式で複数行にわたって記述され、空行で終了します。
• MIMEHeader 型: map[string][]string のエイリアスです。ヘッダーのキー（例: "Content-Type"）を文字列として持ち、その値は文字列のスライスとして保持されます。これは、同じキーを持つヘッダーが複数存在する場合（例: "Set-Cookie"）に対応するためです。

bufio.Reader.Peek() と bufio.Reader.Buffered()

bufio.Reader は、I/O操作の効率化のためにバッファリングを行います。

• Peek(n int): バッファから最大 n バイトを読み込まずに覗き見ることができます。返されるスライスは、次の読み込み操作によって無効になる可能性があります。この関数は、実際にデータを消費せずに、次に何が来るかを事前に確認するのに役立ちます。
• Buffered(): 現在バッファに読み込まれているバイト数を返します。

これらの関数は、実際にデータを処理する前に、入力ストリームの構造を推測し、それに基づいてリソースを事前に割り当てるような最適化に利用できます。

技術的詳細

このコミットの主要な技術的アプローチは、ReadMIMEHeader 関数がヘッダーを解析する前に、必要なメモリ量を「ヒント」として事前に見積もり、それに基づいてスライスを事前割り当てすることです。これにより、ヘッダーの各行や各値が追加されるたびに発生する可能性のある動的な再割り当てと、それに伴うガベージコレクションの負荷を軽減します。

具体的な変更点は以下の通りです。

1. upcomingHeaderNewlines() 関数の導入:

   • この新しいヘルパー関数は、Reader の内部バッファを Peek することで、現在のヘッダーブロック内に含まれる改行文字 (\n) の数を概算します。
   • ヘッダーの各行は通常1つの改行文字で終わるため、改行文字の数はヘッダーの行数、ひいてはヘッダーのキーと値のペアの数（または MIMEHeader マップに格納されるエントリの数）の近似値となります。
   • この関数は、バッファの終端やヘッダーの終端 (\r\n\r\n または \n\n) を検出すると、それ以上の改行をカウントせずに終了します。これにより、不正確なヒントが返されることを防ぎます。
   • もしバッファが空であったり、ヒントを正確に計算できない場合は 0 を返します。

2. MIMEHeader マップと値スライスの事前割り当て:

   • ReadMIMEHeader 関数内で、まず upcomingHeaderNewlines() を呼び出して hint を取得します。
   • この hint を使用して、MIMEHeader マップ (m) を make(MIMEHeader, hint) で初期化します。これにより、マップの初期容量が設定され、ヘッダーエントリの追加によるマップの再ハッシュやリサイズが減ります。
   • さらに、ヘッダーの値（文字列）を格納するためのスライス strs を make([]string, hint) で事前割り当てします。この strs スライスは、ヘッダーの値が格納される基底配列として機能します。

3. 値の追加ロジックの最適化:

   • ヘッダーのキーと値のペアが読み込まれるループ内で、値の追加ロジックが変更されました。
   • 以前は単純に m[key] = append(m[key], value) となっていましたが、新しいロジックでは、まず m[key] に対応する値スライス vv を取得します。
   • もし vv が nil であり、かつ事前割り当てされた strs スライスにまだ要素が残っている場合 (len(strs) > 0)、strs から1つの要素を切り出して vv として使用します。
     • vv, strs = strs[:1:1], strs[1:] というスライス操作が重要です。これは strs の最初の要素を長さ1、容量1のスライス vv として切り出し、残りの strs を更新します。容量を1に設定することで、この vv に append しても、strs の他の要素に影響を与えないようにします。
     • この vv の最初の要素 (vv[0]) に読み込んだ value を直接代入します。
     • 最後に、m[key] にこの vv を設定します。
   • vv が既に存在する場合、または strs が空の場合は、従来通り m[key] = append(vv, value) を使用して値を既存のスライスに追加します。この場合でも、MIMEHeader マップ自体の初期容量が設定されているため、マップのリサイズは減ります。

この最適化により、ヘッダーの読み込み中に発生する動的なメモリ割り当ての回数が大幅に削減され、特に多数のヘッダーを持つリクエストやメッセージを処理する際のパフォーマンスが向上します。

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

変更は src/pkg/net/textproto/reader.go ファイルに集中しています。

--- a/src/pkg/net/textproto/reader.go
+++ b/src/pkg/net/textproto/reader.go
@@ -456,7 +456,16 @@ func (r *Reader) ReadDotLines() ([]string, error) {
 //	}
 //
 func (r *Reader) ReadMIMEHeader() (MIMEHeader, error) {
-	m := make(MIMEHeader, 4)
+	// Avoid lots of small slice allocations later by allocating one
+	// large one ahead of time which we'll cut up into smaller
+	// slices. If this isn't big enough later, we allocate small ones.
+	var strs []string
+	hint := r.upcomingHeaderNewlines()
+	if hint > 0 {
+		strs = make([]string, hint)
+	}
+
+	m := make(MIMEHeader, hint)
 	for {
 		kv, err := r.readContinuedLineSlice()
 		if len(kv) == 0 {
@@ -483,7 +492,18 @@ func (r *Reader) ReadMIMEHeader() (MIMEHeader, error) {
 		}
 		value := string(kv[i:])
 
-		m[key] = append(m[key], value)
+		vv := m[key]
+		if vv == nil && len(strs) > 0 {
+			// More than likely this will be a single-element key.
+			// Most headers aren't multi-valued.
+			// Set the capacity on strs[0] to 1, so any future append
+			// won't extend the slice into the other strings.
+			vv, strs = strs[:1:1], strs[1:]
+			vv[0] = value
+			m[key] = vv
+		} else {
+			m[key] = append(vv, value)
+		}
 
 		if err != nil {
 			return m, err
@@ -491,6 +511,29 @@ func (r *Reader) ReadMIMEHeader() (MIMEHeader, error) {
 	}
 }
 
+// upcomingHeaderNewlines returns an approximation of the number of newlines
+// that will be in this header. If it gets confused, it returns 0.
+func (r *Reader) upcomingHeaderNewlines() (n int) {
+	// Try to determine the 'hint' size.
+	r.R.Peek(1) // force a buffer load if empty
+	s := r.R.Buffered()
+	if s == 0 {
+		return
+	}
+	peek, _ := r.R.Peek(s)
+	for len(peek) > 0 {
+		i := bytes.IndexByte(peek, '\n')
+		if i < 3 {
+			// Not present (-1) or found within the next few bytes,
+			// implying we're at the end ("\r\n\r\n" or "\n\n")
+			return
+		}
+		n++
+		peek = peek[i+1:]
+	}
+	return
+}
+
 // CanonicalMIMEHeaderKey returns the canonical format of the
 // MIME header key s.  The canonicalization converts the first
 // letter and any letter following a hyphen to upper case;

コアとなるコードの解説

ReadMIMEHeader 関数の変更点

1. 初期化部分の変更:

   • 変更前: m := make(MIMEHeader, 4)
     • MIMEHeader マップを初期容量 4 で作成していました。これは固定値であり、ヘッダーの数が多い場合には途中でマップのリサイズが発生し、追加のメモリ割り当てとコピーのコストが発生していました。
   • 変更後:

     var strs []string
     hint := r.upcomingHeaderNewlines()
     if hint > 0 {
         strs = make([]string, hint)
     }
     m := make(MIMEHeader, hint)
     

     • upcomingHeaderNewlines() 関数を呼び出して、ヘッダー内の改行数をヒントとして取得します。
     • この hint を使用して、MIMEHeader マップ m を初期化します。これにより、ヘッダーの行数に近い初期容量が設定され、マップのリサイズが大幅に削減されます。
     • さらに、strs という []string 型のスライスを hint の容量で事前割り当てします。このスライスは、後で MIMEHeader の値として使用される個々の文字列スライスを効率的に提供するためのプールとして機能します。

2. 値の追加ロジックの変更:

   • 変更前: m[key] = append(m[key], value)
     • 単純に append を使用して、MIMEHeader マップの特定キーに対応するスライスに値を追加していました。この際、スライスの容量が不足すると新しい基底配列が割り当てられていました。
   • 変更後:

     vv := m[key]
     if vv == nil && len(strs) > 0 {
         // More than likely this will be a single-element key.
         // Most headers aren't multi-valued.
         // Set the capacity on strs[0] to 1, so any future append
         // won't extend the slice into the other strings.
         vv, strs = strs[:1:1], strs[1:]
         vv[0] = value
         m[key] = vv
     } else {
         m[key] = append(vv, value)
     }
     

     • まず、現在のキー key に対応する値スライス vv を取得します。
     • vv が nil (つまり、そのキーがマップにまだ存在しない) かつ、事前割り当てされた strs スライスにまだ要素が残っている場合 (len(strs) > 0)、最適化されたパスに入ります。
       • vv, strs = strs[:1:1], strs[1:] は、strs スライスの最初の要素を、長さ1、容量1の新しいスライス vv として切り出します。残りの strs は、最初の要素を除いた部分になります。この strs[:1:1] という表記は、スライスの再スライスにおいて、長さと容量を明示的に指定するGoのイディオムです。容量を1に設定することで、この vv に後で append が行われても、strs の他の要素が格納されているメモリ領域を侵食しないようにします。
       • vv[0] = value で、切り出したスライス vv の最初の要素に直接 value を代入します。
       • m[key] = vv で、この新しく作成された（しかし事前割り当てされたメモリを利用している）スライスをマップに設定します。
     • 上記以外のケース（vv が既に存在するか、strs が空の場合）では、従来通り m[key] = append(vv, value) を使用します。この場合でも、MIMEHeader マップ自体の初期容量が設定されているため、マップのリサイズは減ります。

upcomingHeaderNewlines 関数の新規追加

func (r *Reader) upcomingHeaderNewlines() (n int) {
	r.R.Peek(1) // force a buffer load if empty
	s := r.R.Buffered()
	if s == 0 {
		return
	}
	peek, _ := r.R.Peek(s)
	for len(peek) > 0 {
		i := bytes.IndexByte(peek, '\n')
		if i < 3 {
			// Not present (-1) or found within the next few bytes,
			// implying we're at the end ("\r\n\r\n" or "\n\n")
			return
		}
		n++
		peek = peek[i+1:]
	}
	return
}

• この関数は、bufio.Reader の Peek メソッドを利用して、実際にデータを消費することなく、バッファ内の内容を覗き見ます。
• r.R.Peek(1) は、バッファが空の場合に強制的にデータを読み込ませるためのものです。
• r.R.Buffered() で現在バッファに存在するバイト数を取得し、その全量を peek します。
• ループ内で bytes.IndexByte(peek, '\n') を使用して改行文字 (\n) を検索します。
• i < 3 の条件は、改行が見つからない場合 (-1) や、非常に近い位置（例: \r\n\r\n の最後の \n や \n\n の2つ目の \n）で見つかった場合に、ヘッダーの終端に達したと判断し、カウントを終了するためのヒューリスティックです。これにより、ヘッダーの終端を示す空行を誤ってヘッダーの一部としてカウントすることを防ぎます。
• 改行が見つかるたびに n をインクリメントし、peek スライスを次の改行以降に移動させて処理を続けます。
• 最終的に n は、ヘッダー内の行数（おおよそのキーと値のペアの数）の予測値として返されます。

これらの変更により、ReadMIMEHeader はより効率的にメモリを使用し、特に多数のヘッダーを処理するシナリオでのパフォーマンスが向上しました。

関連リンク

• Go CL 8179043: https://golang.org/cl/8179043

参考にした情報源リンク

• Go言語の公式ドキュメント: net/textproto パッケージ
• Go言語の公式ドキュメント: bufio パッケージ
• Go言語のスライスに関するドキュメントやチュートリアル (スライスの長さと容量、再スライス操作)
• Go言語のガベージコレクションに関する一般的な情報
• コミットメッセージとコード差分