O GCC é meio doido?!

Considere a seguinte situação:

int i = 0;
while (i < 10)
{
  /* Faz algo aqui */
  i++;
}

Considere que a variável ‘i’ seja o registrador ECX. O código que vocẽ espera que o GCC gere poderia ser algo assim:

  xor ecx,ecx
.loop:
  cmp ecx,10
  jge .exit_loop

  ; faz algo aqui

  inc ecx
  jmp .loop

.exit_loop:

Mas, se vocẽ compilar o código em C verá algo assim:

  xor ecx,ecx
  jmp .loop_test
.loop:

  ; faz algo aqui.

  inc ecx

.loop_test:
  cmp ecx,10
  jl  .loop

Mas, que &@#!*% é essa? Por que o GCC não segue o padrão mais óbvio, mais de acordo com o código-fonte, onde o teste, supostamente, deve ser feito antes de qualquer salto?

O GCC tenta resolver um problema criado a partir de uma otimização dos processadores Intel, desde o 486: Branch Prediction. A historia é a seguinte: Nesses processadores alguns cálculos internos são feitos antes que certas instruções sejam executadas. Um exemplo disso é o cálculo de endereços efetivos. A instrução:

mov eax,[ebx+ecx]

É executada em 1 ciclo de máquina porque o cálculo do endereço, dado pela soma de EBX e ECX, é feito cerca de 2 instruções antes de chegar nessa ai em cima. Do mesmo modo que o processador toma esses atalhos para o cálculo do endereço efetivo, ele também toma atalhos para saltos. Ou seja, o processador assume, baseado em estatísticas, que um salto condicional ocorrerá ou não antes que a instrução seja executada. Isso ajuda a manter os caches carregados com os pedaços de código que provavelmente serão executados.

O processador mantém um registro da quantidade de saltos que foram bem sucedidos e daqueles que não foram feitos. Se tiverem mais saltos que foram feitos do que os que não foram, então é a probabilidade do próximo salto condicional ser bem sucedido é maior que do que ele não ser feito…

O que o GCC faz é tentar manter quantidades maiores de saltos que serão (ou não) feitos do que os que não serão… Por isso ele inverte a lógica de JGE para JL e coloca o salto no final do código. A quantidade de saltos para trás será maior do que a quantidade de saltos para frente. O que ajuda a manter o loop no cache.

Pense nisso da seguinte forma: Se mais saltos forem feitos para frente e estiverem tão “longe” que o cache L1 tenha que ser invalidado, então cerca de 32 kB (nos processadores modernos) têm que ser recarregados da memória (ou do cache L2), causando um delay enorme (as minhas rotinas que usam o RDTSC sofrem disso… estou tentando garantir que isso não ocorra, tenham paciência, ok?)… Se o compilador garante que um tipo de salto ocorre mais que outros, então evitamos essa perda de performance.

Outra maneira de pensar é que saltos para trás são mais frequantes do que saltos para frente por causa dos loops… Dai, minimizar os saltos para frente deve ser uma prioridade do compilador.

E aqui vale um alerta: Escolha muito bem o padrão de testes das estruturas de controle de fluxo (if’s, while’s, for’s, switch’s, goto’s). Principalmente os if’s… Se seus if’s fazem muitos saltos para frente, e se seu código tem muitos if’s, você prejudicará o esquema do branch predition. Como regra geral, os if’s usam semântica invertida com relação ao teste:

if (x == 0) x++;

Tende a gerar código assim:

  or eax,eax
  jnz .skip      ; testa por eax != 0!
  inc eax
.skip

Se esse if estiver num loop e o valor de ‘x’ for diferente de zero na maioria das iterações, então muitos saltos serão feitos para frente, prejudicando o branch prediction. Isso pode te custar alguns ou muitos ciclos, dependendo da rotina. Claro que o exemplo acima é só uma demonstração do que o if faz. Esse alerta é válido mesmo para os if..else:

; if (x == 0) f(); else g();
  or eax,eax
  jnz .else
  call f
  jmp short .exit_if
.else:
  call g
.exit_if

Se a condição for atendida mais vezes (x == 0), então teremos um salto não realizado e um realizado (ambos entram na estatística). Neste caso, vale a pena inverter a lógica!

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