The performance of the generic IDictionary .NET implementations

Hi, today I would like to show you small experiment I prepared. It is performance measurement of bunch of operations invoked on the generic IDictionary implementations in the .NET Framework. I try to answer for the question: Is the ConcurrentDictinary collection efficient or not? So below is a small experiment benchmark code and my runtime results.

namespace DictionaryBenchmark
{
  using System;
  using System.Collections.Concurrent;
  using System.Collections.Generic;
  using System.Diagnostics;

  class Program
  {
    static void DictionaryTest<TDictinary>(uint count, uint seed)
      where TDictinary : IDictionary<uint, string>, new()
    {
      var dictionary = new TDictinary();

      var stAdd = Stopwatch.StartNew();
      for (uint j = seed; j < count; j += seed)
        for (uint i = j + seed; i > j; i -= 2)
          dictionary.Add(i, Guid.NewGuid().ToString());
      stAdd.Stop();
      Console.WriteLine(
        "In {0} {1} invocations of Add method takes about {2} ms.",
        typeof(TDictinary).Name, count / 2, stAdd.ElapsedMilliseconds);

      var stContains = Stopwatch.StartNew();
      for (uint j = seed; j < count; j += seed)
        for (uint i = j + seed; i > j; i--)
          dictionary.ContainsKey(i);
      stContains.Stop();
      Console.WriteLine(
        "In {0} {1} invocations of ContainsKey method takes about {2} ms.",
        typeof(TDictinary).Name, count, stContains.ElapsedMilliseconds);


      string strVal;
      var stIndexer = Stopwatch.StartNew();
      for (uint j = seed; j < count; j += seed)
        for (uint i = j + seed; i > j; i -= 2)
          strVal = dictionary[i];
      stIndexer.Stop();
      Console.WriteLine(
        "In {0} {1} invocations of get by indexer takes about {2} ms.",
        typeof(TDictinary).Name, count / 2, stIndexer.ElapsedMilliseconds);

      Stopwatch stRemove = Stopwatch.StartNew();
      for (uint j = seed; j < count; j += seed)
        for (uint i = j + seed; i > j; i -= 2)
          dictionary.Remove(i);
      stRemove.Stop();
      Console.WriteLine(
        "In {0} {1} invocations of Remove method takes about {2} ms.",
        typeof(TDictinary).Name, count / 2, stRemove.ElapsedMilliseconds);
    }

    static void Main()
    {
      for (int t = 0; t < 2; t++)
      {
        DictionaryTest<Dictionary<uint, string>>(100000, 100);
        DictionaryTest<ConcurrentDictionary<uint, string>>(100000, 100);
        DictionaryTest<SortedDictionary<uint, string>>(100000, 100);
        DictionaryTest<SortedList<uint, string>>(100000, 100);
      }

      Console.ReadKey();
    }
  }
}

As you can see I measure four implementation of IDictionary interface. It was Dictinary<uint, string>, CocnurrentDictionary<uint,string>, SortedDictionary<uint, string> and SortedList<uint, string>. I measure performance of four methods: Add, ContainsKey with exactly half results equals true and false. I also measure getting value by key indexer and remove all elements from dictionary. And my results is shown below.

In Dictionary`2 50000 invocations of Add method takes about 46 ms.
In Dictionary`2 100000 invocations of ContainsKey method takes about 3 ms.
In Dictionary`2 50000 invocations of get by indexer takes about 3 ms.
In Dictionary`2 50000 invocations of Remove method takes about 3 ms.
In ConcurrentDictionary`2 50000 invocations of Add method takes about 75 ms.
In ConcurrentDictionary`2 100000 invocations of ContainsKey method takes about 9 ms.
In ConcurrentDictionary`2 50000 invocations of get by indexer takes about 4 ms.
In ConcurrentDictionary`2 50000 invocations of Remove method takes about 8 ms.
In SortedDictionary`2 50000 invocations of Add method takes about 101 ms.
In SortedDictionary`2 100000 invocations of ContainsKey method takes about 43 ms.
In SortedDictionary`2 50000 invocations of get by indexer takes about 23 ms.
In SortedDictionary`2 50000 invocations of Remove method takes about 41 ms.
In SortedList`2 50000 invocations of Add method takes about 67 ms.
In SortedList`2 100000 invocations of ContainsKey method takes about 20 ms.
In SortedList`2 50000 invocations of get by indexer takes about 9 ms.
In SortedList`2 50000 invocations of Remove method takes about 2623 ms.
In Dictionary`2 50000 invocations of Add method takes about 57 ms.
In Dictionary`2 100000 invocations of ContainsKey method takes about 4 ms.
In Dictionary`2 50000 invocations of get by indexer takes about 3 ms.
In Dictionary`2 50000 invocations of Remove method takes about 4 ms.
In ConcurrentDictionary`2 50000 invocations of Add method takes about 85 ms.
In ConcurrentDictionary`2 100000 invocations of ContainsKey method takes about 9 ms.
In ConcurrentDictionary`2 50000 invocations of get by indexer takes about 4 ms.
In ConcurrentDictionary`2 50000 invocations of Remove method takes about 7 ms.
In SortedDictionary`2 50000 invocations of Add method takes about 109 ms.
In SortedDictionary`2 100000 invocations of ContainsKey method takes about 46 ms.
In SortedDictionary`2 50000 invocations of get by indexer takes about 23 ms.
In SortedDictionary`2 50000 invocations of Remove method takes about 46 ms.
In SortedList`2 50000 invocations of Add method takes about 78 ms.
In SortedList`2 100000 invocations of ContainsKey method takes about 24 ms.
In SortedList`2 50000 invocations of get by indexer takes about 10 ms.
In SortedList`2 50000 invocations of Remove method takes about 2486 ms.

My conclusions is that ConcurrentDictinary is fast and very efficient. In additions, it can be changed in foreach statement because it iterates by a copy of iterator and also it is the thread-safe implementation of the generic IDictionary, so every other implementation will probably fail in Parallel. For invocations and other asynchronically implementations of operations, I measured. So if you want to have very fast single thread implementation of the generic IDictionary. Dictionary is the best choice. If you have multi-thread operations or your dictionary ConcurrentDictinary will be the best choice. I have big disappointed with SortedDictinary that use O(log2n) algorithm for ContainsKey, but it is slow implementation. Maybe with different data SortedDictinary works faster than others. If you know when feeling free to comment on this blog entry.

Regards,

P ;).

Leave a Reply

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.