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

このコミットは、Goランタイムにおけるハッシュマップ（Hmap）のガベージコレクション（GC）を、より「正確（precise）」にするための重要な変更を導入しています。これにより、GCがハッシュマップの内部構造を正確に理解し、マップ内のキーや値、そして内部のサブテーブルが指すオブジェクトをより効率的かつ正確に識別・マークできるようになります。結果として、メモリの再利用効率が向上し、アプリケーションのメモリフットプリントが削減される可能性があります。

コミット

commit 1e01fba2fc9a8824fee899956ead1518eae9613b
Author: Jan Ziak <0xe2.0x9a.0x9b@gmail.com>
Date:   Fri Feb 8 16:00:33 2013 -0500

    runtime: precise garbage collection of hashmaps

    R=golang-dev, rsc
    CC=dave, dvyukov, golang-dev, minux.ma, remyoudompheng
    https://golang.org/cl/7252047

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

https://github.com/golang/go/commit/1e01fba2fc9a8824fee899956ead1518eae9613b

元コミット内容

runtime: precise garbage collection of hashmaps

R=golang-dev, rsc
CC=dave, dvyukov, golang-dev, minux.ma, remyoudompheng
https://golang.org/cl/7252047

変更の背景

Goのガベージコレクタは、プログラムが使用しなくなったメモリを自動的に解放する役割を担っています。初期のGoのGCは、特定のデータ構造（特に複雑な内部構造を持つもの）に対して「保守的（conservative）」なアプローチを取ることがありました。保守的なGCでは、メモリ領域内にポインタのように見える値が存在する場合、それが実際にポインタであるかどうかを厳密に判断せず、安全のためにその領域を「生きている」とみなして解放しないことがあります。これは、誤って使用中のメモリを解放してしまうリスクを避けるための安全策ですが、結果として不要なメモリが解放されずに残り、メモリリークやメモリ使用量の増加につながる可能性があります。

ハッシュマップは、内部的に複雑なデータ構造（バケット、サブテーブル、キーと値のデータなど）を持つため、保守的なGCの対象となりやすい構造の一つでした。このコミットの背景には、ハッシュマップのGCを保守的から「正確（precise）」に移行することで、メモリ管理の効率を向上させ、より多くの不要なメモリを確実に回収するという目的があります。これにより、Goアプリケーションのメモリフットプリントを削減し、全体的なパフォーマンスを改善することが期待されます。

前提知識の解説

ガベージコレクション (GC)

目的: プログラムが動的に確保したメモリのうち、もはや到達不可能（参照されなくなった）になったものを自動的に解放し、メモリリークを防ぎ、開発者のメモリ管理の負担を軽減します。
GoのGC: Goは、並行（concurrent）かつ三色マーク＆スイープ（tri-color mark-and-sweep）アルゴリズムをベースとしたGCを採用しています。これは、GCがアプリケーションの実行と並行して動作し、アプリケーションの一時停止時間（stop-the-world時間）を最小限に抑えることを目指しています。
マーク＆スイープ:
- マークフェーズ: GCは、ルート（グローバル変数、スタック上の変数など）から到達可能なすべてのオブジェクトを「生きている（live）」とマークします。
- スイープフェーズ: マークされなかった（到達不可能な）オブジェクトが占めるメモリ領域を「死んでいる（dead）」と判断し、解放して再利用可能な状態にします。
保守的GC vs. 正確GC:
- 保守的GC: メモリ領域内のビットパターンがポインタのように見える場合、それが実際にポインタであるかどうかを厳密に判断せず、安全のためにポインタであると仮定します。これにより、誤って生きているオブジェクトを解放するリスクは減りますが、実際にはポインタではないデータがポインタと誤認され、不要なメモリが解放されない可能性があります。
- 正確GC: データ構造のレイアウトを正確に把握しており、どのメモリ位置がポインタを格納しているかを正確に識別できます。これにより、ポインタではないデータを誤ってポインタとみなすことがなくなり、より効率的かつ完全に不要なメモリを回収できます。

Goのハッシュマップ (`Hmap`)

Goのマップは、内部的にハッシュテーブルとして実装されています。その構造は、キーと値のペアを格納する「バケット」と、バケットが満杯になった場合にリンクされる「オーバーフローバケット」、そしてマップが大きくなった場合にバケットの集合を管理する「サブテーブル」など、複数の層から構成されています。これらの内部構造は、GCがマップを正確にスキャンするために理解する必要があるポインタを含んでいます。

GCプログラム

GoのGCは、異なる型のオブジェクトをスキャンするために「GCプログラム」と呼ばれる一連の命令を使用します。これは、特定のデータ構造内のどこにポインタが存在するかをGCに指示するものです。例えば、構造体の場合、各フィールドがポインタであるかどうかに応じて、GCは適切なスキャン命令を実行します。

技術的詳細

このコミットの核心は、Goランタイムがハッシュマップの内部構造を正確に走査し、その中に含まれるすべてのポインタ（キー、値、および内部サブテーブルへの参照）を識別できるようにすることです。

