When trying to solve a complex technical problem, it’s easy to get caught up in concerns about performance before anything’s even running. I want to share a story about a time when I introduced what seemed a reasonable idea to solve a transformation problem, but ended up in the middle of a long-running debate about performance. This is a case of premature optimisation, and what we can learn from it.

Case Study

Some time ago, I worked on a project where we needed to process a JSON payload and transform it based on some rules. Due to the requirements of our project, it seemed reasonable to me to use a tree structure to represent and process this data.

This might be why I was so surprised by all the pushback that this idea encountered. Some of my teammates were sincerely concerned about the excessive extra time that it’d take to parse the payload into a tree object, and then traverse this tree multiple times to do the transformations that we needed. I was glad to notice that my team was so mindful of performance degradation, so I took some time to discuss it with them.

Time Complexity

To address these concerns, I decided to take a step back and analyse the solution more formally using the Big O notation to consider the time complexity of the code, and whether the concerns were justified.

If you’re not familiar with the Big O notation, this is a very short summary to get you up to speed:

• O(1) means the code runs in constant time irrespective of input’s length.
• O(n) means the code runs in twice the time for an input twice the size.
• O(n^2) means the runtime is quadratic! Nested loops are examples of this.

In the case of the tree structure I was proposing, the time complexity was O(n), with n being the number of elements in the JSON data. This included creating the tree, traversing the tree a couple of times, and updating the tree in-place in some cases.

It’s worth noting that this was the minimum time complexity that we could get, as we had to parse the entire JSON payload every time anyway.

My team thought deeply about this, and although they were still unconvinced (despite the time complexity analysis), they decided to go ahead anyway because they were unable to think of any other alternative solution that suited our problem.

Big Picture

Shortly after the main algorithm was implemented, other people involved in the project reopened the discussion. Because this was a time-sensitive service, they were concerned that the tree structure was taking too much time to build and traverse. After all, an O(n) algorithm can still be slow compared to another O(n) solution.

Although I could understand that they wanted to have the best possible solution delivered to our users, I believe that they were missing the big picture.

We had a deadline, and my team was committed to delivering in time. In my opinion, spending time trying to optimise something without even knowing if that is truly a problem is a waste of time. I believe that only once we know that we have a problem, and how bad it is, we should start working on fixing it.

I think that in most agile teams and projects, it is reasonable to deliver something good enough, with certainty, and improve it once we identify it doesn’t meet our needs. The alternative of working on the perfect solution, but not delivering, is often out of the question.

Regardless, we eventually need to identify the real bottlenecks before we can improve anything. That’s where performance measurement comes in.

Performance Measurement

From the beginning, I had an educated guess that the tree structure was not going to be an issue, but we had to measure it at some point, so I decided to run a very simple experiment to determine what the negative impact of using a tree structure was.

Our service worked something like this: it received a request, it created and traversed the tree, it made some API requests, and then it returned the final data.

I ran the code a few thousand times with the same input (no caching), to measure the average running time. Then I got the average running time again after hardcoding the tree’s output instead of generating it with the tree.

I expected a low number, but never imagined that the difference would be negligible! The end-to-end running time was about 600ms, but there was no practical difference when compared to the version that had the response hardcoded.

Conclusion

In retrospect, while the team raised valid concerns, I feel that they were based more in gut feelings than actual data, and did not consider the bigger picture into account.

They were too focused on the preconceived idea that the tree structure would be slow to consider the time complexity, what were the main bottlenecks, or if that was the right time to do optimisations.

When choosing how we solve a problem, the optimality of a solution is not the only factor to consider. In some cases, a solution with higher time complexity may be good enough for a project rather than a more optimal but expensive solution.

Sometimes, the only way of finding that out is to write the code and measure the performance. Even a prototype with mocked data can be enough to shed some light on the real bottlenecks and on whether our algorithm needs to be improved.

Without measurements, optimisation is just speculation.

Cheers,
José Miguel

Share if you find this content useful, and Follow me on LinkedIn to be notified of new articles.