Lets cut to the chase (we are talking about optimization anyway ;) The plan was to implement the following functions:
- Alloc: Given a size, allocates memory and returns a reference (offset)
- 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.
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
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:
Now, this came as a surprise, as
IsFreeSpace 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
binary search for the same (as the free spaces were sorted by
startIdx). I knew, theoretically, it should be O(lg n) and ran the same benchmark.
It runs almost on the same size as the previous benchmark (and I promise
IsFreeSpaceis the only function I changed).
So when it comes to optimization, here are the key take-aways from this mini-experiment
- Start with a brute-force approach to test the logic
- If we are certain that a piece of code requires optimization, then go-ahead. (Mostly, a strong intuition is a data-driven subconscious decision ;)
- 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!