3

ここでは、「プール」と「バッファ」という用語を同じ意味で使用できます。
常に呼び出すとは限らないため、プログラムの開始時に割り当てたいプールがあるとしますnew。
ここで、プールのサイズを人為的に制限したくはありませんが、より大きなプールを再割り当てすると、古いプールへのすべてのポインターが無効になります。これは確かにあまりクールではありません。

私が考えた1つの方法は、別名「ページング」でした

const int NUM_PAGES = 5;
char* pool[NUM_PAGES];

また、1 ページだけを再割り当てするのではなく、新しいページを割り当てます。これにより、すべてのポインターが有効なままになりますが、ページ プールの管理が少し難しくなります。また、私はページ数を制限しているので、最終的にはプールのサイズについても同様です。

別の方法は、割り当て関数が返すポインタから実メモリ空間へのポインタへのマッピングを行うことでした。これにより、すべての古いポインターが有効なままになりますが、より多くのメモリが必要になり、マッピングを行う割り当て関数から戻るスマート ポインターを作成する必要があります。

私が望むものを達成するために他にどのような方法がありますか? 上記の実装例で見逃した (欠点) 利点は何ですか?

4

5 に答える 5

2

ページ化された「プール」の概念を拡張すると、ページをリンクされたリストとして保存した場合はどうなりますか??

プールから新しいデータを割り当てるには、リストの先頭にある一番上の「ページ」にアクセスする必要があるだけなので、それは O(1) です。プールの合計サイズを大きくする必要がある場合は、新しいページを割り当てて、それをリストの先頭 (O(1)) にプッシュします。

プールされたアロケーターにも基本的に同じアイデアを使用しますが、最近割り当て解除されたアイテムの「フリーリスト」にも使用します...

編集:あなたのコメントによると、割り当て解除されたデータも利用したい場合は、フリーリストをリンクリストとして保存することもできます。したがって、データの割り当てを解除するときは、ポインタとサイズ マーカーをフリー リストにプッシュします。プールからデータを割り当てるときは、最初に空きリストのアイテムが使用できるかどうかを確認し、使用できない場合はプールから割り当てます。

多くの場合、標準のメモリ マネージャーは既にこのようなことを行っているため、このアプローチが常に優れているとは限りません。具体的には、私は通常、割り当てられた項目が同じサイズである場合にのみ、このタイプのカスタム アロケーターを使用します (そのため、フリー リストのトラバーサルは O(1)!)。std::list のカスタム アロケータはその一例です。

お役に立てれば。

于 2011-04-27T06:43:31.177 に答える
2

を思い出させる何かについて話しているstd::deque。std::dequeをそのまま使用できるのか、それとも基本的な設計を使用してある種のアロケーターを実装する必要があるのか​​ はよくわかりません。

于 2011-04-27T07:05:51.770 に答える
1

もちろん、1 つの質問は、なぜ自分自身を悩ませるのかということです。

あなたはオーバーヘッドを避けたいと言っていますnewが、代わりにより良い実装を選択しないのはなぜnewですか? tcmalloc一般にjemalloc、たとえばマルチスレッド アプリケーションでは非常に優れた候補です。

malloc実際、作成しようとしているものは、カスタマイズされた/new実装を作成することと非常に似ています。したがって、実証済みの実装を本当に使用したくない場合は、実際に使用した人の洞察から利益を得ることができます。

私の個人的な関心は、断片化を防ぐための BiBOP 戦略 (Big Bag of Pages) に傾いています。割り当てのサイズごとに専用のプールを用意するという考え方なので、単純なフリー リスト (割り当てとインターリーブ) で十分です (マージは必要ありません)。通常、これは、要求されたサイズがページ サイズよりも小さく (4KB が使用されているのを見たことがあります)、それより大きいサイズが (複数のページで) 割り当てられている限り行われます。破棄されたページはリサイクルされます。

私が主に関心を持っているのは、BiBOP を使用するとインターバル ツリーのアドレス範囲 -> ページ ヘッダーを維持するのが簡単であり、(おそらく) 内部要素 (属性など) のアドレスからオブジェクトのフル サイズを決定できることです。これは便利です。ガベージ コレクション用 (次の手順を参照)。

マルチスレッド割り当ての場合、次の2 つの異なるアプローチtcmallocを使用します。jemalloc

  • jemallocスレッドごとのプールを使用する: 固定数のスレッド/スレッド プールには適していますが、スレッドを作成するプロセスのコストが高くなります
  • tcmallocロックフリー技術を備えたグローバルマルチスレッドプールを使用し、使用するプールが「ロック」されている場合はスレッドに新しいプールを探すようにさせることで、競合を制限するために利用可能なプールでスレッドの負荷分散を試みます。待機)、各スレッドが最後に使用されたプールをスレッド ローカル変数にキャッシュするようにします。したがって、スレッドは軽量ですが、アクティブなスレッドの数に対してプールの数が少なすぎると、競合が発生する可能性があります。
于 2011-04-27T07:34:46.467 に答える
1

ブースト プールの使用を検討する

于 2011-04-27T06:31:54.043 に答える