C#: Speeding up Dictionary

Level: 2 where 1 is noob and 5 is totally awesome
System: C# on .NET

I like micro optimizing, I find it very funny, relaxing and I learn a lot while doing it. When working on HaveBox, I sometimes discover odd things, which can add performance to HaveBox. Most of the work on HaveBox is micro optimization, which is often expensive and not worth the effort in larger system. But some days ago, when I worked on HaveBox, I did stumble onto something regarding the Dictionary class. It is still micro optimization, but it is so simple and cheap, it might be interesting for other than me.

My Discovery was

When trying to get a value from a key in a Dictionary, the Dictionary class is using a comparer class, to compare the given key with the keys in the dictionary. When instantiating a Dictionary class with the default constructor, The Dictionary class is using the EqualityComparer class as default comparer class. The EqualityComparer class is designed to handle general situations, and is used in other contexts than Dictionary, so it have null checks. These null checks can slow down the Dictionary.

The Trick

As you might have guess, the trick is to write you own comparer, which is amazingly simple. It is inheriting the interface IEqualityComparer, implement the 2 method and then inject it into the Dictionary contructor. Like:

1:  using System;  
2:  using System.Collections.Generic;  
3:  using System.Diagnostics;  
4:    
5:  namespace DictionaryPerformance  
6:  {  
7:    public class Program  
8:    {  
9:      public class DIYCompare : IEqualityComparer<string>  
10:      {  
11:        public bool Equals(string x, string y)  
12:        {  
13:          return x == y;  
14:        }  
15:    
16:        public int GetHashCode(string obj)  
17:        {  
18:          return obj.GetHashCode();  
19:        }  
20:      }  
21:    
22:      static void Main(string[] args)  
23:      {  
24:        IDictionary<string, string> strings = new Dictionary<string, string>();  
25:        IDictionary<string, string> stringsWithDIYCompare = new Dictionary<string, string>(new DIYCompare());  
26:    
27:        for(var i = 0; i < 1000; i++)  
28:        {  
29:          strings.Add("Ipsum " + i, "Not important");  
30:          stringsWithDIYCompare.Add("Ipsum " + i, "Not important");  
31:        }  
32:    
33:        var stopwatch = new Stopwatch();  
34:    
35:        Console.WriteLine("@Intel I5-3337");  
36:    
37:        string tempStr = "";  
38:    
39:        stopwatch.Restart();  
40:        for (var i = 0; i < 1000000; i++)  
41:        {  
42:          strings.TryGetValue("Ipsum 999", out tempStr);  
43:        }  
44:        stopwatch.Stop();  
45:    
46:        Console.WriteLine("Fetched 1 of 1000 elements 1.000.000 times with default comparer and TryGet : {0} ms", stopwatch.ElapsedMilliseconds);  
47:    
48:        stopwatch.Restart();  
49:        for (var i = 0; i < 1000000; i++)  
50:        {  
51:          stringsWithDIYCompare.TryGetValue("Ipsum 999", out tempStr);  
52:        }  
53:        stopwatch.Stop();  
54:    
55:        Console.WriteLine("Fetched 1 of 1000 elements 1.000.000 times with DIY comparer and TryGet : {0} ms", stopwatch.ElapsedMilliseconds);  
56:      }  
57:    }  
58:  }  
59:    

The Numbers

 @Intel I5-3337  
 Fetched 1 of 1000 elements 1.000.000 times with default comparer and TryGet : 56  
  ms  
 Fetched 1 of 1000 elements 1.000.000 times with DIY comparer and TryGet : 49 ms  
 Press any key to continue . . .  

That's all.