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

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

このコミットは、Go言語の net/textproto パッケージにおけるMIMEヘッダーの正規化処理を最適化し、パフォーマンスの向上とメモリ割り当ての削減を実現します。特に、よく使われるヘッダー文字列を再利用することで、文字列の新規割り当てを減らし、処理速度を向上させています。

コミット

commit 7e7b89f7d0191537094d91963c9fe1647ef43635
Author: Jeff R. Allen <jra@nella.org>
Date:   Mon Nov 12 15:31:42 2012 -0800

    net/textproto: faster header canonicalization with fewer allocations
    
    By keeping a single copy of the strings that commonly show up
    in headers, we can avoid one string allocation per header.
    
    benchmark                  old ns/op    new ns/op    delta
    BenchmarkReadMIMEHeader        19590        10824  -44.75%
    BenchmarkUncommon               3168         1861  -41.26%
    
    benchmark                 old allocs   new allocs    delta
    BenchmarkReadMIMEHeader           32           25  -21.88%
    BenchmarkUncommon                  5            5    0.00%
    
    R=bradfitz, golang-dev, dave, rsc, jra
    CC=golang-dev
    https://golang.org/cl/6721055

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

https://github.com/golang/go/commit/7e7b89f7d0191537094d91963c9fe1647ef43635

元コミット内容

net/textproto パッケージにおいて、ヘッダーの正規化処理を高速化し、メモリ割り当てを削減しました。これは、一般的に使用されるヘッダー文字列の単一コピーを保持することで、ヘッダーごとの文字列割り当てを回避することによって実現されます。

ベンチマーク結果は以下の通りです。

ベンチマーク旧 ns/op新 ns/opデルタ
BenchmarkReadMIMEHeader1959010824-44.75%
BenchmarkUncommon31681861-41.26%
ベンチマーク旧 allocs新 allocsデルタ
BenchmarkReadMIMEHeader3225-21.88%
BenchmarkUncommon550.00%

変更の背景

この変更の主な背景は、HTTPなどのプロトコルで頻繁に利用されるMIMEヘッダーの処理におけるパフォーマンスとメモリ効率の改善です。特に、ヘッダーキーの正規化(例: "content-type" を "Content-Type" に変換する)は、リクエストやレスポンスの処理パスで繰り返し行われる操作です。

従来の正規化処理では、ヘッダーキーが入力されるたびに、その正規化された形式の新しい文字列が生成され、メモリに割り当てられていました。これは、特に大量のHTTPリクエストを処理するサーバーのようなアプリケーションにおいて、ガベージコレクションの負荷を増やし、全体的なパフォーマンスのボトルネックとなる可能性がありました。

このコミットは、Goの標準ライブラリが提供するネットワーク処理の基盤部分の効率を高めることを目的としています。よく知られたヘッダーキー("Host", "Content-Type", "User-Agent"など)は限られた種類しかなく、これらが繰り返し出現するという特性に着目し、これらの共通ヘッダーキーに対しては、毎回新しい文字列を生成するのではなく、あらかじめ用意された単一の文字列インスタンスを再利用することで、メモリ割り当てを削減し、結果として処理速度を向上させることを目指しています。

ベンチマーク結果が示すように、この最適化は ReadMIMEHeader の処理時間を約45%削減し、メモリ割り当ても約22%削減するという顕著な効果をもたらしています。これは、Goのネットワークスタック全体の効率向上に寄与する重要な改善です。

前提知識の解説

1. MIMEヘッダーと正規化 (Canonicalization)

MIME (Multipurpose Internet Mail Extensions) ヘッダーは、HTTPメッセージや電子メールなどのインターネットメッセージにおいて、メッセージ本体に関するメタデータ(例: コンテンツタイプ、エンコーディング、送信者など)を記述するために使用されます。ヘッダーは通常、「Key: Value」の形式で表現されます。

MIMEヘッダーのキー(例: Content-Type)は、大文字・小文字を区別しない(case-insensitive)とRFCで定められています。しかし、プログラム内部でこれらのキーを比較したり、マップのキーとして使用したりする際には、一貫した形式に統一する必要があります。この統一された形式を「正規化された形式(Canonical Form)」と呼び、その処理を「正規化(Canonicalization)」と呼びます。

