大型3D阵列的性能:连续1D存储与T*

Question

我想知道是否有人能建议存储大型(例如2000 x 2000 x 2000) 3D阵列进行有限差分离散计算。在现代的CPU体系结构上，连续存储float*是否提供了比float***更好的性能？下面是对整个数组进行计算的一个简化示例：

for i ...
    for j ...
        for k ...
            u[i][j][k] += v[i][j][k+1] + v[i][j][k-1]
                + v[i][j+1][k] + v[i][j-1][k] + v[i+1][j][k] + v[i-1][j][k];

Vs

    u[i * iStride + j * jStride + k] += ...

PS:考虑到问题的大小，存储T***是一个非常小的开销。访问不是随机的。此外，我做循环阻塞，以尽量减少缓存丢失。我只是想知道，在T***情况下，与一维数组中的索引计算和单个去引用相比，三重去引用是如何的。

Answer 1

这些不是苹果对苹果的比较:一个平面数组就是一个平面数组，你的代码根据一个矩形三维数组线性化的逻辑将其划分为若干段。您可以使用单个取消引用来访问数组的一个元素，外加少量的数学操作。

另一方面，float***允许您保留一个数组或数组的“锯齿”数组，因此可以在这种数组中表示的结构要灵活得多。当然，您需要支付这种灵活性，需要额外的CPU周期来取消引用指向指针的指针，然后是指向指针的指针，最后是指针(代码中的三对方括号)。

当然，如果您按真正随机的顺序访问float***的各个元素，那么访问它们的速度会稍微慢一些。但是，如果顺序不是随机的，则所看到的差异可能很小，因为指针的值将被缓存。

float***还需要更多的内存，因为您需要分配两个额外级别的指针。

Answer 2

简单的答案是:基准测试。如果结果不确定，那就意味着这不重要。做那些使您的代码最易读的事情。

正如@dasblinkenlight所指出的，这些结构也不是等价的，因为T*可以被锯齿状排列。

然而，在最基本的层面上，这可以归结为算术和内存访问操作。

对于您的一维数组，正如您已经(几乎)所写的那样，计算如下：

 ptr = u + (i * iStride) + (j * jStride) + k
 read *ptr

与T*

 ptr = u + i
 x = read ptr
 ptr = x + j
 y = read ptr
 ptr = y + k
 read ptr

所以你用两个乘法来交换两个内存访问。

Answer 3

在人们对性能非常敏感的计算机go中，每个人都使用T361而不是T19 (*)。这一决定的基础是基准，无论是孤立的，还是整个项目。(很多年前，每个人都可能做过这些基准测试，而且再也没有在最新的硬件上做过，但我的预感是，一个单一的一维数组还会更好。)

然而，与之相比，您的数组是巨大的。由于每一种情况所涉及的代码都很容易编写，所以我肯定会尝试这两种方法和基准测试。

*：旁白:在大多数程序中，我认为这实际上是T21与t441之间的冲突，因为在所有的程序中都增加了一个额外的行来加速板边检测。