Real Loop Running Times

by Paul Hornsey

Intro

When first starting programming tests such as the ones at Project Euler, sometimes the brute force approach doesn't look like it will take that long.  My thinking was, processors run so fast, that 1014 (100,000,000,000,000) loops can't take that long?? Wrong!!

Code and Prediction

All the times presented here are using the following processor:

  • Intel Core i5 4670 3.4GHz (3.8GHz Turbo) Quad Core

3.4GHz... 3.4x10^9 = 3,400,000,000 CPU clock cycles per second.

To keep the loop as clean as possible without any fancy optimisations, I implemented it in straight 64bit assembler.  The main loop being:
 
        mov r9, [loop_count]
loop_start:
        dec r9
        jnz loop_start

(r9 is a general purpose 64bit register.)

If this was an older processor at the same speed, we could try and predict how long this should take.  Lets say the 'dec' takes 1 clock pulse and the 'jnz' jump takes 2. So 3 pulses per loop.

3,400,000,000 / 3 = 1133333333.33 loops per second.
So 10^10 * 3 clock pulses = 30,000,000,000 pulses
= 30,000,000,000 / 3,400,000,000  seconds
= 8.824 seconds
 

Actual Times

When actually run, the loop finishes much quicker:

  •     1010:   0m2.852s
(I timed the loops using the linux utility command 'time')

It seems that the processor can run each loop in one clock cycle and run at more like 3.5GHz

  •     1010:   0m2.852s
  •     1011:  0m26.864s
  •     1012:  4m30.068s
  •     1013: 44m57.968s

Larger Predictions

So, being a linear O(n) algorithm, we can calculate how long the same
processor will take to finish larger loop counts:

  •     1014:  7.5 hours
  •     1015:  3.125 days
  •     1016:  4.464 weeks

As can be seen, these numbers soon get big enough to take large processing times.  Remember that this is without any calculations
each loop!

Conculsion

Simple stuff, but with such large numbers, a physical timed example brings the processor speed down to human comprehensible values.

Paul Hornsey

Paul Hornsey

Paul Hornsey has developed software since 8 bit machines were cool. Since graduating from Heriot-Watt University in Computer Science he has worked for companies developing software from serious industrial code, to games and other cool stuff.

He is currently one part of 1partCarbon where the emphasis is on developers enjoying their life and career.