3

有人问我一个问题：以下两种情况中哪一种最快：

情况 1：假设 int count = 0；

for (int i = 0; i < 10; i++)
{
    for (int j = 0; j < 5; j++)
    {
        count++;
    }
}

情况 2：假设 int count = 0；

for (int i = 0; i < 5; i++)
{
    for (int j = 0; j < 10; j++)
    {
        count++;
    }
}

在这两种情况下，计数的最终值都是 50。但我不确定哪个会更快？我认为 CASE II 更快，但不确定......

如果有人能对此有所了解，那就太好了。哪个更快，为什么？

4

5 回答 5

10

这是我能想到的唯一例子，你在哪里迭代哪个变量很重要

int array[n][m];
//fast
for (int i=0;i<n;i++)
{ for(int j=0;j<m;j++)
  { count+=array[i][j];
  }
}
//slow
for (int i=0;i<m;i++)
{ for(int j=0;j<n;j++)
  { count+=array[j][i];
  }
}

第二个速度较慢，因为您不会一个接一个地迭代内存中的位置，而是因为您m一次跳转多个位置。处理器缓存紧跟在访问位置之后的内存位置。

于 2012-08-16T12:05:41.360 回答
4

好的，在我的系统上测试了这个。完全优化后，编译器只设置了 count = 50，没有问任何问题。如果没有优化，第二个版本通常会稍微快一点，但完全可以忽略不计。

反汇编：两个循环都有完全相同的代码，除了比较一次是 100，一次是 50（我稍微增加了一些数字以允许更长的执行时间）

    for(int i = 0; i< 100; i++) {
00F9140B  mov         dword ptr [i],0  
00F91412  jmp         main+5Dh (0F9141Dh)  
00F91414  mov         eax,dword ptr [i]  
00F91417  add         eax,1  
00F9141A  mov         dword ptr [i],eax  
00F9141D  cmp         dword ptr [i],64h  
00F91421  jge         main+88h (0F91448h)  

        for(int j = 0; j< 50; j++)
00F91423  mov         dword ptr [j],0  
00F9142A  jmp         main+75h (0F91435h)  
00F9142C  mov         eax,dword ptr [j]  
00F9142F  add         eax,1  
00F91432  mov         dword ptr [j],eax  
00F91435  cmp         dword ptr [j],32h  
00F91439  jge         main+86h (0F91446h)  
        {
            count++;
00F9143B  mov         eax,dword ptr [count]  
00F9143E  add         eax,1  
00F91441  mov         dword ptr [count],eax  
        }
00F91444  jmp         main+6Ch (0F9142Ch)  
    }
00F91446  jmp         main+54h (0F91414h)

外面的大循环，里面的小循环，里面的小循环，外面的大循环之间的唯一区别是你必须多久做一次跳跃

00F91439  jge         main+86h (0F91446h)  
to
00F91446  jmp         main+54h (0F91414h)

以及循环变量的初始化：

00F91423  mov         dword ptr [j],0  
00F9142A  jmp         main+75h (0F91435h)

对于每个新循环，同时跳过以下部分。

00F9142C  mov         eax,dword ptr [j]  
00F9142F  add         eax,1  
00F91432  mov         dword ptr [j],eax

内循环每次迭代的附加命令：mov、add、mov，但没有 mov / jmp

初始化每个内部循环的附加命令：mov、jmp，更常见的是让 JGE 为真。

因此，如果您运行内循环 50 次，那么 JGE 只会实现 50 次，因此在那里进行 50 次跳跃，而当内循环运行 100 次时，您将必须跳跃 100 次。这是代码中唯一的区别。在这种情况下，几乎没有什么区别，而且大多数情况下，您会遇到内存访问问题，这会导致比循环排序更慢的事情。唯一的例外：如果您知道可以正确排序循环以避免分支预测。因此，有两件事值得以一种或另一种方式订购您的循环：

- 内存访问

-分支预测

对于其他一切，影响完全可以忽略不计。

于 2012-08-16T12:07:08.867 回答
1

实际上，尝试针对这些细节进行优化通常不是一个好主意，因为大多数情况下编译器在这方面做得更好（只要算法没有改变）。

循环数相等。

可能是第二个更快一些，因为第二个循环的初始化只发生了 5 次而不是 10 次，但我怀疑这真的会获得一些显着的变化。

最好的方法是使用分析器，甚至更好：分析生成的汇编代码。

于 2012-08-16T12:05:32.513 回答
1

如果您真的想知道，请使您的外循环成为具有最大循环计数（5 或 10）的单个参数的函数，使您的内循环成为具有最大内循环计数（10 或 5）的单个参数的函数，然后在没有任何优化的情况下编译，运行一百万次，并为它们计时。

通过任何优化，您的编译器将内联函数，扩展循环，并count作为优化过程的一部分进行计算。我的猜测是他们会做完全相同的工作量，你会看到完全相同的时间。

于 2012-08-16T12:05:52.297 回答
1

你真的试过了吗？

我假设理论上情况 II 会稍微快一些，因为在外部循环中只有一半的基于堆栈的变量创建/销毁比情况 I 的情况要好，但更好（更清晰）的是：

for(int k = 0; k < 50; k++)
{
     count++;
}

确切地说，您的示例非常抽象，以至于答案可能几乎没有用。这在很大程度上取决于上下文。

于 2012-08-16T12:05:57.883 回答