Performance: SortedDictionary vs Dictionary

20171101_200415199_iOSRecently when I was analyzing a clients code base for performance, I found that they were using the collection SortedDictionary in many places in their projects. After looking on how they are using this collection type, I discovered that they really only needed  the collection sorted once. So I figured, that if would be better performance to 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 version 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 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:

static void TestSortedDictionary()
{
    var sd = new SortedDictionary<string, string>();
    var sw = new Stopwatch();

    sw.Start();

    for (int i = 0; i < 1000000; i++)
    {
        sd.Add(Guid.NewGuid().ToString(), DateTime.Now.Ticks.ToString());
    }

    sw.Stop();

    Console.WriteLine("SD={0}", sw.ElapsedMilliseconds.ToString());
}

static void TestDictionary()
{
    var list = new Dictionary<string, string>();
    var sw = new Stopwatch();
    
    sw.Start();

    for (int i = 0; i < 1000000; i++)
    {
        list.Add(Guid.NewGuid().ToString(), DateTime.Now.Ticks.ToString());
    }
    
    var temp = list.OrderBy(p => p.Value).ToArray();
    
    sw.Stop();

    Console.WriteLine("D={0}", sw.ElapsedMilliseconds.ToString());
}