Fun with optimalization

Sloth, being written in/towards the .Net Framework (currently 2.0), is an object oriented application. I try to follow a few general principles on how to do stuff. One of the things I try to avoid is premature optimalization - the idea being that you first get it to work, with unit tests as a backing confidence booster, and THEN you optimize.

Just for fun, I thought I would optimize something that has survived since the early days of Sloth v0.0.0.1 - it is well proven code, and it would be very easy to verify if my optimizations break anything, as Sloth would cease to function at all.

The area I chose for this experiment is the Channel object, more specifically the OnNow and OnNext properties. These basically tell the caller which show is on the channel right now, and which one is on next.

A run with a profiler shows me that while this does not affect overall application performance much, it is definately ready for some improvements. These properties have largely gone unchanged after being more or less among the first 20 or so things written in Sloth. Optimizing them should be very easy, but I was eager to see just how much I could squeeze out of it. The routines are used by the main window to determine which shows to list, as well as by the "early warning system" that scores OnNow/OnNext before anything else to get alerts launched ASAP after Sloth starts.

The original OnNow would loop through the collection of shows until it found one whose StartTime was less than/equal to DateTime.Now, and whose StopTime was larger than/equal to DateTime.Now. If a match was found, it was returned. Since Sloth never adds shows that end before the current day to the list, at most this would mean having to traverse a whole day of shows before finding the right one. Didn't take long, but it took long enough - there was a definitive room for improvement here!

The implementation of OnNext was way worse. Keep in mind that this was written in the days where Sloth made no warranty that the list of shows was sorted in chronological order. So basically, OnNext would loop through the collection, and if it found any show with a StartTime larger than DateTime.Now, check if it was lower than what it already had (if anything), and if so, grab it. This meant looping through the whole collection. Large room for improvement.

While these numbers are taking from a single profiling session, and in no way represent any real benchmarks, they give you a good indication of the "savings" possible. What I did was basically profile these two properties from Sloth startup until the UpdateScores routine was finished and all alerts fired.

Original OnNow	67 ms
Original OnNext	82 ms

Wow - together they consume a whopping 0.15 seconds on my PC! Way to pick an important target for optimization! ;)

Well, I'm in it for the lesson, not the ... eh ... something.

So time to try to be clever.

Optimization 1 - Cached objects

So how about we cache the show found to be OnNow, the show to be OnNext, and that way, we don't have to look through the list all the time? Excellent idea! How do we know when we actually have to go looking again? Easy - OnNow.StopTime should tell us when the show currently on is over and the next one is ready. So I added two local variables for onNow and onNext, and a DateTime called cachedOnNowSwitch (yeah, clever name) which would be set to the time it was necessary to run the list again.

OnNow simple optimization	19 ms
OnNext simple optimization	42 ms

That's nice - reducing OnNow by a third and halving OnNext shows that caching the objects was a good plan. If only we could tighten the list traversal a little..

Optimization 2 - Cached DateTime.Now

In the profiler, DateTime.Now suddenly stuck out as a sore thumb. It seems like fetching this from the OS takes a relatively long time. So how about instead of calling DateTime.Now all the time I do date comparison in the list, I create a local DateTime called now that I set at the beginning, and then compare to it instead?

OnNow medium optimization	6,8 ms
OnNext medium optimization	28 ms

Okey, now we're talking! But it should be possible to optimize even further...

Optimization 3 - No more OnNext list walking

Since the original code was written, Sloth has started ensuring that the show lists are sorted at all times. It's just more efficient that way. So is it really necessary for OnNext to run through the whole list of shows to find its' target? Of course not.

Since OnNow is cached and these two are always called near each other, lets have OnNext just call showlist.IndexOf(OnNow) and add 1 - that should be our show!

OnNow cool optimization	6,1 ms
OnNext cool optimization	3,2 ms

No special reward for OnNow this time around, just an insignificant brain fart probably. But OnNext is starting to look real good!

Optimization 4 - Cache the IndexOf result

Since we already know via the cached DateTime when our OnNow will be outdated, why don't we just cache the result of the IndexOf call as well? Also, let's add some checking for empty show lists and not doing anything when hitting out-of-bounds conditions.

OnNow super optimization	2,9 ms
OnNext super optimization	0,2 ms

Nice numbers!

So there we have it - I'm not going to try to go further, as there is probably nowhere left to optimize for a developer of my skill level. Most of the fat now is in the looping and date comparison stuff, which I can do very little about. So I am plenty happy with the outcome.

I'm looking forward to seeing what can be done in other time-intensive Sloth loops!

Until next time...