Simple dictionary search slow .Net compared to flat array

Question

I found that dictionary lookups can be very slow when compared to access with flat arrays. Any idea why? I use Ants Profiler for performance testing. Here is an example function that reproduces the problem:

private static void NodeDisplace() { var nodeDisplacement = new Dictionary<double, double[]>(); var times = new List<double>(); for (int i = 0; i < 6000; i++) { times.Add(i * 0.02); } foreach (var time in times) { nodeDisplacement.Add(time, new double[6]); } var five = 5; var six = 6; int modes = 10; var arrayList = new double[times.Count*6]; for (int i = 0; i < modes; i++) { int k=0; foreach (var time in times) { for (int j = 0; j < 6; j++) { var simpelCompute = five * six; // 0.027 sec nodeDisplacement[time][j] = simpelCompute; //0.403 sec arrayList[6*k+j] = simpelCompute; //0.0278 sec } k++; } } } 

Notice the relative magnitude between flat matrix access and dictionary access? A flat array is about 20 times faster than a dictionary (0.403 / 0.0278), after considering the manipulation of the array index ( 6*k+j ).

Oddly enough, the dictionary search takes up most of my time, and I have to optimize it.

Answer 1

Yes, I'm not surprised. The point of dictionaries is that they are used to search for arbitrary keys. Consider what should happen to dereference a single array:

• Check borders
• Multiply Index by Element Size
• Add pointer to pointer

Very, very fast. Now to search for a dictionary (very crude, implementation dependent):

• Potentially check key for invalidation
• Take the key hash
• Find the correct slot for this hash code (perhaps the “mod prime” operation)
• Probably search for an array element to find information for this slot.
• Compare hash codes
• If the hash codes match, compare for equality (and perhaps move on to the next hash code match)

If you have “keys” that can be easily used as indexes of arrays (for example, continuous integers or something that can easily be matched with continuous integers), then this will be very, very fast. This is not a basic use of hash tables. They are good for situations that cannot be easily displayed in this way - for example, when searching by strings or an arbitrary double value (rather than doubles that are evenly distributed and can be easily matched to integers).

I would say that your title is misleading - it’s not that looking up a dictionary is slow, it is that when arrays are a more suitable approach, they are ridiculously fast.

Answer 2

In addition, Jon answer I would like to add that your inner loop is not very suitable, as a rule, you do a minimum of work in the inner loop and then the relative loss of dictionary performance is somewhat lower.

If you look at the Double.GetHashCode() code in Reflector, you will find that it executes 4 lines of code (assuming your double is not 0), this is more than the body of your inner loop. Dictionary<TKey, TValue>.Insert() (called the dialing index) is even more code, almost full screen.

The thing with the dictionary compared to a flat array is that you do not waste a lot of memory when your keys are not dense (as in your case), and that reading and writing ~ O (1) is like arrays (but with a higher constant )

As a note, you can use a multidimensional array instead of the 6*k+j trick.
Declare it this way

 var arrayList = new double[times.Count, 6]; 

and use it that way

 arrayList[k ,j] = simpelCompute; 

It will not be faster, but easier to read.