Dicas para melhorar código crítico em termos de tempo

Artigo
04/03/2023

Para gravar códigos rápidos, você precisa conhecer todos os aspectos do aplicativo e saber como ele interage com o sistema. Este artigo sugere alternativas a algumas das técnicas de codificação mais óbvias para ajudá-lo a garantir que as partes críticas de tempo do seu código sejam executadas satisfatoriamente.

Em suma, para melhorar o código para o qual o tempo é essencial, você precisa:

Saber quais partes do programa precisam ser rápidas.
Conhecer o tamanho e a velocidade do código.
Conhecer o custo dos novos recursos.
Conhecer o trabalho mínimo necessário para concluir a tarefa.

Para coletar informações sobre o desempenho do seu código, você pode usar o monitor de desempenho (perfmon.exe).

Erros de cache e falhas de página

O ocorrência de perda nos caches interno e externo, assim como as falhas de página (direcionamento para o armazenamento secundário das instruções e dos dados do programa), deixam seu programa lento.

Uma ocorrência no cache da CPU pode custar ao programa de 10 a 20 ciclos de relógio. Uma ocorrência no cache externo pode custar de 20 a 40 ciclos de relógio. Uma falha de página pode custar um milhão de ciclos de clock (supondo um processador que lida com 500 milhões de instruções/segundo e um tempo de 2 milissegundos para uma falha de página). Portanto, o melhor para a execução do programa é que você grave um código que diminua as ocorrências de perna no cache e falhas de página.

Uma das causas da lentidão dos programas é que esses programas têm mais falhas de página ou mais perda no cache com mais frequência do que o necessário. Para evitar esse problema, é importante usar estruturas de dados com boa localidade de referência, o que significa manter as coisas relacionadas juntas. Às vezes, uma estrutura de dados, que parece excelente, acaba sendo horrível devido à má localidade de referência, e o contrário também pode acontecer. Veja dois exemplos:

Listas vinculadas alocadas dinamicamente podem reduzir o desempenho do programa. Quando você pesquisa um item, ou quando atravessa uma lista até o final, cada link ignorado pode perder o cache ou causar uma falha de página. Uma implementação de lista baseada em matrizes simples pode ser mais rápida devido a um melhor armazenamento em cache e menos falhas de página. Mesmo se você permitir o fato de que o array seria mais difícil de crescer, ele ainda pode ser mais rápido.
As tabelas de hash que usam listas vinculadas com alocação dinâmica podem prejudicar o desempenho. Consequentemente, esse tipo de tabela usa essas listas para armazenar seu conteúdo podem apresentar desempenho consideravelmente pior. Na verdade, na análise final, uma simples pesquisa linear na matriz pode ser mais rápida (dependendo das circunstâncias). O uso de uma tabela de hash baseada em matriz (o chamado "hash fechado") é uma implementação frequentemente negligenciada que frequentemente tem desempenho superior.

Classificação e pesquisa

Por natureza, a classificação consome mais tempo do que muitas operações comuns. A melhor forma de evitar a lentidão desnecessária é evitar a classificação em tarefas com tempo crítico. Você também pode:

Adiar a classificação até um tempo crítico não relacionado ao desempenho.
Classificar os dados em um tempo crítico anterior, não relacionado ao desempenho.
Classificar apenas os dados que realmente precisam ser classificados.

Em alguns casos, você também pode compilar a lista na ordem classificada. Cuidado. Se precisar inserir dados na ordem classificada, você pode precisar de uma estrutura de dados complexa com má localidade de referência, o que resulta em perdas no cache e falhas de páginas. Não há uma abordagem que funcione em todos os casos. Experimente diversas possibilidades e avalie as diferenças.

Veja algumas dicas gerais referentes à classificação:

Use a classificação de inventário para minimizar os bugs.
Tudo o que for possível fazer previamente para diminuir a complexidade da classificação pode ajudar. Se uma passagem única sobre seus dados simplificar as comparações e reduzir a classificação de O(n log n) para O(n), você quase certamente sairá na frente.
Pense na localidade de referência do algoritmo de classificação e nos dados em que ela deve ser executada.

