Otimização de código

Em programação de computador , a otimização de código é a prática de melhorar a eficiência do código de computador de um programa de software ou biblioteca. Essas melhorias geralmente permitem que o programa resultante seja executado mais rapidamente, ocupe menos memória , limite seu consumo de recursos (por exemplo, arquivos ) ou consuma menos energia elétrica .

Princípios de otimização

A regra número um de otimização é que ela só deve ocorrer depois que o programa estiver em execução e atender às especificações funcionais . A experiência mostra que aplicar otimizações de código de baixo nível antes que essas duas condições sejam atendidas é na maioria das vezes uma perda de tempo e é prejudicial à clareza do código e à operação adequada do programa:

"Otimização prematura é a raiz de todo o mal. "

- Donald Knuth , citando Dijkstra

No entanto, esta citação, truncada, é muitas vezes mal interpretada. A versão completa é:

“Você deve esquecer as pequenas otimizações locais, digamos, 97% do tempo: a otimização prematura é a raiz de todos os males. "

- Donald Knuth

A citação original indica que geralmente durante a escrita de um código, pode-se deixar de lado as otimizações locais, de baixo nível (reescrever em assembler, desenrolamento de loops, etc). É possível interpretar esta citação deduzindo dela que as otimizações de alto nível relativas à escolha de algoritmos ou da arquitetura de um projeto devem vir antes das de baixo nível. Portanto, é apenas no final da escrita do programa, uma vez que a análise mostra que um detalhe de baixo nível é crítico que pode eventualmente precisar ser alterado:

“O que Hoare e Knuth estão realmente dizendo é que os engenheiros de software devem se preocupar com outras questões (como um bom design de algoritmo e boas implementações desses algoritmos) antes de se preocupar com micro-otimizações, como quantos ciclos de CPU uma instrução específica consome. "

- Randall Hyde, ACM Ubiquity Vol. 10, Edição 3

Pelo contrário, quanto mais o projeto cresce, mais essas otimizações de alto nível serão difíceis, onerosas (em termos de tempo, dificuldade e orçamento) ou mesmo impossíveis de realizar.

Os compiladores mais recentes executam automaticamente uma série de otimizações que seriam tediosas de executar manualmente e que tornariam o código-fonte menos legível .

A otimização manual local pode ser necessária em casos muito específicos, mas as medições mostram que em máquinas RISC que têm um alto número de registros e onde a eficiência requer o agrupamento de instruções idênticas para se beneficiar do efeito pipeline . , O otimizador de um compilador C geralmente fornece código mais eficiente do que aquele que seria escrito em assembler por um programador experiente (o que nunca foi o caso em máquinas CISC ). E além disso este código é muito mais fácil de manter, porque as instruções em C permanecem em uma ordem ligada à inteligibilidade do código apenas e não às especificidades da máquina: nos otimizadores atuais, de fato, a máquina ordena associada a uma instrução já não estão necessariamente em posição contígua, por razões de eficiência de execução. Isso torna o código de montagem gerado particularmente indecifrável.

Prática de otimização

Para monitorar a eficácia de uma otimização, o desenvolvedor conta com testes de desempenho , ou seja, com medidas objetivas do tempo de processamento e do tamanho da memória alocada .

Reduzir o tamanho dos dados residentes na memória é complexo, pois liberar uma área de memória raramente disponibiliza a memória para o sistema operacional.

Localização do código para otimizar

Para estimar o tempo e a memória necessários para cada parte do programa, os desenvolvedores realizam o perfil do código . Não é incomum que uma grande parte do tempo seja gasta executando um pequeno trecho de código, esse trecho de código é chamado de " gargalo ".

O software de criação de perfil é responsável por contar o número de execuções de cada função e os ciclos do microprocessador correspondentes durante a execução.

Diferentes abordagens de otimização

Existem várias abordagens para otimizar um código:

no nível algorítmico, escolhendo um algoritmo de menor complexidade matemática e estruturas de dados adequadas;
no nível da linguagem de desenvolvimento , ordenando as instruções da melhor maneira possível e usando as bibliotecas disponíveis;
localmente usando uma linguagem de baixo nível, que pode ser C ou, para as necessidades mais críticas, linguagem assembly .

Otimização Algorítmica

A otimização algorítmica consiste em aplicar sucessivas transformações matemáticas ao código que preservam a especificação do programa e ao mesmo tempo reduzem o consumo de recursos.

Otimizações usando ferramentas de linguagem

O uso de funções diferentes ou mesmo bibliotecas completas diferentes pode otimizar o programa.

Otimização alterando o idioma usado

Na prática, os aplicativos com muita E / S lenta podem ser otimizados sendo reescritos em uma linguagem como Haskell ou Python.

Um aplicativo que requer muita computação e alocação de memória pode ser otimizado sendo reescrito em uma linguagem como C ou C ++.

Otimização automática

Os compiladores geralmente são capazes de fazer otimizações locais, que nenhum desenvolvedor pensaria à primeira vista.

Para a linguagem C, isso pode considerar:

variáveis e registros locais;
funções não implementadas em assembler como uma função;
o switch, que são ótimos.

