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

このコミットは、Go言語のランタイムにおけるハッシュマップ（map型）のメモリ管理を改善し、使用されなくなったマップ構造体（特にバケットや間接的なキー/値）をより積極的に解放することを目的としています。これにより、メモリ使用量の削減とガベージコレクション（GC）の負担軽減が期待されます。

コミット

commit bcb39a778cbf06582615e9110a480cedd096bb8b
Author: Keith Randall <khr@golang.org>
Date:   Wed Mar 20 15:38:51 2013 -0700

    runtime: free map structures more aggressively
    
    R=rsc, bradfitz, khr
    CC=golang-dev
    https://golang.org/cl/7849047

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

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

元コミット内容

runtime: free map structures more aggressively

R=rsc, bradfitz, khr
CC=golang-dev
https://golang.org/cl/7849047

変更の背景

Go言語のmap型は、内部的にハッシュテーブルとして実装されており、キーと値のペアを効率的に格納・検索します。マップが成長すると、より大きな容量を持つ新しいハッシュテーブルにデータを再配置（リハッシュまたはエバキュエーション）する必要があります。また、マップから要素が削除された場合、その要素が占めていたメモリは理論的には解放されるべきです。

しかし、Goのランタイムはガベージコレクタ（GC）に依存しており、メモリの解放はGCのサイクルに委ねられるのが一般的です。マップのような複雑なデータ構造では、GCがすぐにメモリを回収できない場合があります。特に、マップの成長時に古いバケットがすぐに解放されなかったり、間接的に参照されるキーや値が削除後もメモリに残り続けたりすると、メモリフットプリントが増大し、GCの頻度や時間が影響を受ける可能性があります。

このコミットの背景には、このようなマップ関連のメモリ使用効率の改善という課題がありました。特に、マップのイテレータが存在する場合、イテレータが古いマップ構造や間接的なキーへの参照を保持している可能性があるため、安易なメモリ解放はクラッシュや不正な動作を引き起こすリスクがありました。したがって、イテレータの存在を考慮しつつ、安全かつ積極的にメモリを解放するメカニズムが必要とされました。

前提知識の解説

• Goのmap型: Goのmapはハッシュテーブルとして実装されています。内部的には、キーと値のペアを格納する「バケット」と呼ばれる固定サイズの配列の集合で構成されます。キーのハッシュ値に基づいて、対応するバケットに要素が配置されます。
• バケットとオーバーフローバケット: 各バケットには限られた数のキー/値ペアしか格納できません。バケットが満杯になると、Goランタイムは「オーバーフローバケット」を割り当て、元のバケットからリンクして追加の要素を格納します。
• マップの成長（リハッシュ/エバキュエーション）: マップに多くの要素が追加され、負荷係数（要素数とバケット数の比率）が一定の閾値を超えると、マップは「成長」します。これは、より多くのバケットを持つ新しいハッシュテーブルを割り当て、既存の要素を古いバケットから新しいバケットに徐々に移動させるプロセスです。このプロセスは「エバキュエーション（evacuation）」と呼ばれ、マップの操作と並行して行われることがあります。
• 間接的なキー/値: Goのマップでは、キーや値が非常に大きい場合、または特定の型の場合、それらが直接バケットに格納されるのではなく、ポインタとして格納されることがあります。これを「間接的なキー/値」と呼びます。この場合、実際のデータはヒープ上の別の場所に割り当てられ、バケットにはそのデータへのポインタが格納されます。
• マップイテレータ: for rangeループを使ってマップをイテレートする際、Goランタイムは内部的にマップイテレータを作成します。このイテレータは、マップの現在の状態（バケットの配置など）への参照を保持し、イテレーション中にマップが変更されても安定したイテレーションを保証しようとします。
• Goのガベージコレクション（GC）: Goは自動メモリ管理（ガベージコレクション）を採用しています。プログラマが明示的にメモリを解放する必要はほとんどありません。GCは、どのメモリがまだプログラムによって到達可能かを追跡し、到達不能になったメモリを自動的に回収します。しかし、GCは即座に実行されるわけではなく、また、特定のデータ構造のライフサイクルをGCに任せるよりも、構造体自身が不要になったメモリを積極的に解放する方が効率的な場合があります。

技術的詳細

このコミットは、src/pkg/runtime/hashmap.cファイル内のGoマップの内部実装に焦点を当てています。主な変更点は、マップの成長時（evacuate関数）と要素削除時（hash_remove関数）におけるメモリ解放のロジックを強化することです。

