4

Which one of the C# <Key, Value> structure implementations has better performance and higher speed?

P.S.1: I Have two thread, one of them writes into collection, and another one reads and writes into it.

P.S.2: Key items are random numbers, and then my access is random. Write and read actions are simultaneous. I am using hashtable, but I want to know is there any better implementation with less resource usage and better performance?

salman
  • 1,966
  • 3
  • 15
  • 18
  • 2
    Have you tried using them in your scenario and profiling them? – Lasse V. Karlsen Mar 02 '10 at 12:04
  • 4
    You could try each of them and measure them for your requirements - System.Diagonistics.StopWatch is your friend – zebrabox Mar 02 '10 at 12:04
  • 11
    Higher speed for insertions? Or Retreval? Or Removal? One often trades off against the other. Why not tell us what your problem is? We can provide better information then. – Binary Worrier Mar 02 '10 at 12:16
  • No! I don't know about profiling. :( Where can I know it at a glance? – salman Mar 02 '10 at 12:57
  • I Have two thread, one of them writes into collection, and another one reads and writes into it. thanks. – salman Mar 02 '10 at 12:58
  • 2
    Not enough info. How often is data written in? Are items retrieved by specific key or do you need to consume them in sorted order? – Joe Mar 02 '10 at 13:00
  • Key items are random numbers, and then my access is random. I am using hashtable, but I want to know is there any better implementation with less resource usage and better performance? – salman Mar 02 '10 at 13:13
  • The theoretically fastest dictionary possible is when you have a laaarge memory to spare and the entries are directly stored in the slots provided by their hash code. So it's just one direct lookup. Practically it's not possible to allocate memory of that size. Your best bet is to 1) initialize dict with as large a capacity as possible and 2) write an efficient has code function, speed wise and distribution wise. You may also want to see [this](http://stackoverflow.com/questions/1869452/) as well as [this](http://stackoverflow.com/questions/16612936/). – nawfal Jun 11 '14 at 08:09

1 Answers1

3

For profiling yourself, there are many options. One free profiler I've used and which I would recommend is EQATEC. There are plenty more to choose from, many of which are referenced in this SO question.

As for implementations, the first few that pop into mind are Dictionary<TKey, TValue>, SortedDictionary<TKey, TValue> and SortedList<TKey, TValue>. Of course, I would be inclined to guess that Dictionary<TKey, TValue> is the fastest since it's the simplest in terms of features. But I haven't ever tested them against one another for speed.

Note that the above classes are all generic, which should make them more efficient than HashTable in at least one sense: they do not require boxing/unboxing of keys and values as System.Object, which results in unnecessary memory allocation.

Something else to be aware of is that since you're in a multithreaded scenario, you'll need to take care to lock your reads/writes somehow. (The above classes, unlike HashTable, are not guaranteed to be thread-safe for multiple readers and a writer.) Locking on a common object may be your best bet in most cases, whereas if you're performing more reads than writes you might want to consider using a ReaderWriterLock or ReaderWriterLockSlim (both of which permit switching between multiple simultaneous readers and a single writer). If you are enumerating over the collection then you should really be locking anyway--even with a HashTable.

Community
  • 1
  • 1
Dan Tao
  • 125,917
  • 54
  • 300
  • 447
  • HashSet would perhaps be good to be considered, I guess. – Will Marcouiller Mar 02 '10 at 15:18
  • @Will: You may be thinking of a different class? A `HashSet` is a collection of unique values; it does not provide key-value pairing. – Dan Tao Mar 02 '10 at 15:24
  • Duh! You're right! I must have gotten confused with a Dictionary>... Sorry! =( – Will Marcouiller Mar 02 '10 at 15:41
  • @Will: Huh... I like that. Actually I feel like a `Dictionary>` might actually be the appropriate storage structure for an *actual* dictionary (you know, like Webster's, with multiple definitions for each word). – Dan Tao Mar 02 '10 at 15:46
  • @Dan: That's good! Indeed this structure would allow one to search for a word and then get the resulting definitions for this word. Sounds great! I guess I'll remember the idea and apply it when it is appropriate. I have seen such code in the LINQ to AD sample code by Bart de Smet, from Microsoft. He uses it to keep track of property changes. – Will Marcouiller Mar 02 '10 at 16:50