No entanto, pode-se ajudar muito o compilador declarando variáveis com palavras-chave conste / ou restrictquando possível; caso contrário, o compilador não pode saber se uma área da memória é acessível por outras referências e desabilitará as otimizações (fenômeno conhecido como apelidos de memória).

Exemplos

Usando variáveis locais para evitar apelidos de memória

O código C ++ a seguir, em geral, será mal otimizado pelo compilador porque geralmente é incapaz de saber se o código no loop modifica o contador de iteração ou não: um ponteiro ou uma referência pode modificá-lo.

void MyClass::DoSomething() const { for( int i=0; i<m_nbrElements; ++i ) { void *ptr = GetSomePtr(); .... } }

Nesta versão, indicamos claramente que usamos uma série de iterações fixadas com antecedência e que nunca serão modificadas, permitindo que o compilador execute otimizações mais agressivas:

void MyClass::DoSomething() { const int nbrElements = m_nbrElements; for( int i=0; i<nbrElements; ++i ) { .... } } Uma especificidade do binário: a mudança

Uma das primeiras otimizações foi dividir e multiplicar por uma potência de 2.

Na verdade, a computação atual é baseada no binário, uma vez que usa como elemento básico o transistor (e, historicamente, anteriormente o relé ) que permite apenas dois valores diferentes.

Portanto, implementamos logicamente as operações de deslocamento à esquerda e à direita em linguagem de máquina .

De fato, em binário , deslocar um número em um ponto para a esquerda o multiplica por 2.

Assim, 2 ( ) deslocado por 1 bit resulta em 4 ( ).

10_ {2}

100_ {2}

5 ( ) deslocado em 2 bits resulta em 20 ( ) .

101_ {2}

10100_ {2}

5 * 2 ^ {2} = 20

Isso também funciona para a divisão, deslocando os bits para a direita.

100 ( ) deslocado 3 bits para a direita, portanto, dá 12 ( ) porque estamos trabalhando com inteiros.

1100100_ {2}

100/2 ^ {3} = 12,5

1100_ {2}

Toda a aritmética de um processador é, na verdade, a aritmética do anel de, por exemplo. E assim, todos os números primos com têm um inverso, e é possível realizar uma divisão por qualquer um desses números em uma única instrução. Por exemplo, no anel inteiro de 32 bits, dividir por 3 é o mesmo que multiplicar por 2863311531. Dividir por 14 é multiplicar por 3067833783 e depois dividir por 2. Portanto, é possível com duas instruções. Os compiladores sabem fazer essas otimizações, mas para isso o divisor deve ser conhecido na compilação. ${\ mathbb {Z}} / 2 ^ {{32}} {\ mathbb {Z}}$ $2 ^ {32}$

A divisão no caso geral é uma instrução cara em tempo de computador e, além disso, ainda não está disponível na grande maioria dos processadores do tipo RISC .

A palavra-chave inline de C

A palavra-chave inline anexada a uma função diz ao compilador que ele deve tentar estender essa função . Considere, por exemplo, o seguinte código C:

inline int f(int a, int b) { return a * b; } int g (int a) { switch (a) { case 10: return f(a, a); case 11: case 12: return f(a - 2, a); case 1200: return f(a - 2, a); default: return f(a, a); } }

Uma compilação com gcc -O4 -S dá, no assembler i386:

.file "opt.c" .text .p2align 4,,15 .globl g .type g, @function g: pushl %ebp movl %esp, %ebp movl 8(%ebp), %edx cmpl $12, %edx jg .L14 leal -2(%edx), %eax cmpl $11, %edx jge .L15 movl $100, %eax cmpl $10, %edx .L17: je .L2 movl %edx, %eax .L15: imull %edx, %eax .L2: popl %ebp ret .p2align 4,,7 .L14: movl $1437600, %eax cmpl $1200, %edx jmp .L17 .size g, .-g .section .note.GNU-stack,"",@progbits .ident "GCC: (GNU) 3.3.2 (Mandrake Linux 10.0 3.3.2-6mdk)"

Isso poderia ser traduzido, para facilitar o entendimento, pelo seguinte código C:

int g(int a) { int eax, b; if (a > 12) /* cas a == 1200 */ goto L14; eax = a - 2; if (a >= 11) /* cas a == 11 ou a == 12 */ goto L15; eax=100; /* = 10 * 10 */ b=10; L17: if (a == b) /* cas a == 10 */ goto L2; /* cas "default" */ eax=a; L15: eax=eax*a; L2: return eax; L14: eax = 1437600; /* = 1200*(1200-2) */ b = 1200; goto L17; }

Podemos notar por exemplo que a função 'f' não foi gerada, mas seu código foi incorporado diretamente na função 'g' (a palavra-chave 'inline' permite forçar este tipo de otimização em C )

Notas e referências

" Devemos esquecer as pequenas eficiências, digamos cerca de 97% das vezes: a otimização prematura é a raiz de todos os males. "
(em) " Otimização de memória " em redis.io (acessado em 25 de março de 2020 )

Veja também

links externos

A falácia da otimização prematura, de Randall Hyde, explicando a citação de Donald Knuth e sua interpretação errônea
Otimização prematura por Charles Cook nesta mesma citação de Donald Knuth.