[ACCEPTED]-Should I be concerned about .NET dictionary speed?-dictionary

1. You are micro-optimizing. Do you even have 12 working code yet? Remember, "If it 11 doesn't work, it doesn't matter how fast it 10 doesn't work." (Mich Ravera) http://www.codingninja.co.uk/best-programmers-quotes/.

   You have 9 no idea where the bottlenecks will be, and 8 already you're focused on Dictionary. What 7 if the problem is somewhere else?

2. How do 6 you know how the Dictionary class is implemented? Maybe 5 it already uses an array with hashed keys!

P.S. It's 4 really ".NET Dictionaries", not 3 "C# Dictionaries", because C# is 2 just one of several programming languages 1 that use the framework.

Hello, I will be creating a project that 50 will use dictionary lookups and inserts 49 quite a bit. Is this something to be concerned 48 about?

Yes. It is always wise to consider 47 performance factors up front.

The form 46 that your concern should take is as follows: your 45 concern should be encouraging you to write 44 realistic, user-focused performance specifications. It 43 should be encouraging you to start writing 42 performance tests early, and running them 41 often, so that you can see how every single 40 change to the product affects performance. That 39 way you will be informed immediately when 38 a code change causes a user-affecting change 37 in performance. And it should be encouraging 36 you to run profiles often, so that you are 35 reasoning about performance based on empirical 34 measurements, rather than random guesses 33 and hunches.

Also, if I do benchmarking and 32 such and it is really bad, then what is 31 the best way of replacing dictionary with something 30 else?

The best way to do this is to build 29 a reasonable abstraction layer. If you have 28 a class (or interface) which represents 27 the "insert" and "lookup" abstract data 26 type, then you can replace its internals 25 without changing any of the callers.

Note 24 that adding a layer of abstraction itself 23 has a performance cost. If your profiling 22 shows that the abstraction layer is too 21 expensive, if the extra couple nanoseconds 20 per call is too much, then you might have 19 to get rid of the abstraction layer. Again, this 18 decision will be driven by real-world performance 17 data.

Would using an array with "hashed" keys 16 even be faster? That wouldn't help on 15 insert time though will it?

Neither you nor 14 anyone reading this can possibly know which 13 one is faster until you write it both ways 12 and then benchmark it both ways under real-world conditions. Doing 11 it under "lab" conditions will skew your 10 results; you'll need to understand how things 9 work when the GC is under realistic memory 8 pressure, and so on. You might as well ask 7 us which horse will run faster in next year's 6 Kentucky Derby. If we knew the answer just 5 by looking at the racing form, we'd all 4 be rich already. You can't possibly expect 3 anyone to know which of two entirely hypothetical, unwritten 2 pieces of code will be faster under unspecified 1 conditions!

The Dictionary<TKey, TValue> class is actually implemented as a 4 hash table which makes lookups very fast 3 (close to O(1)). See the API documentation for more information. I 2 doubt you could make a better implementation 1 yourself.

Wait and see if the performance of your 8 application is below expectations
If it 7 is then use a profiler to determine if the 6 Dictionary lookup is the source of the problem
If 5 it is then do some tests with representative data to see if 4 another choice of list would be quicker.

In 3 short - no, in general you shouldn't worry 2 about the performance of implementation 1 details until after you have a problem.

I would do a benchmark of the Dictionary, HashTable 5 (HashSet in .NET), and perhaps a home grown 4 class, and see which works out best under 3 your typical usage conditions.

Normally I 2 would say it's fine (insert StackOverflow's 1 favorite premature ejaculation quote here), but if this is a core peice of the application, Benchmark, Benchmark, Benchmark.

The only concern that I can think of is 13 that the speed of the dictionary relies 12 on the key class having a reasonably fast 11 GetHashCode method. Lookups and inserts 10 are really fast, so you shouldn't have any 9 problem there.

Regarding using an array, that's 8 what the Dictionary class does already. Actually 7 it uses two arrays, one for the keys and 6 one for the values.

If you would have any 5 performance problems with a Dictionary, it 4 would be quite easy to make a wrapper for 3 any kind of storage, that has the same methods 2 and behaviour as a Dictionary so that you 1 can replace it seamlessly.

I'm not sure that anyone has really answered 13 this part yet:

Also, if I do benchmarking 12 and such and it is really bad, then what 11 is the best way of replacing dictionary 10 with something else?

For this, wherever 9 possible, declare your variables as IDictionary<TKey, TValue>. That's 8 the main interface that Dictionary derives 7 from. (I'm assuming that if you care that 6 much about performance, then you aren't 5 considering non-generic collections.) Then, in 4 the future, you can change the underlying 3 implementation class without having to change 2 any of the code that uses that dictionary. For 1 example:

IDictionary<string, int> myDict = new Dictionary<string, int>();

If your application is multithreaded then 6 the key part of performance is going to 5 be synchronizing this Dictionary correctly.

If 4 it is single-threaded then almost certainly 3 bottleneck will be elsewhere. Such as reading 2 these objects from wherever you are reading 1 them.

I use Dictionary for UDP relay server . Each 5 time packet arrives it performs Dictionary.ContainsKey 4 and Dictionary[Key] , and it works great 3 (massive number of clients). I had concerns 2 when I was making the thing but it turned 1 out that was last thing I should worry about.

Have a look at C# HybridDictionary Usage

HybridDictionary Class

This class is recommended 6 for cases where the number of elements 5 in a dictionary is unknown. It takes advantage 4 of the improved performance of a ListDictionary 3 with small collections, and offers the flexibility 2 of switching to a Hashtable which handles 1 larger collections better than ListDictionary

You may consider using the C5 library. I've 9 found it to be very fast and thoughtfully 8 designed. Others on stackoverflow have 7 found the same. With C5 you have the option 6 of using general type interfaces (with a 5 captial I), or directly the data structures 4 underneath. Naturally the interfaces allow 3 you to swap out different implementations, but 2 I have found in performance testing that 1 the interfaces will cost you.