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

コミット

コミットハッシュ: 00224a356a5be3c134230bfa8fe11e0af2977aaf
作者: Keith Randall khr@golang.org
コミット日時: 2013年3月20日水曜日 13:51:29 -0700

コミットメッセージ:

runtime: faster hashmap implementation.

Hashtable is arranged as an array of
8-entry buckets with chained overflow.
Each bucket has 8 extra hash bits
per key to provide quick lookup within
a bucket.  Table is grown incrementally.

Update #3885
Go time drops from 0.51s to 0.34s.

R=r, rsc, m3b, dave, bradfitz, khr, ugorji, remyoudompheng
CC=golang-dev
https://golang.org/cl/7504044

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

https://github.com/golang/go/commit/00224a356a5be3c134230bfa8fe11e0af2977aaf

このコミットは、Goランタイムにおけるハッシュマップ（map型）の実装を大幅に改善し、パフォーマンスを向上させるものです。主な変更点は、ハッシュテーブルの内部構造を、8エントリのバケットとチェインによるオーバーフローを持つ配列として再設計したことです。これにより、各バケット内で高速なルックアップを可能にするために、キーごとに8ビットの追加ハッシュ情報が使用されます。また、テーブルの拡張が段階的に行われるようになりました。

この変更により、Goの実行時間が0.51秒から0.34秒に短縮されたと報告されており、パフォーマンスへの大きな影響が示唆されています。コミットメッセージには「Update #3885」とありますが、公開されているGoのIssueトラッカーで直接この番号のIssueは見つかりませんでした。これは内部的なトラッキング番号である可能性があります。

変更の背景

Go言語のmap型は、その柔軟性と使いやすさから広く利用されていますが、その内部実装はパフォーマンスに直結する重要な要素です。このコミットが行われた2013年当時、Goのランタイムはまだ成熟の途上にあり、様々な最適化が継続的に行われていました。ハッシュマップの効率は、プログラム全体の実行速度、特にデータ構造の操作が頻繁に行われるアプリケーションにおいて、ボトルネックとなる可能性がありました。

コミットメッセージにある「Go time drops from 0.51s to 0.34s」という記述は、特定のベンチマークまたはGoコンパイラ自身のビルド時間のような、Goエコシステム内の重要なワークロードにおいて顕著な改善が見られたことを示しています。これは、既存のハッシュマップ実装に改善の余地があり、それがパフォーマンス上の課題となっていたことを示唆しています。

「Update #3885」という記述は、このコミットが特定の課題または機能要求に対応するものであることを示していますが、外部から参照可能なGoのIssueトラッカーで直接的な対応するIssueは見つかりませんでした。これは、内部的なバグトラッキングシステムや、より広範なパフォーマンス改善プロジェクトの一部として扱われていた可能性が高いです。

前提知識の解説

ハッシュテーブル (Hash Table)

ハッシュテーブルは、キーと値のペアを格納するために使用されるデータ構造です。キーをハッシュ関数に入力することで、値が格納される配列（バケット配列）内のインデックスが計算されます。これにより、平均的にはO(1)の定数時間で要素の挿入、検索、削除が可能になります。

ハッシュ衝突 (Hash Collision)

異なるキーが同じハッシュ値、したがって同じバケットインデックスを生成する場合、ハッシュ衝突が発生します。ハッシュ衝突を解決するための一般的な方法がいくつかあります。

チェイン法 (Chaining)

チェイン法は、ハッシュ衝突を解決するための一般的な手法の一つです。各バケットが、そのバケットにハッシュされたすべてのキーと値のペアを格納するリンクリスト（または同様のデータ構造）のヘッドとして機能します。衝突が発生した場合、新しいキーと値のペアは、対応するバケットのリンクリストの末尾に追加されます。

バケット (Bucket)

ハッシュテーブルの基本的なストレージ単位です。このコミットでは、各バケットが固定数のエントリ（8エントリ）を保持するように設計されています。これにより、バケット内の要素へのアクセスが効率化されます。

インクリメンタルなリサイズ (Incremental Resizing)

ハッシュテーブルの要素数が増加し、ロードファクタ（要素数とバケット数の比率）が一定の閾値を超えると、パフォーマンスを維持するためにテーブルを拡張（リサイズ）する必要があります。従来のリサイズでは、新しいより大きなバケット配列を割り当て、既存のすべての要素を新しい配列に再ハッシュして移動させるため、一時的に大きな遅延が発生する可能性がありました。インクリメンタルなリサイズでは、このプロセスを一度に行うのではなく、複数の操作（例えば、挿入や削除）にわたって段階的に行います。これにより、リサイズによる一時的なパフォーマンスの低下を分散させ、アプリケーションの応答性を維持することができます。古いバケットから新しいバケットへの要素の移動は、マップ操作中に少しずつ行われます。

