I recently had to do some performance optimizations against a sorted dictionary that yielded some interesting results...
Background: I am used to using Tuples a lot, simply because they are easy to use and normally quite efficient. Please remember that Tuples were changed from structs to classes back in .NET 4.0.
Problem: A struct decreased performance!
I had a SortedDictionary that was using a Tuple as a key, so I thought "hey, I'll just change that tuple to a struct and reduce the memory usage." ...bad news, that made performance WORSE!
Why would using a struct make performance worse? It's actually quite simple and obvious when you think about it: it was causing comparisons to repeatedly box the primitive data structure, thus allocating more memory on the heap and triggering more garbage collections.
Solution: Use a struct with an IComparer.
I then created a custom struct and used that; it was must faster, but it was still causing boxing because of the non-generic IComparable interface. So finally I added a generic IComparer and passed that into my dictionary constructor; my dictionary then ran fast and efficient, causing a total of ZERO garbage collections!
See for yourself:
The Moral of the Story
Try to be aware of what default implementations are doing, and always remember that boxing to object can add up fast. Also, pay attention to the Visual Studio Diagnostics Tools window; it can be very informative!
Here is how many lines of code it took to achieve a 5x performance increase:
private struct MyStruct
{
public MyStruct(int i, string s) { I = i; S = s; }
public readonly int I;
public readonly string S;
}
private class MyStructComparer : IComparer<MyStruct>
{
public int Compare(MyStruct x, MyStruct y)
{
var c = x.I.CompareTo(y.I);
return c != 0 ? c : StringComparer.Ordinal.Compare(x.S, y.S);
}
}
Test Program
I have written some detailed comments in the Main function about what each test is doing and how it will affect performance. Let's take a look...
