/小さなオブジェクトの自由多くを割り当てるための戦略

Question

私はやや困難です特定のキャッシュアルゴリズム、いじるいます。 基本的には、マッピングされた値、map[key] = array介してアクセス可能なオブジェクトと、小さなオブジェクト（二重アレイ、1〜256の要素）のロットを割り当てる必要があります。初期化された配列への時間は、通常以上の1万CPUサイクル、非常に大きくなることがあります。

は、たくさんのことで私は、合計でギガバイトの周りを意味します。オブジェクトが一つのオブジェクト時点で、一般的にランダムな場所で、必要に応じてプッシュ/ポップする必要があるかもしれません。オブジェクトの寿命は、一般的に、長い分以上であるが、オブジェクトは、プログラムの期間中に数回割り当て/解除の対象となる場合があります。

まだ割り当て解除速度を割り当てる合理的な維持しながら、メモリの断片化を避けるために良い戦略をでしょうか？

私はC ++を使用していますので、私は新しい、malloc関数を使用することができます。 おかげます。

私は、ウェブサイト上で同様の質問が知っている、多くの短命小さなオブジェクトは、に多少異なっている、スレッドの安全性は私にとって当面の問題ではありません。

私の開発プラットフォームは、IntelのXeon、Linuxオペレーティングシステムです。 理想的には私もPPCのLinux上で動作するようにしたいと思いますが、それは私にとって最も重要ではありません。

Answer 1

スロット・アロケータを作成します：

アロケータは、同じサイズの各（512K、256K、サイズはご使用のために調整されなければならない）メモリの多くのページで作成されます。

オブジェクトがページを割り当てるメモリこのアロケータを要求初めて。ページを割り当てると（何の検索、すべてのページが同じサイズではない）、フリーリストから削除し、このページに割り当てられますオブジェクトのサイズを設定することで構成されています。一般的に要求されたサイズを取り、同じサイズの2割り振りの最寄りのパワーにそれを切り上げて計算し、このサイズはちょうどポインタの数学の少しを必要とし、ページ上のオブジェクトの数をインクリメントます。

スロットは全て同じ大きさであり、後続の割り当てに補充することができるので、

フラグメンテーションが防止されます。 （割当てが配分が大きくなったら、このアロケータは、利用可能なメモリのほぼ50％を無駄に開始し、小型で大きな違い）割当あたり何memheaderがないので効率は（いくつかのケースで改善）が維持される。

の割り当てと割り当て解除の両方が（正しいスロットの空きリストのない検索）一定の時間で行うことができます。解放についての唯一のトリッキーな部分は...あなたがページで自分自身をページとインデックスを把握する必要がありますので、一般的に、割り当ての前memheaderを望んでいないということですそれは土曜日だと私は私は私のコーヒーを持っていませんでしたそれをやってについて何か良いアドバイスを持っていない、それはしかし、割り当て解除アドレスから把握することは簡単です。

編集：この答えは少し長い息切れされます。いつものはあなたの背中を持っています。

Answer 2

あなたが事前に割り当てられたオブジェクトのサイズを予測することができる場合（@Keridoが示唆したように）

あなたはおそらくメモリの直線的に割り当てられたチャンクと独自のカスタムアロケータで行くのがベストでしょう。そのために、私が最も効率的な方法は、割り当て内の位置のためにゼロとスワップすること、および再パーティションと配列（配分との間のデッドスペースを残す）を圧縮する心配はないだろうと追加することになりますので、インデックスの更新とインデックスに対処する必要はありませんメンテナンスます。

あなたは、事前にあなたのオブジェクトを分割することができた場合（つまり、あなたは非固定サイズの要素を持って知っているが、簡単にグループ）は、各バケットにバケットとメモリの事前割り当てチャンクにそれらを分割し、適切なバケツにアイテムを交換。あなたのオブジェクトが管理するのが難しい得ることができ、その寿命にわたってサイズを変更することができますので、もしこのアプローチは慎重に検討します。

Answer 3

あなたは配列の最大サイズを知っている場合は、

は、カスタムアロケータを使用することができます。あなたはアロケータクラスを自分で記述する必要があります。それは何をすべきことは、一度にメモリの大きなチャンクを割り当て、リンクリストにキャストです。オブジェクトのインスタンスを作成する必要があるたびに、リストから尾を削除します。オブジェクトが解放される必要があるたびに、あなたがリストにエントリを追加します。

編集：ここビャーネ・ストロヴストルップさんの C ++プログラミング言語、の第3版からのサンプルがあります：

class Pool
{
private:
  struct Link
    { Link * next; };

  struct Chunk
  {
    enum {size = 8*1024-16};

    Chunk * next;
    char mem[size];
  };

private:
  Chunk * chunks;
  const unsigned int esize;
  Link * head;

private:
  Pool (const Pool &) { }      // copy protection
  void operator = (Pool &) { } // copy protection

public:
  // sz is the size of elements
  Pool(unsigned int sz)
    : esize(sz < sizeof(Link*) ? sizeof(Link*) : sz),
      head(0), chunks(0)
    { }

  ~Pool()
  {
    Chunk * n = chunks;

    while(n)
    {
      Chunk * p = n;
      n = n->next;
      delete p;
    }
  }


public:

  // allocate one element
  void * alloc()
  {
    if(head == 0)
      grow();

    Link * p = head;
    head = p->next;

    return p;
  }

  // put an element back into the pool
  void free(void * b)
  {
    Link * p = static_cast<Link*>(b);
    p->next = head; //put b back as first element
    head = p;
  }

private:
  // make pool larger
  void grow()
  {
    Chunk* n = new Chunk;
    n->next = chunks;
    chunks = n;

    const int nelem = Chunk::size / esize;
    char * start = n->mem;
    char * last = &start [ (nelem - 1) * esize ];

    for(char * p = start; p < last; p += esize) // assume sizeof(Link) <= esize
      reinterpret_cast<Link>(p)->next = reinterpret_cast<Link *>(p + esize);

    reinterpret_cast<Link *>(last)->next = 0;
    head = reinterpret_cast<Link *>(start);
  }
};