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

このコミットは、Goランタイムのヒーププロファイリング機能におけるメモリオーバーヘッドを削減することを目的としています。具体的には、ヒーププロファイラがメモリ使用量を追跡するために内部的に使用するデータ構造の粒度を変更し、プロファイラ自体のメモリ消費量を大幅に削減しています。

コミット

commit baf91c313fdd50601f40915fa42a423faa1a5c76
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Thu May 31 23:30:55 2012 +0200

    runtime: lower memory overhead of heap profiling.
    
    The previous code was preparing arrays of entries that would be
    filled if there was one entry every 128 bytes. Moving to a 4096
    byte interval reduces the overhead per megabyte of address space
    to 2kB from 64kB (on 64-bit systems).
    The performance impact will be negative for very small MemProfileRate.
    
    test/bench/garbage/tree2 -heapsize 800000000 (default memprofilerate)
    Before: mprof 65993056 bytes (1664 bucketmem + 65991392 addrmem)
    After:  mprof  1989984 bytes (1680 bucketmem +  1988304 addrmem)
    
    R=golang-dev, rsc
    CC=golang-dev, remy
    https://golang.org/cl/6257069

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

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

元コミット内容

Goランタイムのヒーププロファイリングにおけるメモリオーバーヘッドを削減する。

以前のコードでは、128バイトごとにエントリが1つある場合に埋められるエントリの配列を準備していた。これを4096バイト間隔にすることで、アドレス空間1メガバイトあたりのオーバーヘッドが（64ビットシステムで）64KBから2KBに削減される。

非常に小さいMemProfileRateの場合、パフォーマンスへの影響は負になる可能性がある。

ベンチマーク結果 (test/bench/garbage/tree2 -heapsize 800000000 (デフォルトのmemprofilerate)):

• 変更前: mprof 65993056 bytes (1664 bucketmem + 65991392 addrmem)
• 変更後: mprof 1989984 bytes (1680 bucketmem + 1988304 addrmem)

変更の背景

Goのランタイムには、プログラムのメモリ使用状況を分析するためのヒーププロファイリング機能が組み込まれています。このプロファイリングは、メモリリークの特定やメモリ使用量の最適化に不可欠です。しかし、プロファイリングツール自体が過剰なメモリを消費すると、プロファイリング対象のアプリケーションのパフォーマンスに悪影響を与えたり、プロファイリング結果が不正確になったりする可能性があります。

このコミット以前のGoランタイムのヒーププロファイラは、メモリアドレスとそれに対応するアロケーション情報（Bucket）をマッピングするために、比較的細かい粒度でデータ構造を構築していました。具体的には、128バイトごとにエントリを準備するような設計になっており、これがプロファイラ自身のメモリオーバーヘッドを増大させていました。特に、大規模なヒープを持つアプリケーションをプロファイリングする場合、このオーバーヘッドは無視できないレベルに達し、ベンチマーク結果が示すように、プロファイラだけで数千万バイトものメモリを消費していました。

この問題に対処し、プロファイラのメモリフットプリントを削減することが、この変更の主要な背景です。プロファイラのオーバーヘッドを減らすことで、より少ないリソースで、より大規模なアプリケーションのプロファイリングが可能になり、開発者がメモリ関連の問題を効率的に診断できるようになります。

前提知識の解説

このコミットを理解するためには、以下の概念についての基本的な知識が必要です。

1. Goランタイム (Go Runtime): Goプログラムは、Goランタイムと呼ばれる実行環境上で動作します。ランタイムは、ガベージコレクション、スケジューリング、メモリ管理、プロファイリングなど、プログラムの実行に必要な低レベルの機能を提供します。
2. ヒーププロファイリング (Heap Profiling): プログラムがヒープメモリをどのように使用しているかを分析する手法です。Goのヒーププロファイラは、メモリのアロケーションサイト（どこでメモリが確保されたか）や、アロケーションされたメモリのサイズなどを追跡し、メモリ使用量の傾向やリークの可能性を特定するのに役立ちます。
3. メモリオーバーヘッド (Memory Overhead): ある機能やシステムを動作させるために追加で必要となるメモリ量のことです。プロファイリングツールの場合、プロファイラ自体が消費するメモリがオーバーヘッドとなります。理想的には、プロファイラのオーバーヘッドは最小限に抑えられるべきです。
4. データ構造 (Data Structures):
   • ハッシュテーブル (Hash Table): キーと値のペアを格納し、キーを使って高速に値を検索できるデータ構造です。内部的には、ハッシュ関数を使ってキーを配列のインデックスに変換します。衝突が発生した場合は、リンクリストなどで解決します。
   • リンクリスト (Linked List): 各要素が次の要素へのポインタを持つ線形データ構造です。要素の追加や削除が容易ですが、特定の位置へのアクセスは線形探索になります。
   • 配列 (Array): 同じ型の要素が連続したメモリ領域に格納されるデータ構造です。インデックスを使って高速に要素にアクセスできます。
