Conversion of an IEnumerable to a dictionary for performance?

Question

I have recently seen a new trend in my firm where we change the IEnumerable to a dictionary by a simple LINQ transformation as follows:

enumerable.ToDictionary(x=>x);

We mostly end up doing this when the operation on the collection is a Contains/Access and obviously a dictionary has a better performance in such cases.

But I realise that converting the Enumerable to a dictionary has its own cost and I am wondering at what point does it start to break-even (if it does) i.e the performance of IEnumerable Contains/Access is equal to ToDictionary + access/contains.

Ok I might add there is no databse access the enumerable might be created from a database query and thats it and the enumerable may be edited after that too..

Also it would be interesting to know how does the datatype of the key affect the performance?

The lookup might be 2-5 times generally but sometimes may be one too. But i have seen things like For an enumerable:

 var element=Enumerable.SingleorDefault(x=>x.Id);
 //do something if element is null or return

for a dictionary:

 if(dictionary.ContainsKey(x))
 //do something if false else  return

This has been bugging me for quite some time now.

Answer 1

Performance of Dictionary Compared to IEnumerable

A Dictionary, when used correctly, is always faster to read from (except in cases where the data set is very small, e.g. 10 items). There can be overhead when creating it.

Given m as the amount of lookups performed against the same object (these are approximate):

• Performance of an IEnumerable (created from a clean list): O(mn)
  • This is because you need to look at all the items each time (essentially m * O(n)).
• Performance of a Dictionary: O(n) + O(1m), or O(m + n)
  • This is because you need to insert items first (O(n)).

In general it can be seen that the Dictionary wins when m > 1, and the IEnumerable wins when m = 1 or m = 0.

In general you should:

• Use a Dictionary when doing the lookup more than once against the same dataset.
• Use an IEnumerable when doing the lookup one.
• Use an IEnumerable when the data-set could be too large to fit into memory.
  • Keep in mind a SQL table can be used like a Dictionary, so you could use that to offset the memory pressure.

Further Considerations

Dictionarys use GetHashCode() to organise their internal state. The performance of a Dictionary is strongly-related to the hash code in two ways.

• Poorly performing GetHashCode() - results in overhead every time an item is added, looked up, or deleted.
• Low quality hash codes - results in the dictionary not having O(1) lookup performance.

Most built-in .Net types (especially the value types) have very good hashing algorithms. However, with list-like types (e.g. string) GetHashCode() has O(n) performance - because it needs to iterate over the whole string. Thus you dictionary's performance can really be seen as (where M is the big-oh for an efficient GetHashCode()): O(1) + M.

Answer 2

It depends....

How long is the IEnumerable?

Does accessing the IEnumerable cause database access?

How often is it accessed?

The best thing to do would be to experiment and profile.

Answer 3

If you searching elements in your collection by some key very often - definatelly the Dictionary will be faster because or it's hash-based collection and searching is faster in times, otherwise if you don't search a lot thru the collection - the convertion is not necessary, because time for conversion may be bigger than you one or two searches in the collection,