Quando, se for o caso, o desenrolamento de loop ainda é útil?

93

Tenho tentado otimizar alguns códigos extremamente críticos para o desempenho (um algoritmo de classificação rápida que está sendo chamado milhões e milhões de vezes dentro de uma simulação de monte carlo) por meio do 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]) {}

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 mudei de volta para a forma mais legível. Tive experiências semelhantes outras vezes em que tentei desenrolar loop. Dada a qualidade dos preditores de branch no hardware moderno, quando, se alguma vez, o desenrolamento de loop ainda é uma otimização útil?

dsimcha
fonte
1
Posso perguntar por que você não está usando rotinas de classificação rápida de biblioteca padrão?
Peter Alexander
14
@Poita: Porque os meus possuem alguns recursos extras que eu preciso para os cálculos estatísticos que estou fazendo e são altamente ajustados para meus casos de uso e, portanto, menos gerais, mas mensuravelmente mais rápidos do que a biblioteca padrão. Estou usando a linguagem de programação D, que tem um otimizador de baixa qualidade, e para grandes arrays de floats aleatórios, ainda supero a classificação C ++ STL do GCC em 10-20%.
dsimcha

Respostas:

122

O desenrolamento do loop faz sentido se você pode quebrar as cadeias de dependência. Isso dá a uma CPU fora de ordem ou superescalar a possibilidade de programar melhor as coisas e, assim, funcionar mais rápido.

Um exemplo simples:

for (int i=0; i<n; i++)
{
  sum += data[i];
}

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

Por outro lado, este código:

for (int i=0; i<n; i+=4)
{
  sum1 += data[i+0];
  sum2 += data[i+1];
  sum3 += data[i+2];
  sum4 += data[i+3];
}
sum = sum1 + sum2 + sum3 + sum4;

poderia correr mais rápido. Se você obtiver uma perda de cache ou outro bloqueio em um cálculo, ainda existem três outras cadeias de dependências que não dependem do bloqueio. Uma CPU fora de serviço pode executá-los.

Nils Pipenbrinck
fonte
2
Obrigado. Eu tentei desenrolar loop neste estilo em vários outros lugares na biblioteca onde estou calculando somas e outras coisas, e nesses lugares funciona maravilhas. Tenho quase certeza de que o motivo é que isso aumenta o paralelismo do nível de instrução, como você sugere.
dsimcha
2
Boa resposta e exemplo instrutivo. Embora eu não veja como as paralisações em falhas de cache podem afetar o desempenho deste exemplo específico . Eu vim para explicar para mim mesmo as diferenças de desempenho entre as duas partes do código (em minha máquina, a segunda parte do código é 2 a 3 vezes mais rápida) observando que a primeira desativa qualquer tipo de paralelismo de nível de instrução nas pistas de ponto flutuante. O segundo permitiria a uma CPU superescalar executar até quatro acréscimos de ponto flutuante ao mesmo tempo.
Toby Brull
2
Lembre-se de que o resultado não será numericamente idêntico ao loop original ao calcular uma soma dessa maneira.
Barabas
A dependência do loop é um ciclo , a adição. Um núcleo OoO vai servir. Aqui, o desenrolamento pode ajudar o SIMD de ponto flutuante, mas isso não é sobre OoO.
Veedrac de
2
@Nils: Não muito; CPUs OoO x86 mainstream ainda são semelhantes o suficiente ao Core2 / Nehalem / K10. Recuperar o atraso após uma falha de cache ainda era muito pequeno, ocultar a latência do FP ainda era o principal benefício. Em 2010, CPUs que podiam fazer 2 cargas por clock eram ainda mais raras (apenas AMD porque o SnB ainda não foi lançado), então múltiplos acumuladores eram definitivamente menos valiosos para código inteiro do que agora (claro que este é um código escalar que deveria se auto-vetorizar , então quem sabe se os compiladores transformarão múltiplos acumuladores em elementos vetoriais ou em múltiplos acumuladores vetoriais ...)
Peter Cordes
25

Isso não faria nenhuma 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();
}

escrever:

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

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

No entanto, o desenrolamento manual de loop em geral é em grande parte um artefato da história. É mais uma da lista crescente de coisas que um bom compilador fará por você quando for importante. Por exemplo, a maioria das pessoas não se preocupa em escrever x <<= 1ou em x += xvez de escrever x *= 2. Você apenas escreve x *= 2e o compilador irá otimizá-lo para você da maneira que for melhor.

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

