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

このコミットは、Go言語の標準ライブラリである net/http パッケージ内の HeaderWriteSubset 関数におけるメモリ割り当てを削減することを目的としています。具体的には、HTTPヘッダーをワイヤーフォーマットで書き出す際に発生していた不要なメモリ割り当てを排除し、パフォーマンスを向上させています。

コミット

commit a30bede5ef81fd90b4792e97707d264cc6a3cf1a
Author: Brad Fitzpatrick <bradfitz@golang.org>
Date:   Wed Mar 6 14:10:47 2013 -0800

    net/http: remove allocations in HeaderWriteSubset
    
    Before:
    BenchmarkHeaderWriteSubset  500000  2354 ns/op  197 B/op  2 allocs/op
    After:
    BenchmarkHeaderWriteSubset 1000000  2085 ns/op    0 B/op  0 allocs/op
    
    Fixes #3761
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/7508043

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

https://github.com/golang/go/commit/a30bede5ef81fd90b4792e97707d264cc6a3cf1a

元コミット内容

net/http: remove allocations in HeaderWriteSubset

このコミットは、HeaderWriteSubset 関数におけるメモリ割り当てを削除します。

変更前: BenchmarkHeaderWriteSubset 500000 2354 ns/op 197 B/op 2 allocs/op

変更後: BenchmarkHeaderWriteSubset 1000000 2085 ns/op 0 B/op 0 allocs/op

Issue #3761 を修正します。

変更の背景

この変更の背景には、Go言語のHTTPサーバーにおけるパフォーマンス最適化の取り組みがあります。特に、HTTPヘッダーの書き出しは、リクエストごとに頻繁に実行される操作であり、ここでのわずかなメモリ割り当てや処理時間の増加が、高負荷な環境下では大きなオーバーヘッドとなる可能性があります。

元の実装では、HTTPヘッダーをソートして書き出す際に、ソート用のスライスを毎回新しく作成していました。これにより、ベンチマーク結果が示すように、HeaderWriteSubset の呼び出しごとに197バイトのメモリが2回割り当てられていました。これは、ガベージコレクションの頻度を増加させ、全体的なパフォーマンスに悪影響を与える可能性があります。

このコミットは、この不要なメモリ割り当てを排除し、HeaderWriteSubset の実行をより効率的にすることで、HTTPサーバーの応答性能とスループットを向上させることを目的としています。コミットメッセージに記載されているベンチマーク結果は、この最適化が成功し、メモリ割り当てがゼロになったことを明確に示しています。

前提知識の解説

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

Go言語は、自動メモリ管理（ガベージコレクション、GC）を採用しています。開発者は明示的にメモリを解放する必要はありませんが、不要なメモリ割り当てを減らすことは、GCの負荷を軽減し、アプリケーションのパフォーマンスを向上させる上で非常に重要です。

割り当て (Allocation): プログラムが実行時にメモリを要求する操作です。Goでは make や new、あるいはスライスやマップへの要素追加などで発生します。
ガベージコレクション (Garbage Collection): 不要になったメモリを自動的に回収するプロセスです。割り当てられたメモリが増えれば増えるほど、GCが実行される頻度や時間が長くなり、アプリケーションの実行が一時的に停止する（ストップ・ザ・ワールド）可能性があります。

このコミットの目的は、HeaderWriteSubset 関数におけるメモリ割り当てをゼロにすることで、GCの負担を軽減し、関数の実行速度を向上させることです。

`sort.Interface` インターフェース

Go言語の sort パッケージは、任意のデータ構造をソートするための汎用的なインターフェース sort.Interface を提供しています。このインターフェースは以下の3つのメソッドを定義しています。

Len() int: ソート対象の要素数を返します。
Swap(i, j int): インデックス i と j の要素を入れ替えます。
Less(i, j int) bool: インデックス i の要素がインデックス j の要素よりも小さい場合に true を返します。

このインターフェースを実装することで、sort.Sort() 関数を使ってカスタムデータ型をソートできます。

オブジェクトプーリング（sync.Poolの概念）

