TheDeveloperBlog.com


C# Dictionary String Key Length

Dictionary string key. 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 much better than longer keys.

So: Are shorter lookup keys faster? We find as keys become shorter, lookup time is reduced.

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.

Note: This micro-benchmark compares 20, 10, 5, and 2 character string keys in a Dictionary.

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("", 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();
    }
}

Next, I found 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, you can improve performance.

And: In my program I programmatically modified the keys to save a total of 10% of key length.


Optimization. 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. This achieves a performance boost in all key adds and lookups, to the tune of 17% or 10 nanoseconds faster.

Dictionary StringComparer Tip

Summary. We achieved a performance boost when using the Dictionary generic class in the C# programming language by shortening and simplifying string keys. Generally, shorter strings perform better than longer ones.