7

私は特定のキャッシングアルゴリズムをいじっていますが、これはやや困難です。基本的に、マップされた値を介してアクセス可能なオブジェクトを使用して、多数の小さなオブジェクト（double配列、1〜256要素）を割り当てる必要がありますmap[key] = array。アレイを初期化するまでの時間は非常に長く、通常は1万CPUサイクルを超える場合があります。

ロットとは、合計で約ギガバイトを意味します。オブジェクトは、必要に応じて、通常はランダムな場所で、一度に1つのオブジェクトをポップ/プッシュする必要がある場合があります。オブジェクトの存続期間は一般に長く、数分以上ですが、プログラムの期間中にオブジェクトが数回割り当て/割り当て解除される場合があります。

妥当な割り当て解除速度を維持しながら、メモリの断片化を回避するための適切な戦略は何でしょうか。

私はC++を使用しているので、newとmallocを使用できます。ありがとう。

私はウェブサイトに同様の質問があることを知っています。多くの短命の小さなオブジェクトを効率的に割り当てることは多少異なります。スレッドセーフは私にとって当面の問題ではありません。

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

4

3 に答える 3

6

スロット付きアロケータを作成します。

アロケータは、それぞれが同じサイズ（512k、256k、使用に合わせてサイズを調整する必要があります）のメモリの多くのページで作成されます。

オブジェクトがこのアロケータにメモリを初めて要求すると、ページが割り当てられます。ページの割り当ては、フリーリストからページを削除し（検索なし、すべてのページが同じサイズ）、このページに割り当てられるオブジェクトのサイズを設定することで構成されます。通常、このサイズは、要求されたサイズを取得し、2の最も近い累乗に切り上げることによって計算されます。同じサイズの後続の割り当てには、少しのポインター計算とページ上のオブジェクトの数の増分が必要です。

スロットはすべて同じサイズであり、後続の割り当てで補充できるため、断片化は防止されます。割り当てごとにメンバーヘッダーがないため、効率が維持されます（場合によっては改善されます）（割り当てが小さい場合は大きな違いがあり、割り当てが大きくなると、このアロケータは使用可能なメモリのほぼ50％を浪費し始めます）。

割り当てと割り当て解除の両方を一定時間で実行できます（正しいスロットの空きリストを検索する必要はありません）。割り当て解除の唯一のトリッキーな部分は、通常、割り当ての前にmemheaderが必要ないことです。そのため、ページを把握し、ページ内のインデックスを自分で作成する必要があります...土曜日で、コーヒーを飲んでいないので、それを行うことについての良いアドバイスはありませんが、割り当て解除されたアドレスから理解するのは簡単です。

編集：この答えは少し長蛇の列です。いつものようにブーストはあなたの背中を持っています。

于 2010-03-13T19:09:06.810 に答える
1

割り当てられたオブジェクトのサイズを事前に予測できる場合は、線形に割り当てられたメモリのチャンクと独自のカスタムアロケータ（@Keridoが提案したように）を使用するのがおそらく最善でしょう。それに加えて、最も効率的な方法は、割り当て内の位置をゼロにしてスワップすることであり、配列の再パーティション化と圧縮（割り当て間にデッドスペースを残す）について心配する必要がないため、インデックスの更新とインデックスを処理する必要がないことを付け加えますメンテナンス。

オブジェクトを事前に分割できる場合（つまり、サイズが固定されていない要素があることはわかっているが、グループは簡単に）、オブジェクトをバケットに分割し、メモリのチャンクを各バケットに事前に割り当てて、アイテムを適切なバケットに交換します。オブジェクトのサイズが存続期間中に変更され、管理が難しくなる可能性がある場合は、このアプローチを慎重に検討してください。

于 2010-03-13T18:57:31.803 に答える
0

アレイの最大サイズがわかっている場合は、カスタムアロケータを使用できます。アロケータクラスは自分で作成する必要があります。それがすべきことは、一度に大量のメモリを割り当て、それをリンクリストにキャストすることです。オブジェクトインスタンスを作成する必要があるたびに、リストからテールを削除します。オブジェクトを解放する必要があるたびに、リストにエントリを追加します。

編集：これはBjarneStroustrupのTheC ++ Programming Language、第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);
  }
};
于 2010-03-13T18:51:35.920 に答える