HTTP/MIMEヘッダーの正規化ルールは以下の通りです。

  • 各単語の最初の文字(ハイフンで区切られた単語も含む)は大文字にする。
  • それ以外の文字は小文字にする。
  • 例: content-type -> Content-Type, user-agent -> User-Agent, ACCEPT-ENCODING -> Accept-Encoding

このコミットでは、net/textproto パッケージが提供する CanonicalMIMEHeaderKey 関数がこの正規化ルールに従って文字列を変換します。

2. Go言語における文字列とメモリ割り当て

Go言語において、文字列は不変(immutable)な値です。これは、一度作成された文字列の内容は変更できないことを意味します。文字列操作(結合、部分文字列の抽出、変換など)を行うと、多くの場合、新しい文字列がメモリに割り当てられます。

例えば、strings.ToLower("HELLO") のような操作は、新しい小文字の文字列 "hello" をヒープに割り当てます。このような頻繁な文字列割り当ては、特にパフォーマンスが要求されるネットワーク処理において、ガベージコレクション(GC)の頻度を増加させ、アプリケーションのレイテンシやスループットに悪影響を与える可能性があります。

3. 文字列のインターニング (String Interning) / 共通文字列の再利用

文字列のインターニングとは、プログラム内で同じ内容を持つ文字列が複数回出現する場合に、それらをメモリ上で単一のインスタンスとして管理する最適化手法です。これにより、メモリ使用量を削減し、文字列の比較をポインタ比較(アドレス比較)で行えるため高速化できます。

このコミットで採用されているのは、厳密な意味でのインターニング(全ての文字列を対象とする)ではありませんが、それに近い「共通文字列の再利用」という概念です。つまり、MIMEヘッダーキーのように、出現頻度が高く、種類が限られている文字列については、あらかじめ正規化された形式の文字列インスタンスを静的に定義しておき、実行時に正規化されたヘッダーキーがそのリストに含まれる場合は、リスト内の既存のインスタンスを返すことで、新規の文字列割り当てを回避します。

これにより、ヒープ割り当てが減少し、ガベージコレクションの負担が軽減され、全体的なパフォーマンスが向上します。

4. net/textproto パッケージ

net/textproto パッケージは、Go言語の標準ライブラリの一部であり、テキストベースのネットワークプロトコル(HTTP、SMTP、NNTPなど)を解析するための低レベルな機能を提供します。このパッケージは、行指向のプロトコルメッセージの読み書き、ヘッダーの解析、MIMEヘッダーの正規化などのユーティリティを提供します。

Reader 型は、bufio.Reader をラップし、プロトコル固有の読み取り操作(例: ReadLine, ReadMIMEHeader)を提供します。MIMEHeader 型は、map[string][]string のエイリアスであり、MIMEヘッダーのキーと値のペアを表現します。

このコミットで変更される CanonicalMIMEHeaderKey および canonicalMIMEHeaderKey 関数は、ReadMIMEHeader メソッドが内部で呼び出し、読み込んだヘッダーキーを正規化するために使用されます。

技術的詳細

このコミットの主要な技術的変更点は、src/pkg/net/textproto/reader.go 内の canonicalMIMEHeaderKey 関数に、commonHeaders というグローバルな文字列スライスを導入し、これを利用してヘッダーキーの正規化と文字列割り当ての最適化を行う点です。

commonHeaders スライス

新しく追加された commonHeaders は、Goのソースコード内に静的に定義された []string 型のスライスです。このスライスには、HTTP/MIMEプロトコルで一般的に使用されるヘッダーキーが、すでに正規化された形式(例: "Accept", "Content-Type", "User-Agent")で格納されています。

var commonHeaders = []string{
	"Accept",
	"Accept-Charset",
	"Accept-Encoding",
	// ... (他の一般的なヘッダー)
	"User-Agent",
	// ...
}

このスライスは、以下の重要な特性を持っています。

  1. 正規化済み: 格納されている全ての文字列は、MIMEヘッダーの正規化ルールに従って大文字・小文字が適切に処理されています。
  2. ソート済み: スライス内の文字列はアルファベット順にソートされています。これは、後述する効率的な検索アルゴリズム(二分探索に似た手法)を可能にするために不可欠です。
  3. 不変: プログラムの実行中にこのスライスの内容が変更されることはありません。

