8

非常に特殊な状況を処理するためのヒープマネージャーのアイデアを探しています。それぞれ12〜64バイトの範囲の非常に小さな割り当てがたくさんあります。それよりも大きいものは、通常のヒープマネージャーに渡すので、小さなブロックだけに対応する必要があります。4バイトのアライメントのみが必要です。

私の主な関心事は

  1. オーバーヘッド。通常のlibcヒープは通常、割り当てを16バイトの倍数に切り上げてから、別の16バイトヘッダーを追加します。これは、20バイトの割り当てで50％を超えるオーバーヘッドを意味します。
  2. パフォーマンス

1つの有用な側面は、Lua（このヒープのユーザー）がfree（）を呼び出すときに解放するブロックのサイズを通知することです。これにより、特定の最適化が可能になる場合があります。

現在のアプローチを投稿します。これは問題なく機能しますが、可能な限り改善したいと思います。何か案は？

4

6 に答える 6

6

すべて同じサイズのオブジェクトに対して非常に効率的なヒープマネージャーを構築することが可能です。必要なオブジェクトのサイズごとにこれらのヒープの1つを作成できます。または、少しスペースを使用してもかまわない場合は、16バイトのオブジェクト用に1つ、32バイト用に1つ、64バイト用に1つ作成します。最大オーバーヘッドは次のようになります。 33バイトの割り当ての場合は31バイト（64ブロックサイズのヒープになります）。

于 2008-10-23T00:55:02.953 に答える
6

Greg Hewgill が言っていることを拡張すると、超効率的な固定サイズのヒープを実行する 1 つの方法は次のとおりです。

  1. 大きなバッファをノードに分割します。ノードのサイズは sizeof(void*) 以上である必要があります。
  2. リンク ポインターとして各フリー ノードの最初の sizeof(void*) バイトを使用して、単一リンク リスト (「フリー リスト」) にそれらをつなぎ合わせます。割り当てられたノードはリンク ポインターを必要としないため、ノードごとのオーバーヘッドは 0 です。
  3. リストの先頭を削除して返すことで割り当てます (2 回のロード、1 回のストア)。
  4. リストの先頭に挿入することで解放されます (1 ロード、2 ストア)。

明らかに、ステップ 3 では、リストが空かどうかもチェックする必要があります。空の場合は、新しい大きなバッファーを取得する (または失敗する) 一連の作業を行います。

Greg D と hazzen が言うように、さらに効率的なのは、ポインターをインクリメントまたはデクリメントすること (1 ロード、1 ストア) によって割り当てることであり、1 つのノードを解放する方法をまったく提供しません。

編集: どちらの場合も、free の呼び出しでサイズが返されるという便利な事実により、free は「通常のヒープ マネージャーに渡すより大きなもの」という複雑さに対処できます。それ以外の場合は、フラグ (ノードごとにおそらく 4 バイトのオーバーヘッド) を見るか、使用したバッファーのある種のレコードを参照することになります。

于 2008-10-23T01:10:08.600 に答える
3

答えは、これらのオブジェクトの有効期間パターンに依存する場合があります。先に進むにつれてオブジェクトがすべてインスタンス化され、その後すべてが一気に削除される場合は、ポインタをインクリメントするだけでメモリを割り当てる非常に単純なヒープ マネージャを作成するのが理にかなっています。次に、完了したら、ヒープ全体を吹き飛ばします。

Raymond Chen は、あなたを刺激するのに役立つかもしれない興味深い投稿をしました。:)

于 2008-10-23T01:02:15.370 に答える
1

一人一人の答えが好きです。

また、固定サイズのヒープのセットにバディ システムを検討することもできます。

于 2008-10-23T02:20:16.947 に答える
0

大量のメモリが割り当てられ、使用され、解放されてから次の割り当てラウンドに進む場合は、可能な限り単純なアロケーターを使用することをお勧めします。

typedef struct _allocator {
    void* buffer;
    int start;
    int max;
} allocator;

void init_allocator(size_t size, allocator* alloc) {
    alloc->buffer = malloc(size);
    alloc->start = 0;
    alloc->max = size;
}

void* allocator_malloc(allocator* alloc, size_t amount) {
    if (alloc->max - alloc->start < 0) return NULL;
    void* mem = alloc->buffer + alloc->start;
    alloc->start += bytes;
    return mem;
}

void allocator_free(allocator* alloc) {
    alloc->start = 0;
}
于 2008-10-23T01:05:38.313 に答える
0

私は主に O(1) Small Block Memory Manager (SBMM) を使用しています。基本的には次のように動作します。

1) OS からより大きなスーパーブロックを割り当て、開始アドレスと終了アドレスを範囲として追跡します。SuperBlock のサイズは調整可能ですが、1MB で十分なサイズになります。

2) SuperBlocks はブロックに分割されます (サイズも調整可能です...アプリによっては 4K-64K が適しています)。これらの各ブロックは、特定のサイズの割り当てを処理し、ブロック内のすべての項目を単独でリンクされたリストとして格納します。SuperBlock を割り当てると、フリー ブロックのリンク リストが作成されます。

3) アイテムの割り当てとは、A) そのサイズを処理する空きアイテムを含むブロックがあるかどうかを確認することを意味します。ない場合は、スーパーブロックから新しいブロックを割り当てます。B) ブロックの空きリストからアイテムを削除する。

4) アドレスによるアイテムの解放 A) アドレス (*) を含むスーパーブロックの検索 B) スーパーブロック内のブロックの検索 (スーパーブロックの開始アドレスを減算し、ブロック サイズで割る) C) ブロックのフリー アイテム リストにアイテムを押し戻す。

前述したように、この SBMM は O(1) パフォーマンス (*) で実行されるため、非常に高速です。私が実装したバージョンでは、AtomicSList (Windows の SLIST に似ています) を使用して、実装で O(1) パフォーマンスだけでなく、ThreadSafe と LockFree も実現できるようにしています。必要に応じて、実際に Win32 SLIST を使用してアルゴリズムを実装できます。

興味深いことに、スーパーブロックからのブロックまたはブロックからの項目を割り当てるためのアルゴリズムは、ほぼ同一のコードになります (どちらもフリー リストからの O(1) 割り当てです)。

(*) スーパーブロックは、平均パフォーマンスが O(1) の範囲マップに配置されます (ただし、N がスーパーブロックの数である場合、最悪の場合は O(Lg N) になる可能性があります)。範囲マップの幅は、O(1) のパフォーマンスを得るために必要なメモリ量を大まかに把握することに依存します。オーバーシュートすると、メモリが少し無駄になりますが、それでも O(1) のパフォーマンスが得られます。アンダーシュートすると、O(Lg N) のパフォーマンスに近づきますが、N は SuperBlock の数であり、アイテムの数ではありません。SuperBlock の数は Item の数に比べて非常に少ないため (私のコードではバイナリで約 20 桁)、残りのアロケーターほど重要ではありません。

于 2009-09-28T04:30:56.610 に答える