分配/释放大量小对象的策略

Question

我正在研究一种缓存算法，有些具有挑战性。基本上，它需要分配大量的小对象（双数组，1到256个元素），对象可通过映射值访问，map[key] = array。初始化数组的时间可能相当长，通常超过10,000个CPU周期。

所谓“大量”，指的是总共约1GB。对象可能需要按需弹出/推入，通常在随机位置，每次一个对象。对象的生命周期通常很长，几分钟或更长时间，但在程序持续时间内，对象可能会多次分配/释放。

在仍然保持合理的分配/释放速度的同时，如何避免内存碎片化，这将是一个好策略？

我使用C++，因此可以使用new和malloc。 谢谢。

我知道网站上有类似的问题，例如Efficiently allocating many short-lived small objects，但有些不同，线程安全对我来说并不是立即的问题。

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

- Anycorn

---

平台是什么？我的意思是操作系统、CPU架构、编译器等等。这些因素可能会对答案产生重大影响。 - A. Levy

Answer 1

创建一个插槽分配器：

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

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

通过使用相同大小的插槽并可以在后续分配中重新填充这些插槽，可以防止碎片化。在某些情况下可以保持效率（甚至提高效率），因为没有每个分配的memheader（当分配变小时会有很大的区别，一旦分配变大，此分配器开始浪费近50％的可用内存）。

分配和释放都可以在常数时间内完成（不需要搜索正确插槽的空闲列表）。关于释放的唯一棘手部分是通常不希望在分配之前有memheader，因此必须自己找出页面和页面中的索引...今天是星期六，我还没喝咖啡，所以我没有关于如何做到这一点的好建议，不过从释放的地址中可以很容易地找出来。

编辑：这个答案有点冗长。像往常一样，boost为您提供了帮助。

- Dan O

---

Boost 在池库中实现了这一功能。 - GManNickG

Answer 2

如果您可以预测分配对象的大小，最好使用线性分配的内存块和自定义分配器（正如@Kerido建议的那样）。此外，最有效的方法是将分配内部的位置清零和交换，而不用担心重新分区和压缩数组（在分配之间保留无用空间），因此您无需处理索引更新和维护。

如果您可以提前分区对象（即知道您有非固定大小元素，但可以轻松地组合它们），则将它们分成桶，并为每个桶预分配内存块，并将项目交换到适当的桶中。如果您的对象可以在其生命周期内更改大小，则管理起来可能会变得棘手，因此请仔细考虑这种方法。

- GrayWizardx

Answer 3

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

编辑：这里是Bjarne Stroustrup的《C++程序设计语言》第三版的示例：

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

- Kerido

---

这个回答有点含糊，但听起来你是在告诉他重新实现已经存在于操作系统内存分配器中的“空闲列表”。除非他的列表实际上是一个更智能的数据结构，否则他仍然会遇到严重的内存碎片化减速问题。 - A. Levy

@ALevy：这不可能分段，因为所有块的大小都相同。 - Ben Voigt

@ALevy：不会出现碎片化，因为我建议分配单一大小的元素。大小应该足够存储@aaa提到的数组。关于速度，它比调用操作系统内置的分配例程更快。如果块的大小是内存页面的大小，并使用页面分配例程进行分配，则可以更快，正如@DanO所提到的那样。关于“模糊性”，很遗憾你已经投了反对票。 - Kerido