commit e8018fbebe2e6e86f94111b21c5749ebeea15dbd
Author: Russ Cox <rsc@golang.org>
Date: Wed Jul 31 08:35:43 2013 -0400
runtime: rewrite map size test
I don't know why the memstats code is flaky.
TBR=bradfitz
CC=golang-dev
https://golang.org/cl/12160043
---
src/pkg/runtime/hashmap.c | 3 +++
src/pkg/runtime/map_test.go | 41 -----------------------------------------
2 files changed, 3 insertions(+), 41 deletions(-)
diff --git a/src/pkg/runtime/hashmap.c b/src/pkg/runtime/hashmap.c
index 7e0c9572dd..4b51436dc2 100644
--- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -1112,6 +1112,9 @@ runtime·makemap_c(MapType *typ, int64 hint)
Type *key;
key = typ->key;
+
+ if(sizeof(Hmap) > 48)
+ runtime·panicstring("hmap too large");
if(hint < 0 || (int32)hint != hint)
runtime·panicstring("makemap: size out of range");
diff --git a/src/pkg/runtime/map_test.go b/src/pkg/runtime/map_test.go
index 0e36bb2d34..9f9c40d156 100644
--- a/src/pkg/runtime/map_test.go
+++ b/src/pkg/runtime/map_test.go
@@ -371,44 +371,3 @@ func testMapLookups(t *testing.T, m map[string]string) {\n }\n }\n }\n-\n-func TestMapSize(t *testing.T) {\n-\tif runtime.GOMAXPROCS(-1) != 1 {\n-\t\tt.Skip(\"gomaxprocs > 1 - not accurate\")\n-\t}\n-\tvar m map[struct{}]struct{}\n-\tsize := bytesPerRun(100, func() {\n-\t\tm = make(map[struct{}]struct{})\n-\t})\n-\tif size > 48 {\n-\t\tt.Errorf(\"size = %v; want <= 48\", size)\n-\t}\n-}\n-\n-// like testing.AllocsPerRun, but for bytes of memory, not number of allocations.\n-func bytesPerRun(runs int, f func()) (avg float64) {\n-\tdefer runtime.GOMAXPROCS(runtime.GOMAXPROCS(1))\n-\n-\t// Warm up the function\n-\tf()\n-\n-\t// Measure the starting statistics\n-\tvar memstats runtime.MemStats\n-\truntime.ReadMemStats(&memstats)\n-\tsum := 0 - memstats.Alloc\n-\n-\t// Run the function the specified number of times\n-\tfor i := 0; i < runs; i++ {\n-\t\tf()\n-\t}\n-\n-\t// Read the final statistics\n-\truntime.ReadMemStats(&memstats)\n-\tsum += memstats.Alloc\n-\n-\t// Average the mallocs over the runs (not counting the warm-up).\n-\t// We are forced to return a float64 because the API is silly, but do\n-\t// the division as integers so we can ask if AllocsPerRun()==1\n-\t// instead of AllocsPerRun()<2.\n-\treturn float64(sum / uint64(runs))\n-}\n```
## GitHub上でのコミットページへのリンク
[https://github.com/golang/go/commit/e8018fbebe2e6e86f94111b21c5749ebeea15dbd](https://github.com/golang/go/commit/e8018fbebe2e6e86f94111b21c5749ebeea15dbd)
## 元コミット内容
このコミットは、Goランタイムにおけるマップ（`map`型）のサイズテストを書き直すものです。コミットメッセージには「memstatsコードが不安定な理由がわからない」とあり、既存のテストが信頼性に欠けるため、より堅牢な方法に置き換える意図が示されています。具体的には、`src/pkg/runtime/hashmap.c`に`Hmap`構造体のサイズチェックを追加し、`src/pkg/runtime/map_test.go`から既存の`TestMapSize`関数と`bytesPerRun`ヘルパー関数を削除しています。
## 変更の背景
Goの`map`型は、内部的にはハッシュテーブルとして実装されており、その基盤となるデータ構造は`runtime`パッケージ内の`Hmap`構造体です。この`Hmap`構造体のサイズは、Goランタイムのメモリ効率とパフォーマンスに直接影響します。
元の`TestMapSize`テストは、`runtime.MemStats`を使用してマップ作成時のメモリ割り当てを測定していました。しかし、コミットメッセージにあるように、この`memstats`コードは「flaky」（不安定、信頼性に欠ける）であったとされています。これは、テスト環境や実行時のGC（ガベージコレクション）のタイミングなど、様々な要因によってメモリ統計の取得が不安定になり、テストが非決定的な結果を返す可能性があったことを示唆しています。
このような不安定なテストは、開発プロセスにおいて問題となります。テストが頻繁に失敗すると、それが実際のバグによるものなのか、単にテストの不安定性によるものなのかを区別するのが難しくなり、開発者の生産性を低下させます。そのため、Russ Coxは、より直接的で信頼性の高い方法で`Hmap`構造体のサイズを検証することを選択しました。具体的には、コンパイル時に`Hmap`のサイズが想定外に大きくなっていないかをチェックする`panic`を追加することで、テストの不安定性を回避しつつ、重要な制約を強制しています。
## 前提知識の解説
### Goの`map`型とハッシュテーブル
Goの組み込み`map`型は、キーと値のペアを格納するためのハッシュテーブルとして実装されています。内部的には、`runtime`パッケージの`hmap`構造体がこのハッシュテーブルを管理しています。
* **ハッシュテーブル**: キーをハッシュ関数に通して得られるハッシュ値に基づいて、値を格納するデータ構造です。これにより、平均O(1)の高速な検索、挿入、削除が可能になります。
* **バケット**: ハッシュテーブルは、データを格納するための「バケット」と呼ばれる固定サイズの配列で構成されます。Goのマップでは、各バケットは最大8つのキーと値のペアを保持できます。
* **オーバーフローバケット**: 1つのバケットに8つ以上のキーと値のペアがハッシュされる場合（衝突が発生した場合）、オーバーフローバケットが連結されて追加のエントリを収容します。
* **動的な成長**: マップ内のエントリ数が増加し、特定のロードファクタ（バケットあたりのアイテム数）を超えると、マップは自動的に成長します。これは、古いバケット配列の2倍のサイズの新しいバケット配列を割り当て、データを古いバケットから新しいバケットに段階的にコピーすることで行われます。
* **`hmap`構造体**: Goのマップの全体を管理する主要な構造体です。バケット配列へのポインタや、その他の内部的な管理情報を含んでいます。
* **`bmap`構造体**: 各バケットを表す構造体で、ハッシュの上位ビット（tophash）、キーと値のペア、そしてオプションでオーバーフローバケットへのポインタを含みます。
### `runtime.MemStats`
`runtime.MemStats`は、Goプログラムのメモリ割り当てに関する統計情報を提供する構造体です。`runtime.ReadMemStats`関数を呼び出すことで、この構造体に現在のメモリ使用状況が書き込まれます。
* `Alloc`: ヒープに割り当てられたオブジェクトによって現在使用されているバイト数。
* `TotalAlloc`: ヒープに割り当てられたオブジェクトによってこれまでに使用された合計バイト数。
* `Sys`: OSから取得された合計バイト数。
* `Lookups`: ポインタルックアップの合計数。
* `Mallocs`: 割り当てられたオブジェクトの合計数。
* `Frees`: 解放されたオブジェクトの合計数。
これらの統計は、プログラムのメモリプロファイリングやデバッグに役立ちますが、GCの動作やシステムの状態に影響されるため、正確な測定が難しい場合があります。特に、特定の操作による正確なメモリ割り当て量を測定しようとすると、GCの実行タイミングや他のゴルーチンの活動によって結果が変動し、「flaky」なテストにつながることがあります。
### `sizeof`演算子（C言語）
C言語における`sizeof`演算子は、型または式のサイズをバイト単位で返します。このコミットでは、`src/pkg/runtime/hashmap.c`というC言語で書かれたファイル内で`sizeof(Hmap)`が使用されており、これは`Hmap`構造体がメモリ上で占めるバイト数を取得するために使われています。Goランタイムの一部は、パフォーマンス上の理由からC言語で実装されています。
### `runtime·panicstring`
Goランタイム内部で使用されるパニック関数です。Go言語の`panic`とは異なり、これはランタイムの低レベルなエラー処理メカニズムであり、通常は回復不能なエラーが発生した場合に呼び出されます。このコミットでは、`Hmap`構造体のサイズが想定よりも大きい場合に、ランタイムが異常終了するように設定されています。
## 技術的詳細
このコミットの技術的な核心は、Goの`map`型の内部表現である`Hmap`構造体のサイズに関する制約を、テストコードからランタイムコード自体に移した点にあります。
### 変更前のアプローチ（`map_test.go`）
変更前は、`TestMapSize`関数が`bytesPerRun`ヘルパー関数を利用して、空のマップを作成する際のメモリ割り当て量を測定していました。
* `bytesPerRun`は、`runtime.ReadMemStats`を呼び出して、関数実行前後の`memstats.Alloc`（ヒープに割り当てられたバイト数）の差分を計算することで、メモリ使用量を測定していました。
* `TestMapSize`では、`make(map[struct{}]struct{})`という空のマップを作成し、その際に割り当てられるメモリが48バイト以下であることを期待していました。
* `runtime.GOMAXPROCS(-1) != 1`の場合にテストをスキップするロジックがありました。これは、`GOMAXPROCS`が1より大きい場合、並行処理によってメモリ統計の測定がさらに不安定になる可能性があったためです。
このアプローチの問題点は、`memstats.Alloc`がヒープ全体の割り当て量を反映するため、特定の操作（この場合はマップの作成）による正確なメモリ割り当て量を分離して測定するのが難しい点にありました。GCの実行や他のゴルーチンのメモリ使用が、テスト結果にノイズとして影響を与え、テストが不安定になる原因となっていました。
### 変更後のアプローチ（`hashmap.c`）
変更後は、`src/pkg/runtime/hashmap.c`内の`runtime·makemap_c`関数に直接、`Hmap`構造体のサイズチェックが追加されました。
* `runtime·makemap_c`は、Goの`make(map[K]V)`が呼び出された際に、実際にマップを初期化するランタイム関数です。
* 追加されたコードは`if(sizeof(Hmap) > 48)`という条件文です。ここで`sizeof(Hmap)`は、C言語の`sizeof`演算子を用いて、`Hmap`構造体のコンパイル時のサイズをバイト単位で取得します。
* もし`Hmap`のサイズが48バイトを超えていた場合、`runtime·panicstring("hmap too large")`が呼び出され、ランタイムがパニックを起こして異常終了します。
この変更により、`Hmap`構造体のサイズが意図せず大きくなった場合に、コンパイル時または初期化時に即座に問題が検出されるようになります。これは、不安定なメモリ統計に依存するテストよりもはるかに堅牢で決定的なチェック方法です。48バイトという値は、当時のGoランタイムにおける`Hmap`構造体の設計上の最大サイズとして設定されたものと考えられます。このサイズは、ポインタやカウンタ、バケットへの参照など、マップの管理に必要な最小限のメタデータを格納するために必要な領域です。
### なぜ48バイトなのか？
2013年当時のGoランタイムにおける`Hmap`構造体の具体的なレイアウトは、Goのソースコード（`src/runtime/map.go`や`src/runtime/hashmap.c`）に依存しますが、一般的にハッシュマップのヘッダ構造には以下のような情報が含まれます。
* `count`: マップ内の要素数
* `flags`: マップの状態を示すフラグ
* `B`: バケットの数を決定する対数（2^B個のバケット）
* `noverflow`: オーバーフローバケットの数
* `hash0`: ハッシュシード
* `buckets`: バケット配列へのポインタ
* `oldbuckets`: 成長中のマップにおける古いバケット配列へのポインタ
* `nevacuate`: 成長中のマップで移動済みのバケット数
これらのフィールドがポインタ（8バイト）や整数型（4バイトまたは8バイト）で構成されることを考えると、合計で48バイトというサイズは、当時の64ビットシステムにおけるこれらのフィールドの合計サイズとして妥当な値であったと推測されます。このサイズ制約は、マップのメモリフットプリントを小さく保ち、パフォーマンスを最適化するための重要な設計上の決定でした。
## コアとなるコードの変更箇所
このコミットにおけるコアとなるコードの変更は以下の2箇所です。
1. **`src/pkg/runtime/hashmap.c`への追加**:
`runtime·makemap_c`関数内に、`Hmap`構造体のサイズチェックが追加されました。
```c
if(sizeof(Hmap) > 48)
runtime·panicstring("hmap too large");
```
2. **`src/pkg/runtime/map_test.go`からの削除**:
`TestMapSize`関数と、それに付随する`bytesPerRun`ヘルパー関数が完全に削除されました。
```go
// 削除されたコードの概要
func TestMapSize(t *testing.T) { ... }
func bytesPerRun(runs int, f func()) (avg float64) { ... }
```
## コアとなるコードの解説
### `src/pkg/runtime/hashmap.c`の変更
`runtime·makemap_c`関数は、Goの`map`型が`make`関数によって初期化される際に呼び出されるC言語で実装されたランタイム関数です。この関数は、新しいマップのメモリを割り当て、初期設定を行います。
追加された`if(sizeof(Hmap) > 48)`の行は、`Hmap`構造体のコンパイル時のサイズが48バイトを超えているかどうかをチェックします。
* `sizeof(Hmap)`: `Hmap`構造体がメモリ上で占めるバイト数を返します。これはコンパイル時に決定される定数です。
* `> 48`: `Hmap`のサイズが48バイトよりも大きい場合に条件が真となります。
* `runtime·panicstring("hmap too large")`: 条件が真の場合、ランタイムが「hmap too large」というメッセージと共にパニックを起こします。これにより、`Hmap`構造体のサイズが設計上の制約を超えた場合に、早期に問題が検出され、開発者に通知されます。
この変更は、マップのメモリフットプリントが意図せず増加するのを防ぐためのガードレールとして機能します。`Hmap`構造体のサイズは、マップのパフォーマンスとメモリ効率に直接影響するため、この制約は重要です。
### `src/pkg/runtime/map_test.go`の変更
`TestMapSize`関数は、Goのテストフレームワーク（`testing`パッケージ）を使用して、マップ作成時のメモリ割り当てをテストしていました。このテストは、`runtime.MemStats`を利用してメモリ使用量を測定する`bytesPerRun`ヘルパー関数に依存していました。
* `TestMapSize`は、空の`map[struct{}]struct{}`を作成し、その際に割り当てられるメモリが48バイト以下であることを検証していました。
* `bytesPerRun`は、`runtime.ReadMemStats`を呼び出して、関数実行前後の`memstats.Alloc`の差分を計算することで、メモリ使用量を測定していました。
このテストが削除されたのは、コミットメッセージにあるように、`memstats`コードが「flaky」（不安定）であったためです。メモリ統計の測定は、GCのタイミングや他のゴルーチンの活動など、外部要因に影響されやすく、テストが非決定的な結果を返すことがありました。このような不安定なテストは、開発の妨げとなるため、より堅牢なランタイムレベルのチェックに置き換えられました。
## 関連リンク
* Go言語の`map`型に関する公式ドキュメント: [https://go.dev/blog/maps](https://go.dev/blog/maps)
* Goの`runtime`パッケージに関する公式ドキュメント: [https://pkg.go.dev/runtime](https://pkg.go.dev/runtime)
* Goのハッシュマップ実装に関する詳細な解説（Goのバージョンによって内部実装は異なる可能性がありますが、基本的な概念は共通です）:
* The Go Programming Language Specification - Map types: [https://go.dev/ref/spec#Map_types](https://go.dev/ref/spec#Map_types)
* Go maps in action: [https://go.dev/blog/go-maps-in-action](https://go.dev/blog/go-maps-in-action)
## 参考にした情報源リンク
* Goの`map`実装に関するStack Overflowの議論:
* [https://stackoverflow.com/questions/20099010/how-are-go-maps-implemented-internally](https://stackoverflow.com/questions/20099010/how-are-go-maps-implemented-internally)
* [https://stackoverflow.com/questions/30000000/how-does-go-map-grow](https://stackoverflow.com/questions/30000000/how-does-go-map-grow)
* Goの`hmap`構造体に関する情報:
* [https://go.googlesource.com/go/+/refs/heads/master/src/runtime/map.go](https://go.googlesource.com/go/+/refs/heads/master/src/runtime/map.go) (現在のGoのソースコード)
* [https://cheney.net/golang-internals/](https://cheney.net/golang-internals/) (Goの内部構造に関するブログ記事)
* Goの`runtime.MemStats`に関する公式ドキュメント: [https://pkg.go.dev/runtime#MemStats](https://pkg.go.dev/runtime#MemStats)
* Goのコミット履歴: [https://github.com/golang/go/commits/master](https://github.com/golang/go/commits/master)
* Goのコードレビューシステム (Gerrit): [https://go.dev/cl/](https://go.dev/cl/) (コミットメッセージに記載されているCLリンクのベースURL)
* Goのソースコード（当時のバージョンに近いもの）: [https://go.googlesource.com/go/+/refs/tags/go1.1.2/src/pkg/runtime/hashmap.c](https://go.googlesource.com/go/+/refs/tags/go1.1.2/src/pkg/runtime/hashmap.c) (Go 1.1.2は2013年当時のバージョンに近い)
* Goのソースコード（当時のバージョンに近いもの）: [https://go.googlesource.com/go/+/refs/tags/go1.1.2/src/pkg/runtime/map_test.go](https://go.googlesource.com/go/+/refs/tags/go1.1.2/src/pkg/runtime/map_test.go) (Go 1.1.2は2013年当時のバージョンに近い)