1. CanFreeBucketとCanFreeKeyフラグの導入と利用の明確化:

   • Hmap構造体（Goマップの内部表現）には、マップの状態を示すフラグがいくつかあります。このコミットでは、CanFreeBucket（バケットを解放できるか）とCanFreeKey（間接的なキーを解放できるか）の利用がより厳密になります。
   • 特に、CanFreeKeyは、キーが間接的である場合にのみ設定されるようになり、そのコメントも「キーが間接的で、キーを解放しても安全である」と変更されました。
   • IteratorとOldIteratorフラグは、マップのイテレータが存在するかどうかを示し、これらのフラグが設定されている場合は、メモリの積極的な解放が制限されます。これは、イテレータが解放されたメモリを参照してしまうことを防ぐためです。

2. hash_initにおけるCanFreeKeyの条件付き設定:

   • マップの初期化時（hash_init）、以前は常にCanFreeKeyが設定されていましたが、この変更により、キーのサイズがMAXKEYSIZEを超える（つまり、キーが間接的に格納される）場合にのみCanFreeKeyが設定されるようになりました。これにより、不要な場合にCanFreeKeyが設定されるのを防ぎ、より正確なメモリ管理が可能になります。

3. evacuate関数における古いバケットの積極的な解放:

   • マップが成長し、古いバケットから新しいバケットへの要素の移動（エバキュエーション）が完了した後、古いバケットが不要になります。
   • このコミットでは、evacuate関数内に新しいロジックが追加され、OldIteratorフラグが設定されておらず、かつCanFreeBucketフラグが設定されている場合に、古いオーバーフローバケットを積極的に解放するようになりました。
   • さらに、全てのエバキュエーションが完了し、古いメインバケット配列（h->oldbuckets）が不要になった際も、同様の条件（OldIteratorがなく、CanFreeBucketがある）でruntime·freeを使ってメインバケット配列を解放するようになりました。これにより、GCに頼らずにメモリを早期に回収できます。

4. hash_grow関数におけるCanFreeKeyのクリア:

   • マップが成長する際（hash_grow）、もし既存のイテレータ（Iteratorフラグ）が存在する場合、新しいマップ構造に移行する際にOldIteratorフラグを設定します。
   • この時、非常に重要な変更として、flags &= ~CanFreeKey;が追加されました。これは、イテレータが存在する場合、間接的なキーが古いバケットと新しいバケットの間でエイリアス（同じメモリを指す）されている可能性があるため、CanFreeKeyをクリアして、これらのキーを積極的に解放しないようにします。これにより、イテレータが不正なメモリを参照するのを防ぎます。

5. hash_remove関数における間接的なキー/値の解放:

   • マップから要素が削除される際（hash_remove）、もしキーが間接的でCanFreeKeyフラグが設定されている場合、そのキーが占めていたメモリをruntime·free(k)で解放するようになりました。
   • 同様に、値が間接的でIndirectValueフラグが設定されている場合、その値が占めていたメモリをruntime·free(v)で解放するようになりました。
   • これにより、削除された要素に関連するメモリがGCを待たずに即座に回収される可能性が高まります。

これらの変更は、Goのマップが使用するメモリをより効率的に管理し、特にマップのサイズ変更や要素の削除時にメモリフットプリントを削減することを目的としています。イテレータの存在という複雑なシナリオを考慮し、安全性を確保しながら積極的なメモリ解放を実現しています。

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

変更はsrc/pkg/runtime/hashmap.cファイルに集中しています。

1. enum定義の変更:

   --- a/src/pkg/runtime/hashmap.c
   +++ b/src/pkg/runtime/hashmap.c
   @@ -113,10 +112,10 @@ enum
    {
    	IndirectKey = 1,    // storing pointers to keys
    	IndirectValue = 2,  // storing pointers to values
   -	Iterator = 4,       // there may be an iterator using buckets  TODO: use
   -	OldIterator = 8,    // there may be an iterator using oldbuckets  TODO: use
   -	CanFreeBucket = 16, // ok to free buckets  TODO: use
   -	CanFreeKey = 32,    // ok to free pointers to keys  TODO: use
   +	Iterator = 4,       // there may be an iterator using buckets
   +	OldIterator = 8,    // there may be an iterator using oldbuckets
   +	CanFreeBucket = 16, // ok to free buckets
   +	CanFreeKey = 32,    // keys are indirect and ok to free keys
    };
   

   TODO: useコメントが削除され、CanFreeKeyのコメントがより正確になりました。

