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

コミット

commit 3be4d95731a17073afb1f69bde264eecbdfa32bb
Author: Josh Bleecher Snyder <josharian@gmail.com>
Date:   Tue Jan 14 12:54:05 2014 -0800

    runtime: change map iteration randomization to use intra-bucket offset
    
    Map iteration previously started from a random bucket, but walked each
    bucket from the beginning. Now, iteration always starts from the first
    bucket and walks each bucket starting at a random offset. For
    performance, the random offset is selected at the start of iteration
    and reused for each bucket.
    
    Iteration over a map with 8 or fewer elements--a single bucket--will
    now be non-deterministic. There will now be only 8 different possible
    map iterations.
    
    Significant benchmark changes, on my OS X laptop (rough but consistent):
    
    benchmark                              old ns/op     new ns/op     delta
    BenchmarkMapIter                       128           121           -5.47%
    BenchmarkMapIterEmpty                  4.26          4.45          +4.46%
    BenchmarkNewEmptyMap                   114           111           -2.63%
    
    Fixes #6719.
    
    R=khr, bradfitz
    CC=golang-codereviews
    https://golang.org/cl/47370043

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

https://github.com/golang/go/commit/3be4d95731a17073afb1f69bde264eecbdfa32bb

元コミット内容

このコミットは、Go言語のランタイムにおけるマップ（map）のイテレーション（要素の走査）のランダム化メカニズムを変更します。以前は、マップのイテレーションはランダムなバケットから開始されていましたが、各バケット内では常に先頭から要素が走査されていました。この変更により、イテレーションは常に最初のバケットから開始されますが、各バケット内ではランダムなオフセットから要素が走査されるようになります。このランダムなオフセットはイテレーション開始時に一度だけ選択され、パフォーマンスのために各バケットで再利用されます。

この変更の結果、8つ以下の要素を持つマップ（単一のバケットに収まるマップ）のイテレーション順序は非決定論的になります。具体的には、8つの異なるイテレーション順序が可能になります。

ベンチマーク結果として、BenchmarkMapIterが約5.47%改善され、BenchmarkNewEmptyMapが約2.63%改善されています。一方で、BenchmarkMapIterEmptyはわずかに悪化しています。

このコミットは、Issue #6719を修正します。

変更の背景

Go言語のマップイテレーションの順序は、意図的にランダム化されています。これは、開発者がマップの順序に依存するコードを書くことを防ぎ、将来のランタイムの最適化や実装変更の自由度を確保するためです。もしマップの順序が常に一定であると保証されてしまうと、開発者はその順序に依存したコードを書いてしまい、ランタイムの内部実装を変更する際に互換性の問題が生じる可能性があります。

しかし、以前の実装では、マップのイテレーションはランダムなバケットから開始されるものの、各バケット内では常に先頭から走査されていました。これにより、特に要素数が少ないマップ（単一のバケットに収まるマップ）の場合、イテレーションのランダム性が不十分であるという問題がありました。Issue #6719は、このランダム性の不足、特に小さなマップにおける予測可能なイテレーション順序に関する問題を指摘していました。

このコミットは、バケット内の走査開始位置もランダム化することで、マップイテレーションのランダム性をさらに強化し、特に小さなマップにおける非決定性を向上させることを目的としています。これにより、開発者がマップの順序に依存することをより困難にし、Goの設計思想に沿った挙動を実現します。また、この変更は一部のベンチマークでパフォーマンスの改善ももたらしています。

前提知識の解説

このコミットを理解するためには、以下のGo言語およびコンピュータサイエンスの基本的な概念を理解しておく必要があります。

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

   • Goのmapは、キーと値のペアを格納するハッシュテーブル（連想配列）です。
   • Goのマップは、内部的にバケットと呼ばれる構造にデータを格納します。キーのハッシュ値に基づいて、どのバケットにデータが格納されるかが決定されます。
   • マップのイテレーション順序は、Goの仕様によって「非決定論的」であることが保証されています。これは、同じマップに対して同じ要素を格納しても、イテレーションのたびに異なる順序で要素が返される可能性があることを意味します。これは意図的な設計であり、開発者がマップの順序に依存するコードを書くことを防ぐためです。

