Immutable Dictionary Vs Dictionary Vs C5 Vs F# - performance

Your presumption that immutable dictionaries allow faster lookup is wrong, because the way almost all immutable collections manage to avoid copying the whole structure on 'modification' is by storing data in a tree and only copying some of the nodes on 'modification', sharing all other nodes. And tree access will generally be slower than accessing a flat array by index, as the mutable cousins do.

I compared the single-thread read performance of Dictionary<,>, ConcurrentDictionary<,>, and ImmutableDictionary<,> based on your code.

The average results of 30 runs, after warmup:

To get a feel for write performance, I also ran a test which adds 50 more entries to the dictionaries. Again, the average results of 30 runs, after warmup:

Tested on

• .net 4.5.1
• Microsoft Bcl Immutable 1.0.34.0

N.B. It should be noted that immutable dictionaries are so much faster and/or allow for higher levels of concurrency in many real life multi-threaded applications that otherwise would have to resort to slow or error-prone techniques like defensive copying, locking and the likes, in order to cope with mutability in the face of threads. This is especially true if you need snapshot-abilty such as for optimistic concurrency, MVCC.

Btw, if you run your sample code as is, the value for at least the immutable dictionary will be highly untypical in a normal (longer running) application, because for some reason the immutable dictionary apparently needs time to warm up. The difference in performance is enormous. Just have a look at the output of the first 3 runs:

Items    Dict   Conc   Immu
===========================
   100   1.90   1.00 361.81
  1000   1.07   1.00   4.33
 10000   1.24   1.00   1.74
100000   1.00   1.33   2.71
---------------------------
   100   1.06   1.00   2.56
  1000   1.03   1.00   4.34
 10000   1.00   1.06   3.54
100000   1.00   1.17   2.76
---------------------------
   100   1.06   1.00   2.50
  1000   1.66   1.00   4.16
 10000   1.00   1.02   3.67
100000   1.00   1.26   3.13

Your question was about read performance (of frozen dictionaries), but the tree characteristics of immutable collections show similarly in the write performance:

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
                       Mutable (amortized)  Mutable (worst)  Immutable 
───────────────────────────────────────────────────────────────────────
 Stack.Push            O(1)                 O(n)             O(1)      
 Queue.Enqueue         O(1)                 O(n)             O(1)      
 List.Add              O(1)                 O(n)             O(log n)  
 HashSet.Add           O(1)                 O(n)             O(log n)  
 SortedSet.Add         O(log n)             O(n)             O(log n)  
 Dictionary.Add        O(1)                 O(n)             O(log n)  
 SortedDictionary.Add  O(log n)             O(n log n)       O(log n)  
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

The standard dictionary is already quite well optimized. All it really does when you do a lookup is calculate the hash of the provided key (the speed of which depends on the type of the key and how it implements GetHashCode), a modulo operation on the hash value to find the right bucket and then it iterates through the contents of the bucket until it finds the right value (the speed of which depends on the quality of the GetHashCode function, so if the buckets are well balanced and don't contain too many items, and the speed of the Equals method for the type).

All in all, it doesn't do that much for lookups, so I don't think you'll be able to find a significantly faster generic data structure. However, it's possible that depending on how you plan to use the dictionaries, you're able to build a more specialized solution. For example, I needed a really fast lookup where the key was a type. Instead of using a dictionary and doing dictionary[typeof(T)], I made a generic class like so:

class ValueStore<T> 
{
  public static T Value;
}

So I could just do ValueStore<T>.Value with pretty much zero lookup overhead.

Whether or not you could do something similar (and whether it's worth it) really depends on your usecase; how many items the structure would hold, how often it's being read and written to, whether it needs to be threadsafe, how important write speed is, etc. For example, if write speed didn't matter at all but if thread safety was required, you would need to do a copy-on-write, where the data structure is never written to but instead copied, ensuring thread safety and lockless (thus: fast) reads, at the cost of write speeds. Specializing it could go as far as reordering the structure on writes to optimize it so the hash buckets don't contain more than N items.

PS: if you were really desperate for speed but couldn't build a more specialized data structure then you could perhaps get small gains from copying Dictionary<TKey,TValue> and removing the various sanity checks (null checks and such) and virtual/interface method calls. However, I doubt this would give you any more than 20% gain, if that.

The F# map structure is implemented as a binary tree and, as such, is not actually a dictionary. As noted here, a standard .net dictionary is the fastest you're going to get.