5. ビット演算 (Bitwise Operations): ビット単位で数値を操作する演算です。
   • ビットシフト (>>): 数値のビットを左右に移動させます。右シフトは数値を2のべき乗で割ることに相当し、特定のアドレス範囲を抽出する際によく使われます。
   • ビットAND (&): 2つの数値の対応するビットが両方とも1の場合にのみ1を返します。特定のビットをマスク（抽出）する際に使われます。
   6. メモリのアドレス空間 (Address Space): プログラムがアクセスできるメモリの範囲を抽象化したものです。各メモリ位置は一意のアドレスを持ちます。

Goのヒーププロファイラは、メモリアドレスをキーとして、そのアドレスに関連するプロファイリング情報（Bucket）を効率的に検索できるようなデータ構造を必要とします。このコミットは、そのデータ構造の内部実装、特にアドレスをハッシュしてマッピングするロジックを最適化しています。

技術的詳細

このコミットは、Goランタイムのヒーププロファイラが使用するアドレスマッピング構造であるAddrHashとAddrEntryの設計を変更することで、メモリオーバーヘッドを削減しています。

Goのヒーププロファイラは、アロケーションされたメモリのアドレスを追跡し、そのアドレスがどのBucket（アロケーション情報を含む構造体）に関連付けられているかを効率的に検索できる必要があります。このために、Goランタイムは多段階のハッシュテーブルのような構造を使用しています。

変更前の構造は以下のようでした：

1. トップレベルのハッシュテーブル (addrhash):
   • AddrHashBits = 12 を使用し、addrhash配列のサイズは 1 << 12 = 4096 エントリでした。
   • アドレスの最上位20ビット (addr >> 20) をハッシュキーとして使用し、アドレス空間を1MB (2^20バイト) のチャンクに分割していました。各addrhashエントリは、その1MBチャンク内のアドレスを管理するAddrHash構造体へのリンクリストのヘッドを指していました。
2. セカンドレベルのdense配列 (AddrHash構造体内部):
   • 各AddrHash構造体には、AddrEntry *dense[1<<13]; という配列がありました。これは 1 << 13 = 8192 個のポインタを保持していました。
   • このdense配列は、1MBチャンク内のアドレスをさらに細かく分割するために使用されました。具体的には、アドレスの下位20ビットのうち、ビット7からビット19までの13ビット ((addr >> 7) & (nelem(ah->dense)-1)) をインデックスとして使用していました。これにより、各dense配列のエントリは 2^7 = 128 バイトの範囲をカバーしていました。
3. サードレベルのリンクリスト (AddrEntry構造体):
   • dense配列の各エントリは、AddrEntry構造体のリンクリストのヘッドを指していました。同じ128バイト範囲内に複数のアドレスが存在する場合、それらはこのリンクリストで管理されました。AddrEntryは、実際のアドレスの下位ビット（e->addr = (uint32)~(addr & ((1<<20)-1))）と、関連するBucketへのポインタを保持していました。

変更点と最適化:

このコミットの主要な変更は、セカンドレベルのdense配列の粒度を粗くすることです。

• 新しいenum定数 AddrDenseBits = 8 が導入されました。
• AddrHash構造体内のdense配列の宣言が AddrEntry *dense[1<<13]; から AddrEntry *dense[1<<AddrDenseBits]; に変更されました。これにより、dense配列のサイズは 1 << 8 = 256 エントリに削減されました（以前の8192エントリから大幅減）。
• setaddrbucketおよびgetaddrbucket関数内で、dense配列のインデックスを計算するロジックが変更されました。
  • 変更前: h = (addr>>7)&(nelem(ah->dense)-1); （アドレスのビット7-19を使用）
  • 変更後: h = (addr>>(AddrHashShift-AddrDenseBits))&(nelem(ah->dense)-1);
    • AddrHashShiftは20、AddrDenseBitsは8なので、AddrHashShift - AddrDenseBits = 20 - 8 = 12 となります。
    • したがって、新しいインデックス計算は h = (addr>>12)&(nelem(ah->dense)-1); となります。これは、アドレスのビット12からビット19までの8ビットをインデックスとして使用することを意味します。

