生命游戏中的循环和复杂性

Question

在试图优化C代码的性能时（4门滑翔机枪，在游戏人生中每个角落都有一门），我不得不在两种情况下做出选择。

int M = (int) DIM / 2 + 1;
for (int y = 1; y < M; y += TILE_SIZE)
  for (int x = 1; x < M; x += TILE_SIZE)
  {
    change |= do_tile(x, y, TILE_SIZE, TILE_SIZE, omp_get_thread_num());
    change |= do_tile(DIM - x, y, TILE_SIZE, TILE_SIZE, omp_get_thread_num());
    change |= do_tile(x, DIM - y, TILE_SIZE, TILE_SIZE, omp_get_thread_num());
    change |= do_tile(DIM - x, DIM - y, TILE_SIZE, TILE_SIZE, omp_get_thread_num());
  }

和

for (int y = 1; y < DIM - 1; y += TILE_SIZE)
  for (int x = 1; x < DIM - 1; x += TILE_SIZE)
    change |= do_tile(x, y, TILE_SIZE, TILE_SIZE, omp_get_thread_num());

如果我们用复杂度的方式来思考，就会得到它们的时间复杂度都是一样的。

(DIM2) * (DIM2) * 4 = DIM * DIM

但当我执行它们时，第一个总是在不到600ms的时间内完成，而第二个则在650ms左右完成。这怎么可能呢？有没有什么更好的优化方法来解决这个游戏的配置？

Answer 1

正如Oppen上面所说，我给出的复杂度只是一个估计 ( O(DIM * DIM) ) 。而且由于处理器不喜欢在循环里面的跳转，所以迭代次数少意味着时间少。