优化3D循环(C++)

Question

我正在使用C++编写多重网格解算器,现在我正在尝试提高串行性能.最耗时的部分是更平滑,在我的例子中是一个连续的过度放松求解器.这看起来如下(我希望它非常自我解释):

int idx; 
int strideY = stride_[level][0];
int strideZ = stride_[level][1];
for(int i = 0; i < steps; ++i) {

    for(int z = 1; z <= innerGridpoints_[level][2]; ++z) {
        for(int y = 1; y <= innerGridpoints_[level][1]; ++y) {
            idx = getIndexInner(level, 1,y,z);
            for(int x = 1; x <= innerGridpoints_[level][0]; ++x, ++idx) {
                grid[idx] = (1. - omega)  * grid[idx] + omega * 1./6. * (grid[idx+1] + grid[idx-1] +
                                    grid[idx + strideY]  + grid[idx - strideY] + 
                                    grid[idx + strideZ]  + grid[idx - strideZ] - 
                                    spacing_[level] * spacing_[level] * rhs[idx]);
            }
        }
    }
}

我已经做了一些优化:循环定位使得内部循环给出最多的本地条目(即相邻元素沿x维度),以及idx的预先计算(即使这是一个内联函数,它节省了很多时间这样).我也试过阻塞,即不迭代整个网格,但只是在小块上增加局部性,但这没有任何影响.我的最后一个想法是尝试一些循环展开,但实际上我不希望从那里获得重大改进.我在想,也许对内存访问有一些可能的改进.欢迎任何tipps :)

仅供参考:网格大小将从非常小到255x255x255不等.此外,网格在每个维度中都有一些边界,由少量行组成,即迭代不在整个网格上.

Answer 1

一个好的优化编译器无论如何都会为你做大部分简单的事情,因此要始终衡量你所做的改变是否真正改善了事情.并且,检查(并学习理解)生成的汇编代码,以查看编译器实际执行的操作.

但是我会尝试一些事情,因为表达式很复杂,即使是优秀的优化者也需要一些帮助: -

首先,将内循环中不变的子表达式提升到周围的循环中.在你的例子中,显而易见的是 spacing_[level] * spacing_[level]和omega * 1./6.

另一个尝试是使idx成为指针而不是数组索引,并在循环中递增指针.

 int *idx = &grid[getIndexInner(level, 1,y,z)];  // assuming grid is array of ints.

然后你的表情看起来像这样

*idx = (1. - omega)  * *idx + omega * 1./6. * (idx[1] + idx[-1] +
                                idx[strideY]  + idx[- strideY] + // etc...

你的优化器(假设它已打开???)可能已经这样做了.但它值得一试.正如我所说,没有测量,这是一个毫无意义的练习.

而且,正如@AkiSuihkonen在上面的评论中提到"首先让它发挥作用".调试高度优化的代码要困难得多,因此在开始担心性能之前,请确保算法能够准确地执行算法.