2. ハッシュテーブルの内部構造:

   • ハッシュテーブルは、キーをハッシュ関数に通して得られるハッシュ値を使って、データを格納するメモリ上の位置（バケット）を決定します。
   • バケット: ハッシュテーブルの基本的な格納単位です。複数のキーが同じバケットにマッピングされることがあります（ハッシュ衝突）。
   • 衝突解決: ハッシュ衝突が発生した場合、Goのマップでは通常、同じバケット内に複数のキーと値のペアを連結リストのように格納します。
   • リサイズ (Grow): マップに要素が追加され、バケットの密度が高くなりすぎると、パフォーマンスを維持するためにマップはより多くのバケットを持つ新しい、より大きなハッシュテーブルにリサイズされます。このプロセスは「grow」と呼ばれます。

3. ランダム性 (Randomness) と非決定性 (Non-determinism):

   • ランダム性: 予測不可能な結果を生み出す性質です。Goのマップイテレーションのランダム化は、開発者が順序に依存できないようにするためのセキュリティ対策でもあります（例: サービス拒否攻撃を防ぐため）。
   • 非決定性: 同じ入力に対して常に同じ出力が保証されない性質です。マップのイテレーション順序が非決定論的であるということは、プログラムを複数回実行しても、マップの要素が異なる順序で列挙される可能性があることを意味します。

4. runtime パッケージ:

   • Go言語のruntimeパッケージは、ガベージコレクション、スケジューリング、マップの実装など、Goプログラムの実行を管理する低レベルの機能を提供します。C言語とGo言語の混合で実装されています。
   • hashmap.c: Goランタイムにおけるマップのコアロジック（ハッシュ、バケット管理、イテレーションなど）がC言語で実装されているファイルです。
   • reflect.c: Goのreflectパッケージに関連するランタイムの型情報や構造体レイアウトを定義するC言語のファイルです。mapのイテレータ構造体（hash_iter）のサイズやフィールドのオフセットをコンパイラが認識するために、このファイルで定義された情報が使用されます。

5. BUCKETSIZE:

   • Goのマップ実装において、各バケットが保持できるキーと値のペアの最大数です。このコミットの時点では8でした。

技術的詳細

このコミットの技術的な核心は、Goランタイムのマップイテレーションロジック、特にsrc/pkg/runtime/hashmap.c内のhash_iter構造体とhash_iter_init、hash_next関数の変更にあります。

変更前のイテレーションロジック

変更前は、マップのイテレーションは以下の手順で行われていました。

1. hash_iter_initで、runtime·fastrand1()を使ってランダムな開始バケット（it->bucketおよびit->endbucket）が選択されていました。
2. hash_nextでは、選択された開始バケットから順にバケットを走査し、各バケット内では常にインデックス0からBUCKETSIZE-1まで要素を走査していました。
3. すべてのバケットを走査し終えるか、endbucketに到達してwrappedフラグがtrueになるとイテレーションが終了しました。

この方式では、バケットの選択はランダムでしたが、バケット内の要素の走査順序は常に一定でした。そのため、特に要素数がBUCKETSIZE（当時8）以下のマップの場合、単一のバケットにすべての要素が収まるため、イテレーションの順序は実質的に決定論的になってしまうという問題がありました。

変更後のイテレーションロジック

このコミットでは、イテレーションのランダム化戦略が以下のように変更されました。

1. hash_iter構造体の変更:

   • uintptr endbucket; と bool wrapped; フィールドが削除され、代わりに uint32 offset; と bool done; フィールドが追加されました。
     • offset: 各バケット内でイテレーションを開始するランダムなオフセット（0からBUCKETSIZE-1の範囲）。
     • done: イテレーションが完了したかどうかを示すフラグ。
   • これにより、hash_iter構造体のサイズが11 * uintptrから10 * uintptrに減少しました。この変更は、コンパイラがhash_iter構造体のレイアウトを正しく認識するために、src/cmd/gc/reflect.cにも反映されています。

2. hash_iter_init関数の変更:

   • イテレーションの開始バケットは常に0に設定されるようになりました (it->bucket = 0;)。
   • it->offset = runtime·fastrand1() & (BUCKETSIZE - 1); により、バケット内のランダムな開始オフセットが一度だけ計算され、it->offsetに格納されます。このオフセットは、そのイテレーション全体で再利用されます。
   • it->done = false; が初期化されます。
   • hash_iter構造体のサイズチェックが11から10に変更されました。