Há menos alternativas para as pesquisas do que para a classificação. Se o tempo for crítico na operação de pesquisa, uma pesquisa binária ou verificação da tabela de hash quase sempre é a melhor opção, mas no caso da classificação, é necessário levar a localidade em consideração. Uma pesquisa linear por meio de uma matriz pequena pode ser mais rápida do que uma pesquisa binária por meio de uma estrutura de dados com muitos ponteiros que causam falhas de página ou erros de cache.

MFC e bibliotecas de classes

As MFC (Microsoft Foundation Classes) podem simplificar muito a gravação do código. Ao gravar códigos para os quais o tempo é crítico, você deve levar em consideração a sobrecarga inerente a algumas dessas classes. Avalie o código da MFC que seu código com tempo crítico usa para ver se ele atende às suas necessidades de desempenho. A lista a seguir identifica as classes e as funções de MFC que você deve conhecer:

CString MFC chama a biblioteca de tempo de execução C para alocar memória para um CString dinamicamente. De um modo geral, CString é tão eficiente quanto qualquer outra cadeia de caracteres alocada dinamicamente. Da mesma forma que na cadeia de caracteres com alocação dinâmica, há sobrecarga desse tipo de alocação e versão. Geralmente, uma matriz char simples na pilha pode ter a mesma finalidade e ser mais rápida. Não use um CString para armazenar uma cadeia de caracteres constante. Use o const char * em vez disso. Qualquer operação executada com um objeto CString acarreta alguma sobrecarga. Pode ser mais rápido usar funções de cadeia de caracteres de biblioteca de runtime.
CArray A CArray fornece flexibilidade que uma matriz regular não oferece, mas seu programa pode não precisar disso. Se conhecer os limites específicos da matriz, você pode usar uma matriz global fixa. Se usar CArray, use CArray::SetSize para estabelecer seu tamanho e especificar em quantos elementos ela cresce quando a realocação é necessária. Caso contrário, a adição de elementos pode fazer com que a matriz seja realocada e copiada com frequência, o que é ineficaz e pode fragmentar a memória. Além disso, se você inserir um item em uma matriz, CArray move os itens subsequentes na memória e talvez seja necessário aumentar a matriz. Essas ações podem resultar em perdas no cache e falhas de página. Se verificar o código usado pela MFC, você pode ver que é possível gravar códigos mais específicos a seu cenário, para melhorar o desempenho. Como CArray é um modelo, você pode fornecer especializações CArray para tipos específicos, por exemplo.
CListCList é uma lista duplamente vinculada, portanto, a inserção de elementos é rápida na cabeça, cauda e em uma posição conhecida (POSITION) na lista. A verificação de elementos por valor ou índice requer uma pesquisa sequencial, mas esse tipo de pesquisa pode ser lento se a lista for longa. Se o seu código não exigir uma lista duplamente vinculada, convém reconsiderar o uso CListdo . O uso de uma lista vinculada isoladamente economiza a sobrecarga de atualizar outro ponteiro para todas as operações e a memória desse ponteiro. A memória extra não é grande, mas é outra oportunidade para erros de cache ou falhas de página.
IsKindOf Esta função pode gerar muitas chamadas e pode acessar a memória em diferentes áreas de dados, levando a má localidade de referência. É útil para uma compilação de depuração (em uma chamada ASSERT, por exemplo), mas tente evitar usá-la em uma compilação de versão.
PreTranslateMessage Use PreTranslateMessage quando uma determinada árvore do Windows precisar de diferentes aceleradores de teclado ou quando for necessário inserir o tratamento de mensagens na bomba de mensagens. PreTranslateMessage altera as mensagens de expedição da MFC. Se você substituir PreTranslateMessage, só faça isso no nível necessário. Por exemplo, não é necessário substituir CMainFrame::PreTranslateMessage se você estiver interessado apenas em mensagens enviadas para crianças de um modo de exibição específico. Em vez disso, substitua PreTranslateMessage na classe de exibição.