canonicalMIMEHeaderKey 関数の変更

canonicalMIMEHeaderKey 関数は、ReadMIMEHeader メソッドによって内部的に呼び出され、読み込んだヘッダーキーのバイトスライスを受け取り、それを正規化された文字列に変換します。この関数は、パフォーマンス最適化のために、入力のバイトスライスを直接変更する(mutate)ことが許されています。

変更後の canonicalMIMEHeaderKey の動作は以下のようになります。

  1. インプレース正規化:

    • 入力されたバイトスライス a を、MIMEヘッダーの正規化ルールに従ってインプレースで変更します。
    • 具体的には、各文字を走査し、必要に応じて大文字・小文字を変換します。ハイフン (-) の後の文字や、文字列の最初の文字は大文字に、それ以外は小文字に変換されます。
    • スペース ( ) が見つかった場合は、ハイフン (-) に変換されます(例: "Content Type" -> "Content-Type")。
    • この処理はASCII文字のみを対象とし、非ASCII文字は変更されません。
  2. commonHeaders を利用した最適化:

    • 正規化処理と並行して、commonHeaders スライスに対する「二分探索に似た」範囲絞り込みを行います。
    • lohi という2つのインデックスを維持し、現在の文字 c と比較しながら、commonHeaders 内で a と一致する可能性のある文字列の範囲を絞り込みます。
    • この絞り込みは、各文字を処理するたびに行われます。例えば、a[i]C であれば、commonHeaders 内で C で始まる文字列の範囲に lohi を絞り込みます。
    • 全ての文字の正規化が完了した後、lohi の範囲が有効であり、かつ commonHeaders[lo] の長さが正規化されたバイトスライス a の長さと一致する場合、それは commonHeaders[lo]a の正規化された形式と完全に一致することを示します。
    • この場合、新規に文字列を割り当てることなく、commonHeaders[lo] に格納されている既存の文字列インスタンスを返します。
  3. 新規文字列割り当て:

    • もし commonHeaders 内に一致する文字列が見つからなかった場合(つまり、ヘッダーキーが一般的でない場合)、正規化されたバイトスライス a から新しい文字列を生成し、それを返します (string(a))。この場合でも、正規化処理自体はインプレースで行われているため、従来のバージョンと比較して効率的です。

ベンチマークの改善

この最適化により、ベンチマーク結果が大幅に改善されました。

  • BenchmarkReadMIMEHeader: 複数の一般的なヘッダーを含むMIMEヘッダー全体を読み取るシナリオ。このベンチマークでは、多くのヘッダーキーが commonHeaders から再利用されるため、新規割り当てが減少し、処理時間が大幅に短縮されました。
  • BenchmarkUncommon: 一般的でない単一のヘッダーを読み取るシナリオ。この場合、commonHeaders からの再利用は発生しませんが、インプレースでの正規化処理自体が効率的であるため、処理時間は改善されています。メモリ割り当ては変わっていませんが、これは元々新規割り当てが発生するケースであるため想定通りです。

このアプローチは、Goのランタイムが文字列のインターニングを自動的に行わないため、特定のホットパス(頻繁に実行されるコードパス)において手動で文字列の再利用を促進する典型的な最適化手法と言えます。

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

src/pkg/net/textproto/reader.go

