Os compiladores produzem código melhor para loops do-while em comparação com outros tipos de loops?

Há um comentário na biblioteca de compactação zlib (que é usada no projeto Chromium entre muitos outros) que implica que um loop do-while em C gera código "melhor" na maioria dos compiladores. Aqui está o trecho de código onde ele 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 alguma evidência de que a maioria (ou qualquer) compilador geraria um código melhor (por exemplo, mais eficiente)?

Atualização: Mark Adler , um dos autores originais, deu um pouco de contexto nos comentários.

Em primeiro lugar:

Um do-whileloop não é o mesmo que um while-loop ou um for-loop.

• whilee os forloops podem nem mesmo executar o corpo do loop.
• Um do-whileloop sempre executa o corpo do loop pelo menos uma vez - ele ignora a verificação de condição inicial.

Então essa é a diferença lógica. Dito isso, nem todo mundo adere estritamente a isso. É bastante comum o uso de loops for whileou formesmo quando é garantido que ele sempre fará um loop pelo menos uma vez. (Especialmente em idiomas com loops foreach .)

Portanto, para evitar comparar maçãs e laranjas, continuarei presumindo que o loop sempre será executado pelo menos uma vez. Além disso, não mencionarei os forloops novamente, pois eles são essencialmente whileloops com um pouco de açúcar de sintaxe para um contador de loop.

Portanto, responderei à pergunta:

Se um whileloop tem garantia de loop pelo menos uma vez, há algum ganho de desempenho com o uso de um do-whileloop.

A do-whileignora a primeira verificação de condição. Portanto, há um ramo a menos e uma condição a menos para avaliar.

Se a verificação da condição for cara e você souber que fará um loop pelo menos uma vez, um do-whileloop pode ser mais rápido.

E embora isso seja considerado, na melhor das hipóteses, uma microotimização, é algo que o compilador nem sempre pode fazer: especificamente quando o compilador não consegue provar que o loop sempre entrará pelo menos uma vez.

Em outras palavras, um loop while:

while (condition){
    body
}

É efetivamente o mesmo que este:

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

Se você sabe que sempre fará o loop pelo menos uma vez, essa instrução if é estranha.

Da mesma forma, no nível de montagem, é aproximadamente assim que os diferentes loops são compilados para:

loop do-while:

start:
    body
    test
    conditional jump to start

while-loop:

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

Observe que a condição foi duplicada. Uma abordagem alternativa é:

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

... que troca o código duplicado por um salto adicional.

De qualquer forma, ainda é pior do que um do-whileloop normal .

Dito isso, os compiladores podem fazer o que quiserem. E se eles puderem provar que o loop sempre entra uma vez, isso fez o trabalho para você.

Mas as coisas são um pouco estranhas para o exemplo específico na questão porque ele tem um corpo de loop vazio. Como não há corpo, não há diferença lógica entre whilee do-while.

FWIW, testei isso no Visual Studio 2012:

• Com o corpo vazio, ele realmente gera o mesmo código para whilee do-while. Essa parte provavelmente é um resquício dos velhos tempos, quando os compiladores não eram tão bons.

• Mas com um corpo não vazio, VS2012 consegue evitar a duplicação do código de condição, mas ainda gera um salto condicional extra.

Portanto, é irônico que, embora o exemplo da pergunta destaque por que um do-whileloop poderia ser mais rápido no caso geral, o exemplo em si não parece oferecer nenhum benefício em um compilador moderno.

Considerando a idade do comentário, só podemos imaginar por que ele seria importante. É bem possível que os compiladores da época não fossem capazes de reconhecer que o corpo estava vazio. (Ou, se usaram, não usaram as informações.)

Existe alguma evidência de que a maioria (ou qualquer) compilador geraria um código melhor (por exemplo, mais eficiente)?

Não muito, a menos que você observe a montagem real gerada de um compilador real específico em uma plataforma específica com algumas configurações de otimização específicas.

Provavelmente valeu a pena se preocupar com isso décadas atrás (quando o ZLib foi escrito), mas certamente não hoje em dia, a menos que você tenha descoberto, por perfis reais, que isso remove um gargalo de seu código.

Em poucas palavras (tl; dr):

