for 循环 - 优化 C 语言中康威生命博弈的邻居计数函数

Question

在优化Conway's Game of Life实现中返回单元格邻居数量的函数时遇到一些麻烦。我正在努力学习C语言，以便在编程方面做得更好。我不是很擅长识别潜在的优化，我花了很多时间在网上阅读各种方法，但我还没有真正点击。

具体来说，我试图找出如何以最有效的方式展开这个嵌套的for循环，但每次我尝试，我只是使运行时间更长。我包括了这个函数，我认为不需要任何其他的上下文。谢谢你给的任何建议!

以下是countNeighbors()函数的代码:

static int countNeighbors(board b, int x, int y)
{
   int n = 0;
   int x_left = max(0, x-1);
   int x_right = min(HEIGHT, x+2);
   int y_left = max(0, y-1);
   int y_right = min(WIDTH, y+2);
   int xx, yy;
   for (xx = x_left; xx < x_right; ++xx) {
       for (yy = y_left; yy < y_right; ++yy) {
           n += b[xx][yy];
       }
   }
   return n - b[x][y];
}

Answer 1

将board声明为b[WIDTH][HEIGHT]而不是声明为b[WIDTH + 2][HEIGHT + 2]。这提供了一个额外的空白，它将为零，但它可以防止索引越界。所以，不是:

 x x
 x x

我们将有:

 0 0 0 0 
 0 x x 0
 0 x x 0
 0 0 0 0 

x表示已使用的单元格，0将未使用。

典型的权衡:一点内存换取速度。

由于我们不需要调用min和max函数(if语句对性能不利)。

最后，我将这样写你的函数:

int countNeighborsFast(board b, int x, int y)
{
    int n = 0;
    n += b[x-1][y-1];
    n += b[x][y-1];
    n += b[x+1][y-1];
    n += b[x-1][y];
    n += b[x+1][y];
    n += b[x-1][y+1];
    n += b[x][y+1];
    n += b[x+1][y+1];
    return n;
}

基准(更新)

完整的工作源代码。

感谢Jongware的评论，我添加了线性化(将数组的维度从2减少到1)并将int更改为char。

我还使主循环线性化，并直接计算返回的和，没有中间的n变量。

二维数组为10002 × 10002，一维数组为100040004个元素。

我拥有的CPU是2.30 GHz的奔腾双核T4500，这里有更多细节(cat /prof/cpuinfo的输出)。

默认优化级别O0:

Original: 15.50s
Mine: 10.13s
Linear: 2.51s
LinearAndChars: 2.48s
LinearAndCharsAndLinearLoop: 2.32s
LinearAndCharsAndLinearLoopAndSum: 1.53s

这比原来的版本快了大约10倍。

O2的结果:

Original: 6.42s
Mine: 4.17s
Linear: 0.55s
LinearAndChars: 0.53s
LinearAndCharsAndLinearLoop: 0.42s
LinearAndCharsAndLinearLoopAndSum: 0.44s

快了15倍。

On O3:

Original: 10.44s
Mine: 1.47s
Linear: 0.26s
LinearAndChars: 0.26s
LinearAndCharsAndLinearLoop: 0.25s
LinearAndCharsAndLinearLoopAndSum: 0.24s

大约快了44倍。

最后一个版本，LinearAndCharsAndLinearLoopAndSum是:

typedef char board3[(HEIGHT + 2) * (WIDTH + 2)];
int i;
for (i = WIDTH + 3; i <= (WIDTH + 2) * (HEIGHT + 1) - 2; i++)
    countNeighborsLinearAndCharsAndLinearLoopAndSum(b3, i);
int countNeighborsLinearAndCharsAndLinearLoopAndSum(board3 b, int pos)
{
    return
    b[pos - 1 - (WIDTH + 2)] +
    b[pos     - (WIDTH + 2)] +
    b[pos + 1 - (WIDTH + 2)] +
    b[pos - 1] +
    b[pos + 1] +
    b[pos - 1 + (WIDTH + 2)] +
    b[pos     + (WIDTH + 2)] +
    b[pos + 1 + (WIDTH + 2)];
}

将1 + (WIDTH + 2)更改为WIDTH + 3不会有帮助，因为编译器无论如何都会照顾它(即使在O0优化级别)。