Look-up Performance in .Net Generic Collections

A co-worker of mine recently shared some information regarding the performance of generic collections in the .Net Framework. He, as well as I, typically collect large amounts of data and we have typically stored them in a List<string> collection. We then will query this collection to check if some value exists in the list use the Contains() method.

Recently, he began to think about what type would be the fastest generic collection to use for this type of process. He created a very basic and simple performance testing method, ran the test twice for each type of collection and recorded the milliseconds required for each loop.

The results were surprising...

List <string> SortedSet <string> HashSet <string> LinkedList <string> Dictionary <string,bool> SortedDictionary <string,bool>
Run 1 (ms) 39547 24265 5101 38058 5099 26117
Run 2 (ms) 39245 24402 5129 38152 5099 26079

<note>The bool in the dictionary objects are not actually used in the code, it is set to false in the add method.</note>

Testing Method

  1. These requests were from a large number of queries in a small collection… The timings may/will change as the collection sizes increase.
  2. The collections were already established before the queries were executed… Thus, none of the timings take into consideration load times.
  3. Memory allocation was not captured… Each collection type allocates memory differently.

Summary

The performance of each collection type will be unique based on individual programs usage. Of course usage of any of these collections would need to be benchmarked for other object types to determine the exact collection type that should be used… <note important>You should always benchmark and find the right collection for your needs.</note>