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

このコミットは、Go言語のランタイムにおけるマップ（ハッシュテーブル）の実装を根本的に変更するものです。具体的には、既存のsrc/runtime/map.cに存在していたマップの実装を削除し、新たにsrc/runtime/hashmap.cとsrc/runtime/hashmap.hで定義される、より洗練されたハッシュマップの実装に置き換えています。

変更されたファイルは以下の通りです。

src/runtime/Makefile: ビルド設定が更新され、古いmap.oの代わりに新しいhashmap.oがリンクされるようになりました。また、hashmap.hがヘッダーファイルとして追加されています。
src/runtime/hashmap.c: 新規追加されたファイルで、Goランタイムの新しいハッシュマップのコアロジックがC言語で実装されています。
src/runtime/hashmap.h: 新規追加されたファイルで、hashmap.cで実装されたハッシュマップのデータ構造とAPIの定義が含まれています。
src/runtime/map.c: 既存のマップ実装ファイルが削除されました。
src/runtime/runtime.c: メモリ操作関数mmovが追加され、memhash、stringhash、pointerhashといったハッシュ関数が具体的な実装を持つように変更されました。これらは新しいハッシュマップがキーのハッシュ値を計算するために使用されます。
src/runtime/runtime.h: mmov関数のプロトタイプ宣言が追加されました。

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

https://github.com/golang/go/commit/bc0b4f0d2a610059afb95ef0360704714815187d

元コミット内容

commit bc0b4f0d2a610059afb95ef0360704714815187d
Author: Ken Thompson <ken@golang.org>
Date:   Thu Nov 13 10:35:44 2008 -0800

    mike's map code
    
    R=r
    OCL=19146
    CL=19146
---
 src/runtime/Makefile  |   4 +-
 src/runtime/hashmap.c | 861 ++++++++++++++++++++++++++++++++++++++++++++++++++
 src/runtime/hashmap.h | 160 ++++++++++
 src/runtime/map.c     | 252 ---------------
 src/runtime/runtime.c |  44 ++-
 src/runtime/runtime.h |   1 +
 6 files changed, 1059 insertions(+), 263 deletions(-)

変更の背景

このコミットが行われた2008年11月は、Go言語がまだ初期開発段階にあった時期です。Go言語の設計目標の一つに、高効率な並行処理とシステムプログラミング能力がありました。その中で、キーと値のペアを効率的に管理するデータ構造であるマップ（ハッシュテーブル）は、言語の基本的な機能として不可欠です。

既存のsrc/runtime/map.cにあったマップの実装は、おそらく初期のプロトタイプ的なものであり、パフォーマンスやスケーラビリティの面で課題があったと推測されます。Go言語の組み込みmap型が期待される性能を発揮するためには、より堅牢で最適化されたハッシュマップの実装が必要でした。

このコミットは、Go言語のランタイムの基盤を強化し、将来のGoプログラムがマップを効率的に利用できるようにするための重要なステップでした。コミットメッセージの「mike's map code」は、この新しい実装がMike Burrows（Go言語の初期開発に貢献した著名なエンジニア）によって開発されたものであることを示唆しています。

Go言語のランタイムは、Goプログラムの実行を管理する低レベルなシステムです。これには、ガベージコレクション、ゴルーチン（軽量スレッド）のスケジューリング、メモリ管理、そして組み込みデータ構造（マップ、スライスなど）の基盤となる実装が含まれます。Goプログラムは、コンパイル時にランタイムとリンクされ、ランタイムの機能を利用して動作します。初期のGoランタイムは、パフォーマンスが重要な部分やOSとのインタフェース部分はC言語で実装されていました。

ハッシュマップ (Hash Map / Hash Table)

ハッシュマップは、キーと値のペアを格納するデータ構造で、キーを使って値に高速にアクセスできるのが特徴です。

ハッシュ関数: キーを入力として受け取り、そのキーに対応するメモリ上の「バケット」のインデックスを計算する関数です。良いハッシュ関数は、異なるキーに対して均一にインデックスを分散させ、衝突（異なるキーが同じインデックスを生成すること）を最小限に抑えます。
衝突解決: 複数のキーが同じバケットにハッシュされる「衝突」が発生した場合に、それらをどのように処理するかを決定するメカニズムです。一般的な方法には以下のものがあります。
- チェイン法 (Chaining): 各バケットをリンクリストとして扱い、衝突した要素をそのリストに追加します。
- オープンアドレス法 (Open Addressing): 衝突が発生した場合、別の空いているバケットを探して要素を配置します。線形プロービング、二次プロービング、ダブルハッシュなどの手法があります。
リサイズ (Resizing): ハッシュマップが一定の負荷係数（要素数/バケット数）を超えると、パフォーマンスが低下する可能性があります。これを避けるため、マップは自動的にバケット数を増やし、既存の要素を新しいバケットに再配置（リハッシュ）します。

C言語