この変更がもたらす効果:

dense配列のインデックスに使用するビット数が13ビットから8ビットに減ったことで、各dense配列のエントリがカバーするアドレス範囲が 2^7 = 128 バイトから 2^12 = 4096 バイトに拡大されました。

これにより、同じ量のメモリをプロファイリングする場合でも、必要となるAddrEntryオブジェクトの総数が大幅に減少します。AddrEntryオブジェクトは、それぞれがメモリを消費するため、その数を減らすことはプロファイラ自体のメモリオーバーヘッドの直接的な削減につながります。

コミットメッセージのベンチマーク結果は、この効果を明確に示しています。addrmem（アドレスマッピング構造が消費するメモリ）が約66MBから約2MBへと劇的に減少しており、これはプロファイラのメモリフットプリントが約33分の1に削減されたことを意味します。

ただし、粒度が粗くなったことで、非常に細かいMemProfileRate（プロファイリング頻度）を設定した場合、同じdense配列のエントリに複数のアロケーションが集中し、リンクリストの探索が長くなることでパフォーマンスがわずかに低下する可能性も指摘されています。しかし、一般的な使用シナリオでは、メモリオーバーヘッドの削減というメリットがこの潜在的なデメリットを上回ると判断されています。

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

src/pkg/runtime/mprof.goc ファイルにおいて、以下の変更が行われました。

1. enum定数の追加と変更:

   --- a/src/pkg/runtime/mprof.goc
   +++ b/src/pkg/runtime/mprof.goc
   @@ -107,20 +107,26 @@ runtime·MProf_GC(void)
    
    // Map from pointer to Bucket* that allocated it.
    // Three levels:
   -//	Linked-list hash table for top N-20 bits.
   -//	Array index for next 13 bits.
   -//	Linked list for next 7 bits.
   +//	Linked-list hash table for top N-AddrHashShift bits.
   +//	Array index for next AddrDenseBits bits.
   +//	Linked list for next AddrHashShift-AddrDenseBits bits.
    // This is more efficient than using a general map,
    // because of the typical clustering of the pointer keys.
    
    typedef struct AddrHash AddrHash;\n typedef struct AddrEntry AddrEntry;
    
   +enum {
   +\tAddrHashBits = 12,\t// good for 4GB of used address space
   +\tAddrHashShift = 20,\t// each AddrHash knows about 1MB of address space
   +\tAddrDenseBits = 8,\t// good for a profiling rate of 4096 bytes
   +};
   +
    struct AddrHash
    {
    	AddrHash *next;\t// next in top-level hash table linked list
    	uintptr addr;\t// addr>>20
   -\tAddrEntry *dense[1<<13];
   +\tAddrEntry *dense[1<<AddrDenseBits];
    };
    
    struct AddrEntry
   @@ -130,9 +136,6 @@ struct AddrEntry
    	Bucket *b;
    };
    
   -enum {
   -\tAddrHashBits = 12\t// 1MB per entry, so good for 4GB of used address space
   -};
    static AddrHash *addrhash[1<<AddrHashBits];
    static AddrEntry *addrfree;
    static uintptr addrmem;
   

   • AddrDenseBits = 8 が新しく定義されました。
   • AddrHash構造体内のdense配列のサイズが 1<<13 から 1<<AddrDenseBits に変更されました。
   • 古いenumブロックが削除され、新しいenumブロックに統合されました。