3. hash_next関数の変更:

   • バケット内の要素を走査するループが変更されました。以前はfor(; i < BUCKETSIZE; i++)のようにiを0から順に増やしていましたが、変更後はoffi = (i + it->offset) & (BUCKETSIZE - 1); を使って、it->offsetで指定されたランダムな開始位置から要素を走査するようになりました。& (BUCKETSIZE - 1)は、BUCKETSIZEが2の冪乗であることを利用した剰余演算（% BUCKETSIZE）の高速化です。
   • イテレーションの終了条件がit->doneフラグに基づいて行われるようになりました。すべてのバケットを走査し終えるとit->doneがtrueに設定されます。

src/cmd/gc/reflect.cの変更

src/cmd/gc/reflect.cは、Goコンパイラがランタイムのデータ構造、特にhash_iterのような内部構造体のレイアウトを認識するために使用されます。hash_iter構造体のフィールドが変更され、サイズが小さくなったため、このファイル内のhiter関数で定義されているhash_iterのサイズとotherフィールドの配列サイズが更新されました。具体的には、otherフィールドのboundが5から4に、widthが5 * widthptrから4 * widthptrに、そして最終的なhash_iterの合計サイズチェックが11 * widthptrから10 * widthptrに変更されています。これは、コンパイラがランタイムの内部構造を正しく理解し、それに対応するGoのreflect型を生成するために必要な変更です。

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

マップイテレーションのランダム性が向上したことをテストするために、TestMapIterOrder関数内のテストケースが拡張されました。以前は9, 15の要素数でテストしていましたが、この変更により、単一バケットに収まる要素数である3, 7もテスト対象に追加されました。これにより、小さなマップでもイテレーション順序が非決定論的になることを確認できるようになりました。

パフォーマンスへの影響

コミットメッセージに記載されているベンチマーク結果は、この変更がパフォーマンスに与える影響を示しています。

• BenchmarkMapIter: マップのイテレーション自体のパフォーマンスが向上しています。これは、ランダムなバケット選択のオーバーヘッドが減り、バケット内のオフセット計算が効率的であるためと考えられます。
• BenchmarkMapIterEmpty: 空のマップのイテレーションはわずかに悪化しています。これは、新しいdoneフラグのチェックなどのオーバーヘッドが影響している可能性があります。
• BenchmarkNewEmptyMap: 新しい空のマップの作成は改善しています。これは、hash_iter構造体のサイズが小さくなったことによるメモリフットプリントの削減などが寄与している可能性があります。

全体として、この変更はマップイテレーションのランダム性を強化しつつ、主要なイテレーションシナリオでのパフォーマンスを改善しています。

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

このコミットにおけるコアとなるコードの変更箇所は以下の3つのファイルにまたがっています。

1. src/cmd/gc/reflect.c:

   • hiter関数内で定義されているhash_iter構造体のotherフィールドのサイズが変更されました。
     • - field[6]->type->bound = 5;
     • - field[6]->type->width = 5 * widthptr;
     • + field[6]->type->bound = 4;
     • + field[6]->type->width = 4 * widthptr;
   • hash_iter構造体の合計サイズチェックが変更されました。
     • - if(off != 11 * widthptr)
     • + if(off != 10 * widthptr)

