TheDeveloperBlog.com


C# Dictionary Versus List Loop

Dictionary vs. list loops. Dictionary optimizes lookup of keys. The List provides an easily-resized array type. But the Dictionary is not faster in all situations. One case where List is faster is when looping over all elements.

Tip: If looping through elements is a common task in a program, a List is more efficient.


Example. This program creates a Dictionary and adds five key-value pairs. Next, it creates a List and adds five strings. These correspond to the keys in the Dictionary. In Method1 and Method2, we use a foreach-loop over the Dictionary and the List.

Also: Some dummy code ensures that the loop executes and is not optimized out by the JIT compiler.

JIT
C# program that benchmarks loops

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

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.

Dictionary GetEnumerator

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.

However: If looping time is prominent, the List would provide better performance.