Como medir a complexidade na prática em seu grande projeto de software?

Na universidade, em nossos cursos de algoritmos, aprendemos a calcular com precisão a complexidade de vários algoritmos simples usados ​​na prática, como tabelas de hash ou classificação rápida.

Mas agora em um grande projeto de software, quando queremos torná-lo mais rápido, tudo o que fazemos é olhar para partes individuais - alguns loops aninhados que podem ser substituídos por uma tabela de hash mais rápida, uma pesquisa lenta aqui que pode ser acelerada por uma técnica mais sofisticada - mas nunca computamos a complexidade de todo o nosso pipeline.

Existe alguma maneira de fazer isso? Ou as pessoas na prática estão apenas confiando "localmente" usando um algoritmo rápido, para tornar o aplicativo inteiro mais rápido, em vez de considerar globalmente o aplicativo como um todo?

(Como me parece não trivial mostrar que, se você acumular um grande número de algoritmos conhecidos por serem muito rápidos por conta própria, também terá um aplicativo rápido como um todo).

Estou perguntando isso, porque estou encarregado de acelerar um grande projeto que outra pessoa escreveu, onde muitos algoritmos estão interagindo e trabalhando nos dados de entrada, portanto, não está claro para mim como o impacto de tornar o algoritmo único mais rápido toda a aplicação.

Os grandes projetos de software consistem em muitos componentes diferentes e nem todos são tipicamente um gargalo. Muito pelo contrário: para quase todos os programas que vi na minha vida em que o baixo desempenho era um problema, o princípio de Pareto se aplicava: mais de 80% dos ganhos de desempenho podem ser alcançados otimizando menos de 20% do código (na realidade, eu acho que os números costumam ser mais de 95% a 5%).

Portanto, começar a olhar para peças individuais geralmente é a melhor abordagem. É por isso que a criação de perfil (conforme explicado na resposta de David Arno ) é boa, pois ajuda a identificar os 5% mencionados do código em que a otimização fornecerá o "maior retorno do investimento". A otimização de "todo o aplicativo" acarreta um certo risco de engenharia excessiva e, se você otimizar esses 95% mesmo com um fator de 10, muitas vezes isso não terá efeito mensurável. Observe também que o perfil indica muito mais do que qualquer estimativa hipotética da complexidade do algoritmo, pois um algoritmo simples que precisa de etapas O (N ^ 3) ainda pode ser mais rápido que um algoritmo complexo que requer O (N log (N)), desde que N é pequeno o suficiente.

Após o perfil revelar os pontos de acesso, é possível otimizá-los. Obviamente, um "hot spot" pode ser maior do que apenas uma ou duas linhas de código; às vezes é preciso substituir um componente inteiro para torná-lo mais rápido, mas isso normalmente ainda é uma pequena parte da base de código em um programa maior .

Técnicas de otimização típicas incluem

• melhorando o uso de algoritmos e estruturas de dados

• ajuste fino do antigo

• micro-otimizações em alguns pontos de acesso reais

• recodificando seções críticas usando código de montagem ou CUDA

Observe que essas técnicas estão trabalhando em diferentes níveis de abstração, algumas delas visualizando um componente mais "como um todo" do que outras. Portanto, depende do que você quer dizer com "tudo o que fazemos é olhar para peças individuais" - se você tivesse apenas micro-otimizações em mente, discordo que "nós" trabalhamos apenas nisso. Mas se você quer aplicar essas otimizações em larga escala em peças ou componentes isolados, então "nós" provavelmente estamos trabalhando nas peças certas e você deve questionar suas expectativas.

A maneira padrão, testada e comprovada, é criar um perfil do código . Você realiza análises dinâmicas do sistema em execução para medir tempos, uso de memória etc. Em seguida, analisa os resultados para encontrar gargalos de desempenho.

Esses gargalos são reescritos experimentalmente e o resultado é analisado novamente para determinar que foi alcançado um aumento de velocidade, redução no uso de memória, etc. Esse processo é repetido até que um ganho de desempenho aceitável seja alcançado.

Embora as outras respostas estejam corretas e forneçam alguma orientação, acho que elas perdem um passo. Em um sistema complexo com o qual você está trabalhando agora, entender os diferentes componentes que compõem o sistema é essencial para entender por que algo está lento.

Meu primeiro passo seria obter um diagrama detalhado da arquitetura ou criar um eu mesmo. Descubra quais etapas são executadas, quais componentes do software e quanto tempo cada etapa leva.

Além disso, descubra como os componentes interagem entre si. Isso pode fazer toda a diferença.

Por exemplo, eu vi código em C # em que a interface entre dois componentes estava passando um IEnumerable criado pelo primeiro componente, que depois foi enumerado pelo segundo componente. Em C #, isso requer alternância de contexto, que pode ser onerosa em determinadas circunstâncias. Resolvê-lo não tem impacto no algoritmo. Um simples .ToList () garante que o resultado seja coletado antes que a próxima etapa resolva esse problema.

Outra coisa a considerar é o impacto no sistema em que você está executando o código. As interações de hardware podem obviamente ser um fator em sistemas complexos. Procure por E / S de disco, alocações de memória grande e E / S de rede. Às vezes, eles podem ser resolvidos de maneira mais eficiente, aprimorando o sistema ou até substituindo o hardware.