C# Dictionary Versus List Loop

You know that Dictionary optimizes lookup of keys while the List provides an easily-resized array type in the C# language. However, the Dictionary is not faster in all situations, such as when looping over all elements.

This C# benchmark tests the performance of looping over Dictionary and List. List is much faster in loops.

Example

This program creates a Dictionary and adds five key/value pairs to it. Next, it creates a List and adds five strings to it; these correspond to the keys in the Dictionary. In Method1 and Method2, we use a foreach-loop over the Dictionary and the List. Some dummy code ensures that the loop executes and is not optimized out.

Program that benchmarks loops [C#]

using System;
using System.Collections.Generic;
using System.Diagnostics;

class Program
{
    static void Main()
    {
	var dictionary = new Dictionary<string, int>();
	dictionary["a"] = 1;
	dictionary["b"] = 2;
	dictionary["c"] = 3;
	dictionary["d"] = 4;
	dictionary["e"] = 5;

	var list = new List<string>();
	list.Add("a");
	list.Add("b");
	list.Add("c");
	list.Add("d");
	list.Add("e");

	var s1 = Stopwatch.StartNew();
	const int max = 10000000;
	for (int i = 0; i < max; i++)
	{
	    Method1(dictionary);
	}
	s1.Stop();
	var s2 = Stopwatch.StartNew();
	for (int i = 0; i < max; i++)
	{
	    Method2(list);
	}
	s2.Stop();
	Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000000) /
	    max).ToString("0.00 ns"));
	Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000000) /
	    max).ToString("0.00 ns"));
	Console.Read();
    }

    static void Method1(Dictionary<string, int> collection)
    {
	foreach (var pair in collection)
	{
	    if (pair.Key == "z")
		throw new Exception();
	}
    }

    static void Method2(List<string> collection)
    {
	foreach (var value in collection)
	{
	    if (value == "z")
		throw new Exception();
	}
    }
}

Output

117.18 ns
78.19 ns

Results. You can see that it was faster to enumerate a List type. The Dictionary took more time to loop over, but the difference was not extreme. Thus, looping over a Dictionary will not cause huge performance problems that a List would fix.

GetEnumerator

For the Dictionary collection, you can improve looping performance slightly by using the GetEnumerator method. This avoids some exception handling overhead. The improvement would still leave Dictionary slower to loop over than the List.

Summary

When choosing between List and Dictionary, one consideration you should take into account is how often looping over the elements will occur. If lookup time is more important, the Dictionary would be best suited for your program. If looping time is prominent, the List would provide better performance.