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

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

このコミットは、Go言語のランタイムにおけるマップ（map）の内部実装に関する最適化です。具体的には、新しく作成されるマップの最初のバケットテーブルのメモリ割り当てを遅延させることで、特に空のまま使用されるマップのメモリフットプリントと初期化コストを削減します。

コミット

commit 5b3ff61be63c87ff3e85609c774143b63e762f4b
Author: Brad Fitzpatrick <bradfitz@golang.org>
Date:   Wed Mar 27 16:28:51 2013 -0700

    runtime: allocate maps' first bucket table lazily
    
    Motivated by garbage profiling in HTTP benchmarks. This
    changes means new empty maps are just one small allocation
    (the HMap) instead the HMap + the relatively larger h->buckets
    allocation. This helps maps which remain empty throughout
    their life.
    
    benchmark               old ns/op    new ns/op    delta
    BenchmarkNewEmptyMap          196          107  -45.41%
    
    benchmark              old allocs   new allocs    delta
    BenchmarkNewEmptyMap            2            1  -50.00%
    
    benchmark               old bytes    new bytes    delta
    BenchmarkNewEmptyMap          195           50  -74.36%
    
    R=khr, golang-dev, r
    CC=golang-dev
    https://golang.org/cl/7722046

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

https://github.com/golang/go/commit/5b3ff61be63c87ff3e85609c774143b63e762f4b

元コミット内容

このコミットは、Goランタイムのマップ実装において、マップの最初のバケットテーブルのメモリ割り当てを遅延させる変更を導入しています。これにより、特にHTTPベンチマークにおけるガーベージプロファイリングで明らかになった、空のマップ作成時の不要なメモリ割り当てを削減します。

変更前は、新しい空のマップを作成する際に、マップのヘッダ構造（HMap）と、それに続く比較的大きなバケットテーブル（h->buckets）の両方がすぐに割り当てられていました。この変更により、空のマップはHMapのみの小さな割り当てで済むようになり、マップがその寿命を通じて空のままである場合に特に効果を発揮します。

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

  • BenchmarkNewEmptyMap (空のマップ作成):
    • 実行時間 (ns/op): 196 ns/op から 107 ns/op へ 45.41% 削減
    • メモリ割り当て回数 (allocs): 2回 から 1回 へ 50.00% 削減
    • 割り当てバイト数 (bytes): 195バイト から 50バイト へ 74.36% 削減

この最適化は、Goのランタイムパフォーマンス、特にメモリ使用量とガーベージコレクションの効率に大きく貢献します。

変更の背景

この変更の背景には、HTTPベンチマークにおけるガーベージプロファイリングがあります。HTTPサーバーのようなアプリケーションでは、リクエストごとに多数のマップが作成され、その中には一時的に使用されるだけで、ほとんど、あるいは全く要素が追加されないまま破棄されるものも少なくありません。

従来のGoのマップ実装では、make(map[K]V) のようにして新しいマップが作成されると、たとえそれが空であっても、マップのヘッダ構造（Hmap）に加えて、キーと値を格納するための最初のバケットテーブルがすぐに割り当てられていました。このバケットテーブルは、マップの初期容量に応じてサイズが決まりますが、たとえ空のマップであっても一定のメモリを消費します。

このような「空のマップ」が大量に作成されるシナリオでは、実際に使用されないバケットテーブルの割り当てが頻繁に発生し、これが不要なメモリ消費とガーベージコレクションの負荷増大につながっていました。特に、HTTPリクエスト処理のような高頻度でオブジェクトが生成・破棄される環境では、このオーバーヘッドが顕著になります。

このコミットは、この問題に対処し、空のマップ作成時のメモリ割り当てを最小限に抑えることで、全体的なパフォーマンスとリソース効率を向上させることを目的としています。

前提知識の解説

このコミットを理解するためには、以下のGo言語のランタイムとデータ構造に関する前提知識が必要です。

1. Goのマップ（map）の内部構造