2. src/pkg/runtime/hashmap.c:

   • hash_iter構造体の定義が変更されました。
     • - uintptr endbucket;
     • - bool wrapped;
     • + uint32 offset;
     • + bool done;
   • hash_iter_init関数で、イテレーションの初期化ロジックが変更されました。
     • hash_iter構造体のサイズチェックが変更されました。
       • - if(sizeof(struct hash_iter) / sizeof(uintptr) != 11)
       • + if(sizeof(struct hash_iter) / sizeof(uintptr) != 10)
     • 開始バケットのランダム選択が削除され、常に0から開始するようになりました。
       • - it->bucket = it->endbucket = runtime·fastrand1() & (((uintptr)1 << h->B) - 1);
       • + it->bucket = 0;
     • バケット内オフセットのランダム選択が追加されました。
       • + it->offset = runtime·fastrand1() & (BUCKETSIZE - 1);
     • イテレーション完了フラグの初期化が変更されました。
       • - it->wrapped = false;
       • + it->done = false;
     • 空マップの場合のイテレーション終了条件が変更されました。
       • - it->wrapped = true;
       • + it->done = true;
   • hash_next関数で、バケット内の要素走査ロジックが変更されました。
     • イテレーション終了条件が変更されました。
       • - if(bucket == it->endbucket && it->wrapped)
       • + if(it->done)
     • 次のバケットへの移動時のイテレーション完了フラグ設定が変更されました。
       • - it->wrapped = true;
       • + it->done = true;
     • バケット内の要素アクセスにランダムオフセットが適用されるようになりました。
       • - k = b->data + h->keysize * i;
       • - v = b->data + h->valuesize * i;
       • + offi = (i + it->offset) & (BUCKETSIZE - 1);
       • + k = b->data + h->keysize * offi;
       • + v = b->data + h->keysize * BUCKETSIZE + h->valuesize * offi;
     • tophash配列のアクセスにもランダムオフセットが適用されるようになりました。
       • - if(b->tophash[i] != Empty && b->tophash[i] != EvacuatedEmpty)
       • + if(b->tophash[offi] != Empty && b->tophash[offi] != EvacuatedEmpty)
       • - if(check_bucket >> (it->B - 1) != (b->tophash[i] & 1))
       • + if(check_bucket >> (it->B - 1) != (b->tophash[offi] & 1))
       • - if(b->tophash[i] != EvacuatedX && b->tophash[i] != EvacuatedY)
       • + if(b->tophash[offi] != EvacuatedX && b->tophash[offi] != EvacuatedY)

