メモリプール：効率的なメモリ管理手法

mallocとfreeによる小さなメモリの頻繁な管理は非効率的です

伝統的なmalloc/freeとの比較

従来のmalloc/freeは深刻な断片化問題を引き起こします：

  • 外部断片化：頻繁な割り当て/解放により、ヒープに利用できない小さな空きブロックが多数残ります
  • 内部断片化：割り当てごとにメタデータオーバーヘッド（ブロックサイズ、フラグなど）が発生し、アライメントによる無駄なスペースが生じます

一方、フリーリストは分類管理、再利用メカニズム、バッチ操作を通じて、これら2種類の断片化を大幅に減少させます。

まとめ

フリーリストがメモリ断片化を減少させる核心的な要素：

  1. 固定サイズブロック：ランダムなサイズの割り当てによる間隔を回避
  2. 即時再利用：解放されたメモリは直ちに再利用される
  3. バッチ割り当て：OSとの相互作用を減らし、メモリの連続性を維持
  4. アライメント最適化：アライメント要件による追加オーバーヘッドを排除

設計思想

1. システムコールオーバーヘッドの削減

  • 伝統的なmalloc/freeやnew/deleteはシステムコールを必要とし、ユーザーモードからカーネルモードへの切り替えコストが高い
  • メモリプールは一度に大容量のメモリ（数KB～数MB）を割り当てることで、複数の小メモリ割り当てを一度の大容量割り当てに変換し、システムコール回数を削減する

2. メモリ断片化の低減

  • 頻繁な割り当てと解放によりメモリが断片化します（外部断片化と内部断片化）
  • メモリプールは固定サイズブロック割り当てとオブジェクト再利用メカニズムを通じて、利用できない小さな空きブロックの生成を回避する

3. 割り当て効率の向上

  • システムレベルのアロケータは複雑なメモリ状態情報（空きリスト、ビットマップなど）を維持する必要があり、適切なメモリブロックの検索に時間がかかる
  • メモリプールは単純なデータ構造（リスト、配列など）でメモリを管理し、割り当てと解放の操作は通常O(1)の時間計算量となる

4. カスタムメモリ戦略

  • 特定のシナリオ（小さなオブジェクトの頻繁な作成/破棄）向けに割り当て戦略を最適化
  • メモリ事前割り当て、オブジェクトプール化、バッチ解放などの機能をサポート

基本原理

1. メモリの事前割り当て

  • メモリプールの初期化時に、OSに連続したメモリ領域（メモリプールチャンクと呼ぶ）を要求します
  • このメモリは通常、単回要求よりはるかに大きく、例えば：

cpp

char* memory_pool = new char[1024 * 1024]; // 1MBを事前割り当て

2. メモリブロック管理

  • 事前割り当てたメモリを複数のメモリブロックに分割します。割り当て戦略により、ブロックサイズは：
  • 固定サイズ（8B、16B、32Bなど）：同じ種類の小さなオブジェクトの管理に適しています
  • 可変サイズ：実際のニーズに応じて動的に分割されますが、管理の複雑さが高くなります

3. アロケータインターフェース

  • mallocとfreeに代わるカスタムのallocate()とdeallocate()関数を提供します：

cpp

void* allocate(size_t size);    // メモリプールから指定サイズのメモリを割り当て
void deallocate(void* ptr);     // メモリブロックをメモリプールに返却

4. 空きリスト（Free List）

  • 最も一般的な実装方式は空きメモリブロックのリストを維持することです：
  • 各空きブロックの先頭には次の空きブロックへのポインタが含まれます
  • 割り当て時はリストの先頭からブロックを取り出し、解放時はブロックをリストの先頭に挿入します
  • 操作の計算量はO(1)です

5. メモリプール枯渇時の処理

  • 事前割り当てたメモリが使い切られた場合、2つの処理方式があります：
  • メモリプールの拡張：OSに新しいメモリブロックを要求し、メモリプール管理に追加します
  • システムアロケータへのフォールバック：mallocを呼び出してメモリを割り当てますが、メモリプールの最適化効果が損なわれる可能性があります

SGI STLメモリプールの実装詳細

SGI STLのメモリプールは2段階アロケータアーキテクチャを採用しています：

  1. 一次アロケータ：大容量メモリ（>128B）を処理し、直接mallocとfreeを呼び出します
  2. 二次アロケータ：小容量メモリ（≤128B）を処理し、フリーリスト（Free List）で管理します

フリーリストの構造

  • メモリブロックを8バイトアライメントでグループ化し、合計16個のリストを保持します：

plaintext

インデックス0：8Bのメモリブロックを管理
インデックス1：16Bのメモリブロックを管理
...
インデックス15：128Bのメモリブロックを管理
  • 各リストのノード構造は以下の通りです：

cpp

union _Obj {
    union _Obj* _M_free_list_link;  // 空き時はリストポインタとして使用
    char _M_client_data[1];         // 割り当て後はユーザーデータとして使用
};

割り当てフロー

  1. ユーザーがnバイトのメモリを要求します
  2. nに対応するリストインデックスiを計算します（_S_freelist_index(n)を介して）
  3. リストiが空でない場合、先頭ノードを取り出して割り当てます。空の場合：
  • refill()を呼び出してメモリプールから20個の新ノードを取得し、1つをユーザーに返し、19個をリストに格納します
  • メモリプールが不足している場合、chunk_alloc()を呼び出して新しいメモリプールチャンク（通常は2^nサイズ）を割り当てます

