3

非常に多くの（実行時に修正された、約1,000万から3,000万の）アレイがあります。各配列は、それぞれ6バイトの0〜128個の要素です。

すべての配列をmmapされたメモリに格納する必要があり（mallocを使用できないため）、配列は動的に拡張できる必要があります（最大128要素で、配列は縮小しません）。

私は、mmapされたメモリ内の6バイトの各ブロックの状態を表すint配列を持つという単純なアプローチを実装しました。オフセットでの0xffffffffの値は、mmapされたメモリ内の対応するオフセットが空いていることを表します。その他の値は、配列のIDです（現在の実装ではブロックの最適化に必要です。ブロックは、なしでは移動できません。他のデータ構造を更新するために配列のIDを知っている）。割り当て時に、配列が割り当てを超えた場合、十分な空きブロックが見つかるまで単純に反復し、対応するオフセットに挿入します。

これは、割り当て配列とmmapされたメモリがどのように見えるかです。

| 0xffffffff | 0xfffffff |    1234    |    1234    | 0xffffffff | ...
-----------------------------------------------------------------
|    free    |   free    |array1234[0]|array1234[1]|    free    | ...


offset of furthest used block in mmap'ed memory x 4ただし、このアプローチには（4バイトの整数） のメモリオーバーヘッドがあります。

この特定のケースには、どのようなより良いアプローチがありますか？

これに対する私の理想的な要件は次のとおりです。

  • メモリオーバーヘッド（任意の割り当てテーブル+未使用スペース）<=要素あたり1.5ビット+配列あたり4*6バイト
  • O（1）配列の割り当てと拡張
4

3 に答える 3

1

Boost.Interprocessは、malloc / freeと同様のプロビジョニングを備えた、管理されたメモリマップトファイルの適切な実装を備えているようですが、マップされたファイル用です（つまり、適切に大きいメモリマップトファイルへのハンドルがあり、ライブラリにサブを要求できます-ファイルの未使用部分を配列などの何かに割り当てます）。ドキュメントから：

Boost.Interprocessは、共有メモリオブジェクトとファイルマッピングを作成し、それらのマップ可能なクラスをプロセスのアドレス空間にマップするためのいくつかの基本的なクラスを提供します。

ただし、これらのメモリセグメントの管理は、重要なタスクでは簡単ではありません。マップされた領域は固定長のメモリバッファであり、任意のタイプのオブジェクトを動的に作成および破棄するには、そのセグメントの一部を割り当てるためにメモリ管理アルゴリズムをプログラミングする必要があるため、多くの作業が必要です。多くの場合、共有メモリに作成されたオブジェクトに名前を関連付けて、すべてのプロセスがその名前を使用してオブジェクトを見つけられるようにします。

Boost.Interprocessは、4つのマネージドメモリセグメントクラスを提供します。

  • 共有メモリマップ領域（basic_managed_shared_memoryクラス）を管理します。
  • メモリマップトファイル（basic_managed_mapped_file）を管理します。
  • ヒープに割り当てられた（演算子new）メモリバッファー（basic_managed_heap_memoryクラス）を管理します。
  • ユーザー提供の固定サイズのバッファー（basic_managed_external_bufferクラス）を管理します。

マネージドメモリセグメントの最も重要なサービスは次のとおりです。

  • セグメントのメモリの一部の動的割り当て。
  • メモリセグメントでのC++オブジェクトの構築。これらのオブジェクトは匿名にすることも、名前を関連付けることもできます。
  • 名前付きオブジェクトの検索機能。
  • 多くの機能のカスタマイズ：メモリ割り当てアルゴリズム、インデックスタイプ、または文字タイプ。
  • セグメントが2つのプロセス間で共有されている場合、同じ名前に関連付けられた2つのオブジェクトを作成することが不可能であるため、アトミックな構築と破棄により、同期が簡素化されます。
于 2012-10-19T19:54:29.570 に答える
1

いくつのmmap領域を購入できますか？128で問題がない場合は、アレイのすべての可能なサイズに対応する128の領域を作成しました。そして理想的には、各エリアの無料エントリーのリンクリストです。この場合、各領域のレコードの固定サイズを取得します。そして、配列をNからN + 1に拡張することは、データをarea[N]からarea[N + 1]に移動する操作です（N + 1の空のエントリのリンクリストが空の場合）。そうでない場合は空のスロット。area [N]の場合、削除されたスロットが空きエントリのリストに追加されます

更新：リンクリストは主要な構造に埋め込むことができます。したがって、追加の割り当ては必要ありません。すべての可能なレコード（サイズ1から128まで）内の最初のフィールド（int）は、次の空きエントリへのインデックスになります。割り当てられたエントリの場合、常に無効（0xffffffff）ですが、エントリが空いている場合、このインデックスは対応するリンクチェーンのメンバーになります。

于 2012-10-20T05:17:44.110 に答える
-1

私は、O（1）が償却され、断片化がほとんどなく、オーバーヘッドがほとんどない、要件にほぼ一致するメモリ割り当てアルゴリズムを考案し、最終的に採用しました。コメントしてください。機会があれば詳しく説明します。

于 2012-10-20T23:20:11.837 に答える