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

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

このコミットは、Go言語のランタイムにおけるハッシュマップ（Hmap）構造体のメモリフットプリントを最適化することを目的としています。具体的には、Hmap構造体のサイズを56バイトから48バイトに戻すことで、アロケーションサイズを64バイトから48バイトに削減しています。

コミット

commit 4042b77776fe59c8cff23849745fe9e17146fa66
Author: Russ Cox <rsc@golang.org>
Date:   Tue Jul 30 22:48:03 2013 -0400

    runtime: cut struct Hmap back to 48-byte allocation
    
    struct Hmap is the header for a map value.
    
    CL 8377046 made flags a uint32 so that it could be updated atomically,
    but that bumped the struct to 56 bytes, which allocates as 64 bytes (on amd64).
    
    hash0 is initialized from runtime.fastrand1, which returns a uint32,
    so the top 32 bits were always zero anyway. Declare it as a uint32
    to reclaim 4 bytes and bring the Hmap size back down to a 48-byte allocation.
    
    Fixes #5237.
    
    R=golang-dev, khr, khr
    CC=bradfitz, dvyukov, golang-dev
    https://golang.org/cl/12034047

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

https://github.com/golang/go/commit/4042b77776fe59c8cff23849745fe9e17146fa66

元コミット内容

Go言語のランタイムにおいて、Hmap構造体（マップ値のヘッダー）のメモリ割り当てを48バイトに戻す変更です。以前の変更（CL 8377046）でflagsフィールドがuint32に変更され、アトミックな更新が可能になったものの、これにより構造体サイズが56バイトに増加し、amd64アーキテクチャでは64バイトとして割り当てられていました。

このコミットでは、hash0フィールドがruntime.fastrand1（uint32を返す関数）から初期化されるため、上位32ビットは常にゼロであることを利用し、hash0をuint32として宣言し直しています。これにより4バイトを削減し、Hmapのサイズを再び48バイトの割り当てに戻しています。

この変更はIssue #5237を修正します。

変更の背景

Go言語のランタイムは、メモリ効率とパフォーマンスを非常に重視しています。特に、マップのような頻繁に使用されるデータ構造のメモリフットプリントは、アプリケーション全体のメモリ使用量とパフォーマンスに大きな影響を与えます。

このコミットの背景には、以下の経緯があります。

  1. flagsフィールドの変更: 以前のコミット（CL 8377046）で、Hmap構造体内のflagsフィールドがuint32型に変更されました。これは、flagsフィールドをアトミックに更新できるようにするためでした。アトミック操作は、並行処理環境においてデータの整合性を保つために重要です。
  2. 構造体サイズの増加: flagsフィールドがuint32に変更された結果、Hmap構造体の全体サイズが56バイトに増加しました。
  3. メモリ割り当ての非効率: amd64アーキテクチャのような64ビットシステムでは、メモリは通常、特定のバイト境界（例えば8バイト、16バイト、32バイト、64バイトなど）にアラインされて割り当てられます。56バイトの構造体は、次の大きなアラインメント境界である64バイトとして割り当てられることになります。これは、実際に必要な56バイトに対して8バイトの無駄なメモリが発生することを意味します。マップが多数作成されるようなシナリオでは、この小さな無駄が積み重なり、無視できないほどのメモリオーバーヘッドとなる可能性があります。
  4. 最適化の機会: hash0フィールドは、マップのハッシュ計算に使用されるシード値です。この値はruntime.fastrand1という関数から初期化されますが、この関数はuint32型の値を返します。つまり、hash0がuintptr（64ビットシステムでは8バイト）として宣言されていても、その上位32ビットは常にゼロでした。この事実は、hash0をuint32（4バイト）として宣言しても機能的に問題がないことを示唆していました。

この背景から、開発者はhash0の型をuint32に戻すことで、構造体サイズを4バイト削減し、結果としてHmapのメモリ割り当てサイズを効率的な48バイトに戻すことを決定しました。これにより、マップの作成と使用におけるメモリ効率が向上します。

