0

特定のサイズ（MAX_OBJECT_SIZEと呼びましょう）を超えることのない複数のオブジェクトを割り当てるプログラム（C++など）があるとします。

また、ヒープ上にリージョン（「ページ」と呼びます）があります（たとえば、malloc（REGION_SIZE）で割り当てられます。ここで、REGION_SIZE> = MAX_OBJECT_SIZE）。
いっぱいになったスペースが PAGE_SIZE に等しくなるまで (または少なくとも > PAGE_SIZE - MAX_OBJECT_SIZE になるまで)、そのページにスペースを確保し続けます。

ここで、より多くのメモリを割り当てたいと思います。明らかに、以前の「ページ」では十分ではありません。したがって、少なくとも 2 つのオプションがあります。

  1. NEW_SIZE > PAGE_SIZE の realloc(page, NEW_SIZE) を使用します。
  2. 新しい「ページ」(page2) を割り当て、そこに新しいオブジェクトを配置します。

カスタム割り当て関数が必要な場合は、次のようにします。

  1. 最初の方法を使用して、どれだけ満たしたかを確認し、そこに新しいオブジェクトを配置します (オブジェクトのサイズを、満たされたメモリ変数に追加します)。
  2. 2 番目の方法を使用すると、ページのリスト (ベクトル? 配列?) を取得し、現在のページを探して、選択したページで 1 と同様の方法を使用します。

最終的には、メモリを解放する方法も必要になりますが、その部分は理解できます。

私の質問は次のとおりです。このような問題を解決する最も効率的な方法は何ですか? それはオプション 1、オプション 2、またはここで検討していない他のオプションですか? 現実世界の状況で結論を引き出すには、小さなベンチマークが必要ですか、または十分ですか? 操作が異なればパフォーマンスも異なる可能性があることは理解していますが、全体的な指標を探しています。

4

6 に答える 6

1

私の経験では、オプション 2 の方が作業がはるかに簡単で、オーバーヘッドは最小限です。Reallocは、既存のメモリのサイズを増加させることを保証しません。そして実際には、それはほとんどありません。これを使用する場合は、戻って古いオブジェクトをすべて再マップする必要があります。それには、割り当てられたすべてのオブジェクトがどこにあったかを覚えておく必要があります...それはオーバーヘッドを大幅に超える可能性があります。

しかし、使用している指標を正確に知らずに「最も効率的」と判断することは困難です。

これは、私がいつも使用しているメモリ マネージャーです。1 つのオブジェクトだけでなく、アプリケーション全体で機能します。

割り当てます:

割り当てごとに、割り当てられたオブジェクトのサイズを決定します。

1 そのサイズのオブジェクトの解放のリンク リストを調べて、何かが解放されているかどうかを確認します。

2 検索テーブルで検索し、見つからない場合

2.1 割り当てられるサイズの N 個のオブジェクトの配列を割り当てます。

3 目的のサイズの次の空きオブジェクトを返します。

3.1 配列がいっぱいの場合は、新しいページを追加します。

N 個のオブジェクトをプログラマーで調整できます。16 バイトのオブジェクトが 100 万個あることがわかっている場合は、N を少し大きくしたいと思うかもしれません。

サイズ X を超えるオブジェクトの場合、配列を保持しないで、新しいオブジェクトを割り当てるだけです。

解放:

オブジェクトのサイズを決定し、フリーのリンク リストに追加します。

割り当てられたオブジェクトのサイズがポインタのサイズよりも小さい場合、リンク リストはメモリ オーバーヘッドを発生させる必要はありません。すでに割り当てられているメモリを使用してノードを格納するだけです。

この方法の問題点は、アプリケーションが終了するか、プログラマがメモリの最適化を決定するまで、メモリがオペレーティング システムに返されないことです。最適化は別の投稿です。それはできます。

于 2010-06-29T12:45:35.137 に答える
0

Linux (およびおそらく他の POSIX システム) では、3 番目の可能性がありますshm_open。このような領域は、アクセスするとゼロで初期化されますが、予約した仮想メモリのアドレス範囲だけではない場合、アクセスしないAFAIKページは無料です。したがって、実行の最初に (必要以上に) 大量のメモリを予約し、最初から段階的に埋めることができます。

于 2010-06-29T13:03:44.770 に答える
0

このような問題を解決する最も効率的な方法は何ですか? それはオプション 1、オプション 2、またはここで検討していない他のオプションですか? 現実世界の状況で結論を引き出すには、小さなベンチマークが必要ですか、または十分ですか?

オプション 1. 効率的にするには、NEW_SIZE を古いサイズに非線形的に依存させる必要があります。そうしないと、冗長なコピーのために realloc() の O(n^2) パフォーマンスが発生するリスクがあります。理論的には、最悪の場合、未使用のメモリを予約しすぎる可能性があるため、通常はそうしますnew_size = old_size + old_size/4(25% 増加) 。new_size = old_size*2

