6

Visual Studio 2008 C ++アプリケーションがあり、標準コンテナーにカスタムアロケータを使用して、メモリがヒープではなくメモリマップトファイルから取得されるようにしています。このアロケータは、4つの異なるユースケースで使用されます。

  1. 104バイトの固定サイズ構造std::vector< SomeType, MyAllocator< SomeType > > foo;
  2. 200バイトの固定サイズ構造
  3. 304バイトの固定サイズ構造
  4. nバイトの文字列std::basic_string< char, std::char_traits< char >, MyAllocator< char > > strn;

これらのそれぞれに合計約32MBを割り当てることができる必要があります。

std::mapアロケータは、割り当てサイズへのポインタを使用してメモリ使用量を追跡します。typedef std::map< void*, size_t > SuperBlock;各スーパーブロックは4MBのメモリを表します。

std::vector< SuperBlock >1つのSuperBlockに十分なスペースがない場合に備えて、これらがあります。

アロケータに使用されるアルゴリズムは次のようになります。

  1. スーパーブロックごとに：スーパーブロックの最後にスペースはありますか？そこに割り当てを置きます。（速い）
  2. そうでない場合は、各SuperBlock内で十分なサイズの空きスペースを検索し、そこに割り当てを配置します。（スロー）
  3. まだ何もありませんか？別のSuperBlockを割り当て、その割り当てを新しいSuperBlockの先頭に配置します。

残念ながら、ステップ2はしばらくすると非常に遅くなる可能性があります。オブジェクトのコピーが作成され、一時変数が破棄されると、多くの断片化が発生します。これにより、メモリ構造内で多くの詳細な検索が発生します。使用できるメモリの量が限られているため、断片化が問題になっています（下記の注を参照）

プロセスをスピードアップするこのアルゴリズムの改善を誰かが提案できますか？2つの別々のアルゴリズム（1つは固定サイズの割り当て用、もう1つは文字列アロケータ用）が必要ですか？

注：理由が必要な場合：ヒープに32MBのプロセススロット制限があるWindowsMo​​bileでこのアルゴリズムを使用しています。だから、いつもstd::allocatorはそれをカットしません。十分なスペースを確保するために、1GBの大容量メモリ領域に割り当てを配置する必要があります。

4

6 に答える 6

6

割り当てる固定サイズのタイプごとに個別のメモリ割り当てプールを設定できますか？そうすれば、割り当てられたオブジェクトは常にnバイト境界に整列するため、断片化は発生しません。もちろん、これは可変長文字列には役立ちません。

AlexandrescuのModernC++デザインには、この原則を説明し、いくつかのアイデアを与える可能性のある小さなオブジェクトの割り当ての例があります。

于 2011-05-17T16:49:42.513 に答える
2

固定サイズのオブジェクトの場合、固定サイズのアロケータを作成できます。基本的に、ブロックを割り当て、適切なサイズのサブブロックに分割し、結果を含むリンクリストを作成します。使用可能なメモリがある場合（リストから最初の要素を削除してポインタを返すだけ）、割り当て解除（ブロックを空きリストに追加）と同様に、このようなブロックからの割り当てはO（1）です。割り当て中に、リストが空の場合は、新しいスーパーブロックを取得し、パーティションを作成して、すべてのブロックをリストに追加します。

可変サイズのリストの場合、既知のサイズ（32バイト、64バイト、128バイト、512バイト）のブロックのみを割り当てることにより、固定サイズのブロックに簡略化できます。あまり多くのメモリを浪費しないように、さまざまなバケットを考え出すためにメモリ使用量を分析する必要があります。大きなオブジェクトの場合、動的なサイズ割り当てパターンに戻ることができます。これは遅くなりますが、大きなオブジェクトの量が制限されていることを願っています。

于 2011-05-17T16:57:49.590 に答える
2

ティムの答えに基づいて、私は個人的にBiBOPに似たものを使用します。

基本的な考え方は単純です。固定サイズのプールを使用します。

これにはいくつかの改良点があります。

まず、プールのサイズは一般的に固定されています。これは割り当てルーチンによって異なります。通常、mallocを使用するときにマップで作業しているOSが一度に少なくとも4KBであることがわかっている場合は、その値を使用します。メモリマップトファイルの場合、これを増やすことができる場合があります。

固定サイズのプールの利点は、断片化をうまく防ぐことです。すべてのページが同じサイズであるため、空の256バイトのページを128バイトのページに簡単にリサイクルできます。