2. hash_init関数内のフラグ設定:

   --- a/src/pkg/runtime/hashmap.c
   +++ b/src/pkg/runtime/hashmap.c
   @@ -213,12 +212,12 @@ hash_init(MapType *t, Hmap *h, uint32 hint)\n     uint8 flags;\n     Bucket *b;\n     \n    -    flags = CanFreeBucket | CanFreeKey;\n    +    flags = CanFreeBucket;\n     \n     // figure out how big we have to make everything\n     keysize = t->key->size;\n     if(keysize > MAXKEYSIZE) {\n    -        flags |= IndirectKey;\n    +        flags |= IndirectKey | CanFreeKey;\
    		keysize = sizeof(byte*);\
    	}\
    	valuesize = t->elem->size;\
   

   CanFreeKeyの初期設定が変更され、間接キーの場合にのみ設定されるようになりました。

3. evacuate関数内のメモリ解放ロジック:

   --- a/src/pkg/runtime/hashmap.c
   +++ b/src/pkg/runtime/hashmap.c
   @@ -378,13 +378,35 @@ evacuate(MapType *t, Hmap *h, uintptr oldbucket)\n     \t\tb = nextb;\
    \t\t} while(b != nil);\
   +\n    +\t\t// Free old overflow buckets as much as we can.\
   +\t\tif((h->flags & OldIterator) == 0) {\
   +\t\t\tb = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);\
   +\t\t\tif((h->flags & CanFreeBucket) != 0) {\
   +\t\t\t\twhile((nextb = overflowptr(b)) != nil) {\
   +\t\t\t\t\tb->overflow = nextb->overflow;\
   +\t\t\t\t\truntime·free(nextb);\
   +\t\t\t\t}\
   +\t\t\t} else {\
   +\t\t\t\t// can't explicitly free overflow buckets, but at least\
   +\t\t\t\t// we can unlink them.\
   +\t\t\t\tb->overflow = (Bucket*)1;\
   +\t\t\t}\
   +\t\t}\
    \t}\
    \n     // advance evacuation mark\
    \tif(oldbucket == h->nevacuate) {\
    \t\th->nevacuate = oldbucket + 1;\
    \t\tif(oldbucket + 1 == newbit) { // newbit == # of oldbuckets\
   -\t\t\th->oldbuckets = nil;\
   +\t\t\t// free main bucket array\
   +\t\t\tif((h->flags & (OldIterator | CanFreeBucket)) == CanFreeBucket) {\
   +\t\t\t\tob = h->oldbuckets;\
   +\t\t\t\th->oldbuckets = nil;\
   +\t\t\t\truntime·free(ob);\
   +\t\t\t} else {\
   +\t\t\t\th->oldbuckets = nil;\
   +\t\t\t}\
    \t\t}\
    \t}\
    \tif(docheck)\
   

   古いオーバーフローバケットとメインバケット配列の解放ロジックが追加されました。

4. hash_grow関数内のフラグ変更:

   --- a/src/pkg/runtime/hashmap.c
   +++ b/src/pkg/runtime/hashmap.c
   @@ -421,8 +443,12 @@ hash_grow(MapType *t, Hmap *h)\n     // NOTE: this could be a big malloc, but since we don't need zeroing it is probably fast.\
    	new_buckets = runtime·mallocgc(h->bucketsize << (h->B + 1), 0, 1, 0);\
    	flags = (h->flags & ~(Iterator | OldIterator));\
   -\tif((h->flags & Iterator) != 0)\
   +\tif((h->flags & Iterator) != 0) {\
    \t\tflags |= OldIterator;\
   +\t\t// We can't free indirect keys any more, as\
   +\t\t// they are potentially aliased across buckets.\
   +\t\tflags &= ~CanFreeKey;\
   +\t}\
    \n     // commit the grow (atomic wrt gc)\
    \th->B++;\
   

   イテレータが存在する場合にCanFreeKeyをクリアするロジックが追加されました。