技術的詳細

このコミットは、Goランタイムのmap実装を根本的に変更し、パフォーマンスとメモリ効率を向上させています。主要な変更は以下のファイルに集中しています。

src/pkg/runtime/hashmap.c
src/pkg/runtime/hashmap.h
src/pkg/runtime/hashmap_fast.c
src/cmd/gc/builtin.c
src/cmd/gc/walk.c

新しいハッシュマップ構造 (`Hmap`と`Bucket`)

以前のハッシュマップ実装は、hash_subtableという構造体を中心とした、より複雑な多段階のハッシュ構造を持っていました。このコミットでは、よりシンプルで効率的なバケットベースの構造に移行しています。

`Bucket`構造体

新しいBucket構造体は、src/pkg/runtime/hashmap.hで定義されています。

typedef struct Bucket Bucket;
struct Bucket
{
    uint8 tophash[BUCKETSIZE];  // top 8 bits of hash of each entry (0 = empty)
    Bucket *overflow;           // overflow bucket, if any
    byte data[1];               // BUCKETSIZE keys followed by BUCKETSIZE values
};

tophash[BUCKETSIZE]: 各エントリのハッシュ値の上位8ビットを格納します。これにより、バケット内のキーを比較する前に、ハッシュ値の上位ビットを比較することで、高速なフィルタリングが可能になります。0はエントリが空であることを示します。
overflow: バケットが満杯になった場合に、追加のエントリを格納するためのオーバーフローバケットへのポインタです。これにより、チェイン法による衝突解決が実現されます。
data[1]: 可変長配列のプレースホルダーで、BUCKETSIZE個のキーとBUCKETSIZE個の値が連続して格納されます。キーと値をまとめて格納することで、パディングを減らし、メモリ効率を向上させています。

`Hmap`構造体

src/pkg/runtime/hashmap.cで定義されるHmap構造体は、ハッシュマップ全体の状態を管理します。

struct Hmap
{
    uintgo  count;        // # live cells == size of map.  Must be first (used by len() builtin)
    uint8   B;            // log_2 of # of buckets (can hold up to LOAD * 2^B items)
    uint8   flags;
    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
    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)
};

count: マップ内の要素数。
B: バケット配列のサイズを決定する2の対数（2^B個のバケット）。
flags: キーや値が間接的に格納されているか（ポインタとして）、イテレータが存在するかなどの情報を示すフラグ。
keysize, valuesize, bucketsize: キー、値、バケットのサイズ（バイト単位）。
hash0: ハッシュ計算に使用されるシード値。
buckets: 現在のバケット配列へのポインタ。
oldbuckets: リサイズ中の古いバケット配列へのポインタ。インクリメンタルなリサイズをサポートするために使用されます。
nevacuate: インクリメンタルなリサイズにおける、古いバケットから新しいバケットへの要素移動の進捗を示すカウンタ。

定数と最適化

BUCKETSIZE (8): 各バケットが保持できるキー/値ペアの最大数。
LOAD (6.5): バケットの平均負荷（要素数/バケット数）がこの値を超えると、テーブルの拡張がトリガーされます。この値は、オーバーフローバケットの割合、エントリあたりのオーバーヘッドバイト、プローブ回数などを考慮して決定されています。
MAXKEYSIZE (128), MAXVALUESIZE (128): キーまたは値のサイズがこの値を超えると、インラインで格納する代わりに、ヒープに割り当ててポインタとして格納されます（間接参照）。これにより、大きなキーや値を持つマップのメモリ使用量を最適化します。

インクリメンタルなリサイズ (`grow_work`と`evacuate`)

このコミットの重要な特徴は、ハッシュテーブルのインクリメンタルなリサイズです。

hash_grow(MapType *t, Hmap *h): テーブルの拡張が必要になったときに呼び出されます。新しいより大きなバケット配列を割り当て、h->oldbucketsに古い配列を設定し、h->bucketsに新しい配列を設定します。実際の要素の移動はここで行われません。
evacuate(MapType *t, Hmap *h, uintptr oldbucket): oldbuckets内の特定のバケット（oldbucket）とそのオーバーフローチェイン内のすべてのエントリを、新しいbuckets配列の対応する位置（oldbucketとoldbucket + 2^(B-1)）に移動させます。この関数は、マップの挿入 (hash_insert) や検索 (hash_lookup) などの操作中に、必要に応じて呼び出されます。これにより、リサイズ処理が複数の操作に分散され、一時的な大きな遅延が回避されます。

