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

このコミットは、Goランタイムのハッシュマップ（map型）の内部実装に関する変更です。具体的には、マップのサイズが大きくなる際に行われる「成長（grow）」作業の処理方法を改善しています。

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

• src/pkg/runtime/hashmap.c
• src/pkg/runtime/hashmap_fast.c

コミット

commit 07b6add0ca1f1dc38270cddf3d30f9b06503c9e3
Author: Keith Randall <khr@golang.org>
Date:   Fri May 31 20:58:31 2013 -0700

    runtime: do hashmap grow work during reads.
    
    Before this change, grow work was done only
    during map writes to ensure multithreaded safety.
    This can lead to maps remaining in a partially
    grown state for a long time, potentially forever.
    This change allows grow work to happen during reads,
    which will lead to grow work finishing sooner, making
    the resulting map smaller and faster.
    
    Grow work is not done in parallel.  Reads can
    happen in parallel while grow work is happening.
    
    R=golang-dev, dvyukov, khr, iant
    CC=golang-dev
    https://golang.org/cl/8852047

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

https://github.com/golang/go/commit/07b6add0ca1f1dc38270cddf3d30f9b06503c9e3

元コミット内容

runtime: do hashmap grow work during reads.

Before this change, grow work was done only
during map writes to ensure multithreaded safety.
This can lead to maps remaining in a partially
grown state for a long time, potentially forever.
This change allows grow work to happen during reads,
which will lead to grow work finishing sooner, making
the resulting map smaller and faster.

Grow work is not done in parallel.  Reads can
happen in parallel while grow work is happening.

変更の背景

Goのmap（ハッシュマップ）は、要素数が一定の閾値を超えると、より大きな容量を持つ新しい内部構造に「成長（grow）」します。この成長プロセスは、既存の要素を新しい構造に再配置する「エバキュエーション（evacuation）」という作業を伴います。

このコミット以前は、マップの成長作業（エバキュエーション）は、マップへの書き込み操作（要素の追加、更新、削除）が行われる際にのみ実行されていました。これは、複数のゴルーチンが同時にマップにアクセスする際の並行性安全性を確保するためでした。

しかし、この設計には問題がありました。もしマップへの書き込みが頻繁に行われない場合、マップは部分的に成長した（oldbucketsとbucketsの両方が存在し、データが完全に移行されていない）状態が長く続く可能性がありました。最悪の場合、書き込みが全く行われなければ、マップは永遠に部分的に成長したままとなり、メモリ使用効率が悪く、ルックアップ性能も低下するという問題がありました。部分的に成長したマップは、要素を探す際に古いバケットと新しいバケットの両方をチェックする必要があるため、パフォーマンスが低下します。

このコミットは、この問題を解決し、マップの成長作業をより効率的に、かつ迅速に完了させることを目的としています。

前提知識の解説

Goのmapの基本構造

Goのmapは、内部的にはハッシュテーブルとして実装されています。キーと値のペアを格納し、キーのハッシュ値に基づいてバケットと呼ばれるデータ構造に要素を配置します。衝突が発生した場合は、オーバーフローバケットを使用して要素を連結リストのように格納します。

マップの成長（Grow）とエバキュエーション（Evacuation）

マップの要素数が一定のロードファクタ（通常は6.5程度）を超えると、マップは自動的に成長します。成長プロセスは以下のステップで行われます。

1. 新しいバケット配列の確保: 現在のバケット配列の2倍のサイズの新しいバケット配列（buckets）が確保されます。古いバケット配列はoldbucketsとして保持されます。
2. エバキュエーションの開始: oldbucketsからbucketsへの要素の移行（エバキュエーション）が開始されます。この移行は一度に全て行われるのではなく、段階的に行われます。
3. 部分的な成長状態: エバキュエーションが完了するまでの間、マップは「部分的に成長した状態」にあります。この状態では、要素の検索や操作を行う際に、oldbucketsとbucketsの両方を考慮する必要があります。
4. エバキュエーションの完了: 全ての要素がoldbucketsからbucketsへ移行されると、oldbucketsは解放され、マップは完全に新しい構造に移行します。

エバキュエーションは、各oldbucketsのバケットを2つの新しいバケット（buckets内の対応するバケットと、新しいハッシュビットに対応するバケット）に分割して要素を移動させることで行われます。

並行性（Concurrency）とスレッドセーフティ

Goのmapは、複数のゴルーチンからの同時アクセスに対して安全ではありません。これは、マップの内部構造が変更される際に競合状態が発生する可能性があるためです。そのため、Goのmapは、書き込み操作（追加、更新、削除）中にロックを取得し、排他的アクセスを保証します。読み込み操作は通常、ロックなしで並行して行われますが、成長中のマップでは特別な考慮が必要です。

