Execution time performance when counting up to 1,000,000,000

Question

I have made a simple C++ program that simply counts up a variable to 1,000,000,000 and then displays the time it took. I used a simple for loop to do this.

for(long n=0;n<1000000000;n++);

The time it took is about 22 seconds. This confuses me a little, because the pi operates at 700Mhz and the program used about 96% of the cpu. Why didn't this take about 2 seconds? Does increasing an integer by 1 take 10 clock cycles in this case? I have previously worked with AVR microprocessors and this was a reasonably good way to estimate the speed in those cases. I didn't use any optimization flags when I compiled the code, and the OS I used is Rasbian.

Answer 1

The time it took is about 22 seconds.

Yep. Took 21.7s on a pi here.

Does increasing an integer by 1 take 10 clock cycles in this case?

Hopefully not, but that's not all that's going on. You're also making a comparison each time to evaluate the for loop conditional.

No more than 1 assembly instruction can be processed per cycle, and I believe it may often be less than that, e.g., if the instruction requires fetching or storing stuff from/to RAM. I'm not at all an assembly level guy, but I can show you some clues about what's involved. It's easier if we break that loop down a bit, although the assembly generated won't be quite the same:

int main (void) {
        long i = 0;
        while (1) {
                i++;
                if (i > 1000000000) break;
        }
        return 0;
}

Now compile that with debugging symbols: g++ -g test.cpp, then load it into the debugger: gdb ./a.out. At the prompt, type disassemble/m main. You should get a few dozen lines of output including this:

3               while (1) {
   0x000083fc <+24>:    nop                     ; (mov r0, r0)

4                       i++;
   0x00008400 <+28>:    ldr     r3, [r11, #-8]
   0x00008404 <+32>:    add     r3, r3, #1
   0x00008408 <+36>:    str     r3, [r11, #-8]

5                       if (i > 1000000000) break;
   0x0000840c <+40>:    ldr     r2, [r11, #-8]
   0x00008410 <+44>:    ldr     r3, [pc, #28]   ; 0x8434 <main()+80>
   0x00008414 <+48>:    cmp     r2, r3
   0x00008418 <+52>:    ble     0x83fc <main()+24>
   0x0000841c <+56>:    nop                     ; (mov r0, r0)

6               }

The numbers in the left column correspond to line numbers from the source. Notice line 4, i++ -- incrementing an integer by one -- is three lines of assembly (each is one instruction). Line 5, checking the same condition as the for() loop, is 5 lines of assembly.

The compiler can be made a bit smarter, which should help to speed things up. If you throw in the -O2 switch (2nd level of optimization), i.e., g++ -g -O2 test.cpp, it will spot the fact that this loop does nothing, and that's what it will then do: nothing. If you look at the assembly as per above, there won't be any for that loop, and:

> time ./a.out
real 0m0.016s
user 0m0.010s
sys  0m0.000s

Quite a performance improvement ;) Of course it wasn't really counting anything this time.