Algorithm efficiency

Most of us think that when we are challenged to write some code/algorithm, we try to make sure that the code is well designed, beautifully written and almost 100% unit/integration tested. But is it enough to say it is efficient?

So what is efficiency?

Based on Wikipedia, algorithmic efficiency is a property of an algorithm which relates to the amount of computational resources used by the algorithm.

Thus, the efficiency is related to the amount of computational resources (execution time, CPU, memory usage...) used by the algorithm. The less resources the algorithm consumes, the more efficient it is.

But why we need efficiency?

Simply because computational resources means cost (money spent). So as SWE, we are paid to reduce cost and maximize benefit.

So how we measure the efficiency of an algorithm?

It depends on the use case. Do we need the algorithm to be rapid? or to operate in small amount of memory? or both?

Recently, I was playing with BTree implementation (You can check out the project on github), and I ended up with an insertion algorithm of O(t logt?(n)) (t is the degree of BTree, n the number of elements in BTree). So I was curious about what's the best values of t to make the algorithm efficient in terms of speed and memory usage.

So I tried to insert 1M elements and measure the execution time of the algorithm, I also fixed the memory heap to 50Mbytes which is more than sufficient (BTree root retained size is about 17Mbytes and 33Mbytes, plus some extra space for frequent copies of keys and children).

My first observation was that the algorithm execution time ranged from 5s and 2m30, as the BTree degree t increases. So, 2min for inserting 1M elements? Something should be wrong. I re-ran the same test, but this time, using visualvm and MAT. And I spot the issue.

As the t increases, the Minor GC starts to run more often (Ten thousand times more than in low degree). The Minor GC was desperate to free up some space to create new objects, and thus took longer than it should.

By reviewing the algorithm, converting the recursive function to its iterative form, and optimizing some lines, I was able to run the algorithm between 1s and 3s. At the end, I figured out the best degree for this use case which is about 100 - 200.

As a conclusion, theorical analysis and performance measurement under real-life scenarios (heavy loads, limited resources...) are critical tasks in the cycle of writing the code, as they directly affect the user experience, business outcomes, and overall success of the software application.

Please let me know your thoughts and comments on this.