Does C/C++ offer any guarantee on minimal execution time?

Question

Why do compilers seems to be polite toward loops that do nothing and do not eliminate them?

Does the C standard require loops to take some time?

Example, the following code:

void foo(void) {     while(1) {         for(int k = 0; k < 1000000000; ++k);         printf("Foo\n");     } } 

runs slower than this one:

void foo(void) {     while(1) {         for(int k = 0; k < 1000; ++k);         printf("Foo\n");     } } 

even with -O3 optimization level. I would expect removing empty loops allowed and thus get the same speed on both codes.

Is "time spent" a side effect that should be preserved by a compiler?

Answer 1

No, time spent does not count as observable behaviour to be protected by the as-if rule:

[C++14: 1.8/5]: A conforming implementation executing a well-formed program shall produce the same observable behavior as one of the possible executions of the corresponding instance of the abstract machine with the same program and the same input. However, if any such execution contains an undefined operation, this International Standard places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation).

[C++14: 1.5/8]: The least requirements on a conforming implementation are:

• Access to volatile objects are evaluated strictly according to the rules of the abstract machine.
• At program termination, all data written into files shall be identical to one of the possible results that execution of the program according to the abstract semantics would have produced.
• The input and output dynamics of interactive devices shall take place in such a fashion that prompting output is actually delivered before a program waits for input. What constitutes an interactive device is implementation-defined.

These collectively are referred to as the observable behavior of the program. [ Note: More stringent correspondences between abstract and actual semantics may be defined by each implementation. —end note ]

Those loops can be legally optimised out and, indeed, there are scenarios in which the standard makes deliberate attempts to make doing so even easier:

[C++14: 1.10/24]: The implementation may assume that any thread will eventually do one of the following:

• terminate,
• make a call to a library I/O function,
• access or modify a volatile object, or
• perform a synchronization operation or an atomic operation.

[ Note: This is intended to allow compiler transformations such as removal of empty loops, even when termination cannot be proven. —end note ]

Your compiler may in fact be being "polite" in noticing that the intent of the loop in these programs appears to be in slowing down the emission of repeated text output. :)