排队对象的分配策略

Question

我有一个类如下：

typedef struct grid_cell_type {
int x;
int y;
grid_cell_type(int x0, int y0){
    x=x0;
    y=y0;
}

}网格细胞；

我会把大约1亿个这样的东西排成一排。

现在，情况如下：

my_queue.push(new grid_cell(x0,y0));

所有这些对象的单个分段分配似乎可能不如一些大规模分配那么快。

有没有关于在这里追求最佳战略的想法？

Answer 1

这些都是小型且自包含的对象-将它们直接放入队列中，而不是放入指针。

• 事实上，在64位系统上，假设int是32位的（例如，在Visual C++下是32位），指针将与对象本身一样大！因此，即使你有一个批量分配器，你仍然要付出这个代价
• 通用内存分配器不仅在时间上很昂贵，而且还会有每个对象的开销，在这种情况下，这将使对象本身相形见绌（不适用于大容量分配器）

虽然可以设计一个相当有效的"批量"分配方案，但我认为回避这个问题并完全避免单个对象分配更简单。

---编辑---

您可以将元素推送到std::queue，如下所示：

struct grid_cell {
    grid_cell(int x0, int y0) {
        x=x0;
        y=y0;
    }
    int x;
    int y;
};
// ...
std::queue<grid_cell> q;
q.push(grid_cell(0, 0));
q.push(grid_cell(0, 1));
q.push(grid_cell(0, 2));
q.push(grid_cell(1, 0));
q.push(grid_cell(1, 1));
q.push(grid_cell(1, 2));

对于std::priority_queue，您需要决定如何排序元素。

---编辑2-

@Richard你的密码完全不同。

• 对于每个push，您的代码将分配一个新的动态内存块，在其中构造对象（即分配x和y），然后将指向该内存块的指针推送到队列
• 我的代码直接在queue本身预先分配的较大内存块中的"插槽"中构造对象。正如你已经指出的，很少有大额拨款比许多小的都要好

您的代码是：

1. 容易发生内存泄漏
2. 你为指针支付额外的存储空间
3. 容易出现内存碎片
4. 正如我已经提到的，每个对象都有开销

一个专门的大容量分配器可以删除最后两个问题，但为什么不全部删除呢？

---编辑3-

至于速度，一般的动态内存分配是非常昂贵的（最好的分配器大约有40-50条机器指令）。

专用的块分配器会快得多，但仍然存在内存延迟问题：与通过取消引用指针在队列和实际对象之间重复"跳跃"相比，保证所有东西都能很好地组合在一起，可以实现更好的缓存位置，更适合CPU的预取逻辑。

Answer 2

您可以对它们进行一个大数组并从中进行分配。

int allocation_index = 0;
grid_cell_type* cells = new grid_cell_type[100*1000*100];
my_queue.push(&cells[allocation_index++]);

这样你就可以避免1亿条小新闻的开销。清理就和delete [] cells;一样简单。

编辑：在这种特殊情况下，Branko所说的可能是你最好的选择。假设你使用的是std::queue，它会自动分配你需要的内存。我的建议更适合较大的物体。