分配/释放大量小物体的策略

我正在尝试使用某些缓存算法，这在某种程度上具有挑战性。基本上，它需要分配很多小对象（双数组，1到256个元素），对象可以通过映射值map[key] = array访问。初始化数组的时间可能相当长，一般超过10万cpu周期。分配/释放大量小物体的策略

我的意思是总计大约是千兆字节。物体可能需要根据需要弹出/推动，通常在随机的地方，一次一个物体。一个对象的生命周期通常很长，几分钟或更长，但是，对象在编程期间可能会多次分配/释放。

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

我使用的是C++，所以我可以使用new和malloc。谢谢。

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

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

来源

2010-03-13 Anycorn

什么是平台？我的意思是，操作系统，CPU架构，编译器等，这些可能会大大影响答案。 – 2010-03-13 18:51:10

创建开槽分配：

分配器与内存的许多页，每一页大小相等（512K，256K，规模应该调整为您的使用）的创建。

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

由于插槽大小完全相同，可以在后续分配时重新填充，因此可以防止碎片。效率得以保持（在某些情况下得到改进），因为每个分配都没有memheader（当分配量很小时，一旦分配变大，分配器开始浪费几乎50％的可用内存，这会造成很大的差异）。

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

编辑：这个答案有点啰嗦。像往常一样boost有你的背影。

来源

2010-03-13 19:09:06

而Boost在池库中实现了这一点。 – GManNickG 2010-03-13 19:21:07

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

编辑：这里是从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); 
    } 
};

来源

2010-03-13 18:51:35 Kerido

这个答案有点含糊，但听起来像是告诉他要重新实现已经在OS内存分配器中的“自由列表”。除非他的名单实际上是一个更智能的数据结构，否则他仍然会遇到主要的内存碎片减速。 – 2010-03-13 18:55:27

@ALevy：这不能分片，因为所有的块都是相同的大小。 – 2010-03-13 19:37:33

@ALevy：因为我建议分配单一大小的元素，所以不会出现碎片。大小应该选择足以存储@aaa提到的数组。关于速度，它比调用OS内置分配例程要快。如果Chunks是一个内存页面的大小并且用@DanO提到的页面分配例程分配的话，它可以更快。关于“模糊性”，太糟糕了，你已经低估了。 – Kerido 2010-03-13 19:44:55

如果你能预测的分配对象的大小提前时间，你可能会是最好的去与一个线性分配的内存块和您自己的自定义分配器（如@Kerido建议）。为此，我想补充一点，最有效的方法是在分配内置零和交换位置，而不用担心重新分区和压缩数组（在分配之间留下死区），因此您不必处理索引更新和索引保养。

如果您可以提前对对象进行分区（即，您知道有非固定大小的元素，但是组很容易）将它们分成桶，并将大块内存预先分配到每个桶中，并将这些项交换为适当的桶。如果您的对象可以在其整个生命周期中更改大小，并且可能会非常棘手，那么请仔细考虑此方法。

来源

2010-03-13 18:57:31 GrayWizardx

桶的想法听起来不错 – Anycorn 2010-03-13 18:59:13

分配/释放大量小物体的策略

回答

相关问题