Não contorne o caminho de despacho normal usando PreTranslateMessage para manipular qualquer mensagem enviada para qualquer janela. Use procedimentos de janela e mapas de mensagens de MFC para essa finalidade.
OnIdle Eventos ociosos podem ocorrer em momentos que você não espera, como entre WM_KEYDOWN e WM_KEYUP eventos. Os timers podem ser mais eficientes para disparar seu código. Não force OnIdle a ser chamado repetidamente gerando mensagens falsas ou sempre retornando TRUE de uma substituição de OnIdle, que nunca permitiria que seu fio dormisse. Nesse caso, o timer ou um thread separado pode ser mais adequado.

Bibliotecas compartilhadas

É bom poder reutilizar códigos. No entanto, se você for usar o código de outra pessoa, certifique-se de saber exatamente o que ele faz nos casos em que o desempenho é crítico para você. A melhor maneira de entendê-lo é passando pelo código-fonte ou medindo com ferramentas como PView ou Monitor de Desempenho.

Heaps

Use diversos heaps com discrição. Os heaps adicionais criados com HeapCreate e HeapAlloc permitem que você gerencie e descarte um conjunto relacionado de alocações. Não comprometa muita memória. Se estiver usando diversos heaps, preste atenção principalmente na quantidade de memória que é comprometida inicialmente.

Em vez de usar diversos heaps, você pode usar funções auxiliares para servir de interface entre seu código e o heap padrão. As funções auxiliares facilitam as estratégias de alocação personalizadas que podem melhorar o desempenho do seu aplicativo. Por exemplo, se você sempre faz pequenas alocações de desempenho, pode concentrá-las em uma parte do heap padrão. Você pode alocar um grande bloco de memória e usar a função auxiliar para subalocar desse bloco. Então você não terá vários heaps com memória não utilizada, porque a alocação está saindo do heap padrão.

No entanto, em alguns casos, o uso do heap padrão pode diminuir a localidade de referência. Use o Process Viewer, o Spy++ ou o Monitor de Desempenho para dimensionar os efeitos de mover os objetos entre os heaps.

Dimensione seus heaps para dar conta de cada alocação no heap. Use as rotinas de heap de depuraçãode tempo de execução C para verificar e despejar o heap. Você pode ler o resultado em um programa de planilhas, como o Microsoft Excel, e usar tabelas dinâmicas para exibir os resultados. Observe o número total, o tamanho e a distribuição das alocações. Compare esses resultados com o tamanho dos conjuntos de trabalho. Observe também o clustering dos objetos dimensionados relacionados.

Você também pode usar os contadores de desempenho para monitorar o uso de memória.

Threads

No caso de tarefas em seguindo plano, a manipulação eficiente e ociosa de eventos pode ser mais rápida do que usar threads. Com ela, é mais fácil compreender a localidade de referência em um programa com um único thread.

Uma boa regra é só usar o thread se uma notificação de sistema operacional usada em seu bloco estiver na raiz do trabalho em segundo plano. Os threads são a melhor solução nesse caso, porque é impraticável bloquear um thread principal em um evento.

Os threads também apresentam problemas de comunicação. Você deve gerenciar o vínculo de comunicação entre seus threads por meio de uma lista de mensagens ou da alocação e do uso de memória compartilhada. O gerenciamento do vínculo de comunicação geralmente requer sincronização para evitar condições de corrida e problemas de deadlock. Essa complexidade pode resultar em bugs e problemas de desempenho.

Para obter mais informações, consulte Processamento de loop ocioso e Multithreading.

Conjunto de trabalho pequeno

Conjuntos de trabalho menores possibilitam a melhor localidade de referência, resultam em menos falhas e páginas e geram mais ocorrências de cache. O conjunto de trabalho do processo é a métrica mais próxima que o sistema operacional oferece para medir a localidade de referência diretamente.

Para definir os limites superior e inferior do conjunto de trabalho, use SetProcessWorkingSetSize.
Para obter os limites superior e inferior do conjunto de trabalho, use GetProcessWorkingSetSize.
Para exibir o tamanho do conjunto de trabalho, use o Spy++.

Confira também

Otimizando seu código

Compartilhar via