我有一个类如下:
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));
所有这些对象的单独分段分配似乎可能不如某些批量分配那么快。
关于最佳策略有什么想法吗?
最佳答案
这些是小而独立的对象 - 将它们直接放在队列中而不是放置指针。
- 事实上,在 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
本身预分配的较大内存块中的“槽”中构建对象。正如你已经指出的,很少有大的分配 比许多小的要好。
您的代码是:
- 容易发生内存泄漏
- 您为指针支付额外的存储空间,
- 容易出现内存碎片和
- 正如我已经提到的,存在针对每个对象的开销。
专门的批量分配器可以解决最后两个问题,但为什么不全部解决呢?
--- 编辑 3 ---
至于速度,一般的动态内存分配昂贵(最好的分配器大约需要 40-50 条机器指令)。
专用 block 分配器会快得多,但您仍然有内存延迟问题:将所有内容很好地放在一起可以保证实现更好的缓存局部性,并且比在队列之间反复“跳转”更适合 CPU 的预取逻辑和实际对象通过取消引用指针。
关于c++ - 排队对象的分配策略,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9542896/