Como documentar e ensinar aos outros código "computacionalmente intensivo" otimizado além do reconhecimento?

Ocasionalmente, há 1% de código que é intensivamente computacionalmente e precisa do tipo mais pesado de otimização de baixo nível. Exemplos são processamento de vídeo, processamento de imagem e todos os tipos de processamento de sinal, em geral.

Os objetivos são documentar e ensinar as técnicas de otimização, para que o código não se torne insustentável e propenso à remoção por desenvolvedores mais recentes. (*)

(*) Não obstante a possibilidade de que a otimização específica seja completamente inútil em algumas futuras CPUs imprevisíveis, de modo que o código seja excluído de qualquer maneira.

Considerando que as ofertas de software (comercial ou de código aberto) mantêm sua vantagem competitiva ao ter o código mais rápido e fazer uso da mais nova arquitetura de CPU, os criadores de software geralmente precisam ajustar o código para acelerar o processo e obter a mesma saída por um determinado período. lista de tarefas, tolerando uma pequena quantidade de erros de arredondamento.

Normalmente, um gravador de software pode manter muitas versões de uma função como documentação de cada reescrita de otimização / algoritmo que ocorre. Como alguém disponibiliza essas versões para que outras pessoas estudem suas técnicas de otimização?

Palavras-chave:

• Código legível limpo vs código rápido e difícil de ler. Quando cruzar a linha?

Resposta curta

Mantenha as otimizações locais, torne-as óbvias, documente-as bem e facilite a comparação das versões otimizadas entre si e com a versão não otimizada, tanto em termos de código fonte quanto de desempenho em tempo de execução.

Resposta completa

Se essas otimizações realmente são importantes para o seu produto, você precisa saber não apenas por que as otimizações foram úteis antes, mas também fornecer informações suficientes para ajudar os desenvolvedores a saber se serão úteis no futuro.

Idealmente, você precisa consagrar o teste de desempenho ao seu processo de construção, para descobrir quando as novas tecnologias invalidam as otimizações antigas.

Lembrar:

A primeira regra de otimização de programa: não faça isso.

A Segunda Regra da Otimização de Programas (somente para especialistas!): Não faça isso ainda. "

- Michael A. Jackson

Para saber se agora é a hora, é necessário fazer comparações e testes.

Como você mencionou, o maior problema com código altamente otimizado é que é difícil manter, portanto, na medida do possível, é necessário manter as partes otimizadas separadas das partes não otimizadas. Se você faz isso por meio de vínculos em tempo de compilação, chamadas de função virtual em tempo de execução ou algo intermediário, não importa. O que importa é que, quando você executa seus testes, deseja poder testar todas as versões em que está interessado atualmente.

Eu estaria inclinado a construir um sistema de tal maneira que a versão básica não otimizada do código de produção sempre pudesse ser usada para entender a intenção do código e, em seguida, criar diferentes módulos otimizados ao lado deste contendo a versão ou versões otimizadas, documentando explicitamente onde quer que a versão otimizada difere da linha de base. Ao executar seus testes (unidade e integração), você o executa na versão não otimizada e em todos os módulos otimizados atuais.

Exemplo

Por exemplo, digamos que você tenha uma função Fast Fourier Transform . Talvez você tenha uma implementação algorítmica básica fft.ce faça o teste fft_tests.c.

Aí vem o Pentium e você decide implementar a versão de ponto fixo fft_mmx.cusando as instruções da MMX . Mais tarde, o pentium 3 vem e você decidir adicionar uma versão que usa Streaming SIMD Extensions no fft_sse.c.

Agora você deseja adicionar o CUDA , fft_cuda.cmas também com o conjunto de dados de teste usado há anos, a versão CUDA é mais lenta que a versão SSE! Você faz algumas análises e acaba adicionando um conjunto de dados 100 vezes maior e obtém a velocidade esperada, mas agora sabe que o tempo de configuração para usar a versão CUDA é significativo e que, com pequenos conjuntos de dados, você deve usar um algoritmo sem esse custo de instalação.

Em cada um desses casos, você está implementando o mesmo algoritmo, todos devem se comportar da mesma maneira, mas serão executados com diferentes eficiências e velocidades em arquiteturas diferentes (se for que serão executadas). Porém, do ponto de vista do código, você pode comparar qualquer par de arquivos de origem para descobrir por que a mesma interface é implementada de maneiras diferentes e, geralmente, a maneira mais fácil será consultar a versão original não otimizada.

