Microbenchmarking

Introduction

Performance concerns, in software engineering, has been around for a while now and is a concern that has been increasing in the last couple of years, as it is related to the experience the customer will have, while interacting with some application. There is a study from Amazon, which shows that every 100ms of latency cost them 1% in sales, another one, by Google, which shows an extra 500ms in search page generation time, drops the traffic by 20% and a recent study, showed that users spend 20% of their day, experiencing and complaining about the poor performance of the software they are using.

Well, as shown, performance can have a big impact on how a user perceives it's interaction with the application and might directly affects conversion rates, revenues and lead the customer to choose another company over yours, but it doesn't end there, poorly optimized applications, might be using more resources than it should if it had it's performance improved, as it will need more CPU, memory, disk and network to properly operate in your average load.

Many managers, nowadays, believe that they just need to configurate the autoscaling feature on their cloud provider and they are done, don't need to worry about that anymore, well, at least until their bill arrives and they start to complain that cloud is too expensive. In order to solve all those problems, we have some concepts of performance engineering that should be applied to software development, to solve those problems and one I would like to introduce here, is the microbenchmarking.

Microbenchmarking is focused in assessing the performance of a piece of code and give a quick feedback about the performance of a method, for example, or to compare the performance of two different algorithms. In this article I will bring a solution for Node.js, called Benchmark, which can be integrated in any project by installing in the project, using npm.

Methodology

For this study we will use the Benchmark tool for Node.js, available as a package in the NPM registry. As a general rule, there are many different algorithms that could be used to solve any particular problem, but different algorithms have different complexities, and choosing one over another, will have impact in the software performance.

To define the algorithm complexity it is used the big O notation, as a simplification, it takes the time an algorithm will take to process the data, in number of operations and represents it as some mathematical function.

For the purpose of this article, I have choosen to compare two well known data structures, the linked list and array, the linked list is composed of nodes that migh be in different parts of the memory and, in order to know where the next element is, each node has the information about the next node location, as well as the last element has the information that it is the last element and doesn't point to another node.

When comparing the complexity for search, the linked list takes O(n), in the worst case, to complete the task, while the Array takes O(1), for insert a linked list takes O(1), while the Array takes O(n).

In Order to measure the performance of each data structure, 10 runs were performed with the benchmark tool for each method, in both structures. For this test the push() method, insert at index and search by index, were selected for the Array, whereas the insert last, insert first and find at index methods were selected for the linked list.

The native array from Node.js was used, while the linked list was implemented using the following algorithm for each method:

insertFirst(data) 
            this.head = new Node(data, this.head);
            this.size++;
        }        

      insertLast(data) 
            let node = new Node(data);
            let current;


            // If empty, make head
            if (!this.head) {
                this.head = node;
            } else {
                current = this.head;


                while (current.next) {
                    current = current.next;
                }


                current.next = node;
            }


            this.size++;
        }        

  getAt(index) 
            let current = this.head;
            let count = 0;


            while (current) {
                if (count == index) {
                    console.log(current.data);
                }
                count++;
                current = current.next;
            }


            return null;
        }        

 Results

The results showed that, despite the fact that the algorithm complexity analysis, using the Big O notation, gives a performance advantage for the linked list in the insert category, the Array has shown consistent performance, with a big decrease in the number of operations per seconds, using the push() method, but even with this method, it was a little bit faster, while the insert at index method, was 100 times faster than the insertFirst method from the linked list, on the seach category, the Array list also got the lead by a large margin.

All the numbers are showing the operations per seconds:

Conclusion

Measuring the performance for each different algorithm is very important, to confirm or debunk the ideas about which option has the best performance, as shown in the results, some times the actual performance is not exactly the one some previous analysis make us believe.