.NET Framework - Any way to get Dictionary<> to be a little faster?

Question

I'm doing a Dictionary<> lookup in an O(n^2) loop and need it to be ridiculously fast. It's not. Does anyone have any insight into how Dictionary<> is implemented? I'm testing Dictionary performance with an isolated test case after running my code through a profiler and determining Dictionary lookups are the bulk of the CPU time.. My test code is like this:

Int32[] keys = new Int32[10] { 38784, 19294, 109574, 2450985, 5, 398, 98405, 12093, 909802, 38294394 };

Dictionary<Int32, MyData> map = new Dictionary<Int32, MyData>();
//Add a bunch of things to map


timer.Start();
Object item;
for (int i = 0; i < 1000000; i++)
{
   for (int j = 0; j < keys.Length; j++)
   {
      bool isFound = map.ContainsKey(keys[j]);
      if (isFound)
      {
         item = map[keys[j]];
      }
   }
}
timer.Stop();

ContainsKey and map[] are the two slow parts (equally slow).. If i add a TryGetValue, it's nearly identical in speed to ContainsKey. Here's some interesting facts..

A Dictionary<Guid, T> is about twice as slow as Dictionary<Int32, T>. Dictionary<String, T> is about twice as slow as a Guid dictionary. A Dictionary<Byte, T> is a good 50% faster than using Ints. This leads me to believe that a Dictionary is doing an O(log n) binary search to find the key, and the comparison operators on the keys are the bottleneck. For some reason, I don't believe it's implemented as a Hashtable, because .NET already has a Hashtable class, and in my experience it's even slower than Dictionary.

The dictionaries I'm building are only accessed by one thread at a time, so read locking is not an issue. RAM is also not an issue. The dictionary will most likely only have about 10 buckets, but each bucket can point to one of about 2,000 possibly things. Does anyone have any feedback on how to make this faster? Thanks!

Mike

Answer 1

If you only have 10 buckets with 2000 things each could you just build a single list with all 20000 things which can be directly indexed by a key known to your loop? For example:

List<MyData> = new List(); 

//add all items to list indexed by their key (RAM is not an issue right?)

item = ItemList[key];

This way you reference them directly with no dictionary or hash lookup.

Answer 2

The dictionary is implemented using a hash table, I have looked at the code using Reflector a while back.

"The dictionary will most likely only have about 10 buckets, but each bucket can point to one of about 2,000 possibly things."

There is your problem. The dictionary uses the hash to locate the bucket, but the lookup in the bucket is linear.

You have to implement a hash algorithm with a better distribution to get better performance. The relation should be at least the opposite, i.e. 2000 buckets with 10 items each.

Answer 3

It sounds like you're saying that your dictionary will only have 10 items in it. If so, a hash table may be unwarranted. You can just store your data in a list/array and either iterate over it or use a binary search to find your keys (try both to see what's faster).

If you use a binary search, your list will have to be sorted; if you just iterate over your list and there are some keys that are looked-up more frequently than others, you can put them at the beginning of the list to speed things up.

On the other hand, if your keys are known in advance, you can write your own implementation of a hash table with a fast and perfect hash function (i.e. no collisions), and that should be unbeatable.

Answer 4

The insight into the inner workings of the hash table are spot on. You should definitely be using TryGetValue as your entire inner loop:

  map.TryGetValue(keys[j], out item);

doing ContainsKey and Item[] is doing the hard part (the lookup) twice. An extra if and an extra keys[j] are minor, but will add up in a tight loop. Using a foreach over your keys will probably be slower, but depending on the actual contents of the loop, it might be worth profiling.

Answer 5

Adding to the comments about creating your own implementation based on knowing the data, here is an example that will have no clashes. This may throw OutOfMemoryExceptions based on the size of the objects. I tried using an int indexer but that would throw an OutOfMemoryException. If null is returned the item doesn't exist.

I haven't profiled this but I would expect minor speed improvements, but larger memory use.

public class QuickLookup<T> where T : class
{
    private T[] _postives = new T[short.MaxValue + 1];
    private T[] _negatives = new T[short.MaxValue + 1];
    public T this[short key]
    {
        get
        {
            return key < 0 ? _negatives[(key * -1) - 1] : _postives[key];
        }
        set
        {
            if (key < 0)
                _negatives[key * -1] = value;
            else
                _postives[key] = value;
        }
    }
}