3. src/pkg/runtime/map_test.go:

   • TestMapIterOrder関数内のテスト対象の要素数に3と7が追加されました。
     • - for _, n := range [...]int{9, 15} {
     • + for _, n := range [...]int{3, 7, 9, 15} {

コアとなるコードの解説

src/cmd/gc/reflect.c の変更

このファイルはGoコンパイラのバックエンドの一部であり、Goの型システムとランタイムのデータ構造間の橋渡しをします。hiter関数は、Goのmapイテレータの内部表現であるhash_iter構造体のレイアウトをコンパイラに教える役割を担っています。

変更前は、hash_iter構造体にはendbucketとwrappedというフィールドが含まれており、これらがotherというuintptrの配列の一部として表現されていました。このother配列のサイズは5でした。

// 変更前 (概念図)
struct hash_iter {
    // ... (他のフィールド)
    uintptr endbucket; // other[0]
    bool wrapped;      // other[1] (uintptrにパディングされる)
    // ... (残りのotherフィールド)
    uintptr other[5]; // 実際にはother[0]からother[4]まで
};

コミットによってendbucketとwrappedが削除され、offsetとdoneに置き換えられました。offsetはuint32、doneはboolであり、これらはuintptrよりも小さいサイズです。これにより、hash_iter構造体の全体的なサイズが小さくなり、other配列の必要なサイズも4に減りました。

// 変更後 (概念図)
struct hash_iter {
    // ... (他のフィールド)
    uint32 offset; // 新しいフィールド
    bool done;     // 新しいフィールド
    // ... (残りのotherフィールド)
    uintptr other[4]; // 実際にはother[0]からother[3]まで
};

reflect.cの変更は、このランタイム構造体の変更をコンパイラに正確に反映させるためのものです。field[6]->type->boundとfield[6]->type->widthの変更は、other配列のサイズとそれに伴うメモリ幅の調整を示しています。また、if(off != 11 * widthptr)からif(off != 10 * widthptr)への変更は、hash_iter構造体全体のサイズが11 * uintptrから10 * uintptrに減少したことを確認するためのアサーションです。これにより、Goのreflectパッケージがマップイテレータの内部構造を正しく扱えるようになります。

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

このファイルはGoのマップのランタイム実装の核心です。

1. hash_iter構造体の変更:

   • endbucketとwrappedが削除され、offsetとdoneが追加されました。
   • offset (uint32) は、各バケット内で要素を走査する際の開始位置をランダム化するために使用されます。
   • done (bool) は、イテレーションが完全に終了したかどうかを示すシンプルなフラグです。これにより、以前のwrappedフラグとendbucketの複雑な組み合わせによる終了判定が簡素化されました。

2. hash_iter_init関数の変更:

   • 開始バケットの固定: 以前はit->bucket = it->endbucket = runtime·fastrand1() & (((uintptr)1 << h->B) - 1); のようにランダムなバケットからイテレーションを開始していましたが、変更後はit->bucket = 0; となり、常に最初のバケット（インデックス0）からイテレーションを開始するようになりました。
   • バケット内オフセットのランダム化: it->offset = runtime·fastrand1() & (BUCKETSIZE - 1); が追加されました。runtime·fastrand1()はランダムなuint32値を生成し、それをBUCKETSIZE - 1とビットAND演算することで、0からBUCKETSIZE - 1の範囲のランダムなオフセットを生成します。このオフセットは、そのイテレーションセッション全体で再利用されます。
   • 終了フラグの初期化: it->done = false; が設定されます。空のマップの場合、すぐにit->done = true; に設定され、イテレーションが即座に終了するようにします。

3. hash_next関数の変更:

   • イテレーション終了条件の簡素化: 以前のif(bucket == it->endbucket && it->wrapped)という複雑な条件が、新しいif(it->done)というシンプルな条件に置き換えられました。
   • バケット内走査のランダム化: 最も重要な変更は、バケット内の要素を走査するループ内です。
     • offi = (i + it->offset) & (BUCKETSIZE - 1);
     • この行が、バケット内の要素アクセスにランダム性を導入します。iはバケット内の現在の論理的なインデックス（0からBUCKETSIZE-1）ですが、実際のアクセスはit->offsetを加算し、BUCKETSIZEで剰余を取ることで行われます。これにより、例えばBUCKETSIZEが8でit->offsetが3の場合、最初の要素はインデックス3から、次は4、…、7、0、1、2という順序で走査されます。
     • このoffiを使って、キー(k)、値(v)、およびtophash配列（各要素のハッシュの最上位バイトを格納）にアクセスします。これにより、バケット内の要素の走査順序がランダム化されます。

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

このファイルはGoのマップのテストコードです。TestMapIterOrderは、マップのイテレーション順序が非決定論的であることを確認するためのテストです。

変更前は、要素数が9と15のマップに対してのみテストが行われていました。これらの要素数では、マップは複数のバケットに分散される可能性が高く、イテレーションのランダム性が比較的容易に観察できました。

しかし、Issue #6719で指摘されたように、要素数がBUCKETSIZE（当時8）以下のマップ、つまり単一のバケットに収まるマップでは、イテレーションのランダム性が不十分でした。このコミットの変更により、バケット内の走査順序もランダム化されたため、単一バケットのマップでも非決定性が保証されるようになりました。

そこで、テストケースに3と7という要素数が追加されました。これらの要素数はBUCKETSIZE以下であり、単一のバケットに収まる可能性が高いです。これらのテストケースを追加することで、小さなマップでもイテレーション順序が非決定論的になるという新しい挙動が正しく実装されていることを検証できるようになりました。

関連リンク

• Go Issue #6719: https://github.com/golang/go/issues/6719
• Go CL 47370043: https://golang.org/cl/47370043 (このコミットに対応するGoのコードレビューリンク)

参考にした情報源リンク

• Go言語の公式ドキュメント (map型): https://go.dev/ref/spec#Map_types
• Go言語のマップ実装に関するブログ記事や解説 (一般的な知識として):
  • The Go Blog: Go maps in action: https://go.dev/blog/maps
  • Go's map implementation: https://dave.cheney.net/2018/05/29/gos-map-implementation
• Goのランタイムソースコード (特にsrc/runtime/map.goやsrc/runtime/hashmap.go、src/cmd/compile/internal/gc/reflect.goなど、コミット当時のGo 1.2あたりのバージョンを参照)
  • Go 1.2 Source Code: https://go.dev/doc/go1.2 (当時のソースコード構造を理解するため)
• ハッシュテーブルの一般的な概念に関する情報源 (データ構造とアルゴリズムの教科書など)
• Goのreflectパッケージに関する情報源 (Goの型システムとランタイムの連携を理解するため)
  • The Go Blog: The Laws of Reflection: https://go.dev/blog/laws-of-reflection
• runtime·fastrand1() のようなランタイム内部関数に関する情報 (Goのランタイムソースコードを直接読むことで理解を深める)
• BUCKETSIZE のようなGoマップの内部定数に関する情報 (Goのランタイムソースコードを直接読むことで理解を深める)
• Goのベンチマークに関する情報 (Goのtestingパッケージのドキュメントなど)
  • Go Testing: https://go.dev/pkg/testing/
  • Go Benchmarking: https://go.dev/doc/articles/go_benchmarking.html