Data-Driven O(ptimization) : MyTime vs RunTime

Lets cut to the chase (we are talking about optimization anyway ;) The plan was to implement the following functions:

  1. Alloc: Given a size, allocates memory and returns a reference (offset)
  2. Free: Given the reference (offset), frees the associated memory

We’ll skip how these functions were implemented and we’ll stick to knowing what it does, which is the same as malloc, new, free, etc... So, I had an initial version of my code (alloc & free) in GoLang and ran some benchmark to check its performance.

Allocating multiple objects of random size with totaling to in bytes and implies nanoseconds took per operation.

Even though we are allocating and freeing chunks of objects that sum more than 16MB, 17.24s seemed too much.

I tend to optimize the code pre-maturely but I’ve consciously avoided doing that this time. That being said, it doesn’t mean I had avoided optimization altogether, I’ve optimized wherever I thought was absolutely necessary.

On a higher level, the implementation involves RWLocks, System Calls, Algorithm to Merge overlapping intervals, Random number generator, etc… So instead of witch-hunting the reason(s) for the slow execution, which could take hours or even days, I decided to make a

Data-Driven decision

As fancy as the name may sound, at the core, its pretty simple. Let's start by setting our expectations clear.

1. I’ve not implemented a machine learning algorithm that can optimize any code (and hope it doesn’t exist :P)
2. I’m not here to explain how to write an optimized code

GoLang has a beautiful profiler which tells you precisely the time taken by different functions. Here’s the result of CPU profiling:

Flame graph indicating IsFreeSpace function consuming 89.77% of total time
Flame graph indicating `IsFreeSpace` function consuming 89.77% of total time

Now, this came as a surprise, as is just going to check if the offset belongs to a free space and that’s it. The code for the function is as simple as it can get. Take a look at it yourself!

It loops through the free spaces and checks if offset falls within its boundaries. Even in terms of time complexity, it's just O(n).

But the profiling data did point to this exact function being the time consumer. So believing in data, I went ahead to implement a for the same (as the free spaces were sorted by ). I knew, theoretically, it should be O(lg n) and ran the same benchmark.

Total run time reduced from 17.24s to 2.27s and per operation time from 1061 ns/op to 8.44 ns/op
Flame Graph indicating that IsFreeSpace is not consuming as much time as it did

It runs almost on the same size as the previous benchmark (and I promise is the only function I changed).

So when it comes to optimization, here are the key take-aways from this mini-experiment

  1. Start with a brute-force approach to test the logic
  2. If we are certain that a piece of code requires optimization, then go-ahead. (Mostly, a strong intuition is a data-driven subconscious decision ;)
  3. If we require an optimal code but unsure where we are losing out, a data-driven approach will definitely lend us a helping hand

A parallel thought: After your decide to optimize, let your leetcode mode kick-in. (Yes, they are used in real projects!)

P.S: This is not a one-size-fits-all solution and definitely not the only way!