¿Los compiladores producen un mejor código para bucles do-while en comparación con otros tipos de bucles?

Hay un comentario en la biblioteca de compresión zlib (que se usa en el proyecto Chromium entre muchos otros) que implica que un bucle do-while en C genera un código "mejor" en la mayoría de los compiladores. Aquí está el fragmento de código donde aparece.

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

¿Existe alguna evidencia de que la mayoría (o alguno) de los compiladores generaría un código mejor (por ejemplo, más eficiente)?

Actualización: Mark Adler , uno de los autores originales, dio un poco de contexto en los comentarios.

Ante todo:

Un do-whilebucle no es lo mismo que un whilebucle o un forbucle.

• whiley los forbucles pueden no ejecutar el cuerpo del bucle en absoluto.
• Un do-whilebucle siempre ejecuta el cuerpo del bucle al menos una vez; omite la verificación de condición inicial.

Entonces esa es la diferencia lógica. Dicho esto, no todos se adhieren estrictamente a esto. Es bastante común que se utilicen bucles for whileo forincluso cuando se garantiza que siempre se repetirá al menos una vez. (Especialmente en idiomas con bucles foreach ).

Entonces, para evitar comparar manzanas y naranjas, procederé asumiendo que el ciclo siempre se ejecutará al menos una vez. Además, no volveré a mencionar los forbucles, ya que son esencialmente whilebucles con un poco de azúcar de sintaxis para un contador de bucles.

Entonces estaré respondiendo a la pregunta:

Si whilese garantiza que un bucle se repita al menos una vez, ¿hay alguna ganancia de rendimiento al usar un do-whilebucle en su lugar?

A do-whileomite la primera comprobación de condición. Entonces, hay una rama menos y una condición menos para evaluar.

Si la condición es costosa de verificar y sabe que tiene la garantía de realizar un bucle al menos una vez, entonces un do-whilebucle podría ser más rápido.

Y aunque esto se considera una microoptimización en el mejor de los casos, es una que el compilador no siempre puede hacer: específicamente cuando el compilador no puede probar que el bucle siempre entrará al menos una vez.

En otras palabras, un ciclo while:

while (condition){
    body
}

Es efectivamente lo mismo que esto:

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

Si sabe que siempre hará un bucle al menos una vez, esa instrucción if es extraña.

Del mismo modo, a nivel de ensamblaje, así es aproximadamente como se compilan los diferentes bucles para:

bucle de hacer mientras:

start:
    body
    test
    conditional jump to start

bucle while:

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

Tenga en cuenta que la condición se ha duplicado. Un enfoque alternativo es:

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

... que cambia el código duplicado por un salto adicional.

De cualquier manera, sigue siendo peor que un do-whilebucle normal .

Dicho esto, los compiladores pueden hacer lo que quieran. Y si pueden demostrar que el bucle siempre entra una vez, entonces ha hecho el trabajo por usted.

Pero las cosas son un poco extrañas para el ejemplo particular de la pregunta porque tiene un cuerpo de bucle vacío. Como no hay cuerpo, no hay diferencia lógica entre whiley do-while.

FWIW, probé esto en Visual Studio 2012:

• Con el cuerpo vacío, en realidad genera el mismo código para whiley do-while. Así que esa parte probablemente sea un remanente de los viejos tiempos cuando los compiladores no eran tan buenos.

• Pero con un cuerpo no vacío, VS2012 logra evitar la duplicación del código de condición, pero aún genera un salto condicional adicional.

Así que es irónico que, si bien el ejemplo de la pregunta resalta por qué un do-whilebucle podría ser más rápido en el caso general, el ejemplo en sí no parece ofrecer ningún beneficio en un compilador moderno.

Teniendo en cuenta la antigüedad del comentario, solo podemos adivinar por qué sería importante. Es muy posible que los compiladores en ese momento no fueran capaces de reconocer que el cuerpo estaba vacío. (O si lo hicieron, no usaron la información).

¿Existe alguna evidencia de que la mayoría (o alguno) de los compiladores generaría un código mejor (por ejemplo, más eficiente)?

No mucho, a menos que observe el ensamblaje generado real de un compilador específico real en una plataforma específica con algunas configuraciones de optimización específicas.

Probablemente valió la pena preocuparse por esto hace décadas (cuando se escribió ZLib), pero ciertamente no hoy en día, a menos que descubra, mediante un perfil real, que esto elimina un cuello de botella de su código.

En pocas palabras (tl; dr):

Estoy interpretando el comentario en el código de los OP de manera un poco diferente, creo que el "mejor código" que afirman haber observado se debió a mover el trabajo real a la "condición" del ciclo. Sin embargo, estoy completamente de acuerdo en que es muy específico del compilador y que la comparación que hicieron, aunque pueden producir un código ligeramente diferente, es en su mayoría inútil y probablemente obsoleta, como muestro a continuación.

Detalles:

Es difícil decir qué quiso decir el autor original con su comentario sobre la do {} whileproducción de un mejor código, pero me gustaría especular en otra dirección que la que se planteó aquí; creemos que la diferencia entre los bucles do {} whiley while {}es bastante pequeña (una rama menos como Mystical dijo), pero hay algo aún más "divertido" en este código y es poner todo el trabajo dentro de esta loca condición y mantener la parte interna vacía ( do {}).

Probé el siguiente código en gcc 4.8.1 (-O3), y da una diferencia interesante:

