Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Do compilers produce better code for do-while loops versus other types of loops?

There's a comment in the zlib compression library (which is used in the Chromium project among many others) which implies that a do-while loop in C generates "better" code on most compilers. Here is the snippet of code where it appears.

do { } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&          *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&          *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&          *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&          scan < strend); /* The funny "do {}" generates better code on most compilers */ 

https://code.google.com/p/chromium/codesearch#chromium/src/third_party/zlib/deflate.c&l=1225

Is there any evidence that most (or any) compilers would generate better (e.g. more efficient) code?

Update: Mark Adler, one of the original authors, gave a bit of context in the comments.

like image 781
Dennis Avatar asked Nov 24 '13 07:11

Dennis


People also ask

Which loop is better for or while or do while?

It depends on what you want to use it for. A while loop won't run if the condition is false, but a do-while loop will run at least once before it is terminated. I prefer While loop as it checks the condition first and then goes into the loop.

Is a while loop more efficient than a for loop?

Efficiency, and While vs For Using for: % Time elapsed: 0.0010001659 seconds. Using while: % Time elapsed: 0.026000023 seconds. The main reason that While is much slower is because the while loop checks the condition after each iteration, so if you are going to write this code, just use a for loop instead.

Why for loop is better than while and do while?

for loop: for loop provides a concise way of writing the loop structure. Unlike a while loop, a for statement consumes the initialization, condition and increment/decrement in one line thereby providing a shorter, easy to debug structure of looping.

Are for loops better than while loops?

In general, you should use a for loop when you know how many times the loop should run. If you want the loop to break based on a condition other than the number of times it runs, you should use a while loop.


1 Answers

First of all:

A do-while loop is not the same as a while-loop or a for-loop.

  • while and for loops may not run the loop body at all.
  • A do-while loop always runs the loop body at least once - it skips the initial condition check.

So that's the logical difference. That said, not everyone strictly adheres to this. It is quite common for while or for loops to be used even when it is guaranteed that it will always loop at least once. (Especially in languages with foreach loops.)

So to avoid comparing apples and oranges, I'll proceed assuming that the loop will always run at least once. Furthermore, I won't mention for loops again since they are essentially while loops with a bit of syntax sugar for a loop counter.

So I'll be answering the question:

If a while loop is guaranteed to loop at least once, is there any performance gain from using a do-while loop instead.


A do-while skips the first condition check. So there is one less branch and one less condition to evaluate.

If the condition is expensive to check, and you know you're guaranteed to loop at least once, then a do-while loop could be faster.

And while this is considered a micro-optimization at best, it is one that the compiler can't always do: Specifically when the compiler is unable to prove that the loop will always enter at least once.


In other words, a while-loop:

while (condition){     body } 

Is effectively the same as this:

if (condition){     do{         body     }while (condition); } 

If you know that you will always loop at least once, that if-statement is extraneous.


Likewise at the assembly level, this is roughly how the different loops compile to:

do-while loop:

start:     body     test     conditional jump to start 

while-loop:

    test     conditional jump to end start:     body     test     conditional jump to start end: 

Note that the condition has been duplicated. An alternate approach is:

    unconditional jump to end start:     body end:     test     conditional jump to start 

... which trades away the duplicate code for an additional jump.

Either way, it's still worse than a normal do-while loop.

That said, compilers can do what they want. And if they can prove that the loop always enters once, then it has done the work for you.


But things are bit weird for the particular example in the question because it has an empty loop body. Since there is no body, there's no logical difference between while and do-while.

FWIW, I tested this in Visual Studio 2012:

  • With the empty body, it does actually generate the same code for while and do-while. So that part is likely a remnant of the old days when compilers weren't as great.

  • But with a non-empty body, VS2012 manages to avoid duplication of the condition code, but still generates an extra conditional jump.

So it's ironic that while the example in the question highlights why a do-while loop could be faster in the general case, the example itself doesn't seem to give any benefit on a modern compiler.

Considering how old the comment was, we can only guess at why it would matter. It's very possible that the compilers at the time weren't capable of recognizing that the body was empty. (Or if they did, they didn't use the information.)

like image 167
Mysticial Avatar answered Sep 21 '22 13:09

Mysticial