为什么小循环里面套大循环比大循环里面套小循环要快?

cn8888

下面是用perl写的代码

1. $big=10000000;
   
2. #A:大循环内嵌小循环
   
3. my $begin_time = time;
   
4. foreach my $i (1..$big) {
   
5.         foreach my $p (1..10){
   
6.         }
   
7. }
   
8. my $end_time = time;
   
9. my $t1=$end_time-$begin_time;
   
10. #B:小循环内嵌大循环
    
11. my $begin_time = time;
    
12. foreach my $i (1..10){
    
13. foreach my $p (1..$big){
    
14. }
    
15. }
    
16. my $end_time = time;
    
17. my $t2=$end_time-$begin_time;
    
18. #输出结果
    
19. print $t1;
    
20. print "\n";
    
21. print $t2;
    

复制代码

最后运行结果是

1. $t1=8秒钟
   
2. $t2=3秒钟

复制代码

前者是后者的两倍还要多,
那么请问为什么前者慢后者快,
用C语言或者C++是不是也这么回事?
别的语言呢?

cn8888

理论上两者的速度是一样快的,  但是实际上不一样,  请问为什么呢?
哪位高人能解决一下这个问题呢?

Buffalo

很简单，除了你要求程序做的事情之外，程序还需额外启动和结束许多次循环，以及完成计数器在不同数值上的减一运算，这些工作量对两种循环嵌套是不一样的。

liangbch

谈谈我的观点，从循环代码块的执行的角度来分析一下这个问题。

  在循环体中，执行完最后一条代码后，有2条执行路径，一条是向后跳，继续循环，另一条是向前走，跳出循环体。
现在CPU普遍使用管线技术，在执行当前指令时，接下了几条指令已经在执行取指和译码了操作了。对于顺序执行指令，直接装载接下来的指令到管线就可以了。
但是对于分支语句，CPU只能对最可能的一条路径进行取指和译码，具体哪条路径最可能被执行呢? 这涉及到CPU的分支预测技术。最普遍的分支预测策略是：
1.每次执行的分支语句时，都要记录实际的跳转地址。
2.在第一次遇到分支语句（对应于汇编语言的比较和跳转指令对），向后跳。
3.从第2次开始，根据跳转历史记录，选择一条最可能的路径进行取值和译码。
4.如果预测成功，则执行比较和条件跳转指令对的速度非常快，如果预测失败，则执行比较跳转指令对的时间比预测成功时慢好多倍(典型值是10倍左右)

如果是一个大循环，比如执行10000次循环，则预测技术总是预测向后跳哪条路径，可做到9999次预测成功，1次预测失败。预测成功率为99.99%。
如果是一个小循环，比如执行10次循环，则预测技术可做到9次预测成功，1次预测失败。预测成功率仅为90%.

故仅凭这一点来看，大循环单次循环执行时间优于小循环。

liangbch

学习笔记--分支预测入门
处理器分支预测研究的历史和现状
分支预测器-维基百科

mathe

跳传差别不会这么大。perl是解释执行的，这个完全依赖于解释器是如何执行的

liangbch

mathe 发表于 2014-4-16 13:23
跳传差别不会这么大。perl是解释执行的，这个完全依赖于解释器是如何执行的

同意mathe的观点。我也想到了这一点。

mathe

我在我的linux上测试了同样的代码，运行后两者时间是4和3，差别远没有那么大

wayne

看来perl的loop控制还是偏简单了点。
我刚才测试了下，发现在Mathematica里面 这种差别很小。

mathe

如果我们仅计算跳转次数，内层都是10*big,外层约差big次，所以时间比11：10