Go言語の初期のランタイムは、パフォーマンスが要求される部分や、OSのプリミティブに近い操作を行う部分でC言語が使用されていました。これは、C言語が低レベルなメモリ操作やシステムリソースへの直接アクセスに優れているためです。このコミットで導入されたハッシュマップもC言語で実装されています。

Goの`map`型

Go言語の組み込み型であるmapは、内部的にはハッシュマップとして実装されています。ユーザーがGoコードでmapを使用する際、その背後ではランタイムのハッシュマップ実装が呼び出され、キーのハッシュ計算、値の格納、検索、削除などが行われます。このコミットは、そのmap型の基盤となる実装を、より効率的で堅牢なものに置き換えるものです。

技術的詳細

このコミットの主要な技術的変更点は、Goランタイムのマップ実装を、単純なリンクリストベース（と推測される）のものから、より高度なハッシュテーブルベースのものへと移行したことです。

新しいハッシュマップの導入 (src/runtime/hashmap.c, src/runtime/hashmap.h):
- struct hashとstruct hash_subtableという主要なデータ構造が定義されています。struct hashはハッシュテーブル全体のメタデータ（要素数、データサイズ、ハッシュ関数、比較関数など）を管理し、struct hash_subtableは個々のハッシュバケットの集合を表します。
- 階層的なハッシュテーブル: hash_conv関数に見られるように、この実装は単一の大きなテーブルではなく、必要に応じて「サブテーブル」を作成するメカニズムを持っているようです。これは、特定のハッシュバケットが過密になった場合に、そのバケットをさらに小さなハッシュテーブルに分割することで、衝突解決の効率を高める手法と考えられます。これにより、ハッシュ衝突が多い場合でも、検索や挿入のパフォーマンスを維持しようとします。
- 動的なリサイズとプロービング: hash_grow関数は、ハッシュテーブルが一定の負荷係数を超えた場合に、テーブルのサイズを拡張し、要素を再配置する（リハッシュ）機能を提供します。また、max_probesというフィールドがあり、これはオープンアドレス法におけるプロービングの最大回数を制御している可能性があります。
- 汎用的なキーと値のサポート: keysize, valsize, keyalg, valalgといったフィールドがstruct hashに存在することから、このハッシュマップが任意の型のキーと値を扱えるように設計されていることがわかります。keyalgとvalalgは、キーと値のハッシュ計算や比較、コピーを行うためのアルゴリズム（関数ポインタ）を指します。
ハッシュ関数の具体的な実装 (src/runtime/runtime.c):
- 以前はダミーの実装だったmemhash、stringhash、pointerhashといった関数が、具体的なハッシュ計算ロジックを持つようになりました。
- memhashは任意のバイト列のハッシュを計算し、stringhashは文字列のハッシュを、pointerhashはポインタのハッシュを計算します。これらの関数は、新しいハッシュマップがGoの様々なデータ型をキーとして利用できるようにするために不可欠です。ハッシュ計算には、乗算とXORを組み合わせた一般的なハッシュアルゴリズムが使用されています。
メモリ移動関数の追加 (src/runtime/runtime.c, src/runtime/runtime.h):
- mmov関数は、メモリブロックを移動させるための関数です。特に、コピー元とコピー先のメモリ領域がオーバーラップしている場合でも正しく動作するように設計されています。これは、ハッシュマップのリサイズ時や、要素の挿入・削除時にメモリ上のデータを効率的に再配置するために利用されます。
GoランタイムAPIとの連携:
- sys·newmap, sys·mapaccess1, sys·mapaccess2, sys·mapassign1, sys·mapassign2といった関数は、Go言語のmap型が内部的に呼び出すランタイム関数です。これらの関数は、Goコードからmapの作成、要素のアクセス（存在チェックあり/なし）、要素の代入（挿入/更新/削除）を行うためのC言語レベルのインターフェースを提供します。これにより、Go言語のmap操作が、この新しいC言語で実装されたハッシュマップの機能にマッピングされます。

この変更により、Go言語のmap型は、より効率的でスケーラブルな基盤の上に構築されることになり、Goプログラム全体のパフォーマンス向上に寄与しました。

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

`src/runtime/hashmap.c` (新規追加)

このファイルは、新しいハッシュマップの主要なロジックをC言語で実装しています。

データ構造の定義:
- struct hash: ハッシュテーブル全体の状態を管理します。count (要素数)、datasize (各要素のデータサイズ)、max_power (サブテーブルの最大サイズ)、data_hash (ハッシュ関数へのポインタ)、data_eq (比較関数へのポインタ) などが含まれます。
- struct hash_subtable: ハッシュテーブルのサブテーブル（バケットの集合）を管理します。power (テーブルのサイズを示す2のべき乗)、used (ハッシュ値のどのビットがこのテーブルで使用されているか)、entry (実際のハッシュエントリの配列) などが含まれます。
- struct hash_entry: 各ハッシュエントリの構造を定義します。hash (ハッシュ値)、data (ユーザーデータ) などが含まれます。
主要な関数:
- hash_init: ハッシュテーブルを初期化します。
- hash_lookup: キーに対応する値を検索します。
- hash_insert_internal / hash_insert: キーと値を挿入します。衝突解決とリサイズ（hash_grow）やサブテーブルへの変換（hash_conv）のロジックが含まれます。
- hash_remove: キーに対応する要素を削除します。
- hash_grow: ハッシュテーブルのサイズを拡張し、要素を再配置します。
- hash_conv: 特定のバケットが過密になった場合に、そのバケットをサブテーブルに変換します。
- hash_iter_init / hash_next: ハッシュテーブルの要素をイテレートするための機能を提供します。
- sys·newmap, sys·mapaccess1, sys·mapaccess2, sys·mapassign1, sys·mapassign2: Go言語のmap操作から呼び出されるランタイム関数で、C言語のハッシュマップ機能へのブリッジとなります。

