c++ - 排队对象的分配策略

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++ 下)，指针将与对象本身一样大!因此，即使您有一个批量分配器，您仍然要付出这个代价。
• 一般的内存分配器不仅在时间上很昂贵，它还会有每个对象的开销，在这种情况下会使对象本身相形见绌(不适用于批量分配器)。

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

--- 编辑 ---

您可以像这样将元素推送到 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 条机器指令)。

专用 block 分配器会快得多，但您仍然有内存延迟问题:将所有内容很好地放在一起可以保证实现更好的缓存局部性，并且比在队列之间反复“跳转”更适合 CPU 的预取逻辑和实际对象通过取消引用指针。