C# Dictionary String Key Length

Are shorter Dictionary string keys faster? Is it worthwhile to prefer shorter string keys in your Dictionary? We find out whether shorter keys, which require fewer HashCode computations, perform significantly better than longer keys.

Question: Are shorter lookup keys significantly faster?

Answer: As keys get shorter, lookup time gets faster.

Dictionary string key length benchmark

Key A - 20 characters: 4436 ms [slowest]
Key B - 10 characters: 2010 ms
Key C - 5 characters:  1749 ms
Key D - 2 characters:  1575 ms [fastest]

Benchmark

My intuition was that shorter keys would be faster, but I didn't know the relative times required. The application I was optimizing does very little except look up Dictionary keys. I assumed shorter keys would perform better, and spent several hours making changes without actually testing this. Here I show a micro-benchmark that compares 20, 10, 5, and 2 character string keys.

String key length benchmarking code [C#]

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

class Program
{
    static Dictionary<string, bool> _d = new Dictionary<string, bool>();

    static void Main()
    {
	_d.Add("dotnet", true);
	_d.Add("dotnetperls.com", true);
	_d.Add("samuel allen", true);

	string e0 = "01234567890123456789";
	string e1 = "0123456789";
	string e2 = "01234";
	string e3 = "01";

	const int m = 100000000;
	Stopwatch s1 = new Stopwatch();
	s1.Start();
	for (int i = 0; i < m; i++)
	{
	    if (_d.ContainsKey(e0))
	    {
	    }
	}
	s1.Stop();
	Stopwatch s2 = new Stopwatch();
	s2.Start();
	for (int i = 0; i < m; i++)
	{
	    if (_d.ContainsKey(e1))
	    {
	    }
	}
	s2.Stop();
	Stopwatch s3 = new Stopwatch();
	s3.Start();
	for (int i = 0; i < m; i++)
	{
	    if (_d.ContainsKey(e2))
	    {
	    }
	}
	s3.Stop();
	Stopwatch s4 = new Stopwatch();
	s4.Start();
	for (int i = 0; i < m; i++)
	{
	    if (_d.ContainsKey(e3))
	    {
	    }
	}
	s4.Stop();
	Console.WriteLine("{0},{1},{2},{3}",
	    s1.ElapsedMilliseconds,
	    s2.ElapsedMilliseconds,
	    s3.ElapsedMilliseconds,
	    s4.ElapsedMilliseconds);
	Console.Read();
    }
}

Results. Next, what I found is that there is an incremental speedup as you reduce the number of characters in the lookup string key. This is for 100 million lookups. By reducing the lengths on the string keys for Dictionary in your C# program, you can improve performance. In my program, I programmatically modified the keys to save a total of 10% of key length.

String key optimization

Here we note an easier optimization you can make to the string keys in your Dictionary. Internally, the Dictionary collection in the base class library does many string comparisons using an IEqualityComparer class. You can provide a StringComparer class instance to the parameter list of the Dictionary constructor to achieve a performance boost in all key adds and lookups, to the tune of 17% or 10 nanoseconds faster. This site has more information.

Summary

Here we saw how you can achieve a performance boost when using the Dictionary generic class in the C# programming language by shortening and simplifying your string keys. Generally, shorter strings perform better than longer ones.