通常、このシステムの外部に割り当てられる大きなオブジェクトには、まだいくつかの断片化があります。ただし、特に大きなオブジェクトをページサイズの倍数に収める場合は低く、この方法でメモリを簡単にリサイクルできます。

第二に、プールを処理する方法は？リンクリストの使用。

通常、ページは（それ自体では）型指定されていないため、新しいページを準備して「リサイクル」ページを配置するためのページのフリーリストがあります。

サイズカテゴリごとに、メモリが割り当てられている「占有」ページのリストがあります。保持するページごとに：

  • 割り当てサイズ（このページの場合）
  • 割り当てられたオブジェクトの数（空をチェックするため）
  • 最初のフリーセルへのポインタ
  • 前のページと次のページへのポインタ（リストの「先頭」を指す場合があります）

各フリーセルは、それ自体が次のフリーセルへのポインタ（またはサイズによってはインデックス）です。

特定のサイズの「占有」ページのリストは、単純に管理されます。

  • 削除時：ページを空にした場合は、リストから削除してリサイクルページにプッシュします。それ以外の場合は、このページのフリーセルリストを更新します（注：現在のページの先頭を見つけることは、通常、単純なモジュロ演算です。アドレスに）
  • 挿入時：頭から検索し、完全でないページを見つけたらすぐに、リストの前に移動して（まだ表示されていない場合）、アイテムを挿入します

このスキームは、インデックス作成用に1ページだけが予約されており、メモリに関しては非常にパフォーマンスが高くなっています。

マルチスレッド/マルチプロセスアプリケーションの場合、Googleのtcmallocからインスピレーションを得ることができる場合に備えて、同期（通常はページごとのミューテックス）を追加する必要があります（ブロックする代わりに別のページを見つけて、スレッドローカルキャッシュを使用してください）最後に使用したページを覚えておいてください）。

そうは言っても、Boost.Interprocessを試しましたか？アロケータを提供します。

于 2011-05-17T17:31:34.343 に答える
1

私はTimに同意します-断片化を避けるためにメモリプールを使用します。

ただし、オブジェクトではなくポインタをベクトル（おそらくptr_vector？）に格納することで、チャーンの一部を回避できる場合があります。

于 2011-05-17T17:03:12.110 に答える
1

固定サイズの場合、固定サイズのチャンクに分割された大きなブロックを割り当てる、小さなメモリアロケータタイプのアロケータを簡単に使用できます。次に、使用可能なチャンクへのポインターのベクトルを作成し、割り当て/解放するときにポップ/プッシュします。これは非常に高速です。

可変長のアイテムの場合、それはより困難です。使用可能な連続スペースの検索に対処するか、他のアプローチを使用する必要があります。ブロックサイズ順に並べられたすべての空きノードの別のマップを維持することを検討してください。そうすれば、マップをlower_boundできます。次に使用可能なノードが5％大きすぎる場合は、正確なサイズの使用可能な使用可能なスペースを探す代わりに、それを返します。

于 2011-05-17T16:52:29.410 に答える
1

可変サイズのアイテムに対する私の傾向は、実用的であれば、データへの直接ポインターを保持することを避け、代わりにハンドルを保持することです。各ハンドルは、スーパーブロックのインデックス、およびスーパーブロック内のアイテムへのインデックスになります。各スーパーブロックには、アイテムリストがトップダウンで割り当てられ、アイテムがボトムアップで割り当てられます。各アイテムの割り当ての前には、その長さと、それが表すアイテムのインデックスがあります。インデックスの1ビットを使用して、アイテムが「固定」されているかどうかを示します。

アイテムが最後に割り当てられたアイテムの後に収まる場合は、単にそれを割り当てます。固定されたアイテムにヒットする場合は、次の割り当てマークを固定されたアイテムの先に移動し、次に高い固定されたアイテムを見つけて、割り当てを再試行します。アイテムがアイテムリストと衝突するが、どこかに十分な空き領域がある場合は、ブロックの内容を圧縮します（1つ以上のアイテムが固定されている場合は、別のスーパーブロックが利用可能な場合はそれを使用することをお勧めします）。使用パターンによっては、最後のコレクション以降に追加されたものだけをコンパクト化することから始めることが望ましい場合があります。それでも十分なスペースがない場合は、すべてをコンパクト化します。

もちろん、アイテムの個別のサイズが数個しかない場合は、単純な固定サイズのチャンクアロケータを使用できます。

于 2011-05-17T16:59:17.473 に答える