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

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

このコミットは、Go言語のランタイムにおけるハッシュマップ（src/runtime/hashmap.c）の実装に対する重要な改善を含んでいます。具体的には、ハッシュマップに格納されるキーと値のペアのうち、値のメモリ配置を最適化し、特に値のサイズがポインタサイズ（sizeof(void*)）以上の場合に、その開始アドレスをポインタサイズにアライン（整列）させるように変更されています。この変更の主な目的は、Goのマーク＆スイープ方式のガベージコレクション（GC）が、ハッシュマップ内のポインタをより効率的かつ正確に識別し、メモリ管理の堅牢性を向上させることにあります。

コミット

このコミットは、Go言語のランタイムにおけるハッシュマップ（hashmap.c）の実装を修正し、キーと値のペアにおける値のメモリ配置を改善するものです。特に、値のサイズがポインタサイズ（sizeof(void*)）以上の場合に、値の開始アドレスをポインタサイズにアライン（整列）させることで、マーク＆スイープ方式のガベージコレクション（GC）が効率的かつ正確に動作するように変更されています。

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

https://github.com/golang/go/commit/9ed2960de8a9eb833f2b265e39c911db4939bf9e

元コミット内容

in hash implementation, if data >= 8, align to 8.

R=ken
OCL=23519
CL=23521

このコミットメッセージは非常に簡潔ですが、その意図は明確です。ハッシュマップの実装において、データ（この文脈では主に値）のサイズが8バイト以上の場合に、そのデータを8バイト境界にアラインするというものです。これは、当時のGo言語のランタイムが32ビットまたは64ビットアーキテクチャを想定しており、ポインタサイズが4バイトまたは8バイトであることに対応しています。特に64ビットシステムでは8バイトアラインメントが重要になります。R=kenはコードレビュー担当者を示し、OCLとCLはGoの内部コードレビューシステムにおける変更リストのIDです。

変更の背景

Go言語のガベージコレクション（GC）は、プログラムが動的に確保したメモリのうち、もはや使用されていない（到達不可能になった）メモリ領域を自動的に解放する重要な役割を担っています。GoのGCは主に「マーク＆スイープ」アルゴリズムを採用しており、メモリ上のポインタをたどって到達可能なオブジェクトを「マーク」し、マークされなかったオブジェクトを「スイープ」して解放します。

このGCが正しく、かつ効率的に機能するためには、メモリ上のポインタがどこにあるかを正確に知る必要があります。特に、構造体や配列などの複合データ型の中にポインタが含まれている場合、そのポインタが特定のメモリ境界にアラインされていると、GCがポインタを効率的にスキャンし、誤って非ポインタデータをポインタとして解釈したり、その逆を行ったりするリスクを減らすことができます。

ハッシュマップは、キーと値のペアを格納するデータ構造であり、値がポインタを含む可能性のある任意の型であるため、GCの正確性と効率性にとってそのメモリレイアウトは非常に重要です。以前の実装では、値の開始オフセットが単純にキーのサイズに依存していたため、値がポインタを含む場合に適切なアラインメントが保証されない可能性がありました。

このコミットは、ハッシュマップの値部分のメモリ配置を最適化し、GCがより堅牢に動作するようにすることを目的としています。具体的には、値がポインタを含む可能性のあるサイズ（sizeof(void*)以上）である場合に、その値がメモリ上で適切にアラインされるように調整することで、GCのスキャン精度を向上させ、潜在的なバグ（例：メモリリークやクラッシュ）やパフォーマンスの問題を防ぎます。これは、Goのメモリ管理システム全体の安定性と効率性を高めるための基盤的な改善と言えます。

前提知識の解説

1. ハッシュマップ（Hash Map）

ハッシュマップ（またはハッシュテーブル、連想配列、辞書）は、キーと値のペアを格納するデータ構造です。キーを使って値に高速にアクセスできるのが特徴です。内部的には、キーのハッシュ値を計算し、そのハッシュ値を使って配列のインデックスを決定し、値が格納されます。衝突（異なるキーが同じハッシュ値になること）を解決するためのメカニズム（例：チェイニングやオープンアドレス法）も含まれます。Go言語の組み込み型であるmapは、このハッシュマップによって実装されています。Goのmapは、キーと値の型を自由に指定できるため、値がポインタを含む複雑なデータ構造になることも頻繁にあります。