Goランタイムの原子操作（Atomic Operations）

Goランタイムは、低レベルの並行性プリミティブとして原子操作を提供します。これらは、複数のCPUコアから同時にアクセスされても、操作が中断されずに完了することを保証するものです。

• runtime·casp(ptr, old, new): Compare-And-Swap Pointer。ptrがoldと等しい場合にのみ、ptrをnewに更新します。この操作はアトミックに行われ、成功したかどうかを返します。ロックフリーなアルゴリズムでよく使用されます。
• runtime·atomicstorep(ptr, val): Atomic Store Pointer。ptrにvalをアトミックに書き込みます。

これらの操作は、ロックを使用せずに共有データ構造を安全に更新するために不可欠です。

技術的詳細

このコミットの主要な目的は、マップの成長作業を書き込み時だけでなく、読み込み時にも分散して実行することで、成長プロセスの完了を早め、マップの効率を向上させることです。

既存の問題点と解決策

前述の通り、以前はマップの成長作業は書き込み時のみに行われていました。これにより、書き込みが少ないマップでは、部分的に成長した状態が長く続き、メモリの無駄やパフォーマンスの低下を招いていました。

この変更では、マップの読み込み操作（hash_lookupやhash_next）が行われる際にも、マップが成長中であれば、少量の成長作業（エバキュエーション）を実行するようにしました。これにより、マップへのアクセスがある限り、成長作業が着実に進行し、最終的にマップが完全に成長した状態に移行するまでの時間が短縮されます。結果として、マップはより小さく、より高速になります。

grow_work_read関数の導入

このコミットの核心は、新しく導入されたgrow_work_read関数です。この関数は、マップの読み込みパスから呼び出され、マップの成長作業を少しだけ進めます。

grow_work_readは、複数のゴルーチンから同時に呼び出される可能性があるため、並行性安全性が非常に重要です。この関数は、h->nevacuateフィールドをロックとして利用し、runtime·casp（Compare-And-Swap Pointer）操作を用いて、一度に一つのゴルーチンのみが成長作業を実行できるようにします。

1. h->nevacuateの現在の値nを読み取ります。
2. nがEVAC_LOCK（他のゴルーチンがロック中であることを示す特殊な値）ではなく、かつまだ作業が残っている（n != noldbuckets）ことを確認します。
3. runtime·caspを使って、h->nevacuateをnからEVAC_LOCKにアトミックに設定しようと試みます。
4. caspが成功した場合（つまり、ロックを取得できた場合）、そのゴルーチンが排他的にエバキュエーション作業（evacuate(t, h, n)）を実行します。
5. 作業完了後、runtime·atomicstorepを使ってh->nevacuateをn + 1にアトミックに更新し、ロックを解放します。

このメカニズムにより、複数の読み込みゴルーチンが同時にgrow_work_readを呼び出しても、競合することなく安全に成長作業を進めることができます。成長作業自体は並行して行われませんが、読み込み操作は成長作業と並行して実行可能です。

エバキュエーションの同期とoverflowポインタの変更

evacuate関数も変更され、エバキュエーションの完了をマークする方法が原子的に行われるようになりました。以前は、b->overflow = (Bucket*)((uintptr)nextb + 1);のように直接ポインタを更新していましたが、この変更ではruntime·atomicstorep(&mainb->overflow, (Bucket*)((uintptr)b + 1));のように原子操作を使用しています。

これは、読み込みゴルーチンがoldbucketsから新しいバケットに切り替える際に、エバキュエーションが完了したかどうかを安全にチェックできるようにするためです。overflowポインタの最下位ビットをフラグとして使用し、エバキュエーションが完了したバケットをマークします。読み込み時にこのフラグをチェックすることで、古いバケットから新しいバケットへの参照を安全に切り替えることができます。

hash_lookupとhash_nextの変更

マップのルックアップ（hash_lookup）とイテレーション（hash_next）を行う関数は、マップが成長中である（h->oldbuckets != nil）場合、grow_work_readを呼び出すようになりました。これにより、これらの操作が実行されるたびに、マップの成長作業が少しずつ進められます。

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

src/pkg/runtime/hashmap.c

1. EVAC_LOCKの定義追加:

   #define EVAC_LOCK ((uintptr)-1)
   

   これは、Hmap構造体のnevacuateフィールドに設定され、エバキュエーションロックが取得されていることを示す特殊な値です。

