When an application is not scaling, we soon think of the need to increase the infrastructure, change the database or even the technology used, claiming that it is not performing. But the real problem most of the time can be in the code!
Imagine that when entering a company, the first task received is to create an endpoint that performs some operations, among them performing the calculation of the Fibonacci sequence of a certain value.
In mathematical terms, the sequence is defined by the formula Fn = Fn-1 + Fn-2, the first term being F1= 1 and the initial values F1 = 1, F2 =1. This method is applied in the analysis of financial markets, game theory and computer science, in addition to biological and natural settings.
After knowing how the sequence is calculated, it’s time to get your hands dirty and create the algorithm, as follows:
//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)
}
Well, algorithm done, tests created, coverage 100% and deployment done.
When the created endpoint goes to production, performance problems, high response time, memory overflow, etc.
In a local test, the Fibonacci(50) sequence took 54 seconds to calculate.
But how could a relatively simple algorithm bring about all this?
That’s the key point! When we develop any application we have to think about the whole, and not just the isolated task.
Performance and scalability are two very important items that must be observed when any software development is carried out.
The challenge is to increase performance by reducing resources.
And how can we solve the performance problem of our algorithm?
Solution: Dynamic Programming!
Dynamic programming is a method for building algorithms for solving computational problems, especially those of combinatorial optimization. It is applicable to problems in which the optimal solution can be computed from the optimal solution previously calculated and memorized — in order to avoid recalculation — of other sub-problems that, superimposed, make up the original problem. [Wikipedia]
In the figure below we see that the subproblems Fib(3) and Fib(2) are repeated in our problem, which is the calculation of Fib(5).
Applying the concept of memorization, we can calculate a subproblem and store its result in cache and when we need to recalculate this subproblem we will already have its value to return.
Modifying our algorithm, we add a cache variable, which is queried before a new calculation is performed.
//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)
}
After modification, the same test was done to calculate the Fibonacci(50) sequence, and amazingly it only took 3 milliseconds!
With this, we see that a small detail made all the difference.
Conclusion
- A bad algorithm will be bad in any language, so it’s no use using Go, Java, Python, Node.js, , etc.
- Increasing infrastructure to ensure performance is not always the best way, sometimes it can be a waste of money.
Therefore, it is important to study data structure, algorithms and Big-O notation, in order to measure their complexity.
📌 Link of repository: nosilex/performance-test-go