4
4

2 回答 2

5

每个单独的向量连续存储内容，包括指向向量的指针向量，但是您对 new 进行的连续调用的地址不是连续的，并且向量在内部创建其缓冲区的调用也不是连续的。所以，如果你有一个巨大的指向小向量的指针向量，你的内存实际上是不连续的，你不会得到好的缓存命中。如果你有一个单元素向量到一个巨大的向量，那么内存是连续的，缓存会很好地工作。

从视觉上看，快速/连续布局是：

*a--[0]
.    |
.   [0][1][2][3][4][5][...]

您的缓慢选择是：

.        [0]     [0]
.         \       /
*a--[0][1][2][3][4][5][...]
.    |   \    |     \
.   [0]   \[0][0]   [0]

可以使用例如在堆栈上创建多维数组

int x[10][20];

在这种情况下，内存将是连续的，每个 x[0]、x[1] 等中的内存都是连续的。（所以 x[0][0] 在 x[0][1] 之前，而不是在 x[1][0] 之前。）

为了在堆上有效地拥有一个连续的多维数组，您应该使用预期维度的乘积新建一个向量，然后编写一个包装类，方便地将维度相乘以找到特定元素。

于 2013-06-07T02:58:13.353 回答
3

由于数据缓存，计算时间不同。了解引用的位置后，当您读取内存中的某个位置时，CPU 从相邻地址加载数据。它预测下一次读取将来自您刚刚读取的地址前几个字节的位置。

当数组被分配为[1][N]时，元素确实是连续存储的，所以 CPU 的预测几乎总是成真。您需要的数据几乎总是可以从 CPU 的缓存中获得，它比主存快几倍。CPU 在执行计算时继续加载您刚刚读取的位置之前的位置，因此加载新数据并累加数字继续并行进行。

当您切换尺寸时，您相加的数字不再位于连续的位置。这是因为连续调用new不会在连续的内存区域中分配数据：内存管理库为“簿记”目的添加了几个字节，并且它总是分配一些最小大小的内存块，通常大于double. 当您请求小于最小值的块时，分配的区域将被填充。结果，double在最佳情况下，您的 s 最终可能相隔最多 20 个字节* - 足以抵消从相邻内存位置提前读取的影响。这就是为什么 CPU 在从不同位置加载数据时被迫等待的原因。这会减慢计算数倍。

*在最坏的情况下，值可以任意放置，具体取决于在运行代码之前执行的分配和释放。

于 2013-06-07T02:59:53.540 回答