Abordagens contra a base de código se tornando uniformemente lenta

Estamos trabalhando em uma base de código C ++ de tamanho médio (10Mloc) que, através de nossos esforços de otimização, está se tornando uniformemente lenta .

Essa base de código é um conjunto de bibliotecas que combinamos para colocá-las em funcionamento. Quando a estrutura geral de como essas bibliotecas se comunicam foi desenvolvida, houve alguma ênfase no desempenho e, posteriormente, quando mais partes foram adicionadas, a estrutura geral não mudou muito. A otimização foi feita quando necessário e à medida que nosso hardware evoluiu. Isso tornou a decisão precoce cara aparente apenas muito mais tarde. Agora estamos em um ponto em que novas otimizações são muito mais caras, pois exigiriam reescrever grandes partes da base de código. Nos vemos chegando a um mínimo local indesejável, pois sabemos que, em princípio, o código deve ser capaz de rodar muito mais rápido.

Existem metodologias bem-sucedidas que ajudam a decidir o que significa assumir a evolução de uma base de código em direção a uma solução com desempenho global ideal, que não é facilmente confundida por oportunidades fáceis de otimização?

EDITAR

Para responder à pergunta de como perfilamos atualmente:

Realmente temos apenas dois cenários diferentes de como esse código pode ser usado, ambos embaraçosamente paralelos. A criação de perfil é feita com o tempo médio do relógio de parede em uma grande amostra de entradas e execuções mais detalhadas (custos de instrução, previsões incorretas de ramificação e problemas de armazenamento em cache). Isso funciona bem, já que rodamos exclusivamente em nossas máquinas extremamente homogêneas (um conjunto de algumas milhares de máquinas idênticas). Como geralmente mantemos todas as nossas máquinas ocupadas a maior parte do tempo funcionando mais rápido, podemos observar outras coisas novas. É claro que o problema é que, quando novas variações de entrada aparecem, elas podem sofrer uma penalidade tardia, pois removemos as micro-ineficiências mais óbvias para os outros casos de uso, diminuindo assim o número de cenários de "execução ideal".

Não conheço uma abordagem de uso geral para esse problema, mas duas abordagens um tanto relacionadas funcionaram bem para mim no passado: por falta de termos melhores, chamei-as de agrupamento e otimização horizontal .

A abordagem de agrupamento é uma tentativa de substituir um grande número de operações curtas e rápidas por uma única operação altamente lenta e altamente especializada que, em última análise, produz o mesmo resultado.

Exemplo: Depois de traçar um perfil de uma operação particularmente lenta do nosso editor de regras visual, não descobrimos "frutos baixos": não havia uma única operação que ocupava mais de 2% do tempo de execução, mas a operação como um todo parecia lenta. No entanto, descobrimos que o editor estava enviando um grande número de pequenas solicitações ao servidor. Embora o editor estivesse processando rapidamente as respostas individuais, o número de interações solicitação / resposta teve um efeito multiplicativo, portanto, o tempo total que a operação levou foi de vários segundos. Após catalogar cuidadosamente as interações do editor durante essa operação de longa execução, adicionamos um novo comando à interface do servidor. O comando adicional foi mais especializado, pois aceitou os dados necessários para executar um subconjunto de operações curtas, explorou dependências de dados para descobrir o conjunto final de dados a serem retornados e forneceu uma resposta contendo as informações necessárias para concluir todas as pequenas operações individuais em uma única viagem ao servidor. Isso não reduziu o tempo de processamento em nosso código, mas reduziu uma quantidade muito significativa de latência devido à remoção de várias viagens de ida e volta caras para clientes e servidores.

A otimização horizontal é uma técnica relacionada quando você elimina a "lentidão" que é distribuída entre vários componentes do seu sistema usando um recurso específico do seu ambiente de execução.

Exemplo: Depois de criar um perfil de uma operação de longa execução, descobrimos que fazemos muitas chamadas através do limite do domínio do aplicativo (isso é altamente específico do .NET). Não foi possível eliminar nenhuma das chamadas e não conseguimos agrupá-las: elas vinham em momentos diferentes de seções muito diferentes do nosso sistema, e as coisas solicitadas eram dependentes dos resultados retornados de solicitações anteriores. Cada chamada exigia serialização e desserialização de uma quantidade relativamente pequena de dados. Mais uma vez, as chamadas individuais tiveram curta duração, mas um número muito grande. Acabamos criando um esquema que evitava a serialização quase inteiramente, substituindo-o por passar um ponteiro através do limite do domínio do aplicativo. Essa foi uma grande vitória, porque muitos pedidos de classes totalmente independentes se tornaram instantaneamente muito mais rápidos como resultado da aplicação de um únicosolução horizontal .