5. hash_remove関数内のメモリ解放ロジック:

   --- a/src/pkg/runtime/hashmap.c
   +++ b/src/pkg/runtime/hashmap.c
   @@ -642,11 +668,22 @@ hash_remove(MapType *t, Hmap *h, void *key)\n     \t\tif(!eq)\
    \t\t\t\tcontinue;\
    \n    +\t\t\tif((h->flags & CanFreeKey) != 0) {\
   +\t\t\t\tk = *(byte**)k;\
   +\t\t\t}\
   +\t\t\tif((h->flags & IndirectValue) != 0) {\
   +\t\t\t\tv = *(byte**)v;\
   +\t\t\t}\
   +\n     \t\tb->tophash[i] = 0;\
    \t\th->count--;\
   -\t\t\t// TODO: free key if indirect.  Can't do it if\
   -\t\t\t// there's any iterator ever, as indirect keys are aliased across\
   -\t\t\t// buckets.\
   +\t\t\t\n    +\t\t\tif((h->flags & CanFreeKey) != 0) {\
   +\t\t\t\truntime·free(k);\
   +\t\t\t}\
   +\t\t\tif((h->flags & IndirectValue) != 0) {\
   +\t\t\t\truntime·free(v);\
   +\t\t\t}\
    \t\t\t// TODO: consolidate buckets if they are mostly empty\
    \t\t\t// can only consolidate if there are no live iterators at this size.\
    \t\t\tif(docheck)\
   

   間接的なキーと値のメモリを削除時に解放するロジックが追加されました。

コアとなるコードの解説

このコミットの核心は、Goのマップが内部的に使用するメモリを、不要になった時点でより迅速にシステムに返却することです。これは、特にマップのサイズ変更（成長）や要素の削除といった操作において顕著です。

1. マップの成長時のメモリ解放 (evacuate関数): マップが成長すると、古いバケットから新しいバケットへ要素が移動します。このプロセスが完了すると、古いバケットはもはや必要ありません。以前は、これらの古いバケットはGCによって最終的に回収されるのを待つ必要がありました。しかし、この変更により、もしマップに現在アクティブなイテレータが存在しない（OldIteratorフラグが立っていない）場合、そしてバケットを解放しても安全である（CanFreeBucketフラグが立っている）場合に、古いオーバーフローバケットやメインのバケット配列がruntime·free関数を使って明示的に解放されるようになりました。これにより、GCのサイクルを待たずにメモリが即座にシステムに返却され、メモリフットプリントが削減されます。

2. 要素削除時の間接キー/値のメモリ解放 (hash_remove関数): マップから要素が削除された場合、もしそのキーや値が間接的に（ポインタとして）格納されていた場合、そのポインタが指していた実際のデータはヒープ上に残ったままになります。このコミットでは、要素が削除された後、もしキーが間接的でかつ解放可能である（CanFreeKeyフラグが立っている）場合、そのキーが指していたメモリがruntime·free(k)で解放されます。同様に、間接的な値についてもruntime·free(v)で解放されます。これにより、削除された要素に関連するメモリがGCを待たずに早期に回収され、メモリリークのリスクを低減し、メモリ使用効率を向上させます。

3. イテレータとの安全性の確保 (hash_grow関数): マップのメモリを積極的に解放する上で最も重要な考慮事項の一つは、マップイテレータの存在です。イテレータは、マップの特定の時点のスナップショットのようなものであり、イテレーション中にマップの構造が変更されても安定して動作する必要があります。もしイテレータがまだ古いバケットや間接的なキーを参照している間にそれらが解放されてしまうと、イテレータが不正なメモリにアクセスし、クラッシュや予測不能な動作を引き起こす可能性があります。 このコミットでは、マップが成長する際にイテレータが存在する場合（Iteratorフラグが立っている場合）、CanFreeKeyフラグをクリアするロジックが追加されました。これは、「イテレータが存在する間は、間接的なキーを積極的に解放してはならない」という安全策です。これにより、イテレータが参照している可能性のあるメモリが誤って解放されることを防ぎ、マップ操作の堅牢性を保ちます。

これらの変更は、Goのランタイムがマップのメモリをよりきめ細かく、かつ安全に管理できるようにすることで、全体的なパフォーマンスとメモリ効率を向上させることに貢献しています。

関連リンク

• Go言語の公式ドキュメント: https://golang.org/doc/
• Goのマップに関するブログ記事やドキュメント（Goの内部実装について深く掘り下げたもの）:
  • The Go Blog: Go maps in action: https://go.dev/blog/maps
  • Go map design document (古いですが、基本的な設計思想がわかります): https://go.dev/src/runtime/map.go (これはGoのソースコードへのリンクですが、設計に関するコメントが含まれています)

参考にした情報源リンク

• Goのソースコード: src/pkg/runtime/hashmap.c
• Goのコミット履歴: https://github.com/golang/go/commits/master
• Goのコードレビューシステム (Gerrit): https://go-review.googlesource.com/ (CL 7849047を検索)
• Goのガベージコレクションに関する一般的な情報源
• Goのマップの内部実装に関する技術ブログや解説記事 (例: "Go map internals"などで検索)