#include "stdio.h" 
int main (){
    char buf[10];
    char *str = "hello";
    char *src = str, *dst = buf;

    char res;
    do {                            // loop 1
        res = (*dst++ = *src++);
    } while (res);
    printf ("%s\n", buf);

    src = str;
    dst = buf;
    do {                            // loop 2
    } while (*dst++ = *src++);
    printf ("%s\n", buf);

    return 0; 
}

Después de compilar -

00000000004003f0 <main>:
  ... 
; loop 1  
  400400:       48 89 ce                mov    %rcx,%rsi
  400403:       48 83 c0 01             add    $0x1,%rax
  400407:       0f b6 50 ff             movzbl 0xffffffffffffffff(%rax),%edx
  40040b:       48 8d 4e 01             lea    0x1(%rsi),%rcx
  40040f:       84 d2                   test   %dl,%dl
  400411:       88 16                   mov    %dl,(%rsi)
  400413:       75 eb                   jne    400400 <main+0x10>
  ...
;loop 2
  400430:       48 83 c0 01             add    $0x1,%rax
  400434:       0f b6 48 ff             movzbl 0xffffffffffffffff(%rax),%ecx
  400438:       48 83 c2 01             add    $0x1,%rdx
  40043c:       84 c9                   test   %cl,%cl
  40043e:       88 4a ff                mov    %cl,0xffffffffffffffff(%rdx)
  400441:       75 ed                   jne    400430 <main+0x40>
  ...

Entonces, el primer ciclo hace 7 instrucciones mientras que el segundo hace 6, aunque se supone que deben hacer el mismo trabajo. Ahora, realmente no puedo decir si hay algo de inteligencia del compilador detrás de esto, probablemente no y es solo una coincidencia, pero no he comprobado cómo interactúa con otras opciones del compilador que este proyecto podría estar usando.

En clang 3.3 (-O3), por otro lado, ambos bucles generan este código de 5 instrucciones:

  400520:       8a 88 a0 06 40 00       mov    0x4006a0(%rax),%cl
  400526:       88 4c 04 10             mov    %cl,0x10(%rsp,%rax,1)
  40052a:       48 ff c0                inc    %rax
  40052d:       48 83 f8 05             cmp    $0x5,%rax
  400531:       75 ed                   jne    400520 <main+0x20>

Lo que demuestra que los compiladores son bastante diferentes y que avanzan a un ritmo mucho más rápido de lo que algunos programadores podrían haber anticipado hace varios años. También significa que este comentario carece de sentido y probablemente esté ahí porque nadie había comprobado si todavía tiene sentido.

En pocas palabras: si desea optimizar al mejor código posible (y sabe cómo debería verse), hágalo directamente en ensamblador y elimine el "intermediario" (compilador) de la ecuación, pero tenga en cuenta que el más nuevo Los compiladores y HW más nuevos pueden hacer que esta optimización sea obsoleta. En la mayoría de los casos, es mucho mejor dejar que el compilador haga ese nivel de trabajo por usted y concentrarse en optimizar las cosas importantes.

Otro punto que se debe hacer, el recuento de instrucciones (asumiendo que esto es lo que buscaba el código original de los OP), no es de ninguna manera una buena medida para la eficiencia del código. No todas las instrucciones fueron creadas de la misma manera, y algunas de ellas (movimientos simples de registro a registro, por ejemplo) son realmente baratas ya que son optimizadas por la CPU. Otra optimización podría dañar las optimizaciones internas de la CPU, por lo que eventualmente solo cuenta la evaluación comparativa adecuada.

Un whilebucle a menudo se compila como un do-whilebucle con una rama inicial a la condición, es decir

    bra $1    ; unconditional branch to the condition
$2:
    ; loop body
$1:
    tst <condition> ; the condition
    brt $2    ; branch if condition true

mientras que la compilación de un do-whilebucle es la misma sin la rama inicial. Puede ver en eso que while()es inherentemente menos eficiente por el costo de la sucursal inicial, que sin embargo solo se paga una vez. [Compare con la forma ingenua de implementación while,que requiere tanto una rama condicional como una rama incondicional por iteración].

Dicho esto, no son alternativas realmente comparables. Es doloroso transformar un whilebucle en un do-whilebucle y viceversa. Hacen cosas diferentes. Y en este caso, las varias llamadas a métodos dominarían totalmente cualquier cosa que hiciera el compilador whilefrente ado-while.

La observación no se trata de la elección de la declaración de control (hacer frente a while), ¡se trata de desenrollar el ciclo!

Como puede ver, esta es una función de comparación de cadenas (los elementos de cadena probablemente tienen 2 bytes de longitud), que podría haberse escrito con una sola comparación en lugar de cuatro en un atajo y expresión.

Esta última implementación es sin duda más rápida, ya que realiza una única verificación de la condición de fin de cadena después de cada cuatro comparaciones de elementos, mientras que la codificación estándar implicaría una verificación por comparación. Dicho de otra manera, 5 pruebas por 4 elementos frente a 8 pruebas por 4 elementos.

De todos modos, funcionará solo si la longitud de la cadena es un múltiplo de cuatro o tiene un elemento centinela (de modo que se garantiza que las dos cadenas diferirán más allá del strendborde). ¡Bastante arriesgado!

Esta discusión sobre la eficiencia while vs. do es completamente inútil en este caso, ya que no hay cuerpo.

while (Condition)
{
}

y

do
{
}
while (Condition);

son absolutamente equivalentes.