Estou interpretando o comentário no código dos OPs de maneira um pouco diferente, acho que o "código melhor" que eles afirmam ter observado foi devido à movimentação do trabalho real para a "condição" do loop. No entanto, concordo totalmente que é muito específico do compilador e que a comparação que eles fizeram, embora sendo capazes de produzir um código ligeiramente diferente, é quase inútil e provavelmente obsoleta, como mostro abaixo.

Detalhes:

É difícil dizer o que o autor original queria dizer com seu comentário sobre este do {} whilecódigo melhor produzir, mas eu gostaria de especular em outra direção do que o que foi criado aqui - nós acreditamos que a diferença entre do {} whilee while {}laços é muito pequena (menos um ramo como Mystical disse), mas há algo ainda mais "engraçado" neste código e que é colocar todo o trabalho dentro dessa condição maluca, e manter a parte interna vazia ( do {}).

Eu tentei o seguinte código no gcc 4.8.1 (-O3), e ele dá uma diferença interessante -

#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; 
}

Depois 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>
  ...

Assim, o primeiro loop executa 7 instruções enquanto o segundo executa 6, embora devam fazer o mesmo trabalho. Agora, eu realmente não posso dizer se há alguma inteligência do compilador por trás disso, provavelmente não e é apenas coincidência, mas não verifiquei como ele interage com outras opções do compilador que este projeto pode estar usando.

Por outro lado, no clang 3.3 (-O3), ambos os loops geram este código de 5 instruções:

  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>

O que só mostra que os compiladores são bastante diferentes e avançam a uma taxa muito mais rápida do que alguns programadores podem ter previsto vários anos atrás. Isso também significa que esse comentário não tem sentido e provavelmente está lá porque ninguém jamais verificou se ainda fazia sentido.

Resumindo - se você deseja otimizar para o melhor código possível (e você sabe como deve ser), faça isso diretamente na montagem e corte o "intermediário" (compilador) da equação, mas leve em consideração que o mais recente compiladores e HW mais recentes podem tornar essa otimização obsoleta. Na maioria dos casos, é muito melhor apenas deixar o compilador fazer esse nível de trabalho para você e se concentrar em otimizar as coisas grandes.

Outro ponto que deve ser feito - a contagem de instruções (assumindo que isso é o que o código dos OPs originais buscava), não é de forma alguma uma boa medida da eficiência do código. Nem todas as instruções foram criadas da mesma forma e algumas delas (movimentos simples de reg-para-reg, por exemplo) são realmente baratas, pois são otimizadas pela CPU. Outra otimização pode realmente prejudicar as otimizações internas da CPU, então, eventualmente, apenas o benchmarking adequado conta.

Um whileloop é frequentemente compilado como um do-whileloop com um desvio inicial para a condição, ou seja,

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

enquanto a compilação de um do-whileloop é a mesma sem o desvio inicial. Você pode ver que isso while()é inerentemente menos eficiente pelo custo do ramo inicial, que no entanto é pago apenas uma vez. [Compare com a maneira ingênua de implementação while,que requer tanto um desvio condicional quanto um desvio incondicional por iteração.]

Dito isso, eles não são alternativas comparáveis. É doloroso transformar um whileloop em do-whileloop e vice-versa. Eles fazem coisas diferentes. E, neste caso, as várias chamadas de método iria dominar totalmente o que quer que o compilador fez com whilecontrado-while.

A observação não é sobre a escolha da instrução de controle (do vs. while), é sobre o desenrolar do loop !!!

Como você pode ver, esta é uma função de comparação de string (elementos de string provavelmente tendo 2 bytes de comprimento), que poderia ter sido escrita com uma única comparação em vez de quatro em um atalho e expressão.

Esta última implementação é com certeza mais rápida, pois faz uma única verificação da condição de fim da string após cada comparação de quatro elementos, enquanto a codificação padrão envolveria uma verificação por comparação. Dito de outra forma, 5 testes por 4 elementos vs. 8 testes por 4 elementos.

De qualquer forma, isso funcionará apenas se o comprimento da string for um múltiplo de quatro ou tiver um elemento sentinela (de modo que as duas strings tenham a garantia de diferir além da strendborda). Muito arriscado!

Essa discussão de eficiência while vs. do é completamente inútil neste caso, já que não há corpo.

while (Condition)
{
}

e

do
{
}
while (Condition);

são absolutamente equivalentes.