解放フロー

  1. ポインタアドレスに基づいて所属リストのインデックスiを計算します
  2. ノードをリストiの先頭に挿入します

2つの補助関数

バイト数を8の倍数に切り上げる

enum{_ALIGN = 8};
static size_t _S_round_up(size_t _bytes)
{
    return (((_bytes)+(size_t)_ALIGN-1)&~((size_t)_ALIGN-1));
}
//結果は1～8→8
//9～16→16...

//ALIGN-1 = 0111
//~(ALIGN-1)=11111111 11111111 11111111 11111000

//(_bytes)+(size_t)_ALIGN-1)は_bytes>0の場合桁上がりを生じ、&演算後は桁上がりのみが保持される

指定サイズのチャンクがフリーリスト内にあるインデックスを返す

_S_freelist_index

n>max_bytesの場合は一次アロケータ（malloc）を使用して割り当て n<max_bytesの場合はメモリプールを使用して割り当て フリーリストの追加・削除・変更はスレッドセーフにするため、ロックをかける。コードブロックを抜けるときにロックがデストラクタされる

主要概念

1. 基本定義

(1) チャンク（大容量メモリ）
  • 定義：OSから一度に割り当てられる連続した大容量メモリで、通常は数KB以上です
  • 用途：メモリプールの「原材料」として、複数の小さなBlockに分割されます
  • 管理：メモリプールが直接管理し、複数のChunkはリンクで接続できます
(2) ブロック（小容量メモリ）
  • 定義：Chunkが分割された固定サイズのメモリ単位で、サイズは通常8の倍数（8B、16B、...、128B）です
  • 用途：直接ユーザーに割り当てられるか、フリーリストで管理されます
  • 管理：フリーリストで組織化され、各リストは1種類の固定サイズBlockを管理します

2. 主要な違い

**比較項目** **チャンク** **ブロック**
**サイズ** 通常数KB（8KB、16KBなど） 固定サイズ（8B、16B、...、128B）
**割り当て対象** OS（mallocを介して） ユーザー（メモリプールのallocateを介して）
**割り当て頻度** 低頻度（リストが枯渇した場合のみ新しいチャンクを割り当て） 高頻度（ユーザーがメモリを要求するたび）
**管理方式** メモリプールが直接管理（チャンクリスト） フリーリストで管理（サイズ別に分類）
**ライフサイクル** 長期存在、メモリプールが破棄されるまで 短期存在、頻繁な割り当て/解放

3. フリーリストの内容

フリーリストが格納しているのはChunkのアドレスではなくBlockのアドレスです。具体的には：

  1. 各フリーリストは**同じサイズの複数Block**を管理します
  2. リスト内の各ノードはBlockであり、その最初の4/8バイト（ポインタサイズに依存）は次のBlockへのポインタを格納します
  3. リストが空の場合、メモリプールはChunkから新しいBlockを切り分け、リストに追加します

_S_refill()の役割

  1. メモリプールの空きブロックを補充 メモリプール内で特定サイズ（size）のメモリブロックが枯渇した場合、_S_refill()はシステムから大容量のメモリを要求し、それを複数のsizeサイズのブロックに分割します。これらのブロックをメモリプールの空きリストに追加し、後続の割り当て要求に備えます。
  2. システムコール頻度の削減 一度に複数のメモリブロック（例：n個）を要求することで、頻繁なmallocやmmapの呼び出しを回避し、メモリ割り当て効率を向上させます。
  3. 多階層メモリプール管理のサポート SGI STLのメモリプールは異なるサイズのメモリブロック（8B、16B、32Bなど）に対して独立した空きリストを維持します。_S_refill()は要求されたsizeに対応するリストを選択して補充します。

_S_chunk_alloc()との関係

_S_refill()は通常、_S_chunk_alloc()関数に依存して実際のメモリ割り当てを実行します：

  • _S_chunk_alloc(size_t bytes)：システムからbytesサイズのメモリブロックを要求し、そのアドレスを返します
  • **_S_refill()**は_S_chunk_allocを呼び出して大容量メモリを取得し、さらに分割します

新しい割り当てメモリが未割り当ての予備メモリを占め、かつnobjsが1に変更された場合は、refillリンクする必要はありません。さもなくば、予備ブロックを対応するサイズのリストに挿入します

SGIの利点

  1. 各バイト数のチャンクブロックの割り当てでは、一部を使用し、残りを予備として保持。予備ブロックは現在のバイト数に使用できるだけでなく、他のバイト数にも使用できます
  2. 予備メモリプールの分割後に残る小さなメモリブロックは、再度割り当て時に小さなメモリブロックとして割り当てられ、メモリプールを無駄にしません
  3. 指定バイト数のメモリ割り当てが失敗した後、異常処理プロセスがあります。バイト数が28バイト以下のすべてのチャンクブロックを確認し、特定のバイト数に空きチャンクブロックがある場合、借用して使用します

タグ: メモリ管理 メモリプール C++ パフォーマンス最適化

6月8日 19:46 投稿

ホットタグ

©2026 異端開発室