Como os compiladores conseguem otimizar loops?

A princípio isso não parece possível. Se um loop executa uma ação N vezes, o tempo total deveria ser basicamente o custo dessa ação multiplicado por N. Só que na prática, quando compilamos com -O3, o resultado é bem diferente: o mesmo loop roda mais rápido, mesmo fazendo o mesmo trabalho.

E a culpa (ou o mérito) é de um pequeno trecho de código que se tornou quase uma lenda na história da otimização em C:

register int *to, *from;
register int count = (n + 7) / 8;

switch (n % 8) {
case 0: do { *to = *from++;
case 7:      *to = *from++;
case 6:      *to = *from++;
case 5:      *to = *from++;
case 4:      *to = *from++;
case 3:      *to = *from++;
case 2:      *to = *from++;
case 1:      *to = *from++;
        } while (--count > 0);
}

Este pequeno frame é o Duff Device criado por Tom Duff em 1983.

O que é o desenrolamento de loops?

Loop Unrolling (ou desenrolamento de loop) é uma técnica de otimização onde o compilador duplica o corpo do loop várias vezes para reduzir o custo do controle de iteração.

Em vez de checar a condição e incrementar o contador a cada passo, ele faz operações por iterações, diminuindo o número total de saltos no código.

for (int i = 0; i < n; ++i){
    copia[i] = origem[i];
}

se transforma em algo conceitualmente similar:

for (int i = 0; i < n; i += 4) {
    copia[i] = origem[i];
    copia[i+1] = origem[i+1];
    copia[i+2] = origem[i+2];
    copia[i+3] = origem[i+3];
}

Menos branches, mais instruções seguidas, mais chance de o processador aproveitar o pipeline e executar tudo de forma quase branchless, parecido com o que o SIMD faz.

O Duff Device foi a primeira vez que alguém usou essa ideia manualmente, antes de os compiladores modernos fazerem isso sozinhos.

É uma daquelas otimizações que parecem mágica até você perceber que o compilador só está tentando evitar o que humanos mais odeiam: repetições desnecessárias.

E porque isso funciona em C?

A lógica do Duff Device não é muito diferente de acessar vários elementos de um array de uma vez. Se copia e origem têm o mesmo tamanho, você consegue fazer a mesma operação em uma única iteração, processando múltiplas posições do vetor ao mesmo tempo. Isso reduz o overhead de controle do loop e deixa o processador mais livre para executar instruções em sequência, aumentando a eficiência geral.

O do-while sozinho é simples, executa a iteração uma vez e faz o teste da condição garantindo pelo menos uma execução.

O switch é um salto condicional que usa jump-table para ter tempo de execução O(1).

Agora, dentro de truque do Duff-Device: ele remove os breaks de propósito e coloca o switch dentro do do-while.

Isso cria efeitos simultâneos:

  1. O switch escolhe em qual ponto do loop começar
  2. O do-while continua repetindo o bloco inteiro várias vezes até completar todas as iterações.

Na prática, isso significa que você começa no case certo (alinhando as iterações que sobraram) e depois “cai” pelos demais cases sem saltos adicionais, repetindo tudo até terminar.

Cada execução do-while processa vários elementos do array, e o switch inicial só garante que você comece na posição correta.

Conclusão

Pode ser uma técnica útil em alguns casos, mas não na maioria.

É feio, parece gambiarra e seu compilador quando passa as flags -O3 ou -funroll-loops já adiciona os Duff-Devices automaticamente.

Porém se você estiver estudando programação ou pelo menos otimização de código fonte, complexidade de algoritmos vale a pena dar uama revisada.