提高一个非常简单但经常使用的函数(计算晶格中原子的近邻)的效率。

Question

我在这里比较新，但我想如果有人能帮忙的话，那就是这里的某个人了。

我们用原子点阵模拟做了一个非常大规模的程序，这个非常简单的函数被多次使用，它大大地减缓了这个过程。

它只是检查周期格中一个位置的8个邻居(我们在BCC中)的类型(称为格的三维结构向量的一部分，包括一个整数t表示原子的类型)。

我意识到这可能是不可能简化它更多，但如果有人有任何灵感，请告诉我，谢谢！

//calculates number of neighbours that aren't vacancies
int neighbour(int i, int j, int k)
{
//cout << "neighbour" << endl;
int n = 0;

if (V != lattice[(i+1) & (LATTICE_SIZE-1)][(j+1) & (LATTICE_SIZE-1)][k].t)
{
    n++;
}
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][(j-1) & (LATTICE_SIZE-1)][k].t)
{
    n++;
}
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][j][k+1].t)
{
    n++;
}
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][j][k-1].t)
{
    n++;
}
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][(j+1) & (LATTICE_SIZE-1)][k].t)
{
    n++;
}
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][(j-1) & (LATTICE_SIZE-1)][k].t)
{
    n++;
}
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][j][k+1].t)
{
    n++;
}
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][j][k-1].t)
{
    n++;
}

return n;
}

Answer 1

首先，格形包装解决方案((i+1) & (LATTICE_SIZE-1))只有在LATTICE_SIZE为2次方时才能正常工作，例如LATTICE_SIZE == 100和i == 99，(i+1)&(LATTICE_SIZE-1) == 100 & 99 == 0x64 & 0x63 == 0x60 == 96，期望值为0。

有鉴于此，我建议您检查多维数组索引与编译器和平台的工作方式。在LATTICE_SIZE等于2的情况下，可以有效地用左移代替nth指数的乘法，这在某些体系结构上是非常快的。VC++11自动进行此优化，但是我不知道您的编译器是什么，也不能假设它也是这样做的。

考虑到的另一个改进是尽量避免重新计算高阶索引中的偏移量。优化器可以帮助实现这一目标，如果我们将相同的高阶指数组合在一起。我之所以做到这一点，是因为我对以下几种表达方式进行了分类：

if (V != lattice[(i+1) & (LATTICE_SIZE-1)][(j+1) & (LATTICE_SIZE-1)][k  ].t)  n++;
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][j                       ][k+1].t)  n++;
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][j                       ][k-1].t)  n++;
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][(j-1) & (LATTICE_SIZE-1)][k  ].t)  n++;
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][(j+1) & (LATTICE_SIZE-1)][k  ].t)  n++;
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][j                       ][k+1].t)  n++;
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][j                       ][k-1].t)  n++;
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][(j-1) & (LATTICE_SIZE-1)][k  ].t)  n++;

我的优化器已经利用了这一点，结果的加速比只有4%。然而，对于您的系统，它可能归结为一个不同的价值。

而且，大部分优化实际上取决于函数的使用。例如，我编写了这样一个简单的测试：

volatile int n = 0;
for ( int i = 0; i != LATTICE_SIZE; ++i )
    for ( int j = 0; j != LATTICE_SIZE; ++j )
        for ( int k = 0; k != LATTICE_SIZE; ++k )
            n += neighbour ( i, j, k );

我的测量显示，每个邻居的电话大约有12 ns。在那之后，我注意到邻居们只有两架高级飞机。我重构了这个函数，以便向优化器提供更明确的提示：

int neighbour_in_plane ( elem_t l[LATTICE_SIZE][LATTICE_SIZE], int j, int k )
{
    int n = 0;
    if (V != l[(j-1) & (LATTICE_SIZE-1)][k  ].t)  n++;
    if (V != l[j                       ][k-1].t)  n++;
    if (V != l[j                       ][k+1].t)  n++;
    if (V != l[(j+1) & (LATTICE_SIZE-1)][k  ].t)  n++;
    return n;
}

//calculates number of neighbours that aren't vacancies
int neighbour(int i, int j, int k)
{
    return neighbour_in_plane ( lattice[(i-1) & (LATTICE_SIZE-1)], i, j ) +
           neighbour_in_plane ( lattice[(i+1) & (LATTICE_SIZE-1)], i, j );
}

令人惊讶的是，每次通话只有4 ns。我检查了编译器输出，发现这一次它将两个函数内联到调用循环中，并为我做了许多优化。E.q.它有效地将两个内部循环移动到neighbour_in_plane()函数中，从而避免了lattice[(i-+1) & (LATTICE_SIZE-1)]表达式的数千次重新计算。

底线是，您必须在您的code+compiler+platform环境中使用这个函数，才能使它发挥出最大的速度。

Answer 2

我猜想，LATTICE_SIZE是2的一种力量，否则，& (LATTICE_SIZE-1)不会按你的意愿来做概括。此外，我注意到，"k“维没有包装。是故意的吗？

然后，在C++中，代码的执行时间将在很大程度上取决于“晶格”的“数组”类型，以及比较V != latticeik.t的成本和价格。通常，嵌套的std：：boost::multi_array或latticeLATTICE_SIZELATTICE_SIZE可能比传统的"C“数组:点阵latticeLATTICE_SIZELATTICE_SIZE慢得多。

如果您能够在所有三个维度(基本上是一个空的表面)中保留一个空的边框，那么这可能有助于提高效率，因为您可以省略所有与& (LATTICE_SIZE-1)包在一起的内容。如果您有一个编译时常数LATTICE_SIZE，那么没有这些包装的精确索引的计算要快得多，因为编译器可以确定各种数组访问之间的常量偏移量。

最后，但同样重要的是，我建议您查看为该函数生成的汇编程序输出(只需使用-S开关编译并查看生成的.s文件)。如果编译器将" If“转换为围绕"n++”(被转换为inc %reg)的条件跳转，那么这就为进一步优化留出了空间，因为条件跳转往往会被CPU错误地预测，然后会导致大量额外的时钟周期。如果使用cmov，或者通过条件集指令(如setc或setg)将" If“的结果转换为寄存器，则代码可能更接近最佳。为了帮助编译器有效地使用Intel x86上的setxx操作，您可以尝试将结果计数"n“转换为”无符号字符“。