Goのマップはハッシュテーブルとして実装されており、内部的にはいくつかのコンポーネントから構成されています。

  • Hmap 構造体: マップのメタデータ（要素数、ハッシュシード、バケットへのポインタなど）を保持するメインの構造体です。これはマップを作成した際に必ず割り当てられます。
  • バケット（bmap）: キーと値のペアを実際に格納する配列のような構造です。各バケットは通常、複数のキー/値ペアを保持できます。ハッシュ衝突が発生した場合に備えて、各バケットはオーバーフローバケットへのポインタを持つことがあります。
  • バケットテーブル: 複数のバケットをまとめた配列です。マップのサイズが大きくなると、このバケットテーブルのサイズも動的に拡張されます。

マップに要素を追加する際、Goランタイムはキーのハッシュ値を計算し、そのハッシュ値に基づいて適切なバケットに要素を配置します。

2. メモリ割り当てとガーベージコレクション（GC）

Goは自動メモリ管理（ガーベージコレクション）を採用しています。

  • runtime·mallocgc: Goランタイムがメモリを割り当てるために使用する内部関数です。この関数によって割り当てられたメモリは、GCの対象となります。
  • ガーベージコレクションの負荷: プログラムが頻繁に小さなオブジェクトを割り当て、すぐに解放する場合、GCはより頻繁に実行され、CPU時間を消費します。これは「GCのストップ・ザ・ワールド」と呼ばれる、アプリケーションの実行が一時停止する現象を引き起こす可能性があり、レイテンシに影響を与えます。
  • メモリフットプリント: プログラムが使用するメモリの総量です。不要なメモリ割り当てを減らすことは、メモリフットプリントを削減し、システムリソースの効率的な利用につながります。

3. ベンチマークとプロファイリング

  • ベンチマーク: 特定のコードのパフォーマンス（実行時間、メモリ使用量など）を測定するためのテストです。Goには標準でベンチマーク機能が組み込まれています（go test -bench .）。
  • プロファイリング: プログラムの実行中にリソース（CPU、メモリ、I/Oなど）がどのように消費されているかを詳細に分析する手法です。ガーベージプロファイリングは、メモリ割り当てとGCの動作に焦点を当てます。

4. nil ポインタと遅延初期化

  • nil ポインタ: Goにおけるゼロ値の一つで、ポインタが何も指していない状態を示します。
  • 遅延初期化（Lazy Initialization）: オブジェクトやリソースの初期化を、それが実際に必要になるまで遅らせるプログラミングパターンです。これにより、不要なリソースの割り当てを避け、起動時間やメモリ使用量を最適化できます。

これらの概念を理解することで、コミットがGoランタイムのどの部分に影響を与え、どのようなメリットをもたらすのかを深く把握できます。

技術的詳細

このコミットの技術的詳細を掘り下げると、Goランタイムのマップ実装（src/pkg/runtime/hashmap.c）におけるメモリ割り当て戦略の変更と、それに伴う関連関数の調整が中心となります。

1. hash_init 関数における遅延割り当て

Goのマップが make 関数によって初期化される際に呼び出されるのが hash_init 関数です。 変更前は、この関数内でマップのバケットテーブル（h->buckets）が常に runtime·mallocgc を使って割り当てられ、初期化されていました。

// 変更前 (簡略化)
buckets = runtime·mallocgc(bucketsize << B, 0, 1, 0);
for(i = 0; i < (uintptr)1 << B; i++) {
    b = (Bucket*)(buckets + i * bucketsize);
    clearbucket(b);
}

このコミットでは、B == 0 の場合（これはマップが非常に小さい、または初期容量がゼロであることを意味し、実質的に空のマップに相当します）に、バケットテーブルの割り当てをスキップし、buckets を nil に設定するように変更されました。

