连续内存分配的好处

Question

就性能而言，为矩阵分配一个连续的内存块与分配多个不相邻的内存块相比有什么好处？例如，不要像这样编写代码：

char **matrix = malloc(sizeof(char *) * 50);
for(i = 0; i < 50; i++)
    matrix[i] = malloc(50);

如果我要写一个程序，给我50个不同的块，每个块有50个字节，还有一个包含50个指针的块。相比之下，如果我写：

char **matrix = malloc(sizeof(char *) * 50 + 50 * 50);
char *data = matrix + sizeof(char *) * 50;
for(i = 0; i < 50; i++) {
    matrix[i] = data;
    data += 50;
}

给我一个连续的数据块，有什么好处吗？避免缓存未命中是我唯一能想到的，即使这只针对小量数据（足够适应缓存），对吗？我在一个小应用程序上进行了测试，并注意到了一点速度提升，想知道原因。

- wolfPack88

---

尝试两种并测量？ - Kerrek SB

缓存行通常为64字节，因此超出此大小的缓存行为在很大程度上不受此技术的影响。（尽管在您的情况下，每个矩阵“行”仅为50字节，因此读取一行将同时将部分下一行拉入缓存。） - Oliver Charlesworth

你可以获得一些缓存性能（取决于你的硬件），同时也减少了堆碎片。这并不是一个非常显著的改进，但如果在整个大型应用程序中实现，可能会产生一定的影响。 - Hot Licks

当然，这也取决于您对该矩阵的访问模式。如果是随机访问，我预计几乎不会看到稳态性能差异。 - Oliver Charlesworth

@KerrekSB：我原本以为关于避免缓存未命中的评论已经很明显表明了我想知道为什么它更快。不过，如果您想要严谨一点，我可以编辑这个问题。 - wolfPack88

Answer 1

这很复杂 - 你需要进行测量。

在当前处理器上，使用中间指针而不是在二维数组中计算地址可能会导致损失，你的两个示例都使用了中间指针。

接下来，将所有内容放入L1高速缓存中可以大大提高性能。malloc() 函数最有可能按64字节的倍数舍入。180 x 180 = 32,400 字节可以适配到 L1 高速缓存，而单独的 mallocs 可能分配 180 x 192 = 34,560 字节，特别是如果你添加了另外 180 个指针，就可能无法适配。

一个连续的数组意味着你知道数据如何适配到高速缓存行，并且你知道在硬件上你将具有最少的页面表查找次数。但对于数百个 mallocs，就不保证能做到这点。

- gnasher729

---

使用中间指针而不是在二维数组中计算地址，在当前处理器上很可能会损失性能，你的两个示例都这样做了。不确定你的意思是什么。你是说我应该使用一维向量，并将2D矩阵访问为 matrix[i * rows + j] 吗？ - wolfPack88

@wolfPack88，这正是他的意思。您还可以将指向连续内存的指针转换为指向2D数组的指针（char (*)[50][50]）。使用C99 VLA，即使实际数组维度仅在运行时才知道，它也可以工作。 - Hristo Iliev

Answer 2

在Youtube上观看Scott Meyers的“CPU缓存及其重要性”演示。性能提升可以达到整个数量级。

https://www.youtube.com/watch?v=WDIkqP4JbkE

关于上面的讨论，中间指针参数早已经消失。编译器会优化它们。一个N维数组被分配为一个1D向量，总是如此。如果您使用std::vector，那么您可能会获得有序向前列表的等效形式，但对于原始数组，它们总是以一种平坦的方式分配为一个长连续条，并且多维访问归结为与1维访问相同的指针算术。

要访问array[i][j][k]（假设{A,B,C}的宽度，高度，深度），您需要将i *（B*C）+（j*C）+ k添加到数组前面的地址中。无论如何，在1D表示中，您都必须手动执行此数学运算。

- patrickjp93