C# Dictionary StringComparer Tip

Dictionary StringComparer. A string Dictionary can be optimized.

This requires a small change that requires no algorithmic analysis. The Dictionary provides a way to specify an ordinal-based string comparer. This results in a much faster Dictionary with string keys.

Tip: The StringComparer.Ordinal parameter can improve string lookup performance by 17%. This amounts to around 10 ns per key lookup.

Benchmark. Passing a StringComparer instance to the Dictionary constructor can boost performance in a Dictionary that uses string keys. This will not work properly on a Dictionary with keys of other value or reference types.

By using the StringComparer.Ordinal class, you tell the Dictionary to perform the fastest ordinal comparisons on the string characters. This improves performance on all lookups. Also, lookups occur when adding elements to a Dictionary.

C# program that benchmarks Dictionary

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

class Program
{
    static void Main()
    {
	var dict1 = new Dictionary<string, bool>();
	var dict2 = new Dictionary<string, bool>(StringComparer.Ordinal);

	var arr = GetStrings(500); // Get random keys
	foreach (string val in arr)
	{
	    dict1[val] = true; // Set key
	    dict2[val] = true; // Set key
	}

	const int m = 50000;
	Stopwatch s1 = Stopwatch.StartNew();
	for (int i = 0; i < m; i++)
	{
	    for (int j = 0; j < arr.Length; j++)
	    {
		bool b = dict1[arr[j]]; // Look up element
		b = dict1[arr[0]];      // Look up first element
	    }
	}
	s1.Stop();
	Stopwatch s2 = Stopwatch.StartNew();
	for (int i = 0; i < m; i++)
	{
	    for (int j = 0; j < arr.Length; j++)
	    {
		bool b = dict2[arr[j]]; // Look up element
		b = dict2[arr[0]];      // Look up first element
	    }
	}
	s2.Stop();
	Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000 * 1000) /
	    (m * arr.Length * 2)).ToString("0.00") + " ns");
	Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000 * 1000) /
	    (m * arr.Length * 2)).ToString("0.00") + " ns");
	Console.Read();
    }

    static string[] GetStrings(int len)
    {
	var arr = new string[len]; // Allocate and return an array of random strings.
	for (int i = 0; i < arr.Length; i++)
	{
	    arr[i] = Path.GetRandomFileName();
	}
	return arr;
    }
}

Output
    The output here depends on your computer's hardware and other factors.
    If this optimization succeeds, the second number will be lower.

57.69 ns   (No comparer)
47.48 ns   (Used StringComparer.Ordinal)

The first Dictionary created uses no parameters. The second uses one parameter, the StringComparer.Ordinal class instance. This parameter specifies how the string key comparisons are performed on the Dictionary.

Tip: Ordinal string compares are faster than other kinds because there is less overhead and less logic to execute.

Discussion. By specifying the StringComparer.Ordinal class to perform comparisons, you may be changing the behavior of the Dictionary in some globalization contexts. But my experience is that more often than not this results in more correct programs.

And: These complex globalization edge cases were never anticipated. They would just cause problems elsewhere in the program.

Tip: The StringComparer.Ordinal argument here not only improves performance of lookups by 17% but can help clarify the program's design.

SortedDictionary. You can supply the StringComparer.Ordinal class instance to the SortedDictionary generic class. My experiments showed that this improves performance. But SortedDictionary was still several times slower than Dictionary.

SortedDictionary

Summary. You can use a comparer class for a Dictionary in the C# language. This yields a performance improvement on a string Dictionary. It might also help uncover globalization problems. Ordinal string comparisons are faster.

And: This accelerates key matching and hash code computations in the Dictionary.

Related Links