C# Dictionary StringComparer Tip

You want to improve the lookup performance of your Dictionary collection in the C# language with a small change that requires no algorithmic analysis. The Dictionary collection in System.Collections.Generic provides a way to specify an ordinal-based string comparer, resulting in much faster Dictionaries with string keys. Here we look at how you can use the StringComparer.Ordinal class in the C# programming language with the Dictionary constructor to improve hash table lookups in many programs.

This optimization can improve string lookup performance by 17%.
This amounts to around ten nanoseconds per key lookup.         
You must specify the StringComparer.Ordinal parameter.

Using ordinal Dictionary

First, this example program demonstrates how specifying a StringComparer instance to the Dictionary constructor can boost performance in a Dictionary that uses string keys. This will not work properly on Dictionaries with keys of other value or reference types. By specifying the StringComparer.Ordinal class, you tell the Dictionary to perform the fastest ordinal-based comparisons on the string characters. This improves performance on all lookups. Because lookups also occur when adding elements to a Dictionary, the Dictionary will also be populated with new values more efficiently.

=== Program that benchmarks Dictionary with StringComparer.Ordinal (C#) ===

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

class Program
{
    static void Main()
    {
        var dict1 = new Dictionary<string, bool>();                       // No comparer
        var dict2 = new Dictionary<string, bool>(StringComparer.Ordinal); // 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 of the benchmark ===
    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)

Overview of program text. This program contains the Main entry point and inside that method it instantiates two Dictionary references. The first Dictionary object created uses no parameters. The second Dictionary object uses one parameter, the StringComparer.Ordinal class instance. This parameter specifies how the string key comparisons are performed on the Dictionary. Remember that ordinal string compares are faster than other kinds because there is less overhead and less logic to execute.

SortedDictionary application

Here we note that you can supply the StringComparer.Ordinal class instance, as shown in the above code example, to the SortedDictionary generic class in the C# programming language. The author's experiments showed that this improves performance on SortedDictionary dramatically, although SortedDictionary was still several times slower than Dictionary. You can find more information on SortedDictionary on this site.

See SortedDictionary.

Recommendation

Here we mention the author's view on this particular optimization on the Dictionary class. By specifying the StringComparer.Ordinal class to perform comparisons, you may actually be changing the behavior of the Dictionary in some globalization contexts. However, the author's experience is that more often than not this results in more correct programs because these complex globalization edge cases were never anticipated and would just cause problems elsewhere in the program. For this reason, the StringComparer.Ordinal argument here not only improves performance of lookups by 17% but can help clarify the purpose and design of the Dictionary.

Summary

Here we looked at how you can specify a comparer class to your Dictionary using the C# programming language, yielding a performance improvement on string Dictionaries and also possibly helping discover globalization problems. In the C# language and .NET Framework, ordinal-based string comparisons are faster, which here accelerates the key matching and possibly hash code computations in the Dictionary. Although the savings is only 10 nanoseconds on a fast computer in a small Dictionary, the accumulation of savings is worthwhile.

See Dictionary Articles.