重いチャーン、小さな割り当てのための効率的なヒープマネージャー？

StackOverflow https://stackoverflow.com/questions/228081

質問

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

私の主な関心事は

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

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

大丈夫な現在のアプローチを投稿しますが、可能な限り改善したいと思います。アイデアはありますか？

役に立ちましたか？

解決

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

他のヒント

グレッグヒューギルの言うことを拡張するために、超効率的な固定サイズヒープを実行する1つの方法は次のとおりです。

  1. 大きなバッファをノードに分割します。ノードサイズは少なくともsizeof（void *）でなければなりません。
  2. リンクポインターとして各フリーノードの最初のsizeof（void *）バイトを使用して、それらを単一リンクリスト（「フリーリスト」）にまとめます。割り当てられたノードはリンクポインターを必要としないため、ノードごとのオーバーヘッドは0です。
  3. リストの先頭を削除して返す（2ロード、1ストア）ことにより割り当てます。
  4. リストの先頭に挿入することで無料（1ロード、2ストア）。

もちろん、ステップ3はリストが空かどうかも確認する必要があり、そうであれば、大量の新しいバッファを取得する（または失敗する）作業を行います。

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

編集：どちらの場合も、無料で複雑な「通常のヒープマネージャーに渡すより大きなもの」に対処できます。無料の呼び出しでサイズを戻すという有益な事実によって。それ以外の場合は、フラグ（ノードごとにオーバーヘッドがおそらく4バイト）または使用したバッファのレコードの種類を検索します。

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

Raymond Chenは興味深い投稿を作成しました。あなたを刺激するのに役立つかもしれません。 ：）

onebyonesの回答が好きです。

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

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

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;
}

ほとんどO（1）Small Block Memory Manager（SBMM）を使用しています。基本的には次のように機能します：

1）OSからより大きなSuperBlocksを割り当て、開始+終了アドレスを範囲として追跡します。 SuperBlockのサイズは調整可能ですが、1MBはかなり良いサイズになります。

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

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

4）アドレスによるアイテムの解放は、A）アドレスを含むSuperBlockの検索（*）B）SuperBlock内のブロックの検索（SuperBlockの開始アドレスを減算し、ブロックサイズで除算する）C）ブロックのFree Itemリストにアイテムを戻す/ p>

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

興味深いことに、スーパーブロックからのブロックまたはブロックからのアイテムを割り当てるためのアルゴリズムは、ほぼ同一のコードになります（両方ともフリーリストからO（1）割り当てが行われます）。

（*）SuperBlocksは、O（1）平均パフォーマンス（ただし、NはSuperBlocksの数である最悪の場合の潜在的なO（Lg N））を持つレンジマップに配置されます。レンジマップの幅は、O（1）パフォーマンスを得るために必要なメモリの量を大まかに知ることに依存します。オーバーシュートすると、メモリを少し消費しますが、O（1）パフォーマンスが得られます。アンダーシュートすると、O（Lg N）のパフォーマンスに近づきますが、Nはアイテム数ではなくスーパーブロック数です。 SuperBlockの数はItemの数と比較して非常に少ないため（私のコードでは約20桁のバイナリ）、アロケーターの他の部分ほど重要ではありません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top