オブジェクトプーリングは、頻繁に生成・破棄されるオブジェクトを再利用することで、メモリ割り当てとガベージコレクションのオーバーヘッドを削減する最適化手法です。Go言語では、sync.Pool パッケージがこの機能を提供しています。

このコミットでは、sync.Pool を直接使用しているわけではありませんが、同様の概念で headerSorterCache というチャネルを使って headerSorter オブジェクトを再利用しています。これにより、ソートに必要な headerSorter インスタンスを毎回 new で作成するのではなく、キャッシュから取得し、使用後にキャッシュに戻すことで、メモリ割り当てを回避しています。

技術的詳細

このコミットの主要な変更点は、HTTPヘッダーのキーと値のペアをソートする際に、headerSorter という新しい型を導入し、そのインスタンスを再利用するメカニズムを導入したことです。

変更前は、Header 型の sortedKeyValues メソッドが呼ばれるたびに、byKey 型（sort.Interface を実装したスライス型）の新しいインスタンスが作成され、ソートが行われていました。この byKey 型のインスタンス作成がメモリ割り当ての原因となっていました。

変更後では、以下の点が改善されています。

headerSorter 型の導入: headerSorter は、sort.Interface を実装する新しい構造体です。この構造体は、ソート対象の []keyValues スライスをフィールドとして持ちます。
```
type headerSorter struct {
	kvs []keyValues
}

func (s *headerSorter) Len() int           { return len(s.kvs) }
func (s *headerSorter) Swap(i, j int)      { s.kvs[i], s.kvs[j] = s.kvs[j], s.kvs[i] }
func (s *headerSorter) Less(i, j int) bool { return s.kvs[i].key < s.kvs[j].key }
```
重要なのは、headerSorter がポインタとして使用されることです。これにより、sort.Interface インターフェースの値にフィットさせる際に、追加の割り当てなしで済むようになります。
headerSorterCache の導入: headerSorter のインスタンスを再利用するために、headerSorterCache というチャネルが導入されました。
```
var headerSorterCache = make(chan *headerSorter, 8)
```
これは、最大8つの headerSorter インスタンスをキャッシュできるバッファ付きチャネルです。
sortedKeyValues メソッドの変更: Header 型の sortedKeyValues メソッドは、headerSorterCache から headerSorter インスタンスを取得するように変更されました。
```
func (h Header) sortedKeyValues(exclude map[string]bool) (kvs []keyValues, hs *headerSorter) {
	select {
	case hs = <-headerSorterCache: // キャッシュから取得を試みる
	default:
		hs = new(headerSorter) // キャッシュが空なら新しく作成
	}
	// ...
	hs.kvs = kvs // ソート対象のスライスをセット
	sort.Sort(hs) // headerSorter を使ってソート
	return kvs, hs
}
```
この変更により、ほとんどの場合、新しい headerSorter インスタンスを割り当てる必要がなくなります。また、hs.kvs の容量が足りない場合は、新しいスライスが作成されますが、これはヘッダーのサイズが非常に大きい場合にのみ発生します。
WriteSubset メソッドの変更: WriteSubset メソッドは、sortedKeyValues から返された headerSorter インスタンスを、処理後に headerSorterCache に戻すように変更されました。
```
func (h Header) WriteSubset(w io.Writer, exclude map[string]bool) error {
	// ...
	kvs, sorter := h.sortedKeyValues(exclude)
	// ...
	select {
	case headerSorterCache <- sorter: // キャッシュに戻す
	default:
		// キャッシュが満杯の場合は何もしない（ガベージコレクタに任せる）
	}
	return nil
}
```
これにより、headerSorter インスタンスが再利用可能になり、次の HeaderWriteSubset 呼び出しで再割り当てを回避できます。

これらの変更により、HeaderWriteSubset 関数が呼び出されるたびに発生していた headerSorter の割り当てがほぼなくなり、ベンチマーク結果が示すように、メモリ割り当てがゼロになりました。

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

`src/pkg/net/http/header.go`

