Quando uma aplicação não está escalando, logo pensamos na necessidade de aumentar a infraestrutura, trocar banco de dados ou até mesmo a tecnologia utilizada, alegando que a mesma não está sendo performática. Mas o real problema na maioria das vezes pode estar no código!
Imagine que ao entrar em uma empresa, a primeira tarefa recebida é criar um endpoint que faça algumas operações, entre elas realizar o cálculo da sequência Fibonacci de um determinado valor.
Em termos matemáticos, a sequência é definida pela fórmula Fn = Fn-1 + Fn-2, sendo o primeiro termo F1= 1 e os valores iniciais F1 = 1, F2 =1. Esse método é aplicado na análise de mercados financeiros, na teoria de jogos e na ciência da computação, além de configurações biológicas e naturais.
Depois de conhecer como é feito o cálculo da sequência é hora de colocar a mão na massa e criar o algoritmo, ficando da seguinte forma:
//recursiveFibonacci calculate the result of fibonacci only with recursion
func recursiveFibonacci(n int) int {
if n < 2 {
return n
}
return recursiveFibonacci(n-1) + recursiveFibonacci(n-2)
}
Bom, algoritmo feito, testes criados, coverage 100% e deploy realizado.
Quando o endpoint criado vai para produção começa a surgir problemas de performance, response time alto, estouro de memória, etc.
Em um teste local, a sequência de Fibonacci(50) levou 54 segundos para ser calculada.
Mas, como um algoritmo relativamente simples poderia ocasionar tudo isso?
Esse é o ponto chave! Quando desenvolvemos qualquer aplicação temos que pensar no todo, e não somente na tarefa isolada.
Performance e escalabilidade são dois itens de suma importância que devem ser observadas no momento em que qualquer desenvolvimento de software for realizado.
O desafio é aumentar a performance reduzindo recursos.
E como podemos resolver o problema de performance do nosso algoritmo?
Solução: Programação Dinâmica!
Programação dinâmica é um método para a construção de algoritmos para a resolução de problemas computacionais, em especial os de otimização combinatória. Ela é aplicável a problemas nos quais a solução ótima pode ser computada a partir da solução ótima previamente calculada e memorizada — de forma a evitar recálculo — de outros subproblemas que, sobrepostos, compõem o problema original. [Wikipedia]
Na figura abaixo vemos que os subproblemas Fib(3) e Fib(2) se repetem no nosso problema, que é o cálculo de Fib(5).
Aplicando o conceito de memorização, podemos calcular um subproblema e armazenar seu resultado em cache e quando precisarmos calcular novamente esse subproblema já teremos seu valor para retornar.
Modificando nosso algoritmo, adicionamos uma variável de cache, que é consultada antes de um novo cálculo ser realizado.
//memoizedFibonacci calculate the result of fibonacci with recursion and memoization
func memoizedFibonacci(n int) int {
cache := make(map[int]int)
var fibonacci func(int) int
fibonacci = func(n int) int {
if n < 2 {
return n
}
if _, ok := cache[n]; !ok {
cache[n] = fibonacci(n-1) + fibonacci(n-2)
}
return cache[n]
}
return fibonacci(n)
}
Após modificação, foi feito o mesmo teste para calcular a sequência de Fibonacci(50), e incrivelmente levou apenas 3 milissegundos!
Com isso, vemos que um pequeno detalhe fez toda diferença.
Conclusão
- Um algoritmo ruim, será ruim em qualquer linguagem, portanto não adianta usar Go, Java, Python, Node.js, , etc.
- Aumentar infraestrutura para garantir performance nem sempre é o melhor caminho, as vezes pode ser desperdício de dinheiro.
Por isso, é importante estudar estrutura de dados, algoritmos e notação Big-O, para conseguir medir a complexidade dos mesmos.
📌 Link do repositório: nosilex/performance-test-go