Loop with a zero execution time

Question

Is it possible to have a loop which has a zero execution time? I would think that even an empty loop should have an execution time since there is an overhead associated with it.

Popcorn

loops might be unrolled and/or eliminated completely by the compiler. – Brocket

One of the primary jobs of an optimizing compiler is data flow analysis. Computations that produce data that doesn't flow anywhere are eliminated, including loops. The exact behavior depends on your compiler. – Palatalized

This actually also applies equally to C++ as well, I will add the relevant C++ quote to my answer as well. – Pistoia

Closing based on the question being too broad does not make sense, we don't have many possible answers to this question and it applies to general case perfectly well. – Pistoia

This question fits neither criteria for too broad. As we can see empirically from the answers, there are not too many of them and there is basically one precise answer, the two answers differ only in the amount of detail they offer. The answers are not too long and although they could be expanded upon they have a long way to go before they would come close to the longest good answers to perfectly on topic questions that are out there. – Pistoia

"...since there is an overhead associated with it." What overhead would be associated with, e. g., while(0) {}? – Nickinickie

To rephrase your question, "is it possible to have <any machine code instruction> with a zero execution time", and the answer is no, since even NOP does require some time. An instruction can execute in zero time only if it doesn't exist, as existing answers show. – Paries

@georg: but pipelining can halve the observed processing time for a certain instruction, as it gets executed together with another one in the same CPU cycle. If 'the other instruction' is your NOP, all it would take is the original instruction cycle. – Nordgren

@yu-hao this question applies equally to both C and C++ and I want to be able to close C++ questions asking the same thing with this one which I see no reason not to. If you really disagree then flag for moderator attention. – Pistoia

@ShafikYaghmour That's fine. I do think it's better to keep the language tag as the original question, for these rather "low-level" questions. But as far as this question, your reason is fair. – Volturno

@braiam your edit invalidates the current answers and is therefore not valid. The edit could be argued if there were no current answers but after 3 days and with three answers that are relatively language specific it is not a good edit. – Pistoia

@ShafikYaghmour their problem for not providing a language independent explication.. wait, what answer it invalidates? Most compilers behave using the same independently if it's C-like. – Flinn

@Flinn my answer is not language agnostic and would not be a great answer to the way you retagged the question. It is perfectly valid to ask how a broad issue effects a specific language, in this case it seems to me that the agnostic form of the question would indeed be too broad but the C and C++ version has a concise answer. I am sure the principle applies well across most languages but the specifics probably get hairy and make it a poor agnostic question since everyone would post their favorite language example which fits the SO category of too broad. – Pistoia

Answer 1

Yes, under the as-if rule the compiler is only obligated to emulate the observable behavior of the code, so if you have a loop that does not have any observable behavior then it can be optimized away completely and therefore will effectively have zero execution time.

Examples

For example the following code:

int main()
{
  int j = 0 ;
  for( int i = 0; i < 10000; ++i )
  {
    ++j ;
  }
}

compiled with gcc 4.9 using the -O3 flag basically ends up reducing to the following (see it live):

main:
  xorl  %eax, %eax  #
  ret

Pretty much all optimizations allowed fall under the as-if rule, the only exception I am aware of is copy elison which is allowed to effect the observable behavior.

Some other examples would include dead code elimination which can remove code that the compiler can prove will never be executed. For example even though the following loop does indeed contain a side effect it can be optimized out since we can prove it will never be executed (see it live):

#include <stdio.h>

int main()
{
  int j = 0 ;
  if( false ) // The loop will never execute
  {
    for( int i = 0; i < 10000; ++i )
    {
      printf( "%d\n", j ) ;
      ++j ;
    }
  }
}

The loop will optimize away the same as the previous example. A more interesting example would be the case where a calculation in a loop can be deduced into a constant thereby avoiding the need for a loop(not sure what optimization category this falls under), for example:

int j = 0 ;
for( int i = 0; i < 10000; ++i )
{
  ++j ;
}
printf( "%d\n", j ) ;

can be optimized away to (see it live):

movl    $10000, %esi    #,
movl    $.LC0, %edi #,
xorl    %eax, %eax  #
call    printf  #

We can see there is no loop involved.

Where is as-if Rule covered in the standard

The as-if rule is covered in the draft C99 standard section 5.1.2.3 Program execution which says:

In the abstract machine, all expressions are evaluated as specified by the semantics. An actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no needed side effects are produced (including any caused by calling a function or accessing a volatile object).

The as-if rule also applies to C++, gcc will produce the same result in C++ mode as well. The C++ draft standard covers this in section 1.9 Program execution:

The semantic descriptions in this International Standard define a parameterized nondeterministic abstract machine. This International Standard places no requirement on the structure of conforming implementations. In particular, they need not copy or emulate the structure of the abstract machine. Rather, conforming implementations are required to emulate (only) the observable behavior of the abstract machine as explained below.5

Pistoia

I'd wager that most if not all language specifications have an as-if rule. There usually is no point in doing a computation if it isn't used and has no side effects. It only wastes time and energy. – Durga

@CraigAnderson: That's true that vast majority of the time, but there are rare instances where you do want to do useless computations, such as in cryptographic operations where you want all code paths to take the same amount of time in order to prevent timing side channel attacks. – Whiting

In other words: For real loops that perform actual, unavoidable, non-cheatable work, the answer is: No. For pseudo-loops that only do superfluous stuff: Yes. – Township

Answer 2

Yes - if the compiler determines that the loop is dead code (will never execute) then it will not generate code for it. That loop will have 0 execution time, although strictly speaking it doesn't exist at the machine code level.

Durga

Answer 3

As well as compiler optimisations, some CPU architectures, particularly DSPs, have zero overhead looping, whereby a loop with a fixed number of iterations is effectively optimised away by the hardware, see e.g. http://www.dsprelated.com/showmessage/20681/1.php

Heiskell

Answer 4

The compiler is not obliged to evaluate the expression, or a portion of an expression, that has no side effects and whose result is discarded.

Harbison and Steele, C: A Reference Manual

Ninetieth