Antes
de falar de otimizações no gcc, é necessário primeiro definir
o que é uma otimização. O domínio que estamos trabalhando é o domínio
dos programas de computador, e sobre cada um deles vamos definir
uma função que retorna um valor. Esse valor é a métrica associada
ao programa. Métricas possíveis são o tempo que ele leva pra terminar,
ou a quantidade de memória que usa.
Em geral, estamos interessados no comportamento assintótico dessa
função. Para isso, a ferramenta utilizada é a notação big-O, cuja
definição pode ser encontrada, por exemplo, na
Wikipedia.
Assintoticamente, duas funções tem o mesmo big-O se as
duas crescem na mesma velocidade; e tem big-O diferentes,
caso contrário. Por exemplo, exp(x) cresce
mais rápido que x^2, que cresce mais rápido que log(x).
Isso é fundamental na análise de algoritmos. Nós sempre usamos
quicksort, ao invés de bubblesort, porque quicksort é O(n.log(n)) e
bubblesort é O(n^2).
Daí, concluímos que a melhor maneira de acelerar um programa
de computador é reescrevendo seu algoritmo de modo a reduzir
sua complexidade computacional. Infelizmente, isso nem sempre é
possível. Nos casos onde não existe algoritmo conhecido mais rápido,
o melhor com que você pode se contentar é procurar uma maneira
de acelerar seu programa, sem mudar a complexidade.
E isso é possível? A resposta é sim. Um algoritmo g(x)=k.f(x) é
mais rápido que f(x) sempre que k for menor que um. E como mudar esse k?
Mudando não o algoritmo, mas sim a implementação dele!
Um exemplo rápido é dado pelos dois programas abaixo,
que contam de 0 até 10e6, de um em um.
O segundo deles é 9% mais rápido que o primeiro,
usando o mesmo algoritmo, sendo que a única diferença é que
o segundo conta de trás pra frente.
Programa 1 Programa 2
Tempo: 0.05465s @2.4GHz Tempo: 0.04926s @2.4GHz
#include <stdio.h> #include <stdio.h>
int main(void) { int main(void) {
int i,j=0; int i,j=0;
for (i=0; i<10e6; i++) for (i=10e6-1; i>=0; i--)
j=j+1; j=j+1;
printf ("%d\n",j); printf ("%d\n",j);
return 0; return 0;
} }
|
Idealmente, você não deveria se preocupar com esses detalhes.
Um dos módulos de um compilador é o otimizador, que, como
o próprio nome indica, busca a implementação ótima para um dado
algoritmo. Infelizmente, um resultado teórico, derivado do
teorema da parada de Turing, diz que é impossível criar um
compilador que localize a implementação ótima de um programa,
no caso geral.
Para casos especifícos, você pode usar a força bruta para
otimizar seu programa, chegando a resultados como o
Superotimizador. Em todos os outros
casos, o melhor que você consegue é aplicar heurísticas.
E é exatamente isso que os compiladores do mercado fazem,
incluindo, entre eles, o gcc.
No caso específico do gcc, você pode escolher quais
heurísticas serão utilizadas, através de flags de compilação.
Porém, para escolher de maneira correta quais heurísticas utilizar,
é preciso compreender o mecanismo de funcionamento de cada
uma delas.
Antes de começar a destrinchar as heurísticas, é útil mencionar
qual é o ganho real das otimizações do gcc. Eu acredito
que não se deve falar do ganho das otimizações usando variáveis
como tempo, velocidade ou memória. A variável correta é o dólar.
Minha experiência é que o gcc, quando bem otimizado, faz seu
programa ficar tão rápido quanto o mesmo programa não otimizado,
mas rodando em uma máquina 200 dólares mais cara. Dependendo do
seu prazo de entrega, da quantidade de máquinas, ou do salário do programador, pode
ser mais vantajoso pagar uma máquina mais rápida, que pagar um
programador para mexer em flags de compilação.
Ainda hoje, eu me impressiono com a quantidade de gente que acredita
que o otimizador do gcc não funciona. Sempre tem alguém que pra dizer
que ligar o otimizador pode introduzir erros no seu código.
Isso é fud, e fud caduco ainda por cima. Há 10 anos
atrás isso era razoalvelmente verídico, mas o
compilador evoluiu bastante,
e o código do otimizador está bastante estável.
Entretanto, você sempre pode achar exemplos de código
que quebram ao ligar o otimizador. Todo mundo tem uma história
de estagiário pra contar, e a minha começa assim: certa vez, um
estagiário veio pedir para que eu revisasse um código dele,
que funcionava
sem otimização, mas dava output errado com a otimização ligada.
Após algum tempo checando o código, achei um trecho assim:
int funcao(int b) {
int a;
/* ... */
a+=b;
/* ... */
}
|
Ahá! Variável sem inicialização. Sem a otimização, o gcc
colocava zero, por default, dentro da variável. Com a otimização
ligada, aparecia um valor aleatório. Ou seja, o código não era C
válido, e o otimizador não se responsabiliza por código inválido.
Na imensa maioria dos casos, se o programa quebrar com o otimizador,
o problema está no seu código, e não no gcc. Felizmente, horas
de debugging podem ser evitadas se você tomar duas medidas simples:
-Wall (liga todos os warnings), e -Werror (transforma
os warnings em erros). Usando essas duas flags, o erro da variável
sem inicialização jamais teria acontecido.
Das heurísticas do gcc, uma das que tem resultado mais garantido
é a eliminação do frame pointer, na plataforma x86. Pra entender porque
isso acontece, basta olhar o histórico do processador. Ele é derivado
de uma linha que começou com o 8080, teve um fork para o Z80 e
continuou, via 8088, para o 8086, 80286 e em diante até os
processadores atuais. Uma característica comum a todos é o número
muito reduzido de registradores. Com poucos registradores, o
compilador precisa alocar variáveis em memória, o que é bem mais
lento.
Soluções em hardware pra isso existem. O Z80 tinha o opcode EXX, que
habilitava um banco alternativo de registros, e os processadores mais
recentes tem o mecanismo de register renaming. Mas, do ponto
de vista do conjunto de opcodes, ainda estamos limitados a apenas
oito registradores: eax, ebx, ecx, edx, esi, edi, ebp e esp.
O registrador esp é o stack pointer, e não pode ser usado para
aritmética. O ebp é usado, em compiladores C, como frame pointer.
Para entender a função do frame pointer, é necessário entender como
o C aloca as suas variáveis.
Variáveis globais são declaradas como posições de memórias fixas
na seção de dados do processo. Já as variáveis locais e os parâmetros
de função ficam na pilha do processador, e podem ser endereçadas pelo
esp. Daí, uma variável local será acessada como [esp-4], e um parâmetro
como [esp+8], por exemplo. Porém, o esp não fica fixo dentro da função:
ele é alterado cada vez que você faz um push ou um pop. Se as suas
variáveis estiverem sendo endereçadas indiretamente pelo esp, elas
serão perdidas!
Pra isso usa-se o frame pointer. No começo de cada função, o
valor do esp é copiado para o ebp. Dessa maneira, as variáveis e
parâmetros podem ser acessados, mesmo que o valor de esp mude. Por
outro lado, se antes você tinha 7 registradores pra fazer aritmética,
agora tem só 6, porque o ebp foi alocado como frame pointer.
O gcc, porém, é um compilador esperto. Ele sabe que após um push eax,
o esp foi decrementado de 4. Então, a variável que antes era [esp-8],
passa a ser [esp-4]. Sempre que o comportamento do esp for previsível
em tempo de compilação, o frame pointer pode ser descartado. E, pra isso,
existe o flag do gcc -fomit-frame-pointer, que indica que o
uso de frame pointer não é necessário.
O registrador adicional certamente trará um ganho de velocidade
ao seu programa. Talvez a única desvantagem seja na hora de
fazer debugging em baixo nível, pois o debugger não tem como
saber a qual variável se refere [esp-4], quando o esp está andando.
Mas fazer debugging em cima de código otimizado não é esperto de
qualquer maneira, já que o CSE costuma destruir a estrutura do
código.
Como o ganho principal do -fomit-frame-pointer é liberar
um registrador, o efeito dele pode ser facilmente sentido quando
suas funções tiverem muitas variáveis. Vejamos o exemplo abaixo:
#include <stdio.h>
int count(void) {
int a,b=0,c=0,d=0,e=0,f=0,g=0;
for (a=0; a<10; a++) {
g+=1; f+=g; e+=f;
d+=e; c+=d; b+=c;
}
return b;
}
int main(void) {
printf ("%d\n",count());
return 0;
}
|
Você pode ver o resultado final da compilação usando o flag -S.
Com esse flag, o gcc gera a saída em assembly, ao invés de gerar um
objeto binário. Adicionalmente, você pode usar também -masm=intel.
Eu, particularmente, acho a sintaxe Intel mais clara que a sintaxe AT&T
para assembly. O código completo é muito extenso, então vou copiar
só o loop principal:
Sem -fomit-frame-pointer Com -fomit-frame-pointer
L6: L6:
inc ecx inc ecx
add eax, ecx add eax, ecx
add ebx, eax add ebx, eax
add esi, ebx add esi, ebx
add edi, esi add edi, esi
add DWORD PTR [ebp-16], edi add ebp, edi
dec edx dec edx
jns L6 jns L6
|
Eis a diferença! Sem o flag, os registradores acabaram, e
ele teve que alocar a variável b na posição de memória [ebp-16].
Ligando o flag, ele ganhou um registrador a mais, e a variável
foi encaixada no próprio ebp. Se esse loop for chamado dentro uma
seção crítica de código, a diferença pode ser considerável.
Existe ainda um outro ganho associado ao -fomit-frame-pointer.
Entretanto, esse ganho não é um bom sinal, e está usualmente associado
a uma deficiência de design. Veja o código abaixo, por exemplo:
#include <stdio.h>
int dup(int a) {
return a*2;
}
int main(void) {
printf ("%d\n",dup(4));
return 0;
}
|
Eliminar o frame pointer é uma grande diferença para a função dup, como
pode ser visto abaixo.
Sem -fomit-frame-pointer Com -fomit-frame-pointer
_dup: _dup:
push ebp mov eax, DWORD PTR [esp+4]
mov ebp, esp add eax, eax
mov eax, DWORD PTR [ebp+8] ret
pop ebp
add eax, eax
ret
|
De fato, quando o frame pointer não é necessário, também
não existe necessidade de copiar o seu valor do esp no início
da função, e nem mesmo de salvar o frame pointer anterior,
em caso de funções encadeadas. Mas então, onde está o erro de
design?
O erro é que esse ganho só tem relevância quando a função
é muito pequena. Se a eliminação de três simples opcodes deu
algum ganho de velocidade na função, isso indica que essa
função deveria estar inline. Na próxima seção veremos como
isso pode ser feito.