高速なマップアクセス (`hashmap_fast.c`とコンパイラの変更)

このコミットでは、特定のキー型（uint32, uint64, string）に対して、より高速なマップアクセス関数が導入されています。

src/pkg/runtime/hashmap_fast.c: hashmap.cから分離されたファイルで、これらの高速アクセス関数の実装が含まれています。これらは、キーの比較やハッシュ計算をインライン化し、一般的なケースでのオーバーヘッドを削減します。
src/cmd/gc/builtin.c: ランタイムの組み込み関数定義に、mapaccess1_fast32, mapaccess1_fast64, mapaccess1_faststrなどの高速アクセス関数が追加されています。
src/cmd/gc/walk.c: Goコンパイラのコード生成部分が変更され、マップアクセス時にキーの型とサイズに基づいて、これらの高速アクセス関数を自動的に選択して呼び出すようになりました。これにより、開発者が意識することなく、特定のキー型でのマップ操作が最適化されます。

DWARFデバッグ情報の変更 (`src/cmd/ld/dwarf.c`)

このコミットには、DWARFデバッグ情報生成に関する変更も含まれています。これは主に、新しいハッシュマップ実装の内部構造がデバッガに正しく表示されるようにするための調整です。特に、DW_ABRV_MAPTYPEの処理や、型定義のウォークロジックが簡素化されています。また、DWARFバージョンが2から3に更新されています。

テストの追加 (`src/pkg/runtime/map_test.go`, `src/pkg/runtime/mapspeed_test.go`)

新しいハッシュマップ実装の正確性とパフォーマンスを検証するために、広範なテストが追加されています。

map_test.go: 新しいマップ実装の基本的な機能、エッジケース、および並行性に関するテストが含まれています。
mapspeed_test.go: パフォーマンスベンチマークが含まれており、新しい実装が期待される速度向上を達成していることを確認します。

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

このコミットにおけるコアとなるコードの変更は、主に以下のファイルと機能に集中しています。

src/pkg/runtime/hashmap.c および src/pkg/runtime/hashmap.h:
- ハッシュマップの主要なデータ構造 (Hmap, Bucket) の定義が全面的に刷新されました。
- hash_init: マップの初期化ロジックが変更され、新しいバケット構造に合わせて調整されました。
- hash_grow: マップの拡張（リサイズ）を開始する関数。新しいバケット配列の割り当てと、古いバケット配列の参照を管理します。
- evacuate: インクリメンタルなリサイズの中核をなす関数。古いバケットから新しいバケットへキーと値を移動させます。
- hash_lookup: キーの検索ロジックが新しいバケット構造とインクリメンタルなリサイズに対応するように変更されました。
- hash_insert: キーと値の挿入ロジックが変更され、新しいバケット構造、インクリメンタルなリサイズ、および高速アクセスパスに対応しました。
- hash_remove: キーの削除ロジックが変更されました。
- hash_iter_init: マップイテレータの初期化ロジックが新しい構造に合わせて変更されました。
src/pkg/runtime/hashmap_fast.c:
- runtime·mapaccess1_fast32, runtime·mapaccess1_fast64, runtime·mapaccess1_faststr などの、特定のキー型（uint32, uint64, string）に特化した高速なマップアクセス関数が実装されました。これらの関数は、キーの比較やハッシュ計算を最適化し、一般的なケースでのパフォーマンスを向上させます。
src/cmd/gc/builtin.c:
- Goランタイムの組み込み関数リストに、新しい高速マップアクセス関数（例: mapaccess1_fast32, mapaccess2_faststr）の宣言が追加されました。これにより、コンパイラがこれらの関数を認識し、呼び出すことができるようになります。
src/cmd/gc/walk.c:
- Goコンパイラのコード生成フェーズにおけるマップアクセス処理が変更されました。マップのキー型と値のサイズに基づいて、適切な高速アクセス関数（mapaccess1_fast*, mapaccess2_fast*）を自動的に選択し、呼び出すロジックが追加されました。これにより、コンパイル時にマップ操作が最適化されます。
src/cmd/ld/dwarf.c:
- DWARFデバッグ情報生成ロジックが変更され、新しいハッシュマップの内部構造がデバッガで正しく表示されるように調整されました。特に、synthesizemaptypes関数におけるマップ型のDWARF表現の生成方法が更新されました。また、DWARFバージョンが2から3に更新されています。

