6

This is my Perl code

$big=10_000_000;
#A:big loop outside
my $begin_time = time;
foreach my $i (1..$big) {
        foreach my $p (1..10){
        }
}
my $end_time = time;
my $t1=$end_time-$begin_time; 

#B:small loop outside
my $begin_time = time;
foreach my $i (1..10){
     foreach my $p (1..$big){
     }
}
my $end_time = time;
my $t2=$end_time-$begin_time; 

#output
print $t1;
print "\n";
print $t2;

t1=8 seconds
t2=3 seconds

And the mathematica code:

Timing[Do[2, {i, 1, 10}, {j, 2*1, 10^7}]]
output:{14.328, Null}
Timing[Do[2, {j, 1, 2*10^7}, {i, 1, 10}]]
output:{30.937, Null}

Why does the big loop outside take more time?

Borodin
  • 126,100
  • 9
  • 70
  • 144
cn8341
  • 129
  • 7

1 Answers1

10

There's a certain amount of overhead in executing the inner loop (initialising the variable; making the checks to see if it should end) and in the first case, you are losing this overhead 10,000,000 times; in the second, you are only doing it 10 times.

EDIT: Let s be the time to setup a loop (e.g. initialise a variable) and i the time to iterate a loop (e.g. test the end condition). Then:

Big Inner Loop

T = s1 + 10 * ( i1 + s2 + 10,000,000*i2 )
  = s1 + 10*i1 + 10*s2 + 100,000,000*i2

Big Outer Loop

T = s1 + 10,000,000 * ( i1 + s2 + 10*i2 )
  = s1 + 10,000,000*i1 + 10,000,000*s2 + 100,000,000*i2

Difference

diff = 9,999,990*i1 + 9,999,990*s2

So the iteration time of the outer loop (i1) and the set-up time of the inner-loop (s2) are both performed 9,999,990 times more with the big outer loop than with the big inner loop.

TripeHound
  • 2,721
  • 23
  • 37
  • It's 10,000,000 times, not 10,000. And the time taken to check to see if a loop should end is identical in both cases: it's just the initial loop setup and later tear-down that is different – Borodin Apr 16 '14 at 11:36
  • @Borodin - sorry, misread the number. Added more detail about setting-up and iterating the loops. – TripeHound Apr 16 '14 at 12:17
  • 1
    @Borodin: the inner loop is indeed checked the same number of times in both cases. The outer loop is checked 10 times in one case and 10E6 times in the other case. –  Apr 16 '14 at 12:33