[インデックス 19050] ファイルの概要
このコミットは、Go言語の net/textproto パッケージにおけるMIMEヘッダーの正規化とインターニング処理を最適化するものです。特に、canonicalMIMEHeaderKey 関数が、map[string]string を利用して共通ヘッダーのルックアップを効率化するように変更されました。これにより、パフォーマンスが向上し、コードが簡素化されています。
コミット
commit 8072f46abdf5b2d3ed0ee7d691823b7fcdaa7c21
Author: Brad Fitzpatrick <bradfitz@golang.org>
Date: Mon Apr 7 10:39:24 2014 -0700
net/textproto: simplify common header interning
Takes advantage of CL 83740044, to optimize map[string] lookup
from []byte key.
Deletes code.
No conditional check for gccgo, since Ian plans to add this
to gccgo before GCC 4.10 (Go 1.3).
benchmark old ns/op new ns/op delta
BenchmarkReadMIMEHeader 6066 5086 -16.16%
benchmark old allocs new allocs delta
BenchmarkReadMIMEHeader 12 12 +0.00%
benchmark old bytes new bytes delta
BenchmarkReadMIMEHeader 1317 1317 +0.00%
Update #3512
LGTM=rsc
R=rsc, dave
CC=golang-codereviews, iant
https://golang.org/cl/84230043
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/8072f46abdf5b2d3ed0ee7d691823b7fcdaa7c21
元コミット内容
このコミットは、net/textproto パッケージ内の canonicalMIMEHeaderKey 関数を修正し、共通ヘッダーのインターニング処理を簡素化します。具体的には、以前の commonHeaders というソートされた文字列スライスを用いた線形探索に近いロジックを削除し、commonHeader という map[string]string を使用したルックアップに置き換えています。この変更は、[]byte から string キーへの map ルックアップを最適化する Go コンパイラの変更 (CL 83740044) を活用しています。結果として、BenchmarkReadMIMEHeader の実行時間が約16%改善されています。
変更の背景
この変更の主な背景は、net/textproto パッケージにおけるMIMEヘッダーの処理性能を向上させることです。特に、HTTPなどのプロトコルで頻繁に登場する共通ヘッダー（例: "Content-Type", "Host", "User-Agent"など）の正規化とインターニングの効率化が求められていました。
以前の実装では、canonicalMIMEHeaderKey 関数内で、入力されたバイトスライスを正規化した後、commonHeaders というソートされた文字列スライスに対して、二分探索に似たロジックで既存の共通ヘッダーを探していました。この方法は、文字列の比較とスライス内での探索に一定のコストがかかり、特にヘッダーの数が増えるにつれて性能が劣化する可能性がありました。
このコミットは、Goコンパイラに導入された新しい最適化 (CL 83740044) を活用することで、この問題を解決します。CL 83740044は、map[string] のルックアップにおいて、キーが []byte から string に変換される際に発生する余分なメモリ割り当てを回避するものです。この最適化により、[]byte を直接 string にキャストして map のキーとして使用しても、効率的なルックアップが可能になりました。
このコンパイラ最適化の恩恵を受けることで、commonHeaders スライスでの探索ロジックを、より高速な map[string]string ルックアップに置き換えることが可能になり、コードの簡素化と性能向上が同時に実現されました。
前提知識の解説
1. net/textproto パッケージ
net/textproto はGo言語の標準ライブラリの一部で、テキストベースのネットワークプロトコル（HTTP、SMTP、NNTPなど）を解析するための低レベルな機能を提供します。このパッケージは、ヘッダーの読み取り、行の読み取り、MIMEヘッダーの正規化など、プロトコル処理における共通のタスクを効率的に行うためのユーティリティを提供します。
2. ヘッダーのインターニング (Header Interning)
インターニングとは、プログラム内で同じ値を持つオブジェクトが複数存在する場合に、それらをメモリ上で単一のインスタンスとして共有する最適化手法です。文字列のインターニングは特に一般的で、同じ文字列リテラルや動的に生成された文字列が複数回出現する場合に、それらを同じメモリ上のアドレスにマッピングすることで、メモリ使用量を削減し、文字列比較のパフォーマンスを向上させます（ポインタ比較で済むため）。
MIMEヘッダーの場合、"Content-Type"や"Host"などのヘッダー名は、多くのリクエストやレスポンスで繰り返し使用されます。これらのヘッダー名をインターニングすることで、毎回新しい文字列オブジェクトを生成したり、文字列比較を繰り返したりするオーバーヘッドを削減できます。
3. Goコンパイラの map[string] ルックアップ最適化 (CL 83740044)
Go言語において、map のキーは通常 string 型です。しかし、ネットワークから読み取られるヘッダー名などは []byte 型で提供されることがよくあります。[]byte を map[string] のキーとして使用するには、通常 string(byteSlice) のように string 型に変換する必要があります。この変換は、新しい文字列オブジェクトをメモリに割り当てるため、パフォーマンスに影響を与える可能性があります。
CL 83740044 (Go CL 83740044, "cmd/gc, runtime: optimize map[string] lookup from []byte key") は、この問題に対処するためのGoコンパイラの最適化です。この変更により、コンパイラは m[string(byteSlice)] のようなパターンを特別に認識し、byteSlice の内容を新しい文字列にコピーすることなく、直接 map のルックアップを実行できるようになりました。これにより、余分なメモリ割り当てとコピーのオーバーヘッドが削減され、[]byte から string への変換を伴う map ルックアップが大幅に高速化されます。
4. gccgo と Go 1.3
gccgo は、GCC (GNU Compiler Collection) のフロントエンドとして実装されたGoコンパイラです。Go言語の公式コンパイラである gc とは異なる実装ですが、Go言語の仕様に準拠しています。コミットメッセージに「No conditional check for gccgo, since Ian plans to add this to gccgo before GCC 4.10 (Go 1.3)」とあるのは、この最適化が gc コンパイラだけでなく、gccgo にもGo 1.3のリリース（またはGCC 4.10のリリース）までに組み込まれる予定であることを示しています。これは、Goエコシステム全体でこの最適化が利用可能になることを意味します。
技術的詳細
このコミットの技術的な核心は、net/textproto パッケージの canonicalMIMEHeaderKey 関数における共通ヘッダーのインターニング戦略の変更です。
変更前:
変更前は、canonicalMIMEHeaderKey 関数は、入力された []byte スライスをMIMEヘッダーの正規形式（例: "content-length" -> "Content-Length"）に変換した後、commonHeaders というグローバルな []string スライスに対して、その正規化されたヘッダー名が存在するかどうかを探索していました。commonHeaders は事前にソートされており、探索は二分探索に似た効率的な方法で行われていました。もし見つかれば、commonHeaders 内の既存の文字列インスタンスを返していました。これは、メモリ割り当てを避けるためのインターニング手法でした。
しかし、この方法は以下の課題を抱えていました。
- 探索ロジックの複雑さ:
canonicalMIMEHeaderKey関数内に、正規化と同時にcommonHeadersを探索するための比較的複雑なループと条件分岐が含まれていました。 - パフォーマンスの限界: スライス内での探索は、
mapルックアップと比較して、特に要素数が多い場合にオーバーヘッドが大きくなる可能性があります。
変更後:
このコミットでは、commonHeaders スライスとその探索ロジックが完全に削除され、代わりに commonHeader という map[string]string が導入されました。この map は、init 関数内で一般的なMIMEヘッダー名をキーと値の両方として事前にロードされます。
canonicalMIMEHeaderKey 関数は、入力された []byte スライスを正規化する処理はそのまま維持します。しかし、正規化が完了した後、map[string]string である commonHeader に対して、string(a) (ここで a は正規化された []byte スライス) をキーとしてルックアップを行います。
この変更が機能する鍵は、前述の Goコンパイラの map[string] ルックアップ最適化 (CL 83740044) です。この最適化により、string(a) の部分で新しい文字列が割り当てられることなく、[]byte の内容を直接利用して map のルックアップが実行されます。もし map 内に一致するエントリが見つかれば、その map に格納されている既存の文字列インスタンスが返されます。見つからなければ、string(a) によって新しい文字列が作成され、それが返されます。
パフォーマンスへの影響: コミットメッセージに示されているベンチマーク結果は、この最適化の有効性を示しています。
BenchmarkReadMIMEHeader:old ns/op: 6066 ns/opnew ns/op: 5086 ns/opdelta: -16.16%
これは、MIMEヘッダーの読み取り処理が約16%高速化されたことを意味します。メモリ割り当て (allocs) とメモリ使用量 (bytes) は変化がないことから、この性能向上は主にCPUサイクル（ナノ秒あたりの操作数）の削減によるものであり、map ルックアップが以前の探索ロジックよりも効率的になったことを裏付けています。特に、[]byte から string への変換時の余分な割り当てが回避されているため、メモリ使用量が増加することなく性能が向上しています。
コアとなるコードの変更箇所
src/pkg/net/textproto/reader.go と src/pkg/net/textproto/reader_test.go の2つのファイルが変更されています。
--- a/src/pkg/net/textproto/reader.go
+++ b/src/pkg/net/textproto/reader.go
@@ -562,19 +562,12 @@ const toLower = 'a' - 'A'
// allowed to mutate the provided byte slice before returning the
// string.
func canonicalMIMEHeaderKey(a []byte) string {
- // Look for it in commonHeaders , so that we can avoid an
- // allocation by sharing the strings among all users
- // of textproto. If we don't find it, a has been canonicalized
- // so just return string(a).
upper := true
- lo := 0
- hi := len(commonHeaders)
- for i := 0; i < len(a); i++ {
+ for i, c := range a {
// 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.
- c := a[i]
if c == ' ' {
c = '-'
} else if upper && 'a' <= c && 'z' <= c {
@@ -584,60 +577,61 @@ func canonicalMIMEHeaderKey(a []byte) string {
}
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--
- }
- }
}
- if lo < hi && len(commonHeaders[lo]) == len(a) {
- return commonHeaders[lo]
+ // The compiler recognizes m[string(byteSlice)] as a special
+ // case, so a copy of a's bytes into a new string does not
+ // happen in this map lookup:
+ if v := commonHeader[string(a)]; v != "" {
+ return v
}
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",
- "Cookie",
- "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",
+// commonHeader interns common header strings.
+var commonHeader = make(map[string]string)
+
+func init() {
+ for _, v := range []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",
+ "Cookie",
+ "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",
+ } {
+ commonHeader[v] = v
+ }
+}
diff --git a/src/pkg/net/textproto/reader_test.go b/src/pkg/net/textproto/reader_test.go
index cc12912b63..cbc0ed183e 100644
--- a/src/pkg/net/textproto/reader_test.go
+++ b/src/pkg/net/textproto/reader_test.go
@@ -247,24 +247,20 @@ func TestRFC959Lines(t *testing.T) {
}
func TestCommonHeaders(t *testing.T) {
- // need to disable the commonHeaders-based optimization
- // during this check, or we'd not be testing anything
- oldch := commonHeaders
- commonHeaders = []string{}
- defer func() { commonHeaders = oldch }()
-
- last := ""
- for _, h := range oldch {
- if last > h {
- t.Errorf("%v is out of order", h)
- }
- if last == h {
- t.Errorf("%v is duplicated", h)
+ for h := range commonHeader {
+ if h != CanonicalMIMEHeaderKey(h) {
+ t.Errorf("Non-canonical header %q in commonHeader", h)
}
- if canon := CanonicalMIMEHeaderKey(h); h != canon {
- t.Errorf("%v is not canonical", h)
+ }
+ b := []byte("content-Length")
+ want := "Content-Length"
+ n := testing.AllocsPerRun(200, func() {
+ if x := canonicalMIMEHeaderKey(b); x != want {
+ t.Fatalf("canonicalMIMEHeaderKey(%q) = %q; want %q", b, x, want)
}
- last = h
+ })
+ if n > 0 {
+ t.Errorf("canonicalMIMEHeaderKey allocs = %v; want 0", n)
}
}
コアとなるコードの解説
src/pkg/net/textproto/reader.go の変更
-
canonicalMIMEHeaderKey関数の変更:- 削除されたコード: 以前の
commonHeadersスライスに対する探索ロジック（lo,hi変数とそれに続くforループ）が完全に削除されました。このロジックは、正規化されたヘッダー名がcommonHeaders内に存在するかどうかを効率的に見つけるためのものでした。 - 追加されたコード: 正規化処理の後に、以下の行が追加されました。
このコードは、正規化されたバイトスライス// The compiler recognizes m[string(byteSlice)] as a special // case, so a copy of a's bytes into a new string does not // happen in this map lookup: if v := commonHeader[string(a)]; v != "" { return v }aをstring(a)としてcommonHeaderマップのキーとして使用し、ルックアップを行います。前述のコンパイラ最適化により、このstring(a)変換でメモリ割り当てが発生しないことがコメントで明記されています。もしマップ内に対応するエントリが見つかれば（v != ""）、そのマップに格納されているインターニングされた文字列が返されます。見つからなければ、return string(a)によって新しい文字列が作成され、それが返されます。
- 削除されたコード: 以前の
-
commonHeadersスライスの削除とcommonHeaderマップの導入:- 以前の
var commonHeaders = []string{...}というソートされた文字列スライスが削除されました。 - 代わりに、
var commonHeader = make(map[string]string)というmap[string]string型の変数が導入されました。 init()関数が追加され、このinit()関数内で、以前commonHeadersに含まれていたすべての共通ヘッダー名がcommonHeaderマップにキーと値の両方として追加されます。これにより、マップが事前に共通ヘッダーで初期化され、高速なルックアップが可能になります。
- 以前の
src/pkg/net/textproto/reader_test.go の変更
TestCommonHeaders関数の変更:- 以前のテストコードは、
commonHeadersスライスを一時的に無効化し、その内容がソートされているか、重複がないか、正規化されているかをチェックしていました。 - 新しいテストコードは、
commonHeaderマップのキーがすべて正規化された形式であるかをチェックします。 - さらに重要な変更として、
canonicalMIMEHeaderKey関数が[]byteを受け取り、mapルックアップを行う際にメモリ割り当てが発生しないことを検証するベンチマークスタイルのテストが追加されました。
このテストは、b := []byte("content-Length") want := "Content-Length" n := testing.AllocsPerRun(200, func() { if x := canonicalMIMEHeaderKey(b); x != want { t.Fatalf("canonicalMIMEHeaderKey(%q) = %q; want %q", b, x, want) } }) if n > 0 { t.Errorf("canonicalMIMEHeaderKey allocs = %v; want 0", n) }"content-Length"というバイトスライスをcanonicalMIMEHeaderKeyに渡し、その結果が"Content-Length"であることを確認しつつ、この操作中にメモリ割り当てがゼロであることをtesting.AllocsPerRunを使って検証しています。これは、CL 83740044 の最適化が正しく機能していることを確認するための重要なテストです。
- 以前のテストコードは、
これらの変更により、net/textproto パッケージは、Goコンパイラの最新の最適化を活用し、MIMEヘッダーの処理をより効率的かつ簡潔に行えるようになりました。
関連リンク
- このコミットのGo CL: https://golang.org/cl/84230043
- 関連するGoコンパイラの最適化 (CL 83740044): https://go.googlesource.com/go/+/83740044
- 関連するGo Issue: https://golang.org/issue/3512