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

I don't think that's unusual. Others have gotten the same results.

I think it's pretty straightforward why one would be slower than the other. SortedDictionary is doing more. It's sorting. Dictionary isn't, so it's faster.

The only true test of what should and should not be performant, is the test you're performed above. I don't think you're doing anything wrong here.

Answer 2

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.