--- a/src/pkg/net/http/header.go
+++ b/src/pkg/net/http/header.go
@@ -103,21 +103,41 @@ type keyValues struct {
 	values []string
 }
 
-type byKey []keyValues
-
-func (s byKey) Len() int           { return len(s) }
-func (s byKey) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
-func (s byKey) Less(i, j int) bool { return s[i].key < s[j].key }
-
-func (h Header) sortedKeyValues(exclude map[string]bool) []keyValues {
-\tkvs := make([]keyValues, 0, len(h))\n+// A headerSorter implements sort.Interface by sorting a []keyValues
+// by key. It's used as a pointer, so it can fit in a sort.Interface
+// interface value without allocation.
+type headerSorter struct {
+\tkvs []keyValues
+}
+
+func (s *headerSorter) Len() int           { return len(s.kvs) }
+func (s *headerSorter) Swap(i, j int)      { s.kvs[i], s.kvs[j] = s.kvs[j], s.kvs[i] }
+func (s *headerSorter) Less(i, j int) bool { return s.kvs[i].key < s.kvs[j].key }
+
+// TODO: convert this to a sync.Cache (issue 4720)
+var headerSorterCache = make(chan *headerSorter, 8)
+
+// sortedKeyValues returns h's keys sorted in the returned kvs
+// slice. The headerSorter used to sort is also returned, for possible
+// return to headerSorterCache.
+func (h Header) sortedKeyValues(exclude map[string]bool) (kvs []keyValues, hs *headerSorter) {
+\tselect {
+\tcase hs = <-headerSorterCache:
+\tdefault:
+\t\ths = new(headerSorter)
+\t}\n+\tif cap(hs.kvs) < len(h) {
+\t\ths.kvs = make([]keyValues, 0, len(h))
+\t}\n+\tkvs = hs.kvs[:0]
 \tfor k, vv := range h {\n \t\tif !exclude[k] {\n \t\t\tkvs = append(kvs, keyValues{k, vv})\n \t\t}\n \t}\n-\tsort.Sort(byKey(kvs))\n-\treturn kvs
+\ths.kvs = kvs
+\tsort.Sort(hs)
+\treturn kvs, hs
 }
 
 // WriteSubset writes a header in wire format.
@@ -127,7 +147,8 @@ func (h Header) WriteSubset(w io.Writer, exclude map[string]bool) error {\n \tif !ok {\n \t\tws = stringWriter{w}\n \t}\n-\tfor _, kv := range h.sortedKeyValues(exclude) {\n+\tkvs, sorter := h.sortedKeyValues(exclude)\n+\tfor _, kv := range kvs {\n \t\tfor _, v := range kv.values {\n \t\t\tv = headerNewlineToSpace.Replace(v)\n \t\t\tv = textproto.TrimString(v)\n@@ -138,6 +159,10 @@ func (h Header) WriteSubset(w io.Writer, exclude map[string]bool) error {\n \t\t\t}\n \t\t}\n \t}\n+\tselect {\n+\tcase headerSorterCache <- sorter:\n+\tdefault:\n+\t}\n \treturn nil
 }

`src/pkg/net/http/header_test.go`

--- a/src/pkg/net/http/header_test.go
+++ b/src/pkg/net/http/header_test.go
@@ -196,9 +196,7 @@ func TestHeaderWriteSubsetMallocs(t *testing.T) {\n \t\tbuf.Reset()\n \t\ttestHeader.WriteSubset(&buf, nil)\n \t})\n-\tif n > 1 {\n-\t\t// TODO(bradfitz,rsc): once we can sort without allocating,\n-\t\t// make this an error.  See http://golang.org/issue/3761\n-\t\t// t.Errorf(\"got %v allocs, want <= %v\", n, 1)\n+\tif n > 0 {\n+\t\tt.Errorf(\"mallocs = %d; want 0\", n)\n \t}\n }\

コアとなるコードの解説

`src/pkg/net/http/header.go` の変更

byKey 型の削除と headerSorter 型の追加:
- 以前は byKey という []keyValues のエイリアス型が sort.Interface を実装していました。この型はソートのたびに新しいスライスとして作成され、割り当てが発生していました。
- 新しく headerSorter 構造体が導入されました。これは kvs []keyValues フィールドを持ち、この構造体自体が sort.Interface を実装します。
- headerSorter をポインタとして扱うことで、インターフェース値にフィットさせる際の割り当てを回避しています。
headerSorterCache の導入:
- var headerSorterCache = make(chan *headerSorter, 8): headerSorter のインスタンスを再利用するためのバッファ付きチャネル（サイズ8）がグローバル変数として宣言されました。これにより、頻繁な new(headerSorter) の呼び出しを避けることができます。
Header.sortedKeyValues メソッドの変更:
- キャッシュからの取得: select ステートメントを使用して、まず headerSorterCache から既存の headerSorter インスタンスを取得しようとします。
```
select {
case hs = <-headerSorterCache:
default:
    hs = new(headerSorter)
}
```
  これにより、キャッシュに利用可能なインスタンスがあれば、新しい割り当てなしでそれを使用できます。キャッシュが空の場合のみ、new(headerSorter) で新しいインスタンスが作成されます。
- スライスの容量チェックと再利用:
```
if cap(hs.kvs) < len(h) {
    hs.kvs = make([]keyValues, 0, len(h))
}
kvs = hs.kvs[:0]
```
  取得した headerSorter の内部スライス hs.kvs の容量が、現在のヘッダーのキー数 (len(h)) よりも小さい場合、新しいスライスが作成されます。これは、非常に大きなヘッダーを処理する場合にのみ発生し、通常は既存の容量を再利用できます。kvs = hs.kvs[:0] は、既存のスライスの基盤配列を再利用しつつ、長さをゼロにリセットするイディオムです。これにより、新しいスライスヘッダーの割り当てを回避します。
- ソートの実行: sort.Sort(hs) を呼び出し、headerSorter インスタンス自体をソートインターフェースとして渡します。
- 戻り値の変更: (kvs []keyValues, hs *headerSorter) となり、ソートされたキーバリューのスライスと、使用した headerSorter インスタンスの両方を返すようになりました。
Header.WriteSubset メソッドの変更:
- sortedKeyValues の呼び出し: kvs, sorter := h.sortedKeyValues(exclude) となり、ソートされたキーバリューのスライスと、使用した headerSorter インスタンスの両方を受け取るようになりました。
- headerSorter のキャッシュへの返却: ヘッダーの書き出しが完了した後、使用した headerSorter インスタンスを headerSorterCache に戻します。
```
select {
case headerSorterCache <- sorter:
default:
}
```
  これにより、headerSorter インスタンスが再利用可能になり、次の呼び出しで割り当てを回避できます。キャッシュが満杯の場合は、インスタンスは単にガベージコレクタによって回収されます。

`src/pkg/net/http/header_test.go` の変更

ベンチマークテストの修正:
- TestHeaderWriteSubsetMallocs ベンチマークテストにおいて、以前は n > 1 でエラーとしていた条件が n > 0 に変更されました。これは、このコミットによってメモリ割り当てが完全にゼロになることを期待しているためです。
- コメントアウトされていた TODO と t.Errorf の行が削除され、新しい期待値 (want 0) が直接テストに反映されました。

これらの変更により、HeaderWriteSubset 関数は、HTTPヘッダーのソートと書き出しにおいて、ほとんどの場合にメモリ割り当てを発生させない、非常に効率的な処理を実現しています。

参考にした情報源リンク

Go言語の公式ドキュメント
Go言語のソースコード
Go言語のベンチマークに関する一般的な知識
オブジェクトプーリングの概念に関する一般的な知識
Go言語のガベージコレクションに関する一般的な知識
コミットメッセージに記載されている https://golang.org/cl/7508043 (Gerrit Code Review)
コミットメッセージに記載されている Fixes #3761 (Go issue tracker) - ただし、このIssueは古いものであり、現在のGitHubリポジトリでは直接見つけることができませんでした。

comemo