Bucketは、固定サイズ（BUCKETSIZE、通常8）のキー/値ペアと、オーバーフローバケットへのポインタ、そして各エントリのハッシュ上位8ビットを格納するtophash配列を持ちます。tophashは、バケット内の高速なルックアップを可能にするための重要な最適化です。
Hmapは、マップ全体のメタデータ（要素数、バケット配列のサイズ、キー/値のサイズ、ハッシュシードなど）と、現在のバケット配列(buckets)、そしてインクリメンタルなリサイズ中の古いバケット配列(oldbuckets)へのポインタを保持します。

インクリメンタルなリサイズの実装 (`hash_grow` と `evacuate`)

hash_grow: マップのロードファクタが閾値（LOAD）を超えたときに呼び出されます。この関数は、新しいバケット配列を割り当て、h->oldbucketsに現在の配列を、h->bucketsに新しい配列を設定します。重要なのは、この時点ではまだ要素の移動は行われないことです。
evacuate: oldbuckets内の特定のバケット（oldbucket）の要素を、新しいbuckets配列の対応する2つのバケット（oldbucketとoldbucket + newbit）に分散して移動させます。newbitは、新しいバケット配列の半分を示すビットマスクです。この関数は、マップの読み取り (hash_lookup) や書き込み (hash_insert) 操作中に、必要に応じて呼び出されます。これにより、リサイズ処理がバックグラウンドで少しずつ進行し、アプリケーションの応答性が維持されます。evacuatedフラグは、古いバケットが既に処理されたことを示します。

`hash_lookup` と `hash_insert` の変更

これらの関数は、新しいバケット構造とインクリメンタルなリサイズロジックに対応するように書き直されました。

hash_lookup:
1. キーのハッシュ値を計算します。
2. ハッシュ値の下位ビットを使用して、ターゲットバケットを決定します。
3. もしoldbucketsが存在する場合（リサイズ中）、grow_workを呼び出して、現在のバケットに関連する古いバケットの要素を新しいバケットに移動させます。
4. ターゲットバケットとそのオーバーフローチェインを走査し、tophashとキーの完全な比較を使用して一致するエントリを探します。
hash_insert:
1. キーのハッシュ値を計算します。
2. hash_lookupと同様に、リサイズ中の場合はgrow_workを呼び出します。
3. ターゲットバケットとそのオーバーフローチェインを走査し、既存のキーが見つかれば値を更新します。
4. 既存のキーが見つからず、バケットに空きがあればそこに新しいエントリを挿入します。
5. バケットが満杯で、マップのロードファクタが閾値を超えている場合は、hash_growを呼び出してテーブルを拡張し、再度挿入を試みます。
6. バケットが満杯だが、ロードファクタが閾値を超えていない場合は、新しいオーバーフローバケットを割り当ててそこに挿入します。

`src/pkg/runtime/hashmap_fast.c` における高速アクセス関数の実装

このファイルは、特定のプリミティブ型（uint32, uint64, string）のキーを持つマップに対する最適化されたアクセス関数を提供します。

これらの関数（例: runtime·mapaccess1_fast32）は、ジェネリックなマップアクセス関数よりも少ないオーバーヘッドで動作するように設計されています。
キーのハッシュ計算と等価性チェックが、それぞれの型に特化してインライン化されています。
これにより、コンパイラがこれらの高速パスを選択できる場合、マップ操作の実行速度が向上します。

`src/cmd/gc/walk.c` におけるコンパイラの変更

Goコンパイラのwalk.cファイルは、Goソースコードを中間表現に変換する際の重要なステップです。このコミットでは、マップアクセス式（例: m[key]）の処理方法が変更されました。

コンパイラは、マップアクセスのキーの型を分析し、その型がuint32, uint64, stringのいずれかであり、かつ値のサイズがMAXVALUESIZE（128バイト）以下である場合に、対応する高速アクセス関数（例: mapaccess1_fast32）を呼び出すようにコードを生成します。
これにより、開発者が明示的に何かをする必要なく、コンパイラが自動的に最適なマップアクセスパスを選択し、パフォーマンスを向上させます。

これらの変更により、Goのmapは、より効率的なメモリレイアウト、スムーズなリサイズ、および一般的なキー型に対する高速なアクセスパスを持つ、堅牢で高性能なデータ構造へと進化しました。

参考にした情報源リンク

https://github.com/golang/go/commit/00224a356a5be3c134230bfa8fe11e0af2977aaf
Go hashmap implementation 2013 - Google Search Results (Web search performed by Gemini)
Go issue 3885 - Google Search Results (Web search performed by Gemini)
Go言語のmapの内部実装に関する一般的な情報源（例: Ardan Labsのブログ記事、Stack Overflowの議論など、2013年当時の情報を含む）

comemo