2. evacuate関数の変更:

   • mainb変数の導入。
   • エバキュエーション済みかどうかのチェックをevacuated(mainb)からevacuated(mainb)に変更し、関数冒頭で実行。
   • バケットのエバキュエーション完了マークを原子的に設定する部分:

     // Mark main bucket as evacuated.  This write commits the
     // bucket evacuation (readers can start using the new buckets).
     b = mainb->overflow;
     runtime·atomicstorep(&mainb->overflow, (Bucket*)((uintptr)b + 1));
     
     // Mark overflow buckets for any iterators.
     // These writes don't need to reach anyone until the next hashtable
     // modification, so they don't need to be synchronized.
     while(b != nil) {
         nextb = b->overflow;
         b->overflow = (Bucket*)((uintptr)nextb + 1);
         b = nextb;
     }
     

     mainb->overflowの更新にruntime·atomicstorepを使用することで、他のゴルーチンからの読み込みに対して、エバキュエーションの完了が原子的に可視化されるようにしています。

3. grow_work関数の変更: この関数は、書き込み時に呼び出される成長作業の関数です。以前は複数のバケットをエバキュエーションしていましたが、この変更により、必要なバケットと追加で1つのバケットのみをエバキュエーションするように役割が限定されました。

   static void
   grow_work(MapType *t, Hmap *h, uintptr bucket)
   {
       uintptr noldbuckets;
       intptr n;
   
       // evac the bucket we're going to need
       noldbuckets = (uintptr)1 << (h->B - 1);
       evacuate(t, h, bucket & (noldbuckets - 1));
       // evac another bucket to make progress
       n = h->nevacuate;
       evacuate(t, h, n);
       // record what we've done
       h->nevacuate = n + 1;
       if(n + 1 == noldbuckets)
           h->oldbuckets = nil;
   }
   

4. grow_work_read関数の追加: 読み込み時に成長作業を行うための新しい関数です。

   // Do some work for growing the table.
   // Multithreaded-safe.
   static void
   grow_work_read(MapType *t, Hmap *h) {
       uintptr noldbuckets;
       intptr n;
   
       noldbuckets = (uintptr)1 << (h->B - 1);
   
       // Get evacuation lock.  If we can't get it, fine, that means
       // someone else is making progress which is good enough.
       n = h->nevacuate;
       if(n != EVAC_LOCK &&    // no one has evac lock
          n != noldbuckets &&    // there's still work to do
          runtime·casp((void**)&h->nevacuate, (void*)n, (void*)EVAC_LOCK)) { // we acquired lock
           // We're now the exclusive evacuator.
           evacuate(t, h, n);
   
           // record that we're done.
           runtime·atomicstorep((void**)&h->nevacuate, (void*)(n + 1));
           if(n + 1 == noldbuckets) {
               // commit finishing of grow.
               runtime·atomicstorep(&h->oldbuckets, nil);
               // note: can't free oldbuckets, someone might be using it.
               // it will have to get GCed.
           }
       }
   }
   

5. hash_lookup関数の変更: マップが成長中の場合（h->oldbuckets != nil）、grow_work_readを呼び出すようになりました。

   // ...
   b = runtime·atomicloadp(&h->oldbuckets);
   if(b != nil) {
       grow_work_read(t, h); // ここで成長作業を進める
       b = (Bucket*)((byte*)b + (bucket & (((uintptr)1 << (h->B - 1)) - 1)) * h->bucketsize);
       if(((uintptr)runtime·atomicloadp(&b->overflow) & 1) != 0) // エバキュエーション済みかチェック
           goto newbucket;
   } else {
   newbucket:
       b = (Bucket*)(h->buckets + bucket * h->bucketsize);
   }
   // ...
   

6. hash_next関数の変更: イテレータが成長中のマップを処理する際にも、grow_work_readを呼び出すようになりました。

   // ...
   if(it->B == h->B && (oldbuckets = runtime·atomicloadp(&h->oldbuckets)) != nil) {
       // ...
       grow_work_read(t, h); // ここで成長作業を進める
       // ...
       if(((uintptr)runtime·atomicloadp(&b->overflow) & 1) == 0) { // エバキュエーション済みかチェック
           // ...
       } else {
           // ...
       }
   }
   // ...
   

src/pkg/runtime/hashmap_fast.c

このファイルは、特定のキー型（例: int、string）に最適化されたハッシュマップのルックアップ関数を含んでいます。hashmap.cと同様に、HASH_LOOKUP1とHASH_LOOKUP2関数内でgrow_work_readが呼び出されるように変更されています。変更内容はhashmap.cのhash_lookupと同様です。

コアとなるコードの解説

このコミットの核心は、マップの成長作業を「読み込み時」にも分散して実行するというアイデアと、それを並行性安全に実現するための原子操作の活用です。

grow_work_readの役割と原子操作

