27

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

Also, if I do benchmarking and such and it is really bad, then what is the best way of replacing dictionary with something else? Would using an array with "hashed" keys even be faster? That wouldn't help on insert time though will it?

Also, I don't think I'm micro-optimizing because this really will be a significant part of code on a production server, so if this takes an extra 100ms to complete, then we will be looking for new ways to handle this.

John Saunders
  • 160,644
  • 26
  • 247
  • 397
Earlz
  • 62,085
  • 98
  • 303
  • 499
  • 3
    If dictionary stores and lookups are a central part of your algorithm, benchmarking is in order. This literally takes less time than asking on SO :) – orip Dec 14 '09 at 22:17
  • Dictionary is really fast. See these questions too: http://stackoverflow.com/questions/2151747/c-sharp-binary-trees-and-dictionaries http://stackoverflow.com/questions/4681526/system-collections-generic-dictionary-ultimate-performance – nawfal Apr 03 '13 at 13:08

12 Answers12

82

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

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

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

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

Community
  • 1
  • 1
John Saunders
  • 160,644
  • 26
  • 247
  • 397
  • 36
    +1 for calling out premature optimization... you can't optimize code that hasn't been written – Dave Swersky Dec 14 '09 at 20:24
  • 2
    Another +1 for premature optimization. I agree so much I wrote a new comment in addition to upvoting the answer and clicking the up arrow on Dave's comment. – Daniel Schaffer Dec 14 '09 at 20:28
  • I was going to add a comment to this effect but I knew someone else would get to it first. – Gord Dec 14 '09 at 20:28
  • 18
    "If it doesn't work, it doesn't matter how fast it doesn't work." http://stackoverflow.com/questions/58640/great-programming-quotes/1649033#1649033 – Ryan Lundy Dec 14 '09 at 20:32
  • 61
    It's not "premature optimization" if it's something that will influence the design of the application. You don't want to write an application then halfway through realize that your design is wrong and that you have to rewrite it. People are so quick to regurgitate out-of-context quotes... – Josh Davis Dec 15 '09 at 00:38
  • No, it's premature optimization because the code doesn't work yet! Make it work, make the automated tests work, then if you find you need to change the design because the prformance is inadequate, then you at least have all the automated tests written to prove your faster code _works_ faster. You also don't know ahead of time that this will affect the design. – John Saunders Dec 15 '09 at 00:59
  • 7
    There is video, http://www.youtube.com/watch?v=aAb7hSCtvGw, I saw once with Joshua Bloch talking about how in some it does pay to think about performance before it becomes a problem (I think its about halfway though). From the, Great programming quotes CW - "Weeks of coding can save you hours of planning." –  Dec 15 '09 at 02:11
  • 2
    This downvoter didn't like the attitude displayed in #1. (I am tempted, in the style of the movie The Princess Bride, to call you 'pig'). – ErikE Feb 03 '12 at 00:18
  • @ErikE: thanks for saying. I don't feel there's an "attitude". The two things are different: C# is not .NET. The exact same dictionaries can be used by any other .NET language. I think it's a good idea to call things what they are. – John Saunders Feb 03 '12 at 00:43
  • I actually agree with you--it's a good idea to call things what they are. I always prefer to be exact! On the other hand, the last 3 sentences are irrelevant to the downvote. Do you mind if, without changing the *factual information*, I fix the part I find objectionable? – ErikE Feb 03 '12 at 02:22
  • Go ahead. I'd like to see that. I can always change it back. – John Saunders Feb 03 '12 at 06:02
  • This is indeed premature optimization. Performance and design should always be first planned, but if `O(1)` lookup with a key is what OP wants, then `Dictionary<,>` is what .NET has to offer and worrying about it before having real world data is too much thinking. I mean in .NET, HahSet<>, List<>, LinkedList<>, Dictionary<,>, KeyedCollection<,> etc do different jobs. If you're planning beforehand the type of access/addition your structure would need, that's what is called designing. But if you find Dictionary<> is the right tool, then worrying abt its performance at this stage is worthless. +1 – nawfal Apr 22 '13 at 05:39
  • You didn't answer the question. For some reason I can comment on an upvote but not a downvote, and I suppose I'm going to get nicked for even being bothered by that. – John Thoits Jun 18 '19 at 17:21
  • In game development we have to think of performance up-front or you'll live to have a lot of regrets lol. Sometimes it can make sense to prototype something in a sloppy/suboptimal way and plan to refactor and optimize later, like when you aren't sure how to even do something and need to explore and figure it out. For me, most of the time, writing a bad version first is a huge time waster I can't afford and it does real harm, whereas researching performance and architectural approaches has a very low cost. Performance and advice is contextual, not absolute! – Aaron Carter Dec 05 '22 at 06:15
68

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

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

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

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

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

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

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

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

Eric Lippert
  • 647,829
  • 179
  • 1,238
  • 2,067
  • I agree with, and have used in practice, this approach of using an interface/abstraction up front and then removing it as performance testing indicates. And I'd add not to remove that interface too soon! It can cost you design flexibility down the road which can lead to a lot of refactoring....I've been there too. – Paul Dec 15 '09 at 00:30
  • 2
    I'll take a guess and say "Super Saver" in the 2010 Kentucky Derby. – LarsTech Oct 19 '11 at 19:23
10

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

Anders Fjeldstad
  • 10,724
  • 2
  • 33
  • 50
  • 14
    Not to be Mr Fuzzy Pants here, but O(1) doesn't mean it's fast, it just means that it's constant time. But that constant time might be very long or very short. That said, O(1) tends to be fast in practice. – JulianR Dec 14 '09 at 21:52
10

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

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

Justin
  • 84,773
  • 49
  • 224
  • 367
5

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

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

Neil N
  • 24,862
  • 16
  • 85
  • 145
4

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

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

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

Guffa
  • 687,336
  • 108
  • 737
  • 1,005
4

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

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

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

IDictionary<string, int> myDict = new Dictionary<string, int>();
Travis
  • 956
  • 5
  • 11
2

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

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

yu_sha
  • 4,290
  • 22
  • 19
2

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

Ivan
  • 29
  • 1
1

Have a look at C# HybridDictionary Usage

HybridDictionary Class

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

Adriaan Stander
  • 162,879
  • 31
  • 289
  • 284
0

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

Community
  • 1
  • 1
Paul
  • 5,376
  • 1
  • 20
  • 19
-3

You may want to look at the KeyedCollection class in System.ObjectModel. From the MSDN description, "provides the abstract base class for a collection whose keys are embedded in the values."

Anton
  • 3,170
  • 20
  • 20