cletus
fonte
1
@Mike Certamente desligar a otimização é uma boa ideia quando fica confuso, mas vale a pena ler o link que Poita_ postou. Os compiladores estão se tornando extremamente bons nesse negócio.
dmckee --- gatinho ex-moderador,
16
@Mike "Sou perfeitamente capaz de decidir quando ou quando não fazer essas coisas" ... Duvido, a menos que você seja sobre-humano.
Sr. Boy,
5
@John: Não sei por que você diz isso; as pessoas parecem pensar que a otimização é algum tipo de arte negra que apenas compiladores e bons adivinhadores sabem fazer. Tudo se resume a instruções e ciclos e as razões pelas quais eles são gastos. Como já expliquei muitas vezes no SO, é fácil dizer como e por que esses recursos estão sendo gastos. Se eu tenho um loop que precisa usar uma porcentagem significativa de tempo e gasta muitos ciclos na sobrecarga do loop, em comparação com o conteúdo, posso ver isso e desenrolá-lo. O mesmo para içamento de código. Não é preciso ser um gênio.
Mike Dunlavey
3
Tenho certeza de que não é tão difícil, mas ainda duvido que você consiga fazer isso tão rápido quanto o compilador. Qual é o problema de o compilador fazer isso por você? Se você não gosta, basta desligar as otimizações e gastar seu tempo como se estivéssemos em 1990!
Sr. Boy,
2
O ganho de desempenho devido ao desenrolamento do loop não tem nada a ver com as comparações que você está salvando. Nada mesmo.
bobbogo 01 de
14

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

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

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

Peter Alexander
fonte
7
Essa é uma boa leitura, mas a única parte que achei que estava certa foi onde ele fala sobre como manter a estrutura de dados simples. O resto foi preciso, mas se baseia em uma suposição não declarada gigante - que o que está sendo executado tem que ser. No ajuste que faço, encontro pessoas se preocupando com registros e perdas de cache quando grandes quantidades de tempo estão indo para montanhas desnecessárias de código de abstração.
Mike Dunlavey,
3
"otimizações de mãos quase nunca são eficazes" → Talvez seja verdade se você for completamente novo na tarefa. Simplesmente não é verdade de outra forma.
Veedrac de
Em 2019 eu ainda fiz desdobramentos manuais com ganhos substanciais sobre as tentativas automáticas do compilador ... então não é tão confiável deixar o compilador fazer tudo. Parece que não se desenrola com tanta frequência. Pelo menos para c # eu não posso falar em nome de todos os idiomas.
WDUK
2

Pelo que eu entendi, os compiladores modernos já desenrolam loops quando apropriado - um exemplo sendo o gcc, se passado os sinalizadores de otimização, o manual diz que irá:

Loops de desenrolamento cujo número de iterações pode ser determinado em tempo de compilação ou na entrada no loop.

Portanto, 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.

Rich Bradshaw
fonte
Compiladores just in time geralmente não desdobram loops, as heurísticas são muito caras. Os compiladores estáticos podem gastar mais tempo nisso, mas a diferença entre as duas formas dominantes é importante.
Abel
2

O desenrolamento do loop, seja desenrolamento manual ou desenrolamento do compilador, pode muitas vezes ser contraproducente, particularmente com CPUs x86 mais recentes (Core 2, Core i7). Resumindo: compare seu código com e sem desenrolar de loop em quaisquer CPUs nas quais você planeja implantar esse código.

Paul R
fonte
Por que particularmente em CPUs x86 recet?
JohnTortugo
7
@JohnTortugo: CPUs x86 modernas têm certas otimizações para pequenos loops - veja, por exemplo, Loop Stream Detector no Core e arquiteturas Nehalem - desenrolar um loop de forma que não seja mais pequeno o suficiente para caber no cache LSD anula esta otimização. Consulte, por exemplo, tomshardware.com/reviews/Intel-i7-nehalem-cpu,2041-3.html
Paul R
1

Tentar sem saber não é a maneira de o fazer.
Esse tipo de trabalho ocupa uma alta porcentagem do tempo total?

Tudo o que o desenrolamento de loop faz é reduzir a sobrecarga de loop de incremento / decremento, comparação para a condição de parada e salto. Se o que você está fazendo no loop leva mais ciclos de instrução do que o próprio overhead do loop, você não verá muitas melhorias em termos percentuais.

Aqui está um exemplo de como obter desempenho máximo.

Mike Dunlavey
fonte
1

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

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

Porém, como foi dito antes, depende muito do loop e do compilador e da experiência são necessários. É difícil fazer uma regra (ou a heurística do compilador para desenrolar seria perfeita)

Kamchatka
fonte
0

O desenrolamento do loop depende inteiramente do tamanho do problema. É totalmente dependente de 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 ser desenrolada.

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

Jwendl
fonte
Eu estava desenrolando uma classificação rápida que é chamada do loop interno da minha simulação, não do loop principal da simulação.
dsimcha
0

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

Em seu exemplo, você usa uma pequena quantidade de variáveis ​​locais, não usando demais os registradores.

A comparação (para o final do loop) também é uma grande desvantagem se a comparação for pesada (ou seja, sem testinstrução), especialmente se depender de uma função externa.

O desenrolamento do loop também ajuda a aumentar a percepção da CPU para a previsão de ramificações, mas essas ocorrem mesmo assim.

LiraNuna
fonte