2. setaddrbucket関数内のインデックス計算の変更:

   --- a/src/pkg/runtime/mprof.goc
   +++ b/src/pkg/runtime/mprof.goc
   @@ -155,15 +158,15 @@ setaddrbucket(uintptr addr, Bucket *b)
    	AddrHash *ah;
    	AddrEntry *e;
    
   -\th = (uint32)((addr>>20)*HashMultiplier) >> (32-AddrHashBits);\n \tfor(ah=addrhash[h]; ah; ah=ah->next)
   -\t\tif(ah->addr == (addr>>20))
   +\th = (uint32)((addr>>AddrHashShift)*HashMultiplier) >> (32-AddrHashBits);\n \tfor(ah=addrhash[h]; ah; ah=ah->next)
   +\t\tif(ah->addr == (addr>>AddrHashShift))
    \t\t\tgoto found;
    
    \tah = runtime·mallocgc(sizeof *ah, FlagNoProfiling, 0, 1);
    \taddrmem += sizeof *ah;
    \tah->next = addrhash[h];
   -\tah->addr = addr>>20;
   +\tah->addr = addr>>AddrHashShift;
    \taddrhash[h] = ah;
    
    found:
   @@ -175,9 +178,9 @@ found:
    \t\te[63].next = nil;
    \t}\n \taddrfree = e->next;
   -\te->addr = (uint32)~(addr & ((1<<20)-1));
   +\te->addr = (uint32)~(addr & ((1<<AddrHashShift)-1));
    \te->b = b;
   -\th = (addr>>7)&(nelem(ah->dense)-1);\t// entry in dense is top 13 bits of low 20.
   +\th = (addr>>(AddrHashShift-AddrDenseBits))&(nelem(ah->dense)-1);\t// entry in dense is top 8 bits of low 20.
    \te->next = ah->dense[h];
    \tah->dense[h] = e;
    }\n
   

   • ah->addrとトップレベルのハッシュ計算 (h) で使用されるシフト値が 20 から AddrHashShift に変更されました（値は同じ20ですが、定数を使用するようになりました）。
   • e->addrの計算で使用されるマスク値が (1<<20)-1 から (1<<AddrHashShift)-1 に変更されました（値は同じですが、定数を使用するようになりました）。
   • 最も重要な変更点: dense配列のインデックス h の計算が (addr>>7) から (addr>>(AddrHashShift-AddrDenseBits)) に変更されました。

