优化Conway在C中的生命游戏的邻居计数功能

Question

在Conway的生命游戏实现中优化返回单元格邻居数量的函数时遇到一些麻烦.我正在努力学习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

而不是声明董事会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变量.

2D阵列为10002 x 10002,1D具有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倍.

上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优化级).