如何最好地通知我的编译器如何处理嵌套循环，在C中对大型数组进行复杂的索引以获得最佳性能？

Question

我正在研究一个科学的优化问题，在我们可能考虑的3+1维空间中，额外的维是由程序中的一个张量描述的，这个张量由系数或角度分割，以及仰角和方位坐标来表示。在典型的情况下，当涉及75 x 75 x 75 x 16和系数表示时，我可能需要有效地处理维度的多个数组(双)，以及与75 x 75 x 75 x 16 x 16一样大的可能的中间数组。我必须做一些实际的，一些复杂的算术和三角学，合理的效率，做一些事情，如过采样，投影，从和进入二维，和数值微分。我可能会在将来做一个更方便的算法，但目前，这就是我的方法。

为了完成这些工作，我编写了一个大约1500行的C实现，在适用的情况下，我使用MKL函数的组合，并在其他情况下使用嵌套循环。这里的问题是，循环必须处理大型数组，在具有复杂索引的嵌套循环中，这些数组在编译时是未知的。因此，当我试图使用perf报告分析性能时，我得到的是一些操作的明显随机(但实际上是一致的)瓶颈(例如，以一些稍微复杂的方式将上面两个维度的向量相乘和求和)，但对于类似的操作没有瓶颈。这似乎与各种与存储相关的错误相关，这些错误告诉我，编译后的代码并没有针对如此大的数组进行真正的优化。作为参考，我目前在AMD Ryzen 3900上进行计算，每个线程有一个物理内核；该算法基本上可以在“顶层”级别上并行(所有重要的算法都是由每个内核单独完成的)。

所以，从本质上讲，问题是，我的绩效改进策略应该是什么？我有两个基本想法:一是用我通过计划的主脚本在运行时设置和编译的宏替换维度变量。就我而言，在实现方面，这不是一个问题。通过这种方式，编译器至少可以以数字的方式获得有关大小的信息，尽管我不知道编译器将使用多少此类信息。这里的任何投入都是非常感谢的。

我能想到的第二种方法基本上是，如果我有其他方法告诉编译器，“嘿，这是一个很大的数字，所以这个数组会很大，相应地处理”，这样它就可以考虑到这一点了？目前我正在使用GCC，但我愿意使用其他编译器。

或者任何其他大型数组的通用缓解策略也将受到欢迎。

插入泛型参数的代码片段的示例如下所示

for(int j = 0;j<ALL_3D_SPACE;j++)
{
    for (int k = 0; k< DIM_4_1; k++)
    {
        for (int l = 0; l< DIM_4_2; l++)
        {
            REDUCED_SUM[j*DIM_4_1 +k] += EXPANDED_SUM[j*DIM_4_2*DIM_4_1+k*DIM_4_2+l]*COEFFS[j*DIM_4_2+l];
        }   
    }
}   

各种数据结构都是以标准指针-malloc方式声明的，例如，按照上面的模拟示例：

double * EXPANDED_SUM, *COEFFS, REDUCED_SUM;
EXPANDED_SUM = (double*) malloc(sizeof(double)*ALL_3D_SPACE*DIM_4_2*DIM_4_1);
COEFFS = (double*) malloc(sizeof(double)*ALL_3D_SPACE*DIM_4_2);
REDUCED_SUM = (double*) malloc(sizeof(double)*ALL_3D_SPACE*DIM_4_1);

我尽可能多地重用结构，并在不再需要时释放它们。

预期用例让用户输入一组大约大小为nX*nY*DIM_4_1、维度和其他参数的~100 2D投影，其中ALL_3D_SPACE = nX*nY*nZ和DIM_4_1为10-20级，而nX、nY和nZ都在50-100左右。预期的输出将是(3+1)D的大小为ALL_3D_SPACE*(DIM_4_2+2)的重建，其中DIM_4_2为5-10级。目前，输入和输出都作为文本文件处理。请注意，任何与输入的比较都是代码的一个非常小的部分，而且其中绝大部分都是沿着上述路线进行的算术/数值微分。处理所有处理的实际核心误差函数将投影和当前输出估计作为输入，并在需要时输出误差以及梯度，以便更好地估计输出，以供优化例程使用。

Answer 1

如果您使用这么大的数组，我建议将它们存储到堆或全局变量中。堆叠会有这样的尺寸爆炸