O mesmo vale para uma implementação OOP em que uma classe base que implementa o algoritmo não otimizado e classes derivadas implementam otimizações diferentes.

O importante é manter as mesmas coisas que são as mesmas , de modo que as diferenças são óbvias .

Especificamente, como você tomou o exemplo do processamento de vídeo e imagem, é possível manter o código como parte da mesma versão, mas ativo ou inativo, dependendo do contexto.

Enquanto você não mencionou, estou assumindo Caqui.

A maneira mais simples no Ccódigo, a otimização (e também se aplica ao tentar tornar as coisas portáteis) é manter

 
#ifdef OPTIMIZATION_XYZ_ENABLE 
   // your optimzied code here... 
#else  
   // your basic code here...

Quando você ativa #define OPTIMIZATION_XYZ_ENABLEdurante a compilação no Makefile, tudo funciona de acordo.

Geralmente, cortar algumas linhas de código no meio de funções pode ficar confuso quando há muitas funções otimizadas. Portanto, nesse caso, define-se ponteiros de funções diferentes para executar uma função específica.

o código principal sempre executa através de um ponteiro de função como

   codec->computed_idct(blocks); 

Mas os ponteiros de função são definidos dependendo do tipo de exemplo (por exemplo, aqui a função idct é otimizada para diferentes arquiteturas de CPU).

if(OPTIMIZE_X86) {
  codec->computed_idct = compute_idct_x86; 
}
else if(OPTIMZE_ARM) {
  codec->computed_idct = compute_idct_ARM;
}
else {
  codec->computed_idct = compute_idct_C; 
}

você deve ver os códigos libjpeg e libmpeg2 e pode ser ffmpeg para essas técnicas.

Como pesquisador, acabei escrevendo bastante do código de "gargalo". No entanto, uma vez colocado em produção, o ônus de integrá-lo ao produto e fornecer suporte subseqüente recai sobre os desenvolvedores. Como você pode imaginar, comunicar com clareza o que e como o programa deve operar é da maior importância.

Descobri que existem três ingredientes essenciais para concluir esta etapa com sucesso

1. O algoritmo usado deve ser absolutamente claro.
2. O objetivo de toda linha de implementação deve ser claro.
3. Os desvios dos resultados esperados devem ser identificados o mais rápido possível.

Para a primeira etapa, eu sempre escrevo um pequeno white paper que documenta o algoritmo. O objetivo aqui é realmente escrevê-lo para que outra pessoa possa implementá-lo do zero usando apenas o whitepaper. Se é um algoritmo bem conhecido, publicado, basta fornecer as referências e repetir as equações principais. Se for um trabalho original, você precisará ser um pouco mais explícito. Isso informará o que o código deve fazer .

A implementação real que é entregue ao desenvolvimento deve ser documentada de tal maneira que todas as sutilezas sejam explicitadas. Se você adquirir bloqueios em uma ordem específica para evitar conflitos, adicione um comentário. Se você iterar sobre as colunas em vez de sobre as linhas de uma matriz devido a problemas de coerência de cache, adicione um comentário. Se você fizer algo até um pouco inteligente, comente. Se você pode garantir o whitepaper e o código nunca será separado (por meio do VCS ou sistema similar), consulte o whitepaper. O resultado pode facilmente ter mais de 50% de comentários. Tudo bem. Isso mostrará por que o código faz o que faz.

Por fim, você precisa garantir a correção diante das alterações. Felizmente, temos uma ferramenta útil em testes automatizados e plataformas de integração contínua . Isso informará o que o código está realmente fazendo .

Minha recomendação mais calorosa seria não economizar em nenhuma das etapas. Você precisará deles mais tarde;)

Acredito que isso seja melhor resolvido através de comentários abrangentes do código, a ponto de cada bloco significativo de código ter comentários explicativos de antemão.

Os comentários devem incluir citações das especificações ou material de referência de hardware.

Use nomes de terminologia e algoritmos em todo o setor, quando apropriado - por exemplo, 'a arquitetura X gera traps de CPU para leituras desalinhadas, para que este dispositivo da Duff preencha o próximo limite de alinhamento'.

Eu usaria nomes de variáveis ​​no seu rosto para garantir que não houvesse mal-entendido sobre o que está acontecendo. Não é húngaro, mas coisas como 'stride' para descrever a distância em bytes entre dois pixels verticais.

Eu também complementaria isso com um documento breve e humanamente legível, com diagramas de alto nível e design de blocos.