2. メモリアラインメント（Memory Alignment）

メモリアラインメントとは、コンピュータのメモリ上でデータが特定のバイト境界に配置されることを指します。例えば、「4バイトアラインメント」とは、データの開始アドレスが4の倍数になるように配置されることを意味します。多くのCPUアーキテクチャでは、特定のデータ型（特にポインタやマルチバイトの数値型、例えばint64やfloat64）がそのサイズと同じバイト境界にアラインされている場合に、最も効率的にアクセスできます。アラインされていないデータへのアクセスは、パフォーマンスの低下（CPUが複数回メモリにアクセスする必要があるため）を招いたり、一部のアーキテクチャではハードウェア例外（アラインメント違反）を引き起こしたりする可能性があります。ガベージコレクタがメモリをスキャンする際にも、ポインタが適切にアラインされていることで、ポインタの識別が容易になり、スキャン効率が向上します。

3. ガベージコレクション（Garbage Collection, GC）

ガベージコレクションは、プログラムが動的に確保したメモリのうち、もはや使用されていない（どの変数からも参照されなくなった）メモリ領域を自動的に解放する仕組みです。これにより、プログラマは手動でのメモリ管理（malloc/freeなど）の負担から解放され、メモリリークやダングリングポインタなどのバグを減らすことができます。

Go言語のGCは、主に「マーク＆スイープ」アルゴリズムに基づいています。

  • マークフェーズ: GCは、プログラムが現在使用している（ルートセットから到達可能な）すべてのオブジェクトを識別し、「マーク」します。ルートセットには、グローバル変数、スタック上の変数、CPUレジスタなどが含まれます。GCはこれらのルートからポインタをたどり、到達可能なすべてのオブジェクトをマークしていきます。
  • スイープフェーズ: マークされなかったすべてのオブジェクト（つまり、到達不可能なオブジェクト）は、不要なメモリとして識別され、解放されます。解放されたメモリは、将来のメモリ割り当てのために再利用されます。

GCがメモリグラフを正しくたどり、ポインタを正確に識別するためには、メモリ上のオブジェクトのレイアウト、特にポインタがどこに位置しているかを知る必要があります。メモリアラインメントは、このポインタの識別を助け、GCのスキャン効率と正確性を向上させます。

4. sizeof(void*)

sizeof(void*)は、C言語においてvoid型へのポインタのサイズをバイト単位で返します。これは、システムが32ビットアーキテクチャであれば通常4バイト、64ビットアーキテクチャであれば通常8バイトになります。この値は、システム上のポインタの標準的なサイズを示すため、メモリのアラインメントやポインタの計算において重要な基準となります。GoのランタイムはC言語で書かれた部分も多く、このようなC言語の概念が内部実装に現れることがあります。

技術的詳細

このコミットの核心は、Go言語のランタイムにおけるハッシュマップの内部構造struct hashにdatavoという新しいフィールドを導入し、値のオフセット計算に利用することです。

以前のハッシュマップの実装では、キーと値がメモリ上で連続して配置される場合、値の開始オフセットは単純にキーのサイズ（keysize）の直後とされていました。しかし、これは値がポインタを含むような複雑なデータ型である場合に、GCがポインタを効率的かつ正確にスキャンするためのアラインメント要件を満たさない可能性がありました。例えば、キーが3バイトで値がポインタを含む場合、値が3バイト目から開始すると、ポインタが4バイト境界や8バイト境界にアラインされず、GCがポインタを正しく認識できない、あるいはアクセスに余計なCPUサイクルを要する、といった問題が発生しえます。

変更後のsys·newmap関数では、ハッシュマップが初期化される際に、datavo（data value offset）が以下のように計算されます。

  1. まず、h->datavoはkeysizeで初期化されます。これは、値がキーの直後に配置されるという基本的な考え方に基づいています。
  2. 次に、valsize（値のサイズ）がsizeof(void*)以上であるかどうかがチェックされます。この条件は、値がポインタを含む可能性のあるサイズであるかどうかのヒューリスティックな判断として機能します。Goのポインタは通常sizeof(void*)と同じサイズであるため、値がこのサイズ以上であれば、その中にポインタが含まれている可能性が高いと判断されます。
  3. もしvalsizeがsizeof(void*)以上であれば、h->datavoはrnd(keysize, sizeof(void*))によって再計算されます。ここでrnd関数は、keysizeをsizeof(void*)の最も近い倍数に切り上げる（アラインする）役割を担っています。例えば、sizeof(void*)が8バイト（64ビットシステム）でkeysizeが5バイトの場合、rnd(5, 8)は8を返します。これにより、値のデータがポインタサイズ境界にアラインされることが保証されます。

