Performance - SortedDictionary Vs Dictionary

Recently, when I was analyzing a client's code base for performance, I found that they were using the collection SortedDictionary in many places in their projects. After looking at how they are using this collection type, I discovered that they really only needed the collection sorted once. So, I figured that it would be better for performance that we use just Dictionary and sort it once. Before recommending this change to their code, I needed to prove my theory.

I decided to test my theory with different versions of the .NET Framework and .NET Core. Below are the results.

  • .NET 3.5: SortedDictionary = 8,809ms Dictionary = 1,808ms
  • .NET 4.5.2: SortedDictionary = 7,002ms Dictionary = 1,836ms
  • .NET 4.6.1: SortedDictionary = 6,893ms Dictionary = 1,796ms
  • .NET 4.7: SortedDictionary = 6,785ms Dictionary = 1,771ms
  • .NET Core 2: SortedDictionary = 9,147ms Dictionary = 1,646ms

As you can see, using Dictionary with one sort is many times faster than the SortedDictionary. If your app is putting a few hundred items in SortedDictionary, you might not see much of a gain. The client that I wrote this test for can easily see 10K or more of the items in a single collection. To future-proof your code, it would be better just to use a non-sorted collection.

Below is the test code,

  1. static void TestSortedDictionary() {  
  2.     var sd = new SortedDictionary < string,  
  3.         string > ();  
  4.     var sw = new Stopwatch();  
  5.     sw.Start();  
  6.     for (int i = 0; i < 1000000; i++) {  
  7.         sd.Add(Guid.NewGuid().ToString(), DateTime.Now.Ticks.ToString());  
  8.     }  
  9.     sw.Stop();  
  10.     Console.WriteLine("SD={0}", sw.ElapsedMilliseconds.ToString());  
  11. }  
  12. static void TestDictionary() {  
  13.     var list = new Dictionary < string,  
  14.         string > ();  
  15.     var sw = new Stopwatch();  
  16.     sw.Start();  
  17.     for (int i = 0; i < 1000000; i++) {  
  18.         list.Add(Guid.NewGuid().ToString(), DateTime.Now.Ticks.ToString());  
  19.     }  
  20.     var temp = list.OrderBy(p => p.Value);  
  21.     sw.Stop();  
  22.     Console.WriteLine("D={0}", sw.ElapsedMilliseconds.ToString());  
  23. }  

Do you have any performance tips? Please leave a comment below.