grow_work_read関数は、マップの成長作業を少しずつ進めるためのものです。この関数が重要なのは、複数のゴルーチンが同時にマップを読み込んでいる可能性があるため、成長作業の実行を調整する必要がある点です。

ここでruntime·caspが活躍します。h->nevacuateフィールドは、次にエバキュエーションすべきoldbucketsのインデックスを保持していますが、このコミットではこれを「エバキュエーションロック」としても利用しています。

1. n = h->nevacuate; で現在のエバキュエーション進捗（またはロック状態）を取得します。
2. if(n != EVAC_LOCK && n != noldbuckets && runtime·casp((void**)&h->nevacuate, (void*)n, (void*)EVAC_LOCK))
   • n != EVAC_LOCK: 他のゴルーチンが既にロックを取得していないか確認します。
   • n != noldbuckets: まだエバキュエーションすべきバケットが残っているか確認します。
   • runtime·casp((void**)&h->nevacuate, (void*)n, (void*)EVAC_LOCK): ここが最も重要です。h->nevacuateがまだn（読み取った値）である場合にのみ、それをEVAC_LOCKにアトミックに設定します。もし他のゴルーチンが先にh->nevacuateを更新していた場合、このcaspは失敗し、現在のゴルーチンはロックを取得できません。ロックを取得できなかった場合、それは他のゴルーチンが既に成長作業を進めていることを意味するため、現在のゴルーチンは何もしません。
3. caspが成功した場合、現在のゴルーチンが排他的にエバキュエーション作業（evacuate(t, h, n)）を実行します。
4. 作業完了後、runtime·atomicstorep((void**)&h->nevacuate, (void*)(n + 1)); を使って、h->nevacuateを次のバケットインデックスにアトミックに更新し、ロックを解放します。これにより、他のゴルーチンが次の成長作業を開始できるようになります。

このロックメカニズムにより、成長作業自体は逐次的に実行されますが、マップの読み込み操作は並行して行われ、成長作業の進行を妨げません。

evacuate関数における原子的なマーク

evacuate関数では、バケットのエバキュエーションが完了したことを示すために、overflowポインタの最下位ビットをフラグとして使用しています。

runtime·atomicstorep(&mainb->overflow, (Bucket*)((uintptr)b + 1));

この行は、mainb（現在のバケット）のoverflowポインタを更新し、その最下位ビットを1に設定することで、このバケットがエバキュエーション済みであることをマークしています。runtime·atomicstorepを使用することで、この更新が他のゴルーチンから原子的に可視化されることを保証します。

hash_lookupやhash_next関数は、マップが成長中の場合、このフラグをチェックして、古いバケットから新しいバケットへの参照を安全に切り替えます。

if(((uintptr)runtime·atomicloadp(&b->overflow) & 1) != 0)

このチェックは、b->overflowポインタを原子的に読み込み、その最下位ビットが1であるかどうかを確認しています。これにより、バケットがエバキュエーション済みであるかを安全に判断できます。

全体的な影響

この変更により、Goのmapは、書き込みが少ない状況でも、読み込みが行われるたびに少しずつ成長作業を進めることができるようになりました。これにより、マップが部分的に成長した状態に留まる時間が大幅に短縮され、メモリ効率とルックアップ性能が向上します。これは、特に読み込みが主体のアプリケーションにおいて、マップのパフォーマンスを安定させる上で重要な改善です。

関連リンク

• Goのmapの内部実装に関する公式ドキュメント（Goのバージョンによって変更される可能性がありますが、基本的な概念は共通です）:
  • Go Slices: usage and internals - The Go Programming Language (マップではないが、メモリ管理の基礎理解に役立つ)
  • Go maps in action - The Go Programming Language (Goのマップの基本的な動作について)
• このコミットのGo Code Review (CL) ページ:
  • runtime: do hashmap grow work during reads. - Go Code Review

参考にした情報源リンク

• Go Code Review: runtime: do hashmap grow work during reads. (コミットメッセージと差分)
• Go の map の実装について - Qiita (Goのマップ実装に関する日本語記事、成長戦略の理解に役立つ)
• Go言語のmapの内部構造と実装 - Zenn (Goのマップの内部構造に関する日本語記事)
• Goのmapの内部実装を理解する - Speaker Deck (Goのマップ実装に関するスライド)
• Goのmapの内部実装を理解する - YouTube (上記スライドの解説動画など、Goのマップ実装に関する動画コンテンツ)
• Goのruntimeパッケージにおけるatomic操作 - GoDoc (Goのruntimeパッケージ内のatomic操作に関するドキュメント)

（注：YouTubeリンクは一般的な例であり、特定の動画を指すものではありません。必要に応じて適切な動画を検索してください。）