3. getaddrbucket関数内のインデックス計算の変更:

   --- a/src/pkg/runtime/mprof.goc
   +++ b/src/pkg/runtime/mprof.goc
   @@ -191,16 +194,16 @@ getaddrbucket(uintptr addr)
    	AddrEntry *e, **l;
    	Bucket *b;
    
   -\th = (uint32)((addr>>20)*HashMultiplier) >> (32-AddrHashBits);\n \tfor(ah=addrhash[h]; ah; ah=ah->next)
   -\t\tif(ah->addr == (addr>>20))
   +\th = (uint32)((addr>>AddrHashShift)*HashMultiplier) >> (32-AddrHashBits);\n \tfor(ah=addrhash[h]; ah; ah=ah->next)
   +\t\tif(ah->addr == (addr>>AddrHashShift))
    \t\t\tgoto found;
    \treturn nil;
    
    found:
   -\th = (addr>>7)&(nelem(ah->dense)-1);\t// entry in dense is top 13 bits of low 20.
   +\th = (addr>>(AddrHashShift-AddrDenseBits))&(nelem(ah->dense)-1);\t// entry in dense is top 8 bits of low 20.
    \tfor(l=&ah->dense[h]; (e=*l) != nil; l=&e->next) {
   -\t\tif(e->addr == (uint32)~(addr & ((1<<20)-1))) {
   +\t\tif(e->addr == (uint32)~(addr & ((1<<AddrHashShift)-1))) {
    \t\t\t*l = e->next;
    \t\t\tb = e->b;
    \t\t\te->next = addrfree;
   

   • setaddrbucketと同様に、ah->addr、トップレベルのハッシュ計算 (h)、e->addrの計算で使用される定数が変更されました。
   • 最も重要な変更点: dense配列のインデックス h の計算が (addr>>7) から (addr>>(AddrHashShift-AddrDenseBits)) に変更されました。

コアとなるコードの解説

このコミットの核心は、src/pkg/runtime/mprof.goc ファイル内のAddrHash構造体と、setaddrbucketおよびgetaddrbucket関数におけるアドレスのハッシュおよびインデックス計算ロジックの変更にあります。

AddrHash構造体とenum定数:

enum {
	AddrHashBits = 12,	// good for 4GB of used address space
	AddrHashShift = 20,	// each AddrHash knows about 1MB of address space
	AddrDenseBits = 8,	// good for a profiling rate of 4096 bytes
};

struct AddrHash
{
	AddrHash *next;	// next in top-level hash table linked list
	uintptr addr;	// addr>>20
	AddrEntry *dense[1<<AddrDenseBits]; // 変更点: dense配列のサイズがAddrDenseBitsに依存
};

• AddrHashBits = 12: トップレベルのハッシュテーブル（addrhash配列）のサイズを決定します。1 << 12 = 4096エントリ。
• AddrHashShift = 20: アドレスの最上位20ビットをハッシュキーとして使用し、アドレス空間を1MB (2^20バイト) のチャンクに分割します。AddrHash構造体のaddrフィールドには、このシフトされたアドレスが格納されます。
• AddrDenseBits = 8: このコミットで新しく導入された、または変更された重要な定数です。 これは、AddrHash構造体内のdense配列のサイズを決定します。1 << 8 = 256エントリ。この値が、プロファイリングの粒度（4096バイト）を直接制御します。

setaddrbucketおよびgetaddrbucket関数内のインデックス計算:

これらの関数は、特定のアドレスに対応するBucket（アロケーション情報）を設定または取得するために使用されます。

// setaddrbucket (一部抜粋)
// ...
// トップレベルのハッシュ計算 (変更なし、定数名に変更)
h = (uint32)((addr>>AddrHashShift)*HashMultiplier) >> (32-AddrHashBits);
// ...
// AddrHash構造体のaddrフィールド (変更なし、定数名に変更)
ah->addr = addr>>AddrHashShift;
// ...
// AddrEntryのaddrフィールド (変更なし、定数名に変更)
e->addr = (uint32)~(addr & ((1<<AddrHashShift)-1));
// ...
// dense配列のインデックス計算 (コアとなる変更点)
h = (addr>>(AddrHashShift-AddrDenseBits))&(nelem(ah->dense)-1);
// ...

// getaddrbucket (一部抜粋)
// ...
// dense配列のインデックス計算 (コアとなる変更点)
h = (addr>>(AddrHashShift-AddrDenseBits))&(nelem(ah->dense)-1);
// ...

• h = (addr>>(AddrHashShift-AddrDenseBits))&(nelem(ah->dense)-1);
  • これがこのコミットの最も重要な変更点です。
  • 以前は (addr>>7) を使用していましたが、これはアドレスのビット7からビット19までの13ビットをインデックスとして使用していました。これにより、各denseエントリは128バイトの範囲をカバーしていました。
  • 新しい式では、AddrHashShift (20) と AddrDenseBits (8) を使用します。
    • AddrHashShift - AddrDenseBits = 20 - 8 = 12
    • したがって、式は (addr>>12) となります。これは、アドレスのビット12からビット19までの8ビットをインデックスとして使用することを意味します。
  • &(nelem(ah->dense)-1) は、結果をdense配列の有効なインデックス範囲（0から255）に制限するためのマスクです。
  • この変更により、各denseエントリがカバーするアドレス範囲が 2^12 = 4096 バイトに拡大されました。

変更のメカニズム:

この変更は、ヒーププロファイラがメモリを追跡する際の「粒度」を粗くすることで、メモリオーバーヘッドを削減します。

• 以前（128バイト粒度）: 1MBのアドレス空間をカバーするAddrHash構造体は、8192個のAddrEntryポインタを持つdense配列を持っていました。これは、1MB / 128バイト = 8192個の潜在的なエントリを事前に準備していたことを意味します。たとえその範囲にアロケーションがなくても、ポインタのためのメモリは確保されていました。
• 変更後（4096バイト粒度）: 同じ1MBのアドレス空間をカバーするAddrHash構造体は、256個のAddrEntryポインタを持つdense配列を持つことになります。これは、1MB / 4096バイト = 256個の潜在的なエントリしか事前に準備しないことを意味します。

これにより、プロファイラが管理する必要があるAddrEntryポインタの数が大幅に減少し、結果としてプロファイラ自体のメモリ消費量（addrmem）が劇的に削減されます。

このトレードオフとして、同じ4096バイトの範囲内に複数のアロケーションが存在する場合、dense配列の同じインデックスに複数のAddrEntryがリンクリストとして連なることになります。これにより、リンクリストの探索が長くなり、非常に細かいプロファイリングレートではパフォーマンスがわずかに低下する可能性があります。しかし、コミットメッセージのベンチマーク結果が示すように、メモリ削減のメリットが非常に大きいため、このトレードオフは許容できると判断されています。

関連リンク

• Go言語の公式ドキュメント: https://go.dev/
• Goのプロファイリングに関する公式ドキュメント: https://go.dev/doc/diagnose
• Goのメモリプロファイリングに関する詳細（古い情報も含む可能性あり）: https://go.dev/blog/pprof

参考にした情報源リンク

• Goのソースコード (src/pkg/runtime/mprof.goc)
• Gitコミットメッセージ (baf91c313fdd50601f40915fa42a423faa1a5c76)
• Goのコードレビューシステム (Gerrit) の変更リスト: https://golang.org/cl/6257069 (コミットメッセージに記載されているリンク)