ハッシュマップイテレータの導入:
- src/pkg/runtime/hashmap.h と src/pkg/runtime/hashmap.c に、GC専用の新しいイテレータ構造体 hash_gciter と hash_gciter_data、および関連する関数 hash_gciter_init と hash_gciter_next が追加されました。
- hash_gciter_init は、GCがマップのスキャンを開始する際にイテレータを初期化します。
- hash_gciter_next は、マップの内部を深さ優先で走査し、次のサブテーブル、キーデータ、または値データを返します。これにより、GCはマップの複雑な階層構造を効率的にナビゲートできます。
- このイテレータは、マップのキーや値がポインタを含むかどうか（IndirectKey, IndirectVal フラグ）も考慮し、それに応じてポインタのマーク方法を調整します。
GCスキャンロジックの更新 (mgc0.c):
- src/pkg/runtime/mgc0.c は、GoのGCの主要なスキャンロジックを含むファイルです。このファイルが大幅に更新され、ハッシュマップの正確なGCをサポートするようになりました。
- markonly 関数の追加: これは、特定のオブジェクトがGCアリーナ内にあり、まだマークされていない場合にのみマークするヘルパー関数です。これにより、GCはオブジェクトの開始アドレスを正確に特定し、そのビットマップを更新してマーク済みとして記録できます。
- GC_MAP_NEXT 命令の追加: GCプログラムに新しい命令 GC_MAP_NEXT が追加されました。これは、GCがハッシュマップの要素をスキャンする際に使用されます。
- scanblock 関数の変更:
  - scanblock は、GCがメモリブロックをスキャンする主要な関数です。この関数内で、マップ型のオブジェクトが検出された場合、新しいハッシュマップイテレータ (hash_gciter) が初期化されます。
  - mapProg という新しいGCプログラムが導入され、マップのスキャンに特化しています。
  - GC_MAP_NEXT 命令が実行されると、hash_gciter_next を呼び出してマップの次の要素（サブテーブル、キー、値）を取得します。
  - 取得した要素がポインタを含む場合、それらはGCの内部バッファ（objbuf または ptrbuf）に追加され、後続のGCサイクルでさらにスキャンされます。特に、サブテーブル自体もGCの対象としてマークされます。
- flushobjbuf 関数の追加: PtrTarget と同様に、Obj（オブジェクトのポインタとサイズ、型情報を含む構造体）をバッファリングし、必要に応じてフラッシュするための flushobjbuf 関数が追加されました。これにより、GCはマップから見つかった多数のオブジェクトを効率的に処理できます。

これらの変更により、GCはハッシュマップの内部構造を「ブラックボックス」として扱うのではなく、その内容を正確に検査し、到達可能なすべてのポインタをマークできるようになりました。これにより、マップが不要になった際に、その内部で保持されていたオブジェクトも適切に解放されるようになり、メモリ使用効率が向上します。

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

`src/pkg/runtime/hashmap.c`

hash_subtable_new 関数内で、メモリ割り当てが malloc から runtime·mallocgc に変更されました。これは、ハッシュマップのサブテーブルがGCによって管理されるヒープメモリに割り当てられることを意味します。
hash_gciter_init 関数が追加されました。これは、GCがハッシュマップをスキャンする際に使用するイテレータを初期化します。マップがポインタを含まない場合は false を返します。
hash_gciter_next 関数が追加されました。これは、イテレータを進め、次のサブテーブル、キーデータ、または値データを返します。マップの内部構造（サブテーブルのネストを含む）を再帰的に走査します。

`src/pkg/runtime/hashmap.h`

malloc マクロの定義が削除されました。
GCイテレータのための新しい構造体 hash_gciter と hash_gciter_data が定義されました。
- hash_gciter: イテレータの状態（要素サイズ、フラグ、スタックポインタ、現在のサブテーブル、サブテーブルの状態スタック）を保持します。
- hash_gciter_data: イテレータが返すデータ（サブテーブルポインタ、キーデータ、値データ、キーと値が間接ポインタであるかどうかのフラグ）を保持します。
hash_gciter_init と hash_gciter_next の関数プロトタイプが追加されました。

`src/pkg/runtime/mgc0.c`