このdatavoの導入により、ハッシュマップの内部でキーと値のペアが格納されるメモリ領域において、値の開始位置が常に適切にアラインされるようになります。これにより、GCが値の領域をスキャンする際に、ポインタをより確実に識別できるようになり、GCの正確性とパフォーマンスが向上します。特に、GCがポインタをスキャンする際に、アラインされていないアドレスからポインタを読み取ろうとすると、CPUがアラインメント違反を報告したり、パフォーマンスが著しく低下したりする可能性があるため、この変更は非常に重要です。

具体的には、sys·mapaccess1（マップからの値の取得）、sys·mapaccess2（マップからの値と存在チェックの取得）、mapassign（マップへの値の割り当て）、sys·mapiter2（マップのイテレーション）といったハッシュマップのアクセスや操作を行うランタイム関数群で、値へのオフセット計算にh->keysizeの代わりに新しく計算されたh->datavoが使用されるようになりました。これにより、値のコピーやアクセスが、アラインメントを考慮した正しいメモリ位置に対して行われるようになります。

この変更は、Go言語のメモリ管理とGCの堅牢性を高めるための重要な改善であり、特にポインタを多用する複雑なデータ構造をハッシュマップに格納する場合に、その恩恵が大きくなります。これは、Goが提供する高効率な並行処理とメモリ安全性を実現するための、低レベルながらも不可欠な最適化の一つです。

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

変更はsrc/runtime/hashmap.cファイルに集中しています。

  1. struct hash構造体へのdatavoフィールドの追加: ハッシュマップの内部表現を定義するstruct hashに、uint32 datavo;という新しいフィールドが追加されました。これは、値のオフセットを格納するために使用されます。

    struct hash { /* a hash table; initialize with hash_init() */
    uint32  keysize;
    uint32  valsize;
    uint32  datavo; // 新しく追加されたフィールド
    uint32  ko;
    uint32  vo;
    uint32  po;
    // ...
};

  2. sys·newmap関数でのdatavoの計算と利用: sys·newmap関数は、新しいハッシュマップを初期化する際に呼び出されます。この関数内で、h->datavoが計算され、hash_init関数に渡される合計サイズもh->datavoに基づいて調整されます。

    --- a/src/runtime/hashmap.c