// 変更後 (簡略化)
if(B == 0) {
    // done lazily later.
    buckets = nil;
} else {
    buckets = runtime·mallocgc(bucketsize << B, 0, 1, 0);
    for(i = 0; i < (uintptr)1 << B; i++) {
        b = (Bucket*)(buckets + i * bucketsize);
        clearbucket(b);
    }
}

この変更により、make(map[int]int) のように空のマップを作成した場合、h->buckets は最初は nil となり、バケットテーブルのメモリ割り当ては行われません。

2. hash_insert 関数におけるオンデマンド割り当て

バケットテーブルの割り当てが遅延されたため、マップに最初の要素が挿入される際に、h->buckets が nil であれば、その時点でバケットテーブルを割り当てる必要があります。このロジックは hash_insert 関数に追加されました。

// hash_insert 内の追加ロジック
if(h->buckets == nil) {
    h->buckets = runtime·mallocgc(h->bucketsize, 0, 1, 0);
    b = (Bucket*)(h->buckets);
    clearbucket(b);
}

これにより、マップが空のまま使用される場合はバケットテーブルの割り当てが発生せず、要素が追加された場合にのみ必要なメモリが割り当てられるようになります。

3. nil バケットテーブルのハンドリング

h->buckets が nil になる可能性があるため、マップの検索 (hash_lookup)、削除 (hash_remove)、イテレータの初期化 (hash_iter_init) といった操作を行う関数でも、この新しい状態を適切にハンドリングする必要があります。

  • hash_lookup と hash_remove: マップが空 (h->count == 0) の場合、検索や削除の操作はすぐに終了し、nil バケットテーブルへのアクセスを避けるように変更されました。

    // hash_lookup および hash_remove 内の追加ロジック
if(h->count == 0)
    return nil; // または return;

  • hash_iter_init: イテレータを初期化する際、マップが空で h->buckets が nil の場合、イテレータがすぐに終了状態になるように it->wrapped = true が設定されます。

    // hash_iter_init 内の追加ロジック
if(h->buckets == nil) {
    // Empty map. Force next hash_next to exit without
    // evalulating h->bucket.
    it->wrapped = true;
}

  • hash_gciter_init: ガーベージコレクションのイテレータ初期化に関するコメントが更新され、空のマップでも h->buckets が nil になる可能性が考慮されました。

これらの変更により、Goのマップはより効率的なメモリ管理を実現し、特に空のマップが頻繁に作成されるシナリオでのパフォーマンスが大幅に向上しました。これは、Goのランタイムが継続的に最適化され、実世界のワークロード（HTTPサーバーなど）のプロファイリング結果に基づいて改善されている良い例です。

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

このコミットにおけるコアとなるコードの変更は、主にGoランタイムのマップ実装ファイルである src/pkg/runtime/hashmap.c に集中しています。

  1. src/pkg/runtime/hashmap.c:

    • hash_init 関数: マップの初期化時に、B == 0 (初期容量が非常に小さい、またはゼロ) の場合に、バケットテーブルの割り当てを遅延させ、h->buckets を nil に設定するロジックが追加されました。 
      --- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -255,10 +255,15 @@ hash_init(MapType *t, Hmap *h, uint32 hint)
 	// allocate initial hash table
 	// If hint is large zeroing this memory could take a while.
 	if(checkgc) mstats.next_gc = mstats.heap_alloc;