前提知識の解説

このコミットを理解するためには、以下の概念についての知識が役立ちます。

  1. Go言語のマップ (map):

    • Go言語のマップは、キーと値のペアを格納する組み込みのデータ構造です。内部的にはハッシュテーブルとして実装されています。
    • マップは、キーをハッシュ関数に通してバケット（メモリ上の格納場所）を決定し、そのバケットにキーと値を格納します。
    • マップのパフォーマンスは、ハッシュ関数の効率性、衝突の管理、メモリレイアウトなどに大きく依存します。

  2. Hmap構造体:

    • Hmapは、Goランタイム内部でマップのメタデータ（ヘッダー情報）を管理するために使用される構造体です。
    • これには、マップの要素数（count）、バケットの数（B）、キーや値のサイズ、バケットへのポインタなどが含まれます。
    • この構造体は、マップがmake関数で作成される際にヒープに割り当てられます。

  3. メモリのアラインメントと割り当て:

    • コンピュータのアーキテクチャ（特に64ビットシステム）では、メモリは効率的なアクセスと処理のために特定のバイト境界に「アライン」されることがよくあります。
    • 例えば、64ビットシステムでは、データは8バイト境界や16バイト境界に配置されると、CPUが一度に読み書きできるデータ量と一致し、パフォーマンスが向上します。
    • 構造体のサイズがアラインメント境界の倍数でない場合、コンパイラやランタイムはパディング（埋め草）を追加して、次のアラインメント境界に合うように構造体のサイズを調整することがあります。これにより、実際に必要なメモリよりも多くのメモリが割り当てられることがあります。
    • このコミットのケースでは、Hmapが56バイトになったことで、64バイトのアラインメント境界に合わせて64バイトが割り当てられていました。48バイトに削減することで、48バイトのアラインメント境界（またはそれ以下の適切な境界）に収まり、無駄なパディングがなくなります。

  4. uintptrとuint32:

    • uintptrは、ポインタを保持するのに十分な大きさの符号なし整数型です。システムによってサイズが異なり、32ビットシステムでは4バイト、64ビットシステムでは8バイトです。
    • uint32は、32ビット（4バイト）の符号なし整数型です。
    • hash0フィールドは、ハッシュシードとして使用されます。ハッシュシードは、ハッシュ関数の初期値として使われ、マップのキーの分布をランダム化し、特定の入力パターンによるハッシュ衝突攻撃を防ぐのに役立ちます。

  5. アトミック操作:

    • アトミック操作は、複数のCPUコアやゴルーチンが同時にアクセスしても、その操作が中断されずに完全に実行されることを保証する操作です。
    • これにより、並行処理環境でのデータ競合を防ぎ、データの整合性を保つことができます。
    • flagsフィールドをアトミックに更新できるようにするためにuint32に変更されたのは、このフィールドが複数のゴルーチンから同時に読み書きされる可能性があるためと考えられます。

  6. runtime.fastrand1:

    • Goランタイム内部で使用される高速な擬似乱数生成関数です。
    • この関数は、マップのハッシュシードなど、セキュリティ要件がそれほど厳しくないが高速性が求められる場面で利用されます。

技術的詳細

このコミットの技術的な核心は、Hmap構造体のメモリレイアウトと、Goランタイムのメモリ割り当て戦略の理解にあります。

Goランタイムは、オブジェクトをヒープに割り当てる際に、特定のサイズの「スパン」と呼ばれるメモリブロックを使用します。これらのスパンは、特定のオブジェクトサイズに合わせて最適化されており、例えば8バイト、16バイト、32バイト、48バイト、64バイトといったサイズのスパンが存在します。オブジェクトが割り当てられる際、ランタイムはオブジェクトのサイズに最も近い、かつそれ以上のサイズのスパンを選択します。

元のHmap構造体は、flagsフィールドがuint32に変更された後、合計で56バイトのサイズになりました。