`src/runtime/hashmap.h` (新規追加)

このファイルは、hashmap.cで実装されたハッシュマップのデータ構造とAPIのプロトタイプ宣言を提供します。また、ハッシュマップの利用方法に関する詳細なコメントと例が含まれており、開発者がこの新しいハッシュマップを理解し、利用する上で非常に役立ちます。

`src/runtime/map.c` (削除)

このファイルは、Goランタイムの古いマップ実装を含んでいました。このコミットにより、その内容は完全に削除され、新しいhashmap.cに置き換えられました。

`src/runtime/runtime.c` (変更)

mmov関数の追加:

void
mmov(byte *t, byte *f, uint32 n)
{
    if(t < f) {
        while(n > 0) {
            *t = *f;
            t++;
            f++;
            n--;
        }
    } else {
        t += n;
        f += n;
        while(n > 0) {
            t--;
            f--;
            *t = *f;
            n--;
        }
    }
}

この関数は、メモリブロックを移動させます。特に、コピー元とコピー先の領域が重なっている場合（t < fまたはt >= f）でも正しく動作するように、コピーの方向を調整しています。

ハッシュ関数の実装:
- memhash: 任意のバイト列のハッシュを計算します。
- stringhash: 文字列のハッシュを計算します。これは内部的にmemhashを呼び出します。
- pointerhash: ポインタのハッシュを計算します。これも内部的にmemhashを呼び出します。
これらの関数は、以前はダミーの実装でしたが、このコミットで実際のハッシュ計算ロジックが追加されました。

コアとなるコードの解説

このコミットの核心は、Go言語の組み込みmap型の基盤を、より高性能なハッシュテーブルに置き換えることです。

src/runtime/hashmap.cに実装されたハッシュマップは、以下の重要な概念に基づいています。

動的なサイズ変更とリハッシュ:
- hash_insert_internal関数内で、要素の挿入時にハッシュテーブルの負荷が高くなったと判断されると、hash_grow関数が呼び出されます。
- hash_growは、現在のテーブルよりも大きな新しいテーブルを割り当て、既存の要素を新しいテーブルに再ハッシュしてコピーします。これにより、マップの要素数が増えても、平均的な操作時間が一定に保たれるように設計されています。
階層的な衝突解決（サブテーブル）:
- hash_conv関数は、特定のハッシュバケットに多くの要素が集中し、プロービングの回数が増えすぎた場合に呼び出されます。
- この関数は、過密になったバケットを、さらに小さなハッシュテーブル（サブテーブル）に変換します。これにより、衝突解決の効率が向上し、最悪ケースのパフォーマンス劣化を緩和します。これは、ハッシュテーブルが非常に多くの要素を格納し、ハッシュ衝突が避けられない場合に特に有効な戦略です。
Goランタイムとの統合:
- sys·newmapはGoのmake(map[K]V)に対応し、新しいハッシュマップを初期化します。
- sys·mapaccess1とsys·mapaccess2はGoのm[key]やval, ok := m[key]に対応し、マップからの値の検索を行います。mapaccess2はキーの存在も返します。
- sys·mapassign1とsys·mapassign2はGoのm[key] = valやdelete(m, key)に対応し、マップへの値の代入や削除を行います。mapassign2は、Goのdelete操作のように、キーの存在に基づいて削除を行うことができます。

src/runtime/runtime.cで実装されたmemhash、stringhash、pointerhashは、新しいハッシュマップがキーのハッシュ値を計算するために使用する具体的なアルゴリズムを提供します。これらのハッシュ関数は、異なるデータ型（バイト列、文字列、ポインタ）に対して均一なハッシュ値を生成するように設計されており、ハッシュマップのパフォーマンスに直接影響します。

全体として、このコミットはGo言語のmap型が、その後のGoプログラムで広く利用される高性能なデータ構造となるための重要な基盤を築いたと言えます。

参考にした情報源リンク

GitHubコミットページ: https://github.com/golang/go/commit/bc0b4f0d2a610059afb95ef0360704714815187d
Go言語の初期開発に関する一般的な知識 (Go言語の歴史、ランタイムの構成など)
ハッシュテーブルの一般的なアルゴリズムとデータ構造に関する知識

comemo