オプション 2. ほとんどの最新の OS (C++ の STL のおかげ) は、小さなメモリ割り当てのフラッドに対して既に十分に最適化されているため、より最適なはずです。また、割り当てが小さいと、メモリの断片化が発生する可能性が低くなります。

最終的には、新しいオブジェクトを割り当てる頻度と、解放をどのように処理するかによってすべてが異なります。＃1で多くを割り当てると、展開時に冗長なコピーが発生しますが、すべてのオブジェクトが同じページにあるため、解放は非常に簡単です. オブジェクトを解放/再利用する必要がある場合、#2 では、ページのリストを見て回るのに時間がかかります。

私の経験からすると、#2 の方が優れています。大きなメモリ ブロックを移動すると、ヒープの断片化率が高くなる可能性があるためです。＃2では、オブジェクトがメモリ内の場所を変更しないため、ポインターを使用することもできます（ただし、一部のアプリケーションでは、生のポインターの代わりにpool_id / indexペアを使用することを好みます）。後でページをたどるのが問題になる場合は、最適化しすぎている可能性があります。

最後に、オプション #3: libc も検討する必要があります。libc の malloc() は、多くのタスクに対して十分に効率的だと思います。時間を費やす前にテストしてください。バックワード *NIX に行き詰まっていない限り、小さなオブジェクトごとに malloc() を使用しても問題はありません。カスタム メモリ管理は、オブジェクトを風変わりな場所 (shm や mmap など) に配置する必要がある場合にのみ使用しました。マルチスレッドにも注意してください。malloc()/realloc()/free() は通常、既に最適化されており、MT に対応しています。スレッドがメモリ管理で常に衝突するのを避けるために、最適化を新たに再実装する必要があります。また、メモリ プールまたはゾーンが必要な場合は、そのためのライブラリも既にたくさんあります。

于 2010-06-29T15:29:56.490 に答える
0

必要に応じて各オブジェクトにメモリを割り当てるのではなく、事前に大きなメモリ ブロックを割り当てる必要がある理由は、あなたの質問からは明らかではありません。連続した配列として使用していると仮定しています。mallocそれ以外の場合は、必要に応じて各オブジェクトのメモリにとってより意味があります。

それが実際に配列として機能している場合、malloc-ing another block は、別のポインターを介してアクセスする必要がある別のメモリチャンクを提供します(あなたの場合はpage2. したがって、隣接するブロックではなくなり、2 つのブロックを 1 つの配列の一部として使用することはできません。

realloc一方、1 つの連続したメモリ ブロックを割り当てます。それを単一の配列として使用し、個別のブロックがある場合は不可能なあらゆる種類のポインター演算を実行できます。realloc作業しているブロックを実際に縮小したい場合にも役立ちますが、それはおそらくここでやりたいことではありません。

したがって、これを配列として使用している場合は、realloc基本的により良いオプションです。そうでなければ、 に問題はありませんmalloc。malloc実際には、メモリのブロックを追跡して細かく管理するよりも、作成するオブジェクトごとに使用したい場合があります。

于 2010-06-29T12:36:14.507 に答える
0

実験しているプラ​​ットフォームについての詳細は提供されていません。たとえば、とのrealloc間にはいくつかのパフォーマンスの違いがあります。LinuxWindows

状況によっては、現在のメモリを拡張できず、古いメモリを新しいメモリにコピーできない場合、新しいメモリ ブロックreallocを割り当てなければならない場合がありますが、これにはコストがかかります。連続したメモリ ブロックが本当に必要ない場合は、使用を避ける必要があります。realloc

私の提案は、2 番目のアプローチを使用するか、カスタム アロケーターを使用することです (単純なバディ アロケーター [2]を実装できます)。

次のような、より高度なメモリ アロケータを使用することもできます。

于 2010-06-29T12:41:16.750 に答える
0

In the worst case, option 1 could cause a "move" of the original memory, that is an extrawork to be done. If the memory is not moved, anyway the "extra" size is initialized, which is other work too. So realloc would be "defeated" by the malloc method, but to say how much, you should do tests (and I think there's a bias on how the system is when the memory requests are done).

Depending on how many times you expect the realloc/malloc have to be performed, it could be an useful idea or an unuseful one. I would use malloc anyway.

The free strategy depends on the implementation. To free all the pages as whole, it is enough to "traverse" them; instead of an array, I would use linked "pages": add sizeof(void *) to the "page" size, and you can use the extra bytes to store the pointer to the next page.

If you have to free a single object, located anywhere in one of the pages, it becomes a little bit more complex. My idea is to keep a list of non-sequential free "block"/"slot" (suitable to hold any object). When a new "block" is requested, first you pop a value from this list; if it is empty, then you get the next "slot" in the last in use page, and eventually a new page is triggered. Freeing an object, means just to put the empty slot address in a stack/list (whatever you prefer to use).

于 2010-06-29T12:44:42.427 に答える