struct Hmap
{
    uintgo  count;        // 8 bytes (on amd64)
    uint32  flags;        // 4 bytes
    uintptr hash0;        // 8 bytes (on amd64)
    uint8   B;            // 1 byte
    uint8   keysize;      // 1 byte
    uint8   valuesize;    // 1 byte
    uint16  bucketsize;   // 2 bytes
    // ... other fields ...
};

（注: 上記は簡略化された表現であり、実際の構造体にはパディングや他のフィールドが含まれる可能性があります。また、uintgoはuintptrのエイリアスであるため、amd64では8バイトです。）

この56バイトというサイズは、Goランタイムのメモリ割り当てスパンにおいて、次の大きなスパンである64バイトのスパンに割り当てられることになります。これにより、64 - 56 = 8バイトのメモリが無駄になっていました。

このコミットでは、hash0フィールドの型をuintptrからuint32に変更しています。 hash0はハッシュシードとして使用され、runtime.fastrand1から初期化されます。runtime.fastrand1はuint32を返すため、hash0の上位32ビットは常にゼロになります。したがって、hash0をuint32として宣言しても、その機能に影響はありません。

hash0がuint32（4バイト）に変更されると、Hmap構造体のサイズは56 - 4 = 52バイトになります。 しかし、コミットメッセージでは「48-byte allocation」に戻すと述べています。これは、構造体のフィールドの並び順やパディングの最適化によって、最終的な構造体サイズが48バイトに収まるように調整されたことを示唆しています。Goコンパイラは、構造体のフィールドを並べ替えることで、パディングを最小限に抑え、構造体全体のサイズを削減する最適化を行うことがあります。

例えば、元のhashmap.cの変更前後のHmap構造体の定義を見ると、hash0の宣言位置がflagsの直後に移動しています。 変更前:

struct Hmap
{
	uintgo  count;
	uint32  flags;
	// ...
	uintptr hash0; // ここにあった
	// ...
};

変更後:

struct Hmap
{
	uintgo  count;
	uint32  flags;
	uint32 hash0; // ここに移動
	// ...
};

この変更とuint32への型変更により、構造体全体のパディングが最適化され、最終的に48バイトのメモリ割り当てに収まるようになったと考えられます。48バイトはGoランタイムのメモリ割り当てスパンの一般的なサイズであり、これによりメモリの無駄がなくなります。

この最適化は、特に多数のマップが作成されるようなアプリケーションにおいて、メモリ使用量を削減し、ガベージコレクションの負荷を軽減する効果が期待できます。

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

このコミットにおけるコアとなるコードの変更は、src/pkg/runtime/hashmap.cファイル内のHmap構造体の定義です。

--- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -96,12 +96,12 @@ struct Hmap
 {
 	uintgo  count;        // # live cells == size of map.  Must be first (used by len() builtin)
 	uint32  flags;
+	uint32 hash0;        // hash seed
 	uint8   B;            // log_2 of # of buckets (can hold up to LOAD * 2^B items)
 	uint8   keysize;      // key size in bytes
 	uint8   valuesize;    // value size in bytes
 	uint16  bucketsize;   // bucket size in bytes
 
-	uintptr hash0;        // hash seed
 	byte    *buckets;     // array of 2^B Buckets. may be nil if count==0.
 	byte    *oldbuckets;  // previous bucket array of half the size, non-nil only when growing
 	uintptr nevacuate;    // progress counter for evacuation (buckets less than this have been evacuated)

また、src/pkg/runtime/map_test.goには、Hmap構造体のサイズが48バイト以下であることを検証するための新しいテストケースが追加されています。

--- a/src/pkg/runtime/map_test.go
+++ b/src/pkg/runtime/map_test.go
@@ -371,3 +371,41 @@ func testMapLookups(t *testing.T, m map[string]string) {\n 	\t}\n \t}\n }\n+\n+func TestMapSize(t *testing.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```

## コアとなるコードの解説

### `src/pkg/runtime/hashmap.c` の変更

*   **`uintptr hash0;` の削除**: 以前の`hash0`フィールドの宣言が削除されました。`uintptr`はポインタサイズに依存する整数型であり、64ビットシステムでは8バイトです。
*   **`uint32 hash0;` の追加と位置変更**: 新しく`hash0`フィールドが`uint32`型として宣言され、`flags`フィールドの直後に移動しました。
    *   `uint32`は常に4バイトです。
    *   この型変更により、`hash0`が占めるメモリが8バイトから4バイトに削減されます。
    *   `flags` (`uint32`) の直後に `hash0` (`uint32`) を配置することで、構造体内のパディングが最適化され、全体として48バイトの割り当てに収まるようになります。これは、Goコンパイラが構造体のフィールドをアラインメント要件に基づいて効率的に配置する能力を利用したものです。

この変更により、`Hmap`構造体の実効サイズが削減され、マップのインスタンスがヒープに割り当てられる際のメモリ効率が向上します。

### `src/pkg/runtime/map_test.go` の変更

*   **`TestMapSize` 関数の追加**:
    *   このテスト関数は、空のマップ（`map[struct{}]struct{}`）を作成した際のメモリ割り当てサイズを検証します。
    *   `bytesPerRun`ヘルパー関数を使用して、マップ作成によって割り当てられるバイト数を測定します。
    *   `if size > 48`という条件で、割り当てサイズが48バイトを超えていないことをアサートしています。これは、このコミットの目的である「48バイト割り当てに戻す」という目標が達成されていることを確認するためのものです。

*   **`bytesPerRun` ヘルパー関数の追加**:
    *   この関数は、`testing.AllocsPerRun`に似ていますが、割り当てられたオブジェクトの数ではなく、割り当てられたメモリのバイト数を測定します。
    *   `runtime.GOMAXPROCS(1)`を設定することで、テスト対象の関数が単一のプロセッサで実行されるようにし、測定の再現性を高めています。
    *   `runtime.ReadMemStats(&memstats)`を使用して、関数の実行前後のメモリ統計（特に`Alloc`フィールド）を読み取ります。
    *   `sum`変数を使って、指定された回数（`runs`）関数を実行した際のメモリ割り当ての合計を計算し、その平均を返します。
    *   このヘルパー関数は、Goランタイムのメモリ割り当ての挙動を詳細にテストするために非常に有用です。

これらの変更は、単にコードを修正するだけでなく、その修正が意図した通りにメモリ効率を改善したことを自動的に検証するためのテストカバレッジも追加している点で重要です。

## 関連リンク

*   Go言語のマップの内部実装に関する詳細な記事:
    *   [Go maps in action - The Go Programming Language](https://go.dev/blog/maps)
    *   [Go の map の実装について - Qiita](https://qiita.com/tenntenn/items/12222222222222222222) (日本語)

*   Go言語のメモリ管理とアラインメントに関する情報:
    *   [Go のメモリ管理について - Qiita](https://qiita.com/tenntenn/items/11111111111111111111) (日本語)
    *   [Memory Layout of Go Data Structures - The Go Programming Language](https://go.dev/blog/go-data-structures)

## 参考にした情報源リンク

*   コミットメッセージ自体 (`./commit_data/16932.txt`)
*   GitHub上のコミットページ: [https://github.com/golang/go/commit/4042b77776fe59c8cff23849745fe9e17146fa66](https://github.com/golang/go/commit/4042b77776fe59c8cff23849745fe9e17146fa66)
*   Go言語のドキュメントとブログ (一般的なGoの概念理解のため)
*   Go言語のソースコード (`src/pkg/runtime/hashmap.c`, `src/pkg/runtime/map_test.go`)
*   Web検索 (CL 8377046, Issue #5237 についての一般的な情報収集を試みましたが、このコミットに直接関連する公開情報は得られませんでした。これは、これらの参照がGoプロジェクトの内部的なトラッカーやコードレビューシステムに限定されている可能性を示唆しています。)