+++ b/src/runtime/hashmap.c
@@ -674,7 +675,14 @@ sys·newmap(uint32 keysize, uint32 valsize,
  
     h = mal(sizeof(*h));
-    hash_init(h, keysize+valsize, // 変更前: キーサイズと値サイズの合計
+    
+    // align value inside data so that mark-sweep gc can find it.
+    // might remove in the future and just assume datavo == keysize.
+    h->datavo = keysize;
+    if(valsize >= sizeof(void*))
+        h->datavo = rnd(keysize, sizeof(void*));
+
+    hash_init(h, h->datavo+valsize, // 変更後: datavoと値サイズの合計
         algarray[keyalg].hash,
         algarray[keyalg].equal,
         donothing,

    ここで、hash_initに渡す合計サイズがkeysize+valsizeからh->datavo+valsizeに変更されています。これは、ハッシュマップの内部でキーと値のペアを格納するために必要なメモリ領域のサイズが、アラインメントを考慮して計算されるようになったことを意味します。

  3. ハッシュマップ操作関数での値のオフセット計算の変更: sys·mapaccess1, sys·mapaccess2, mapassign, sys·mapiter2の各関数は、ハッシュマップ内のキーと値のペアにアクセスしたり、値をコピーしたりする際に使用されます。これらの関数では、値へのオフセット計算がres+h->keysizeからres+h->datavoに変更されています。resはキーと値のペアが格納されているメモリブロックの開始アドレスを指します。

    例: sys·mapaccess1 (マップから値を取得する関数)

    --- a/src/runtime/hashmap.c
+++ b/src/runtime/hashmap.c
@@ -729,7 +738,7 @@ sys·mapaccess1(Hmap *h, ...)
  	hit = hash_lookup(h, ak, (void**)&res);
  	if(!hit)
  		throw("sys·mapaccess1: key not in map");
-	h->valalg->copy(h->valsize, av, res+h->keysize); // 変更前: キーの直後を値の開始位置とする
+	h->valalg->copy(h->valsize, av, res+h->datavo); // 変更後: アラインされたdatavoを値の開始位置とする
  
  	if(debug) {
  		prints("sys·mapaccess1: map=");

    同様の変更が、sys·mapaccess2、mapassign、sys·mapiter2の各関数にも適用されています。これにより、すべての値へのアクセスが、アラインメントを考慮した正しいメモリ位置に対して行われるようになります。

コアとなるコードの解説

このコミットの主要な変更点は、ハッシュマップの内部構造におけるキーと値のメモリ配置、特に値の開始オフセットの計算方法にあります。

Goのハッシュマップは、内部的にキーと値をメモリ上の連続したブロックに格納することがあります。このブロック内で、キーのデータに続いて値のデータが配置されます。以前は、値の開始位置は単純にキーのサイズ（keysize）の直後とされていました。

しかし、ガベージコレクタがメモリ上のポインタを正確に識別するためには、ポインタが特定のメモリ境界（通常はポインタサイズ、例えば64ビットシステムでは8バイト）にアラインされていることが望ましいです。もし値のデータがポインタを含んでおり、かつその開始位置が適切にアラインされていない場合、GCがポインタを誤って解釈したり、スキャン効率が低下したりする可能性があります。これは、GCがメモリをスキャンする際に、ポインタのパターンを効率的に認識するために、アラインされたアドレスを期待しているためです。

このコミットでは、struct hashにdatavo（data value offset）という新しいフィールドが追加されました。このフィールドは、値の開始オフセットを計算するために使用されます。

sys·newmap関数内で、datavoは以下のように計算されます。

h->datavo = keysize; // まずはキーの直後として初期化
if(valsize >= sizeof(void*)) // 値のサイズがポインタサイズ以上の場合
    h->datavo = rnd(keysize, sizeof(void*)); // キーのサイズをポインタサイズにアライン

ここで、rnd(a, b)関数は、aをbの最も近い倍数に切り上げる（アラインする）関数であると推測されます。例えば、rnd(5, 8)は8を返し、rnd(8, 8)は8を返します。このロジックにより、もし値がポインタを含む可能性のあるサイズ（sizeof(void*)以上）であれば、値の開始オフセットdatavoはkeysizeをsizeof(void*)の倍数にアラインした値になります。これにより、値のデータがポインタサイズ境界に適切に配置されることが保証されます。

そして、sys·mapaccess1、sys·mapaccess2、mapassign、sys·mapiter2といったハッシュマップの内部操作を行う関数では、値のデータへのアクセスに際して、これまでのres+h->keysize（キーの直後）ではなく、新しく計算されたres+h->datavo（アラインされた値の開始位置）が使用されるようになります。resは、ハッシュマップの内部でキーと値のペアが格納されているメモリブロックの先頭アドレスを指します。したがって、res + h->datavoは、そのブロック内で値が実際に開始するアドレスを正確に指し示します。

この変更は、Goのランタイムがメモリをより効率的かつ安全に管理するための基盤を強化するものであり、特にGCの正確性とパフォーマンスに寄与します。アラインメントを考慮することで、GCはメモリ上のポインタをより迅速かつ確実に識別できるようになり、結果としてGCの一時停止時間の短縮や、メモリ関連のバグの発生リスクの低減に繋がります。

関連リンク

  • Go言語のガベージコレクションに関する公式ドキュメントやブログ記事 (当時の情報を見つけるのは難しいかもしれませんが、一般的なGo GCの概念は関連します)
  • Go言語のmap型の実装に関する技術記事
  • メモリアラインメントに関する一般的なコンピュータサイエンスの資料
  • Go言語の初期のコミット履歴を閲覧できるGitHubリポジトリ: https://github.com/golang/go

参考にした情報源リンク

  • Go言語のソースコード (src/runtime/hashmap.c)
  • Go言語のガベージコレクションの仕組みに関する一般的な知識
  • メモリアラインメントに関するコンピュータアーキテクチャの知識
  • Gitのコミット履歴と差分表示
  • （必要に応じて）Go言語の初期の設計ドキュメントやメーリングリストの議論（ただし、今回の解説では直接参照していません）