Discrepancy between process execution time and CPU speed (lost cycles)

Question

I'm not sure if this is on topic, but I've seen some hardware related questions here so I'll post it here anyway. If it's off topic I'll take it off.

Compile this C code:

int main() {
  unsigned long long int i;
  for (i = 0; i < 30000000000ull; ++i){}
  return 0;
}

with gcc cycleTimer.c. Then run /usr/bin/time -f "%E %P" ./a.out.

I get the following output:

1:17.04 99%

Meaning the process takes 77 seconds to complete and uses 99% of a CPUs time. Running cpufreq-info during the process gives

current CPU frequency is 2.30 GHz

for all four cores. Now create the assembly instructions for cycleTimer.c with gcc cycleTimer.c -S, and we get the following assembly code:

        .file   "cycleTimer.c"
        .text
        .globl  main
        .type   main, @function
main:
.LFB0:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        movq    $0, -8(%rbp)
        jmp     .L2
.L3:
        addq    $1, -8(%rbp)
.L2:
        movabsq $29999999999, %rax
        cmpq    %rax, -8(%rbp)
        jbe     .L3
        movl    $0, %eax
        popq    %rbp
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:
        .size   main, .-main
        .ident  "GCC: (Ubuntu 4.8.2-19ubuntu1) 4.8.2"
        .section        .note.GNU-stack,"",@progbits

From this, we can see that on every iteration of the loop, four assembly instructions are being run. Therefore, to work out the instructions per second, we do (4*30000000000)/77 = 1558441558 which is 1.6 GHz, much less than 0.99*2.3 which gives 2.28 GHz of the processor that we are actually meant to be using.

Why is there such a big discrepancy? The kernel is saying that 99% of the CPU is being used. Are there any other hidden instructions being computed by the CPU we don't see with gcc -S? Have I made a mistake somewhere?

Answer 1

The $2.3\textrm{GHz}$ clock cycle speed of your CPU is something entirely different from the rate at which it executes assembly instructions. Executing a single instruction may take 1, 10 or even more than 100 clock cycles or it might take less than a single cycle (since multiple instructions can sometimes be executed in a single cycle).

An interesting experiment would be to do some work in the loop body, such as an addition or a division. Even though addition and division are both single instructions, the program that does a division will probably take considerably longer than one that does addition since on most architectures division takes many clock cycles.

Answer 2

You didn't calculate the clockspeed. What you calculated was the number of instructions per second, which is about 1.56 billion per second. It seems your code takes 6 cycles per iteration.

Take the first instruction: addq $1, -8(%rbp). What does this instruction actually do? It calculates the memory address %rbp-8. It reads the memory at that location. It adds one to the result. It stores the result at the same memory location. That's four different things that need to be done for one single instruction.

And your code has at least one nasty dependency: You are storing a value at -8(%rbp) and then using the same value. That would normally mean that the store operation has to be completed (which takes a while even in cache), and the compare instruction has to wait reading the data until the store is complete. That will take a while.

But then I think newer Intel CPUs will do some heroic effort to figure out that you are reading from the same address, and therefore reading the memory location will return the value that is being stored right now, and forward the value from the result of the add directly, and not from memory. And the "branch" will be executed speculatively, and not wait for the comparison to finish.

You can't compare an old RISC processor with a current Intel processor. You used complex instructions that will be translated into multiple micro-ops, you had dependencies through memory. Big caches can't be accessed in a single cycle.