7

我在玩某些缓存算法，这有点挑战性。基本上，它需要分配许多小对象（双数组，1 到 256 个元素），对象可通过映射值访问，map[key] = array. 初始化数组的时间可能相当大，一般超过 1 万个 cpu 周期。

很多我的意思是总共大约千兆字节。可能需要根据需要弹出/推送对象，通常在随机位置，一次一个对象。对象的生命周期通常很长，几分钟或更长，但是，在程序执行期间，对象可能会多次分配/释放。

什么是避免内存碎片的好策略，同时仍然保持合理的分配释放速度？

我正在使用 C++，所以我可以使用 new 和 malloc。谢谢。

我知道网站上有一个类似的问题，Efficiently allocating many short-lived small objects，有些不同，线程安全对我来说不是直接问题。

我的开发平台是Intel Xeon，linux操作系统。理想情况下，我也想在 PPC linux 上工作，但这对我来说不是最重要的。

4

3 回答 3

6

创建一个时隙分配器：

分配器由许多内存页创建，每个内存页大小相同（512k、256k，大小应根据您的使用进行调整）。

当一个对象第一次向这个分配器请求内存时，它会分配一个页面。分配页面包括将其从空闲列表中删除（不搜索，所有页面大小相同）并设置将在此页面上分配的对象的大小。通常，这个大小是通过获取请求的大小并将其四舍五入到最接近的 2 的幂来计算的。相同大小的后续分配只需要一点指针数学并增加页面上的对象数量。

可以防止碎片，因为插槽的大小都相同，并且可以在后续分配中重新填充。效率得以维持（在某些情况下有所提高），因为每次分配都没有 memheader（当分配很小时，这会产生很大的不同，一旦分配变大，这个分配器就会开始浪费近 50% 的可用内存）。

分配和解除分配都可以在恒定时间内执行（无需在空闲列表中搜索正确的插槽）。关于解除分配的唯一棘手的部分是，您通常不希望在分配之前有一个 memheader，因此您必须自己找出页面和页面中的索引……今天是星期六，我还没有喝咖啡，所以我对此没有任何好的建议，不过，从解除分配的地址中找出来很容易。

编辑：这个答案有点啰嗦。像往常一样，提升有你的支持。

于 2010-03-13T19:09:06.810 回答
1

如果您可以提前预测分配对象的大小，您可能最好使用线性分配的内存块和您自己的自定义分配器（如@Kerido 建议的那样）。为此，我要补充一点，最有效的方法是将分配中的位置归零并交换位置，而不必担心重新分区和压缩数组（在分配之间留下死空间），因此您不必处理索引更新和索引维护。

如果您可以提前对对象进行分区（即您知道您有非固定大小的元素，但很容易分组）将它们划分为存储桶并将内存块预分配到每个存储桶中，并将项目交换到适当的存储桶中。如果您的对象可以在其生命周期内改变大小，这可能会变得难以管理，那么请仔细考虑这种方法。

于 2010-03-13T18:57:31.803 回答
0

如果您确实知道数组的最大大小，则可以使用自定义分配器。您必须自己编写分配器类。它应该做的是一次分配一大块内存并将其转换为链表。每次需要创建对象实例时，从列表中删除尾部。每次需要释放对象时，都向列表中添加一个条目。

编辑：这是 Bjarne Stroustrup 的The C++ Programming Language, 3rd Edition 中的一个示例：

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 回答