Unexpected poor performance of SortedDictionary compared with Dictionary

Question

I don't understand why the performance of SortedDictionary is approximately 5x slower than Dictionary for setting and retrieving values. I expected inserts and deletes to be slower but not updates or retrieves. I have tested .Net 3.5 and .Net 4.0 release compiled code. An array of random keys was pre-computed to ensure random variations weren't responsible for the differences on random access.

Here are the following scenarios tested.

1. Sequential update of each value using [key] accessor
2. Sequential access of each value using [key] accessor
3. Sequential access of each value using TryGetValue
4. Random access of each value using [key] accessor
5. Random access of each value using TryGetValue

Anyone know why the performance difference?

Please if I am doing something wrong or stupid please point it out.

Sample Code: Simply switch out Dictionary with SortedDictionary to test the difference.

    const int numLoops = 100;
    const int numProperties = 30;
    const int numInstances = 1000;

    static void DictionaryBench(int numLoops, int numValues, int numInstances, string[] keyArray)
    {
        Stopwatch sw = new Stopwatch();
        double total = 0.0d;

        for (int j = 0; j < numLoops; j++)
        {
            //sw.Start();
            Dictionary<string, object> original = new Dictionary<string, object>(numValues);
            for (int i = 0; i < numValues; i++)
            {
                original.Add(String.Format("Key" + i.ToString()), "Value0:" + i.ToString());
            }
            List<Dictionary<string, object>> collectionList = new List<Dictionary<string, object>>(numInstances);
            for (int i = 0; i < numInstances; i++)
            {
                collectionList.Add(new Dictionary<string, object>(original));
            }
            sw.Start();
            //Set values on each cloned instance to uniqe values using the same keys
            for (int k = 0; k < numInstances; k++)
            {
                for (int i = 0; i < numValues; i++)
                {
                    collectionList[k]["Key" + i.ToString()] = "Value" + k.ToString() + ":" + i.ToString();
                }
            }

            //Access each unique value
            object temp;
            for (int k = 0; k < numInstances; k++)
            {
                for (int i = 0; i < numValues; i++)
                {
                    temp = collectionList[k]["Key" + i.ToString()];
                }
            }
            //Random access
            //sw.Start();
            for (int k = 0; k < numInstances; k++)
            {
                for (int i = 0; i < numValues; i++)
                {
                    collectionList[k].TryGetValue(keyArray[i],out temp);
                }
            }
            sw.Stop();
            total += sw.ElapsedMilliseconds;
            sw.Reset();
        }

Answer 1

SortedDictionary uses a binary search lookup, which is O(log n).
Dictionary uses a hashtable, which is O(1).

Therefore, Dictionary gives faster lookups.

The difference will be even greater with string keys, which are costly to compare.
A Dictionary will only iterate the string twice (or more if there are hash collisions) - once to compute the hashcode, and once to ensure that it's an exact match. A SortedDictionary will iterate the string for every comparison.