Isso tornou a decisão precoce cara aparente apenas muito mais tarde. Agora estamos em um ponto em que novas otimizações são muito mais caras, pois exigiriam reescrever grandes partes da base de código.

Quando você inicia essa reescrita, precisa fazer várias coisas de maneira diferente.

Primeiro. E o mais importante. Pare de "otimizar". "Otimização" não importa muito. Como você viu, apenas a reescrita por atacado é importante.

Portanto.

Segundo. Entenda as implicações de toda estrutura de dados e escolha de algoritmo.

Terceiro. Faça a escolha real da estrutura e do algoritmo dos dados uma questão de "ligação tardia". Projete interfaces que podem ter qualquer uma das várias implementações usadas atrás da interface.

O que você está fazendo agora (reescrever) deve ser muito, muito menos doloroso se você tiver um conjunto de interfaces definido que permita fazer uma alteração geral na estrutura ou no algoritmo dos dados.

Um bom truque prático é usar seu conjunto de testes de unidade como um conjunto de testes de desempenho .

A seguinte abordagem funcionou bem em minhas bases de código:

1. Verifique se a cobertura do seu teste de unidade é boa (você já fez isso, certo?)
2. Certifique-se de que sua estrutura de execução de teste relate o tempo de execução em cada teste individual . Isso é importante porque você deseja descobrir onde está ocorrendo um desempenho lento.
3. Se um teste estiver sendo executado lentamente, use-o como uma maneira de aprofundar e direcionar a otimização nessa área . A otimização antes de identificar um problema de desempenho pode ser considerada prematura; portanto, o melhor dessa abordagem é que você obtenha evidências concretas de um desempenho ruim primeiro. Se necessário, divida o teste em testes menores, que avaliam diferentes aspectos, para que você possa identificar onde está o problema raiz.
4. Se um teste é executado extremamente rápido, geralmente é bom, embora você possa considerar executar o teste em um loop com parâmetros diferentes. Isso faz com que seja um melhor teste de desempenho e também aumenta sua cobertura de teste do espaço de parâmetros.
5. Escreva alguns testes extras que visem especificamente o desempenho, por exemplo, tempos de transação de ponta a ponta ou tempo para concluir 1.000 aplicativos de regras. Se você tiver requisitos de desempenho não-funcionais específicos (por exemplo, tempo de resposta <300ms), faça o teste falhar se demorar muito.

Se você continuar fazendo tudo isso, com o tempo, o desempenho médio da sua base de código deverá melhorar organicamente.

Também seria possível rastrear os tempos históricos dos testes e desenhar gráficos de desempenho e detectar regressões ao longo do tempo no desempenho médio. Eu nunca me incomodei com isso, principalmente porque é um pouco complicado garantir que você esteja comparando o mesmo com o que você modifica e adiciona novos testes, mas poderia ser um exercício interessante se o desempenho for suficientemente importante para você.

A resposta de @dasblinkenlight aponta um problema muito comum, especialmente com grandes bases de código (na minha experiência). Pode haver problemas sérios de desempenho, mas eles não estão localizados . Se você executa um criador de perfil, não há rotinas que demorem tempo suficiente para chamar a atenção. (Supondo que você observe a porcentagem de tempo inclusiva que inclui callees. Nem se preocupe com o "tempo próprio".)

De fato, nesse caso, o problema real não foi encontrado por meio de criação de perfil, mas por um insight de sorte.

Eu tenho um estudo de caso, para o qual há uma breve apresentação de slides em PDF , ilustrando essa questão em detalhes e como lidar com ela. O ponto básico é que, como o código é muito mais lento do que poderia ser, isso significa (por definição) que o excesso de tempo é gasto fazendo algo que pode ser removido.

Se você olhasse algumas amostras aleatórias do estado do programa, você o veria fazendo a atividade removível, devido à porcentagem de tempo que leva. É bem possível que a atividade removível não esteja confinada a uma função ou mesmo a muitas funções. Não localiza dessa maneira.

Não é um "ponto quente".

É uma descrição que você faz do que vê, que acontece uma grande porcentagem de tempo. Isso facilita a descoberta, mas a facilidade de correção depende da quantidade de reescrições necessárias.

(Geralmente, é feita uma crítica a essa abordagem, que o número de amostras é muito pequeno para a validade estatística. Isso é respondido no slide 13 do PDF. Resumidamente - sim, há alta incerteza na "medição" de economias em potencial, mas 1) o valor esperado dessa economia potencial é essencialmente inalterado e 2) quando a economia potencial $ x $ é convertida em taxa de aceleração em $ 1 / (1-x) $, é fortemente inclinada para fatores altos (benéficos).)