-	buckets = runtime·mallocgc(bucketsize << B, 0, 1, 0);
-	for(i = 0; i < (uintptr)1 << B; i++) {
-		b = (Bucket*)(buckets + i * bucketsize);
-		clearbucket(b);
+	if(B == 0) {
+		// done lazily later.
+		buckets = nil;
+	} else {
+		buckets = runtime·mallocgc(bucketsize << B, 0, 1, 0);
+		for(i = 0; i < (uintptr)1 << B; i++) {
+			b = (Bucket*)(buckets + i * bucketsize);
+			clearbucket(b);
+		}
 	}
 
 	// initialize Hmap
    • hash_lookup 関数: マップが空 (h->count == 0) の場合に、すぐに nil を返す最適化が追加されました。 
      --- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -485,6 +490,8 @@ hash_lookup(MapType *t, Hmap *h, byte **keyp)
 	key = *keyp;
 	if(docheck)
 		check(t, h);
+	if(h->count == 0)
+		return nil;
 	hash = h->hash0;
 	t->key->alg->hash(&hash, t->key->size, key);
 	bucket = hash & (((uintptr)1 << h->B) - 1);
    • hash_insert 関数: h->buckets が nil の場合に、最初のバケットテーブルを割り当てて初期化するロジックが追加されました。 
      --- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -572,6 +579,12 @@ hash_insert(MapType *t, Hmap *h, void *key, void *value)
 		check(t, h);
 	hash = h->hash0;
 	t->key->alg->hash(&hash, t->key->size, key);
+	if(h->buckets == nil) {
+		h->buckets = runtime·mallocgc(h->bucketsize, 0, 1, 0);
+		b = (Bucket*)(h->buckets);
+		clearbucket(b);
+	}
+\n  again:
 	bucket = hash & (((uintptr)1 << h->B) - 1);
 	if(h->oldbuckets != nil)
    • hash_remove 関数: マップが空 (h->count == 0) の場合に、すぐに処理を終了する最適化が追加されました。 
      --- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -659,6 +672,8 @@ hash_remove(MapType *t, Hmap *h, void *key)
 	
 	if(docheck)
 		check(t, h);
+	if(h->count == 0)
+		return;
 	hash = h->hash0;
 	t->key->alg->hash(&hash, t->key->size, key);
 	bucket = hash & (((uintptr)1 << h->B) - 1);
    • hash_iter_init 関数: h->buckets が nil の場合に、イテレータがすぐに終了状態になるように it->wrapped = true を設定するロジックが追加されました。 
      --- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -749,6 +764,12 @@ hash_iter_init(MapType *t, Hmap *h, struct hash_iter *it)
 
 	// Remember we have an iterator at this level.
 	h->flags |= Iterator;
+\n+	if(h->buckets == nil) {
+		// Empty map. Force next hash_next to exit without
+		// evalulating h->bucket.
+		it->wrapped = true;
+	}
 }\n         
 // initializes it->key and it->value to the next key/value pair
    • hash_gciter_init 関数: コメントが更新され、空のマップでのGCイテレータの挙動が明確化されました。 
      --- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -848,7 +869,7 @@ next:
 bool
 hash_gciter_init (Hmap *h, struct hash_gciter *it)
 {
-	// GC during map initialization
+	// GC during map initialization or on an empty map.
 	if(h->buckets == nil)
 		return false;
 \n

  2. src/pkg/runtime/map_test.go:

    • BenchmarkNewEmptyMap という新しいベンチマーク関数が追加されました。これは、空のマップを作成する際のパフォーマンスを測定するために使用されます。 
      --- a/src/pkg/runtime/map_test.go
+++ b/src/pkg/runtime/map_test.go
@@ -280,3 +280,10 @@ func TestEmptyKeyAndValue(t *testing.T) {
 		t.Errorf("empty key returned wrong value")
 	}
 }\n        +\n        +func BenchmarkNewEmptyMap(b *testing.B) {
+	b.ReportAllocs()
+	for i := 0; i < b.N; i++ {
+		_ = make(map[int]int)
+	}
+}\n        ```

これらの変更は、Goのマップがメモリを割り当てるタイミングと方法を根本的に変更し、特に空のマップの効率を大幅に向上させています。

コアとなるコードの解説

このコミットの核心は、Goのマップがその内部バケットテーブルをいつ、どのように割り当てるかという戦略の変更にあります。

1. hash_init における遅延割り当ての導入

Goで make(map[K]V) を呼び出して新しいマップを作成すると、ランタイムは hash_init 関数を呼び出してマップを初期化します。変更前は、この関数内でマップのヘッダ構造 (Hmap) が割り当てられた直後に、キーと値を格納するための最初のバケットテーブルもすぐに割り当てられていました。たとえマップが空のままであっても、このバケットテーブルは常に存在していました。

このコミットでは、この挙動が変更されました。hash_init 関数内で、マップの初期容量を示す内部パラメータ B が 0 の場合（これはマップが非常に小さい、または初期容量がゼロであることを意味し、実質的に空のマップに相当します）、バケットテーブルの割り当てをスキップし、マップの buckets フィールドを nil に設定するようになりました。

if(B == 0) {
    // done lazily later.
    buckets = nil;
} else {
    // ... 以前と同様にバケットを割り当てる ...
}

この変更により、空のマップを作成する際のメモリ割り当てが、Hmap 構造体のみに削減されます。これにより、メモリフットプリントが小さくなり、GCの対象となるオブジェクトの数が減るため、GCの負荷も軽減されます。

2. hash_insert におけるオンデマンド割り当て

buckets フィールドが nil になる可能性があるため、マップに最初の要素が挿入される際に、バケットテーブルがまだ割り当てられていない場合は、その場で割り当てる必要があります。このロジックは hash_insert 関数に追加されました。

if(h->buckets == nil) {
    h->buckets = runtime·mallocgc(h->bucketsize, 0, 1, 0);
    b = (Bucket*)(h->buckets);
    clearbucket(b);
}

このコードは、マップに要素を追加しようとしたときに h->buckets が nil であることを検出すると、必要なバケットテーブルを runtime·mallocgc を使って割り当て、初期化します。これにより、バケットテーブルは実際にデータが格納されるまでメモリを消費しないため、リソースの無駄がなくなります。

3. nil バケットテーブルの安全なハンドリング

バケットテーブルが nil になる可能性があるため、マップに対する他の操作（検索、削除、イテレーションなど）も、この新しい状態を安全に処理できるように調整されました。

  • hash_lookup と hash_remove: マップが空 (h->count == 0) の場合、これらの関数はバケットテーブルにアクセスする前にすぐに処理を終了するように変更されました。これにより、nil ポインタのデリファレンスを防ぎます。
  • hash_iter_init: マップが空で h->buckets が nil の場合、イテレータはすぐに「終了」状態としてマークされ、無効なメモリへのアクセスを回避します。

これらの変更は、Goのマップが「必要なときに必要なだけメモリを割り当てる」という原則をより厳密に適用するためのものです。特に、HTTPサーバーのように短命なマップが大量に生成されるようなシナリオにおいて、この最適化はメモリ使用量とGCの効率に大きなプラスの影響を与え、全体的なアプリケーションのパフォーマンス向上に貢献します。

関連リンク

  • Go言語のマップ実装に関する公式ドキュメントやブログ記事（当時のものがあれば）
  • Goのランタイムとガーベージコレクションに関する詳細な解説
  • Goのベンチマークとプロファイリングに関するドキュメント

参考にした情報源リンク

  • Go言語の公式ドキュメント: https://golang.org/doc/
  • Goのマップ実装に関するブログ記事や解説（当時の情報源を特定することは困難ですが、一般的にはGoのソースコード自体が最も信頼できる情報源です）
  • Goのガーベージコレクションに関する解説記事（例: "Go's Garbage Collector: A Comprehensive Guide" など）
  • Goのベンチマークに関する公式ドキュメント: https://golang.org/pkg/testing/
  • Goのプロファイリングに関する公式ドキュメント: https://blog.golang.org/profiling-go-programs
  • コミットメッセージに記載されているGoのコードレビューシステムへのリンク: https://golang.org/cl/7722046 (これは当時のGerritシステムへのリンクであり、現在はGitHubのコミットページにリダイレクトされるか、アーカイブされている可能性があります。)
  • Goのソースコード: src/pkg/runtime/hashmap.c および src/pkg/runtime/map_test.go (Goのバージョンによってパスが異なる場合がありますが、このコミットが適用された当時のパスです。)