Qual é a técnica de inversão de loop?

89

Eu estava lendo um documento que fala sobre técnicas de otimização do compilador just-in-time (JIT) para Java. Um deles era "inversão de loop". E o documento diz:

Você substitui um whileloop regular por um do-whileloop. E o do-whileloop é definido dentro de uma ifcláusula. Essa substituição leva a dois saltos a menos.

Como funciona a inversão de loop e como ela otimiza nosso caminho de código?

NB: Seria ótimo se alguém pudesse explicar com um exemplo de código Java e como o JIT o otimiza para código nativo e por que é ideal em processadores modernos.

Tentando
fonte
2
Não é algo que você faria com seu código-fonte. Isso acontece no nível do código nativo.
Marko Topolnik
2
@MarkoTopolnik eu sei. Mas eu quero saber como o JIT faz isso em nível de código nativo. Obrigado.
Tentativa de
1
que legal, há uma página da wikipedia sobre isso com muitos exemplos en.wikipedia.org/wiki/Loop_inversion . O exemplo C é igualmente válido em Java.
Benjamin Gruenbaum
Algum tempo atrás, inspirado por uma das perguntas sobre o SO, conduzi uma pequena pesquisa sobre esse assunto, talvez os resultados sejam úteis para você: stackoverflow.com/questions/16205843/java-loop-efficiency/…
Adam Siemion
É a mesma coisa que onde a condição de loop geralmente é colocada no final (independentemente de haver menos saltos realizados), apenas para que haja menos instruções de salto (1 vs 2 por iteração)?
extremeaxe5,

Respostas:

108
while (condition) { 
  ... 
}

Fluxo de trabalho:

  1. verificar condição;
  2. se falso, pula para fora do loop;
  3. execute uma iteração;
  4. pule para cima.

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

Fluxo de trabalho:

  1. verificar condição;
  2. se falso, pula para além do loop;
  3. execute uma iteração;
  4. verificar condição;
  5. se verdadeiro, pule para a etapa 3.

Comparando esses dois, você pode facilmente ver que o último pode não fazer nenhum salto, desde que haja exatamente uma etapa no loop e, geralmente, o número de saltos será um a menos que o número de iterações. O primeiro terá que voltar para verificar a condição, apenas para sair do loop quando a condição for falsa.

Os saltos nas arquiteturas modernas de CPU com pipeline podem ser bastante caros: como a CPU está terminando a execução das verificações antes do salto, as instruções além desse salto já estão no meio do pipeline. Todo esse processamento deve ser descartado se a previsão do branch falhar. A execução posterior é atrasada enquanto o pipeline está sendo reprimido.

Explicando a previsão de desvio mencionada : para cada tipo de salto condicional, a CPU possui duas instruções, cada uma incluindo uma aposta no resultado. Por exemplo, você colocaria uma instrução dizendo " pule se não for zero, apostando no não zero " no final de um loop, porque o salto terá que ser feito em todas as iterações, exceto na última. Dessa forma, a CPU começa a bombear seu pipeline com as instruções que seguem o destino de salto, em vez daquelas que seguem a própria instrução de salto.

Nota importante

Por favor, não tome isso como um exemplo de como otimizar ao nível do código-fonte. Isso seria totalmente equivocado, pois, como já ficou claro em sua pergunta, a transformação da primeira forma para a segunda é algo que o compilador JIT faz rotineiramente, completamente por conta própria.

Marko Topolnik
fonte
51
Essa nota no final é uma coisa muito, muito importante, de fato.
TJ Crowder
2
@AdamSiemion: O bytecode gerado para o do-whilecódigo-fonte fornecido é irrelevante, porque na verdade não o escrevemos. Escrevemos o whileloop e deixamos o compilador e o JIT conspirarem para melhorá-lo para nós (por meio da inversão do loop) se / conforme necessário.
TJ Crowder
1
@TJCrowder +1 para o acima, mais a nota para Adam: nunca considere o bytecode ao pensar sobre as otimizações do compilador JIT. Bytecode está muito mais próximo do código-fonte Java do que do código real compilado por JIT sendo executado. Na verdade, a tendência nas línguas modernas é não ter bytecode como parte da especificação da linguagem.
Marko Topolnik
1
Teria sido mais informativo a nota importante foi explicada um pouco mais. Por que seria totalmente equivocado?
arsaKasra
2
@arsaKasra É equivocado porque em geral a legibilidade e a estabilidade superam as otimizações no código-fonte. Especialmente com a revelação de que o JIT faz isso por você, você não deve tentar a (muito micro) otimização sozinho.
Radiodef
24

