Delay's Blog is the blog of David Anson, a Microsoft developer who works with the Silverlight, WPF, Windows Phone, and web platforms.
As I've said before, one of our key goals for the March 09 release of Silverlight/WPF Charting was to improve the performance of key customer scenarios. I didn't go into a lot of details with the release notes, but one of the ways we accomplished this was to change some code that had been doing a linear search to use a binary search instead. (Example: Finding the high/low data point values as part of the process of setting the range of an axis.) If this optimization seems obvious and makes you think "golly, they should have done it that way in the first place", you're absolutely right. :) It's not that we didn't want to do this earlier; it was just that we didn't have the resources to do so...
What we hoped to take advantage of was some already-written-and-tested class implementing an ordered multi-dictionary (a kind of associative array) that could be dropped right into the Silverlight Toolkit source code and used without concern. After we found a suitable implementation, we established that it did, indeed, improve performance on non-trivial data sets in the way that we hoped. Unfortunately, something came up at the last minute and we decided not to proceed with the code we'd been using for the previous few weeks. That left us in kind of a funk because we didn't want to give up the performance improvements we'd already seen...
So I set aside some other tasks and dashed off a quick binary tree implementation to do what we needed and preserve the performance gains from faster searching. The resulting code for BinaryTree is part of the Charting source code and can be viewed here or as part of the Silverlight Toolkit download. It's fairly simple and straightforward, though there are a few things worth calling out:
So that's a bit of background on the BinaryTree class that's used by Silverlight/WPF Charting today. An unbalanced binary tree doesn't give the best performance in the world, but it was quick and easy to implement (under time pressure!) and gives a noticeable boost to many of the common scenarios we set out to improve.
And as it happens, this is all very relevant to the topic of my next post! Here's a hint; see if you can guess what it is... :)