An allegory of an optimization story

time to read 2 min | 322 words

I got a call today from a team mate about a piece of software that we wrote. We initially planned it to work with data sizes of hundreds to thousands of records, and considering that we wrote that one in a day, I considered it a great success. We didn’t pay one bit of attention to optimization, but the perf was great for what we needed.

However, a new requirement came up which require us to handle hundred thousand records, and our software was working… well under the new constraints. As a matter of fact, it would take about 0.4 seconds to compute a result when the data size was hundred thousand records. That was probably well within acceptable range, but it had me worried, because 0.4 seconds may be acceptable for this single computation, but it was a CPU bound computation, and it was probably going to kill us when we start hammering the server with multiple requests for that.

Moreover, adding 0.4 to the clients of the system would add an unacceptable delay. So we sat down with dotTrace and tried to figure out what we were doing that could be better.

We spent several hours on that. At some point, a simple extraction of a variable from a loop reduced 7% of the total execution time, but we weren’t really interesting in the small fish. We soon identified a O(N) operation in the code, which was taking about 20% of the total time of the calculation, and focused on that.

By changing the way that we worked with this, we changed this from an O(N) operation to O(1). We did it by introducing indexes and doing intersects of those indexes. The usual choice of time vs. memory has saved us again.

Current time for computing a result? 20 – 50 ms, and that include network time.

I think that I’ll find that acceptable.