hashmap.h がインクルードされました。
GC_MAP_NEXT がGC命令の列挙型に追加されました。
markonly 静的関数が追加されました。これは、与えられたオブジェクトがGCアリーナ内にあり、まだマークされていない場合に、そのオブジェクトをマークします。
BufferList 構造体に Obj obj[IntermediateBufferCapacity]; が追加されました。これは、GCスキャン中に見つかったオブジェクト（ポインタとサイズ、型情報）を一時的にバッファリングするためのものです。
flushobjbuf 関数が追加されました。これは、objbuf にバッファリングされたオブジェクトをGCのワークバッファにフラッシュする役割を担います。
mapProg という新しいGCプログラムが定義されました。これは、ハッシュマップの要素をスキャンするための命令シーケンスです。
scanblock 関数が大幅に修正されました。
- マップ型のオブジェクトが検出された場合 (case TypeInfo_Map)、hash_gciter_init を呼び出してマップイテレータを初期化し、GCプログラムカウンタ (pc) を mapProg に設定してマップのスキャンを開始します。
- GC_MAP_NEXT 命令の処理が追加されました。このロジックは hash_gciter_next を繰り返し呼び出し、マップ内のすべてのサブテーブル、キー、値を走査します。
- 走査中に見つかったサブテーブルは markonly でマークされます。
- キーや値がポインタを含む場合、それらは objbuf または ptrbuf に追加され、GCによってさらにスキャンされる対象となります。
- GC_MAP_PTR 命令の処理も更新され、マップオブジェクト自体をマークし、そのマップの正確なスキャンを開始するようになりました。
- scanblock の終了時に flushobjbuf が呼び出され、バッファリングされたすべてのオブジェクトが処理されることが保証されます。

コアとなるコードの解説

このコミットの核となる変更は、Goのガベージコレクタがハッシュマップの内部構造を正確に理解し、その中のポインタを識別できるようにするための新しいメカニズムの導入です。

hash_gciter とその関連関数:
- hash_gciter は、ハッシュマップの内部を走査するための状態を保持する構造体です。これには、現在の要素サイズ、マップのフラグ（キーや値が間接ポインタであるかなど）、現在のサブテーブル、そしてネストされたサブテーブルを処理するためのスタックが含まれます。
- hash_gciter_init(Hmap *h, struct hash_gciter *it): GCが特定のハッシュマップをスキャンする前に呼び出され、イテレータを初期化します。マップが空であるか、ポインタを含まない場合は false を返します。
- hash_gciter_next(struct hash_gciter *it, struct hash_gciter_data *data): イテレータを次の要素に進めます。この関数は、マップのバケットを走査し、キーと値のペア、またはネストされたサブテーブルを見つけます。見つかった要素の情報は hash_gciter_data 構造体に格納されます。
  - data->st: サブテーブルへのポインタ。サブテーブル自体もGCの対象です。
  - data->key_data, data->val_data: キーと値のデータへのポインタ。
  - data->indirectkey, data->indirectval: キーや値が間接ポインタ（つまり、データ自体がポインタではなく、ポインタを指すポインタ）であるかどうかを示します。これは、GCが正しい深さでポインタを追跡するために重要です。
scanblock におけるマップスキャンロジック:
- scanblock 関数は、GCがメモリブロックを走査し、到達可能なオブジェクトをマークする主要なループです。
- マップオブジェクトの検出: scanblock が TypeInfo_Map 型のオブジェクト（つまり、Goのマップ）に遭遇すると、そのマップの正確なスキャンを開始します。
- hash_gciter_init の呼び出し: まず、hash_gciter_init を呼び出して、このマップのためのGCイテレータを初期化します。
- mapProg の使用: マップのスキャンには、mapProg という専用のGCプログラムが使用されます。このプログラムは、GC_MAP_NEXT 命令を含んでいます。
- GC_MAP_NEXT の処理: scanblock のメインループ内で GC_MAP_NEXT 命令が実行されると、hash_gciter_next が繰り返し呼び出されます。
  - hash_gciter_next がサブテーブルを返した場合 (d.st != nil)、そのサブテーブル自体が markonly 関数によってマークされます。
  - hash_gciter_next がキーまたは値を返した場合 (d.key_data != nil または d.val_data != nil)、GCはそれらがポインタを含むかどうかをチェックします（KindNoPointers フラグと indirectkey/indirectval フラグを使用）。
  - ポインタを含むキーや値は、GCの内部バッファ（objbuf または ptrbuf）に追加されます。これらのバッファは、後続のGCサイクルでさらにスキャンされ、それらが指すオブジェクトもマークされます。
- flushobjbuf: objbuf は、scanblock の実行中に見つかったオブジェクト（ポインタとサイズ、型情報）を一時的に保持するバッファです。このバッファが満杯になった場合や、scanblock の終了時には、flushobjbuf が呼び出されて、バッファ内のすべてのオブジェクトがGCのメインワークキューにフラッシュされます。これにより、GCはこれらのオブジェクトをさらに処理し、それらが指すオブジェクトをマークできます。

これらの変更により、GoのGCはハッシュマップの内部構造を「正確」にスキャンできるようになり、マップが不要になった際に、その内部で保持されていたすべての到達不可能なオブジェクトを確実に解放できるようになりました。これは、メモリ使用量の最適化とGCパフォーマンスの向上に貢献します。

参考にした情報源リンク

Goのソースコード（特に src/pkg/runtime/hashmap.c, src/pkg/runtime/hashmap.h, src/pkg/runtime/mgc0.c の変更点）
Goのガベージコレクションに関する一般的な知識
ハッシュテーブルのデータ構造に関する一般的な知識
コミットメッセージと関連するGo CL (Change List) の情報 (https://golang.org/cl/7252047)

comemo