Quando, se alguma vez, o desenrolamento de loops ainda é útil?

Eu tenho tentado otimizar algum código extremamente crítico de desempenho (um algoritmo de sorting rápida que está sendo chamado milhões e milhões de vezes dentro de uma simulação de monte carlo) por desenrolamento de loop. Aqui está o loop interno que estou tentando acelerar:

// Search for elements to swap. while(myArray[++index1] < pivot) {} while(pivot < myArray[--index2]) {} 

Eu tentei desenrolar para algo como:

 while(true) { if(myArray[++index1] < pivot) break; if(myArray[++index1] < pivot) break; // More unrolling } while(true) { if(pivot < myArray[--index2]) break; if(pivot < myArray[--index2]) break; // More unrolling } 

Isso não fez absolutamente nenhuma diferença, então eu mudei de volta para a forma mais legível. Eu tive experiências semelhantes outras vezes que eu tentei desenrolar o loop. Dada a qualidade dos preditores de ramificação em hardware moderno, quando, se é que alguma vez, o loop desenrola ainda uma otimização útil?

O desenrolamento de loops faz sentido se você puder quebrar cadeias de dependencies. Isso dá a um processador fora de ordem ou superescalar a possibilidade de agendar melhor as coisas e, assim, rodar mais rápido.

Um exemplo simples:

 for (int i=0; i 

Aqui a cadeia de dependência dos argumentos é muito curta. Se você obtiver um stall porque você tem um cache-miss no array de dados, o cpu não pode fazer nada além de esperar.

Por outro lado, este código:

 for (int i=0; i 

poderia correr mais rápido. Se você obtiver uma falha de cache ou outra parada em um cálculo, ainda haverá outras três cadeias de dependência que não dependem da parada. Uma CPU fora de ordem pode executá-los.

Aqueles não fariam qualquer diferença porque você está fazendo o mesmo número de comparações. Aqui está um exemplo melhor. Ao invés de:

 for (int i=0; i<200; i++) { doStuff(); } 

Escreva:

 for (int i=0; i<50; i++) { doStuff(); doStuff(); doStuff(); doStuff(); } 

Mesmo assim, quase certamente não importa, mas agora você está fazendo 50 comparações em vez de 200 (imagine que a comparação seja mais complexa).

O desenrolar manual de laços em geral é em grande parte um artefato da história. É outra da crescente lista de coisas que um bom compilador fará por você quando for importante. Por exemplo, a maioria das pessoas não se incomoda em escrever x < <= 1 ou x += x vez de x *= 2 . Você acabou de escrever x *= 2 e o compilador irá otimizá-lo para você, o que for melhor.

Basicamente, há cada vez menos necessidade de adivinhar o seu compilador.

Independentemente da previsão de ramificação em hardware moderno, a maioria dos compiladores faz o loop de desenrolamento para você de qualquer maneira.

Valeria a pena descobrir quanto otimizações seu compilador faz por você.

Eu achei a apresentação de Felix von Leitner muito esclarecedora sobre o assunto. Eu recomendo que você leia. Resumo: Os compiladores modernos são MUITO inteligentes, então as otimizações manuais quase nunca são eficazes.

Pelo que eu entendi, os compiladores modernos já desenrolam loops onde apropriado – um exemplo é o gcc, se passado os flags de otimização, o manual diz que irá:

Unroll loops cujo número de iterações pode ser determinado em tempo de compilation ou após a input no loop.

Então, na prática, é provável que seu compilador faça os casos triviais para você. Cabe a você, portanto, certificar-se de que o máximo possível de seus loops seja fácil para o compilador determinar quantas iterações serão necessárias.

O desenrolamento de loop, seja o desenrolar da mão ou o desenrolamento do compilador, pode muitas vezes ser contraproducente, particularmente com CPUs x86 mais recentes (Core 2, Core i7). Conclusão: faça o benchmark de seu código com e sem o desenrolar do loop em qualquer CPU na qual você planeja implantar esse código.

Tentar sem saber não é o caminho para isso.
Esse tipo ocupa uma porcentagem alta do tempo total?

O desenrolar de todo o loop é reduzir a sobrecarga do loop de incrementar / decrementar, comparar a condição de parada e saltar. Se o que você está fazendo no ciclo exigir mais ciclos de instrução do que o próprio overhead de loop, você não verá muita melhoria percentualmente.

Veja um exemplo de como obter o máximo desempenho.

O desenrolamento de loop pode ser útil em casos específicos. O único ganho não é pular alguns testes!

Ele pode, por exemplo, permitir a substituição escalar, inserção eficiente de pré-busca de software … Você ficaria surpreso com o quão útil ele pode ser (você pode facilmente obter 10% de aceleração na maioria dos loops mesmo com -O3) desenrolando agressivamente.

Como foi dito anteriormente, depende muito do loop e o compilador e experimento são necessários. É difícil fazer uma regra (ou a heurística do compilador para desenrolamento seria perfeita)

O desenrolar do loop depende inteiramente do tamanho do seu problema. É totalmente dependente do seu algoritmo ser capaz de reduzir o tamanho em grupos menores de trabalho. O que você fez acima não se parece com isso. Não tenho certeza se uma simulação de monte carlo pode até ser desenrolada.

Eu bom cenário para desenrolamento de loop seria girar uma imagem. Desde que você poderia rodar grupos separados de trabalho. Para fazer isso funcionar, você teria que reduzir o número de iterações.

O desenrolamento de loop ainda é útil se houver muitas variables ​​locais dentro e com o loop. Para reutilizar esses registros mais em vez de salvar um para o índice de loop.

No seu exemplo, você usa uma pequena quantidade de variables ​​locais, não usando demais os registros.

A comparação (no final do loop) também é uma grande desvantagem se a comparação for pesada (isto é test instrução sem test ), especialmente se depender de uma function externa.

O desenrolamento de loops também ajuda a aumentar a conscientização do processador quanto à previsão de desvios, mas esses ocorrem de qualquer maneira.