Isso pode otimizar um loop que sempre é executado pelo menos uma vez.

Um whileloop regular sempre voltará ao início pelo menos uma vez e saltará para o final uma vez no final. Um exemplo de um loop simples executado uma vez:

int i = 0;
while (i++ < 1) {
    //do something
}  

Um do-whileloop, por outro lado, pulará o primeiro e o último salto. Aqui está um loop equivalente ao acima, que será executado sem saltos:

int i = 0;
if (i++ < 1) {
    do {
        //do something
    } while (i++ < 1); 
}
Keppil
fonte
1 por estar correto e primeiro, considere adicionar um exemplo de código. Algo como boolean b = true; while(b){ b = maybeTrue();}a boolean b;do{ b = maybeTrue();}while(b);deve bastar.
Benjamin Gruenbaum
Não se preocupe. Isso meio que invalida a linha de abertura da resposta, fwiw. :-)
TJ Crowder
@TJ Bem, ainda não otimizará um loop que não foi inserido, haverá um salto em ambos os casos.
Keppil
Ah sim. Desculpe, eu estava lendo isso para significar que você não pode aplicá-lo a loops que não entraram em loop pelo menos uma vez (em vez de não ajudá-los). Com você agora. :-)
TJ Crowder
@Keppil Você provavelmente deve deixar explícito que, no caso em que temos um grande número de iterações X, salvaremos apenas um único salto entre as X.
Manuel Selva
3

Vamos examiná-los:

A whileversão:

void foo(int n) {
    while (n < 10) {
       use(n);
       ++n;
    }
    done();
}
  1. Primeiro, testamos ne verificamos done();se a condição não é verdadeira.
  2. Então usamos e incrementamos n.
  3. Agora voltamos à condição.
  4. Enxágüe, repita.
  5. Quando a condição não for mais verdadeira, passamos para done().

A do-whileversão:

(Lembre-se de que não fazemos isso no código-fonte [isso introduziria problemas de manutenção], o compilador / JIT faz isso por nós.)

void foo(int n) {
    if (n < 10) {
        do {
            use(n);
            ++n;
        }
        while (n < 10);
    }
    done();
}
  1. Primeiro, testamos ne verificamos done();se a condição não é verdadeira.
  2. Então usamos e incrementamos n.
  3. Agora testamos a condição e voltamos para ver se é verdade.
  4. Enxágüe, repita.
  5. Quando a condição não é mais verdadeira, fluímos (não saltamos) para done().

Então, por exemplo, se ncomeça sendo 9, nunca pulamos na do-whileversão, enquanto na whileversão temos que voltar ao início, fazer o teste e depois voltar ao final quando vemos que não é verdade .

TJ Crowder
fonte
3

A inversão de loop é uma técnica de otimização de desempenho que melhora o desempenho, pois o processador pode obter o mesmo resultado com menos instruções. Isso deve melhorar principalmente o desempenho em condições de limite.

Este link fornece outro exemplo de inversão de loop. Em algumas arquiteturas em que decremento e comparação são implementados como um único conjunto de instruções, faz sentido converter um loop for em um while com decremento e operação de comparação.

A Wikipedia tem um exemplo muito bom e estou explicando-o aqui novamente.

 int i, a[100];
  i = 0;
  while (i < 100) {
    a[i] = 0;
    i++;
  }

será convertido pelo compilador para

  int i, a[100];
  i = 0;
  if (i < 100) {
    do {
      a[i] = 0;
      i++;
    } while (i < 100);
  }

Como isso se traduz em desempenho? Quando o valor de i é 99, o processador não precisa realizar um GOTO (que é necessário no primeiro caso). Isso melhora o desempenho.

Anirudhan J
fonte