Otimizações automáticas (II)

O texto abaixo mostra algumas das otimizações que as opções -O# ativam. Embora essas otimizações ajudem muito é sempre bom lembrar que é bom você dar uma olhada no código gerado, no caso de funções críticas.

Dead Code Elimination (DCE)

Essa otimização é óbvia: Todo código que não será executado é eliminado do programa. Um caso desses é esse qaui:

  if (x)
    return 0;
  else
    return 1;

  /* Daqui pra baixo o código é eliminado (até o final da função)! */

Common Subexpression Elimitation (CSE)

Certas expressões, repetidas no código, são eliminadas com o intuito de serem feitas apenas uma vez, por exemplo:

  dest[2*i+1] = src[2*i+1];

O compilador substituirá isso por:

  _tmp = 2*i+1;
  dest[_tmp] = src[_tmp];

Code Motion

Às vezes colocamos código dentro de um loop que podem muito bem ser colocada fora de um. É o caso de:

  for (i = 0; i < n; i++)
  {
    x = y;
    buffer[x+i] = i;
  }

O compilador percebe que ‘x’ está sendo inicializado com o valor de ‘y’  ‘n’ vezes e, através do code motion ele move a inicialização para fora do loop:

  x = y;
  for (i = 0; i < n; i++)
    buffer[x+i] = i;

O problema que tivemos com a rotina fill(), descrita neste post, provavelmente é um tipo de code motion:

  t = rdtsc();
  /* Um monte de coisas aqui que nada têm haver com 't'. */
  t = rdtsc() - t;

O compilador entendeu que poderia mover a última linha para junto da primeira já que, entre elas, nenhuma das instruções lidavam com a variável ‘t’.

Instruction Scheduling

Outro tipo de code motion, mais sutil, é o rearranjo de instruções para agilizar o uso das pipelines do processador. Já felei delas… cada “core” de seu processador tem duas unidades de execução. Uma chamada U e a outra V. Cada “core” tem a capacidade de executar duas instruções, em linguagem-de-máquina, ao mesmo tempo. Só que isso só acontece se as instruções estiverem perfeitamente arranjadas.

Outra coisa que o perfeito arranjo garante é que certas instruções não gastem ciclos adicionais “esperando” que outra instrução sendo executada em paralelo termine… Por exemplo:

  mov ecx,edx            /* Executa na pipeline U */
  xor eax,eax            /* Executa na pipeline V */
  mov ebx,offset x       /* Executa na pipeline U e põe a V em espera */
  mov dword ptr [ebx],1  /* Executa na pipeline U */

Essas duas instruções em vermelho não podem ser  “paralelizadas” porque EBX é inicializado na primeira instrução e usado como ponteiro na outra. A segunda instrução precisa esperar a primeira terminar. O compilador, através do scheduling poderia rearranjar o codigo acima assim:

  mov ebx,offset x       /* U */
  mov ecx,edx            /* V */
  xor eax,eax            /* U */
  mov dword ptr [ebx],1  /* V */

Colocando as duas instruções que não mexem com EBX no meio dos dois movs faz com que este fragmento de código execute em apenas 2 ciclos. O fragmento anterior executa em 3 (e possivelmente tem a penalidade de mais 1, mas deixo para explicar isso outro dia — Um bom material para entender essas idiossincrasias é o livro Zen and The Art of Code Optimization, de Michael Abrash).

As opções -fschedule-insns e -fschedule-insns2 habilitam o scheduler…

Unroll loops

Quando temos pequenos loops, o compilador pode “desenrolá-los” para garantir melhor performance:

  for (i = 0; i < 4; i++)
    buffer[i] = i;

Pode ser que o compilador desenrole esse loop assim:

  buffer[0] = 0;
  buffer[1] = 1;
  buffer[2] = 2;
  buffer[3] = 3;

Branch probabilities

Essa é uma otimização interessante, mas é feita em dois passos. A documentação do gcc diz que, se você compilar seu código com a opção -fprofile-arcs, e executar o programa, um arquivo será gerado com as probabilidades dos saltos executados pelo programa. Compilando de novo. sem a opção acima, mas com a opção -fbranch-probabilities, o compilador saberá como otimizar melhor os saltos.

Lembro que saltos são feitos não somente em loops, mas em qualquer chamada de função e controle de fluxo (ifs, switches, goto, etc.).

Se quiser seu código bem afinadinho, faça assim:

  $ gcc -O3 -fomit-frame-pointers -fprofile-arcs -o test test.c
  $ ./test
  $ gcc -O3 -fomit-frame-pointers -fbranch-probabilities -o test test.c

A opção -O3 automaticamente liga -fbranch-probabilities, mas nunca é demais ter certeza, né?

Essa otimização parece não ser lá grande coisa, mas entenda que os processadores da Intel (também os da AMD), desde o Pentium original, possuem um recurso chamado branch prediction. Os processadores mais antigos não sabiam para que lado um salto ocorreria até que a instrução fosse executada… Isso causa degradação de performance porque o processador tem que calcular o endereço de destino (que pode ser até mesmo um ponteiro) somente na hora do salto. Com o branch prediction o endereço pode ser calculado pouco antes da execução do salto mas, mesmo assim,  existem casos em que a CPU não tem como saber pra que lado o saldo ocorrerá… Para solucionar isso, existe um algorítimo que prevê, baseado na estatística dos últimos saltos, para que lado ele ocorrerá!

Se tivermos saltos aleatórios (para frente e para trás), então o algorítimo de previsão de saltos (branch prediction) não será eficiente e pode até prejudicar a performance mais do que deveria, já que todo salto não “adivinhado” corretamente causa uma limpeza da chamada fila de pré-busca (prefetch queue) e, talvez, do cache L1, dependendo da distância do salto. Uma vez limpos, precisam ser preenchidos de novo antes que o processador recomece a executar instruções.

Daí, essa otimizaçẽo é muito importante se performance é o que você tem em mente!

Você deve ter reparado que as otimizações automáticas também ligam o flag -fguess-branch-probabilities. Esse flag indica ao compilador que tente adivinhar as probabilidades dos saltos se –fprofile-arcs não tiver sido usado na compilação anterior à execução do programa. Essa adivinhação é eficaz, mas não é tão boa quanto à estatística coletada…

É só isso?!

É óbvio que NÂO! Existem trocentas opções de otimização e controle de compilação no gcc. Essa é uma das diferenças essenciais entre ele e outros compiladores meia-boca como o C Compiler and Linker da Microsoft: No gcc você pode controlar quase todo o processo de compilação e linkagem (existe essa palavra?).

Então Read The Finest Manual (aqui), meus amigos…

Anúncios

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s