--- a/src/pkg/net/textproto/reader.go
+++ b/src/pkg/net/textproto/reader.go
@@ -486,6 +486,7 @@ func (r *Reader) ReadMIMEHeader() (MIMEHeader, error) {
 // letter and any letter following a hyphen to upper case;
 // the rest are converted to lowercase.  For example, the
 // canonical key for "accept-encoding" is "Accept-Encoding".
+// MIME header keys are assumed to be ASCII only.
 func CanonicalMIMEHeaderKey(s string) string {
 	// Quick check for canonical encoding.
 	upper := true
@@ -502,28 +503,90 @@ func CanonicalMIMEHeaderKey(s string) string {
 	return s
 }
 
+const toLower = 'a' - 'A'
+
 // canonicalMIMEHeaderKey is like CanonicalMIMEHeaderKey but is
 // allowed to mutate the provided byte slice before returning the
 // string.
 func canonicalMIMEHeaderKey(a []byte) string {
-	// Canonicalize: first letter upper case
-	// and upper case after each dash.
-	// (Host, User-Agent, If-Modified-Since).
-	// MIME headers are ASCII only, so no Unicode issues.
 	upper := true
-	for i, v := range a {
-		if v == ' ' {
+	lo := 0
+	hi := len(commonHeaders)
+	for i := 0; i < len(a); i++ {
+		// Canonicalize: first letter upper case
+		// and upper case after each dash.
+		// (Host, User-Agent, If-Modified-Since).
+		// MIME headers are ASCII only, so no Unicode issues.
+		if a[i] == ' ' {
 			a[i] = '-'
 			upper = true
 			continue
 		}
-		if upper && 'a' <= v && v <= 'z' {
-			a[i] = v + 'A' - 'a'
+		c := a[i]
+		if upper && 'a' <= c && c <= 'z' {
+			c -= toLower
+		} else if !upper && 'A' <= c && c <= 'Z' {
+			c += toLower
 		}
-		if !upper && 'A' <= v && v <= 'Z' {
-			a[i] = v + 'a' - 'A'
+		a[i] = c
+		upper = c == '-' // for next time
+
+		if lo < hi {
+			for lo < hi && (len(commonHeaders[lo]) <= i || commonHeaders[lo][i] < c) {
+				lo++
+			}
+			for hi > lo && commonHeaders[hi-1][i] > c {
+				hi--
+			}
 		}
-		upper = v == '-'
 	}
+	if lo < hi && len(commonHeaders[lo]) == len(a) {
+		return commonHeaders[lo]
+	}
 	return string(a)
 }
 
+var commonHeaders = []string{
+	"Accept",
+	"Accept-Charset",
+	"Accept-Encoding",
+	"Accept-Language",
+	"Accept-Ranges",
+	"Cache-Control",
+	"Cc",
+	"Connection",
+	"Content-Id",
+	"Content-Language",
+	"Content-Length",
+	"Content-Transfer-Encoding",
+	"Content-Type",
+	"Date",
+	"Dkim-Signature",
+	"Etag",
+	"Expires",
+	"From",
+	"Host",
+	"If-Modified-Since",
+	"If-None-Match",
+	"In-Reply-To",
+	"Last-Modified",
+	"Location",
+	"Message-Id",
+	"Mime-Version",
+	"Pragma",
+	"Received",
+	"Return-Path",
+	"Server",
+	"Set-Cookie",
+	"Subject",
+	"To",
+	"User-Agent",
+	"Via",
+	"X-Forwarded-For",
+	"X-Imforwards",
+	"X-Powered-By",
+}

src/pkg/net/textproto/reader_test.go

--- a/src/pkg/net/textproto/reader_test.go
+++ b/src/pkg/net/textproto/reader_test.go
@@ -24,6 +24,7 @@ var canonicalHeaderKeyTests = []canonicalHeaderKeyTest{\n 	{"uSER-aGENT", "User-Agent"},\n 	{"user-agent", "User-Agent"},\n 	{"USER-AGENT", "User-Agent"},\n+\t{"üser-agenT", "üser-Agent"}, // non-ASCII unchanged\n }\n \n func TestCanonicalMIMEHeaderKey(t *testing.T) {\n@@ -241,18 +242,94 @@ func TestRFC959Lines(t *testing.T) {\n \t}\n }\n \n+func TestCommonHeaders(t *testing.T) {\n+\t// need to disable the commonHeaders-based optimization\n+\t// during this check, or we'd not be testing anything\n+\toldch := commonHeaders\n+\tcommonHeaders = []string{}\n+\tdefer func() { commonHeaders = oldch }()\n+\n+\tlast := ""\n+\tfor _, h := range oldch {\n+\t\tif last > h {\n+\t\t\tt.Errorf("%v is out of order", h)\n+\t\t}\n+\t\tif last == h {\n+\t\t\tt.Errorf("%v is duplicated", h)\n+\t\t}\n+\t\tif canon := CanonicalMIMEHeaderKey(h); h != canon {\n+\t\t\tt.Errorf("%v is not canonical", h)\n+\t\t}\n+\t\tlast = h\n+\t}\n+}\n+\n+var clientHeaders = strings.Replace(`Host: golang.org\n+Connection: keep-alive\n+Cache-Control: max-age=0\n+Accept: application/xml,application/xhtml+xml,text/html;q=0.9,text/plain;q=0.8,image/png,*/*;q=0.5\n+User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US) AppleWebKit/534.3 (KHTML, like Gecko) Chrome/6.0.472.63 Safari/534.3\n+Accept-Encoding: gzip,deflate,sdch\n+Accept-Language: en-US,en;q=0.8,fr-CH;q=0.6\n+Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.3\n+COOKIE: __utma=000000000.0000000000.0000000000.0000000000.0000000000.00; __utmb=000000000.0.00.0000000000; __utmc=000000000; __utmz=000000000.0000000000.00.0.utmcsr=code.google.com|utmccn=(referral)|utmcmd=referral|utmcct=/p/go/issues/detail\n+Non-Interned: test\n+\n+`, "\\n", "\\r\\n", -1)\n+\n+var serverHeaders = strings.Replace(`Content-Type: text/html; charset=utf-8\n+Content-Encoding: gzip\n+Date: Thu, 27 Sep 2012 09:03:33 GMT\n+Server: Google Frontend\n+Cache-Control: private\n+Content-Length: 2298\n+VIA: 1.1 proxy.example.com:80 (XXX/n.n.n-nnn)\n+Connection: Close\n+Non-Interned: test\n+\n+`, "\\n", "\\r\\n", -1)\n+\n func BenchmarkReadMIMEHeader(b *testing.B) {\n 	var buf bytes.Buffer\n 	br := bufio.NewReader(&buf)\n 	r := NewReader(br)\n 	for i := 0; i < b.N; i++ {\n-\t\tbuf.WriteString("User-Agent: not mozilla\\r\\nContent-Length: 23452\\r\\nContent-Type: text/html; charset-utf8\\r\\nFoo-Bar: foobar\\r\\nfoo-bar: some more string\\r\\n\\r\\n")\n+\t\tvar want int\n+\t\tvar find string\n+\t\tif (i & 1) == 1 {\n+\t\t\tbuf.WriteString(clientHeaders)\n+\t\t\twant = 10\n+\t\t\tfind = "Cookie"\n+\t\t} else {\n+\t\t\tbuf.WriteString(serverHeaders)\n+\t\t\twant = 9\n+\t\t\tfind = "Via"\n+\t\t}\n+\t\th, err := r.ReadMIMEHeader()\n+\t\tif err != nil {\n+\t\t\tb.Fatal(err)\n+\t\t}\n+\t\tif len(h) != want {\n+\t\t\tb.Fatalf("wrong number of headers: got %d, want %d", len(h), want)\n+\t\t}\n+\t\tif _, ok := h[find]; !ok {\n+\t\t\tb.Fatalf("did not find key %s", find)\n+\t\t}\n+\t}\n+}\n+\n+func BenchmarkUncommon(b *testing.B) {\n+\tvar buf bytes.Buffer\n+\tbr := bufio.NewReader(&buf)\n+\tr := NewReader(br)\n+\tfor i := 0; i < b.N; i++ {\n+\t\tbuf.WriteString("uncommon-header-for-benchmark: foo\\r\\n\\r\\n")\n \t\th, err := r.ReadMIMEHeader()\n \t\tif err != nil {\n \t\t\tb.Fatal(err)\n \t\t}\n-\t\tif len(h) != 4 {\n-\t\t\tb.Fatalf("want 4")\n+\t\tif _, ok := h["Uncommon-Header-For-Benchmark"]; !ok {\n+\t\t\tb.Fatal("Missing result header.")\n \t\t}\n \t}\n }

コアとなるコードの解説

src/pkg/net/textproto/reader.go

  1. commonHeaders 変数の追加:

    • var commonHeaders = []string{...}: このグローバル変数は、MIMEヘッダーキーとして頻繁に出現する文字列の正規化された形式を事前に定義しています。このリストはアルファベット順にソートされており、これが後の検索最適化の鍵となります。
  2. canonicalMIMEHeaderKey 関数の変更:

    • const toLower = 'a' - 'A': 小文字から大文字への変換、またはその逆の変換を効率的に行うための定数です。
    • lo := 0, hi := len(commonHeaders): commonHeaders スライス内で、正規化中のヘッダーキーと一致する可能性のある範囲を追跡するためのインデックスです。これは二分探索の概念に似ています。
    • for i := 0; i < len(a); i++: 入力バイトスライス a の各文字をループで処理します。
    • インプレース正規化:
      • if a[i] == ' ': スペースをハイフンに変換します。
      • if upper && 'a' <= c && c <= 'z': upper フラグが true(単語の最初の文字またはハイフンの後の文字)で、かつ小文字であれば、大文字に変換します。
      • else if !upper && 'A' <= c && c <= 'Z': upper フラグが false(単語の途中の文字)で、かつ大文字であれば、小文字に変換します。
      • a[i] = c: 変換された文字をバイトスライスに書き戻します。
      • upper = c == '-': 次の文字が単語の最初になるかどうかを判断するために upper フラグを更新します。
    • commonHeaders 検索の絞り込み:
      • if lo < hi: commonHeaders 内の検索範囲がまだ有効な場合にのみ実行されます。
      • for lo < hi && (len(commonHeaders[lo]) <= i || commonHeaders[lo][i] < c): lo インデックスを前進させます。これは、commonHeaders[lo] の長さが現在の文字インデックス i 以下であるか、または commonHeaders[lo]i 番目の文字が現在の文字 c よりも小さい場合、その文字列は一致しないためスキップします。
      • for hi > lo && commonHeaders[hi-1][i] > c: hi インデックスを後退させます。これは、commonHeaders[hi-1]i 番目の文字が現在の文字 c よりも大きい場合、その文字列は一致しないためスキップします。
      • この2つのループにより、lohi の間の範囲が、現在の文字 c で始まる可能性のある commonHeaders 内の文字列に絞り込まれます。
    • 結果の返却:
      • if lo < hi && len(commonHeaders[lo]) == len(a): ループが終了した後、lohi の範囲が有効であり、かつ commonHeaders[lo] の長さが正規化された a の長さと完全に一致する場合、これは commonHeaders[lo] が正規化されたヘッダーキーと一致することを示します。この場合、新規割り当てを避けるために commonHeaders[lo] を返します。
      • return string(a): 一致する共通ヘッダーが見つからなかった場合、正規化されたバイトスライス a から新しい文字列を生成して返します。

src/pkg/net/textproto/reader_test.go

  1. canonicalHeaderKeyTests の追加テストケース:

    • {"üser-agenT", "üser-Agent"}: 非ASCII文字を含むヘッダーキーが正規化されないことを確認するテストケースです。これは、CanonicalMIMEHeaderKey がASCII文字のみを対象としているという仕様を明確にするものです。
  2. TestCommonHeaders 関数の追加:

    • このテストは、commonHeaders スライス自体の整合性を検証します。
    • テスト中は、commonHeaders を一時的に空のスライスに置き換えることで、canonicalMIMEHeaderKey の最適化ロジックがテストに影響を与えないようにしています。
    • commonHeaders がアルファベット順にソートされているか、重複がないか、そして各エントリが実際に正規化された形式であるかを確認します。
  3. ベンチマークテストの改善:

    • BenchmarkReadMIMEHeaderBenchmarkUncommon の両方で、より現実的なヘッダーセット(clientHeadersserverHeaders)を使用するように変更されました。これにより、ベンチマーク結果が実際の使用シナリオをより正確に反映するようになりました。
    • 特に BenchmarkReadMIMEHeader では、クライアントとサーバーのヘッダーを交互に読み込むことで、キャッシュの挙動なども考慮したより堅牢なテストになっています。

これらの変更により、net/textproto パッケージは、MIMEヘッダーの処理において、より高速かつメモリ効率の良い動作を実現しています。

関連リンク

参考にした情報源リンク

  • Go言語のソースコード (特に src/pkg/net/textproto/reader.go および src/pkg/net/textproto/reader_test.go)
  • Go言語の公式ドキュメント
  • RFC 2616 および RFC 2045 (MIMEヘッダーと正規化に関する標準仕様)
  • Go言語における文字列の不変性とメモリ管理に関する一般的な知識