Using structures as composite keys in C# dictionaries

When working with data sets, we often use collections that allow access to data by key. Using a dictionary allows us to get a value from a set with O(1) computational complexity, regardless of how large the collection is. Usually, the key is a simple value type or a string.

The problem arises when we want to use multiple values in the form of a composite key. The usual solution is to create a method that generates a string based on multiple fields and then use the resulting string in dictionaries. Such a procedure is often sufficient for us, but it is not the only option.

In this article, I will introduce the possibilities of using structures as composite keys and what we need to be aware of to avoid performance degradation.

Analyzed structure

Let’s start by presenting the structure under discussion. Our dictionary key will consist of two values, where the first is a string and the second is an integer. Let’s assume that the string represents the country code while the integer represents the subscription identifier. We will use the unique combination of country code and subscription to determine which supplier provides the services.

public struct SupplierKey
{
    public string CountryCode { get; set; }
 
    public int SubscriptionId { get; set; }
}

Next, we want to retrieve the supplier for a specific user using the following dictionary:

Dictionary<SupplierKey, string> SuppliersMapping { get; set; }

The presented dictionary will work, but it will be far from efficient, and we cannot describe the implementation of the structure as correct and following the good practices of the C# language.

Before we move on to examining performance and finding and fixing bugs, we must first discuss the basics of strings, structures, and dictionaries.

Strings

Our structure, which is a value type, contains a string, which is a reference type. As is known, value types are compared by value, while reference types are compared by checking whether the reference points to the same address. Fortunately, strings in C# already have the GetHashCode and Equals methods overridden. This eliminates the need to worry about whether two reference-type objects with the same value are equal.

Equals and GetHashCode for strings

The GetHashCode method goes character by character and performs bitwise operations on the bytes of each character to calculate the final hash code. We can see a similar thing when we analyze the Equals method, where a typical reference check is followed by a calling the EqualsHelper method. Using Span, the helper method iterates over each character from the string and compares its bytes with the bytes of the corresponding character from the other string.

We should also take note of the important comment above the methods we’ve been discussing (System.Private.CoreLib/src/System/String.Comparison.cs):

If strings A and B are such that A.Equals(B), then they will return the same hash code.

As we will see later when we discuss collections, getting the same hash code for equal objects will be important for us. For now, let’s note that changing how a type is compared means changing how the hash code is calculated so that two equal instances return the same code.

Structures

As we begin discussing structures in .NET, it is important to know that they implicitly derive from the ValueType class. This class is the basis that overrides virtual methods from the base Object class, making their implementation more tailored to the needs of value types.

It’s also worth mentioning that because of this implicit inheritance, structures can’t inherit from any other class or structure. In addition, the ValueType class is marked as special and can’t act as a base class for any other class.

When examining how we compare structures and calculate their hash code, we are essentially analyzing methods that come from the ValueType class. The source code for ValueType is available at the link (System.Private.CoreLib/src/System/ValueType.cs) and is not overwhelming at first glance. The file measures just 170 lines of C# code, but when we look closely, we will see that the full code for its methods is not here. We are analyzing C# code that references unmanaged and high-performance CoreCLR code in C++.

Equals in structures

The Equals method has a high-level algorithm defined that references C++ code. The comparison itself begins with a type check. If the types do not match, we immediately know that the instances are not equal. Next, we check if a byte-by-byte comparison is possible. This depends, among other things, on whether all fields are value types. If there is at least one reference type field, we must skip the quick byte check and move on.

There are a few other conditions that can be found in the C++ code (coreclr/vm/comutilnative.cpp). One part of the check is whether Equals or GetHashCode has been overloaded. In our analyzed structure, we used a field with a string type, so we need to proceed with a slower comparison.

Further, the values of all fields are extracted using reflection, which is then used for the final comparison of structures. If we look at the parameters and types used, we will see Object everywhere, which means that we will not avoid boxing, also when comparing each of the fields. The combination of boxing and reflection gives us an obvious reason why this method is inefficient for structures.

GetHashCode in structures

The GetHashCode method is a bit more complex, but, like Equals, it has two main algorithms to choose from, fast and slow. The selection of which is based on the same conditions as before. The fast algorithm calculates the hash code based on bytes, while the slower one is based on a type-specific calculated strategy (coreclr/vm/comutilnative.cpp).

Leaving aside the details that are unnecessary for us now, only the first field from the object is selected, and only this field is used to calculate the hash code. This means that for any structure that has at least one field of reference type, the hash code will be the same if the first field has the same value.

First issue – without an overridden GetHashCode method, structures only use the first field to calculate the hash code

The information obtained by analyzing the source code of the ValueType class is the basis for repairing the implementation of the SupplierKey structure.

As we found out, SupplierKey, in its current form, uses only the first field (country code) to calculate the hash code. This is confirmed by the code below, where changing the subscription ID does not generate a new hash code.

var key1 = new SupplierKey { CountryCode = "DE", SubscriptionId = 1 };
var key2 = new SupplierKey { CountryCode = "DE", SubscriptionId = 2 };
var key3 = new SupplierKey { CountryCode = "PL", SubscriptionId = 1 };
var key4 = new SupplierKey { CountryCode = "PL", SubscriptionId = 2 };
 
Console.WriteLine(key1.GetHashCode()); // 876931578
Console.WriteLine(key2.GetHashCode()); // 876931578
Console.WriteLine(key3.GetHashCode()); // 1001209387
Console.WriteLine(key4.GetHashCode()); // 1001209387

What this means for us is that we will be operating on repeated hash codes when using this structure as a key in a dictionary. This is important for performance reasons since the hash code of a key is used to determine which index in the internal array of a dictionary the entry we are inserting will occupy.

If we have multiple objects with the same hash code, we can’t just use the index to extract values from the dictionary. We also must check the other objects with the same hash code to see which one we want. Thus, our assumed computational complexity O(1) turns into O(n). The code discussed is located inside the Dictionary.FindValue method (System.Private.CoreLib/src/System/Collections/Generic/Dictionary.cs).

Fixing the first issue

We have found a good reason to overload the GetHashCode method. We need to use the remaining fields so that the hash is calculated for the entire key, not just for a part of it. We will use the HashCode.Combine() method for this.

public struct SupplierKey_WithHashCode
{
    public string CountryCode { get; set; }
 
    public int SubscriptionId { get; set; }
 
    public override int GetHashCode()
    {
        return HashCode.Combine(CountryCode, SubscriptionId);
    }
}

Once we override the GetHashCode method, we get a different hash code every time we change the value of any of the fields in our structure.

var key1 = new SupplierKey_WithHashCode { CountryCode = "DE", SubscriptionId = 1 };
var key2 = new SupplierKey_WithHashCode { CountryCode = "DE", SubscriptionId = 2 };
var key3 = new SupplierKey_WithHashCode { CountryCode = "PL", SubscriptionId = 1 };
var key4 = new SupplierKey_WithHashCode { CountryCode = "PL", SubscriptionId = 2 };
 
Console.WriteLine(key1.GetHashCode()); // 92690337
Console.WriteLine(key2.GetHashCode()); // 535339796
Console.WriteLine(key3.GetHashCode()); // -881525390
Console.WriteLine(key4.GetHashCode()); // 195508225

It remains to see if we can get the same hash code for the same values. The code below confirms this.

var key1 = new SupplierKey_WithHashCode { CountryCode = "DE", SubscriptionId = 1 };
var key2 = new SupplierKey_WithHashCode { CountryCode = "DE", SubscriptionId = 1 };
 
Console.WriteLine(key1.GetHashCode()); // 1393730686
Console.WriteLine(key2.GetHashCode()); // 1393730686

First performance tests

In theory, we have fixed the problem, but let’s now conduct a first performance test by checking how long it takes to retrieve values from the dictionary. We will use three sets of data constituting the Cartesian product for X countries and Y subscriptions:

Set 1. X = 50, Y = 50, X×Y = 2 500,

Set 2. X = 100, Y = 100, X×Y = 10 000,

Set 3. X = 200, Y = 200, X×Y = 40 000.

We will be using the BenchmarkDotNet library and .NET 8.0.1 to run the tests. The following code shows the DictionaryGetTests class, which includes the following segments:

• The Size field determines the size of the collection. Its value will vary depending on which data set is used for testing.
• The IterationSetup method is called before each test and is designed to initialize the dictionaries and insert values into them. The code contained in this method will not be taken into account when measuring performance.
• The DictionaryGet_WithoutHashCode and DictionaryGet_WithHashCode methods are the tested blocks of code. This is where the iteration happens across all countries and subscriptions to retrieve values from the corresponding dictionary. For DictionaryGet_WithoutHashCode, the key does not have an overridden GetHashCode method, and for DictionaryGet_WithHashCode, we use a key with an overridden GetHashCode method.

using System.Collections.Generic;
using System.Linq;
using BenchmarkDotNet.Attributes;
 
[MemoryDiagnoser(true)]
public class DictionaryGetTests
{
    // Collection size
    [Params(50, 100, 200)]
    public int Size;
 
    // Tested dictionaries
    private Dictionary<SupplierKey, string> _suppliersMapping_WithoutHashCode;
    private Dictionary<SupplierKey_WithHashCode, string> _suppliersMapping_WithHashCode;
 
    // Available keys
    private SupplierKey[] _supplierKeys_WithoutHashCode;
    private SupplierKey_WithHashCode[] _supplierKeys_WithHashCode;
 
    // The value for each of the keys in the dictionary is invariable
    private const string Value = "supplier";
 
    // Test data preparation method 
    [IterationSetup]
    public void IterationSetup()
    {
        _suppliersMapping_WithoutHashCode = new Dictionary<SupplierKey, string>(Size*Size);
        _suppliersMapping_WithHashCode = new Dictionary<SupplierKey_WithHashCode, string>(Size*Size);
 
        for (int code = 0; code < Size; code++)
        {
            var countryCode = ((char)code).ToString();
 
            for (int subscriptionId = 0; subscriptionId < Size; subscriptionId++)
            {
                // We add a key with the same values but a different type to the dictionaries

                _suppliersMapping_WithoutHashCode.Add(new SupplierKey
                {
                    CountryCode = countryCode,
                    SubscriptionId = subscriptionId
                }, Value);
 
                _suppliersMapping_WithHashCode.Add(new SupplierKey_WithHashCode
                {
                    CountryCode = countryCode,
                    SubscriptionId = subscriptionId
                }, Value);            
            }
        }
 
        _supplierKeys_WithoutHashCode = _suppliersMapping_WithoutHashCode.Keys.ToArray();
        _supplierKeys_WithHashCode = _suppliersMapping_WithHashCode.Keys.ToArray();    
    }
 
    // Test performed for a dictionary based on keys in an unaltered structure
    [Benchmark]
    public void DictionaryGet_WithoutHashCode()
    {
        foreach (var key in _supplierKeys_WithoutHashCode)
        {
            _suppliersMapping_WithoutHashCode.TryGetValue(key, out _);
        }
    }

     // A test performed for a dictionary based on keys in the form of a structure with the GetHashCode method overridden
    [Benchmark]
    public void DictionaryGet_WithHashCode()
    {
        foreach (var key in _supplierKeys_WithHashCode)
        {
            _suppliersMapping_WithHashCode.TryGetValue(key, out _);
        }
    }
}

Results of the first performance tests

After calling the above code, we obtained the results shown in Fig. 1.

We can immediately draw the following conclusions:

• By overriding the GetHashCode method, we were able to reduce the time required to execute the tested code block
• The execution time of DictionaryGet_WithHashCode increases in a nearly linear manner. For 40,000 operations, it represents 4 times the time required to perform 10,000 operations, whereas, for DictionaryGet_WithoutHashCode, it is approximately 7 times more.
• For both DictionaryGet_WithHashCode and DictionaryGet_WithoutHashCode, we see many bytes allocated on the heap, which rises as the number of operations performed increases.

After a quick analysis of the results, we see that we have achieved the desired result, but there is still room for improvement. Most noticeable is the amount of allocated memory. This constitutes the next problem we will be solving.

Second issue – unnecessary memory allocations

To understand the issue related to allocations, we need to look again at the source code of dictionaries and, more specifically, at the way they are compared to each other.

The Dictionary.FindValue method is responsible for finding the key in the dictionary, which searches the internal array of the dictionary and tries to return the value corresponding to the given key. The code below shows a condition that comes from Dictionary.FindValue (System.Private.CoreLib/src/System/Collections/Generic/Dictionary.cs).

// Code called for value types without a defined comparer
if (typeof(TKey).IsValueType && comparer == null)
{
    // code omitted for purposes of the article

         // EqualityComparer<TKey>.Default is used for comparison
    if (entry.hashCode == hashCode && EqualityComparer<TKey>.Default.Equals(entry.key, key))
    {
        goto ReturnFound;
    }

    // code omitted for purposes of the article
} 

As we can see, the default EqualityComparer is used for value types, but to understand what this means, we need to move on to the CreateDefaultEqualityComparer method, which is called from EqualityComparer<TKey>.Default (System.Private.CoreLib/src/System/Collections/Generic/ComparerHelpers.cs).

internal static object CreateDefaultEqualityComparer(Type type)
{
    // code omitted for purposes of the article

    // Condition to check if the dictionary key implements IEquatable<>
    else if (type.IsAssignableTo(typeof(IEquatable<>).MakeGenericType(type)))
    {
        // An efficient GenericEqualityComparer is returned
        result = CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericEqualityComparer<string>), runtimeType);
    }

    // code omitted for purposes of the article

    // Inefficient ObjectEqualityComparer is returned
    return result ?? CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(ObjectEqualityComparer<object>), runtimeType);
}

As we can see, if the type of a dictionary key is implementing the IEquatable<> interface, the GenericEqualityComparer based on the IEquatable<> is used. Otherwise, the dictionary will use the slower ObjectEqualityComparer, which must cast our value type onto the object when comparing, thus causing unnecessary memory allocations.

Fixing the second issue

Now that we know what causes additional allocations, we can proceed to changes in the code. We need to implement the IEquatable<> interface along with the Equals method. The code below shows the structure of SupplierKey_WithHashCode_AndEquals. Note that we have also overridden the Equals method derived from Object to match the one derived from IEquatable.

public struct SupplierKey_WithHashCode_AndEquals : IEquatable<SupplierKey_WithHashCode_AndEquals>
{
    public string CountryCode { get; set; }
 
    public int SubscriptionId { get; set; }
 
    // Equals method derived from base Object
    public override bool Equals(object? other)
    {
        if(other is SupplierKey_WithHashCode_AndEquals key)
        {
            return Equals(key);
        }
 
        return false;
    }
 
    // Equals method derived from IEquatable<>
    public bool Equals(SupplierKey_WithHashCode_AndEquals other)
    {
        return CountryCode == other.CountryCode && SubscriptionId == other.SubscriptionId;
    }
 
    public override int GetHashCode()
    {
        return HashCode.Combine(CountryCode, SubscriptionId);
    }
}

Performance tests after implementing IEquatable<>

After the adjustment, we can move on to the next performance test. The results of which are shown in Fig. 2. The latest changes will be visible in the tests of the DictionaryGet_WithHashCode_AndEquals method, which relies on keys in the form SupplierKey_WithHashCode_AndEquals.

Let’s now analyze the achieved times and allocations:

• The implementation of the IEquatable interface allowed us to speed up the operation of retrieving values from the dictionary. It now works about 6 times faster while maintaining a linear increase in time relative to the increase in the number of elements in the dictionary.
• The number of bytes allocated in memory has dropped significantly. It does not change as the collection size grows. You can see that the BenchmarkDotNet library itself has only allocated 400 bytes (you can find more info at the link). So, we managed to get rid of the boxing of value types when we were getting values from the dictionary.

By making minor changes, we obtained code that is efficient in terms of the time needed to perform calculations and does not cause additional memory allocations. Now, we can conclude that our structure has been properly implemented.

Comparison of the discussed structure to its counterpart as a record struct

Before the introduction of C# 10, we would have stayed with the structure we described at the end of the previous section, but something has changed. With C# 10 and .NET 6, record struct types were introduced. They already have built-in enhancements that we have sequentially applied to SupplierKey, so we can check how they will behave for our test case.

Let’s start by defining a new SupplierKey_Record structure, which has the same fields as our existing structure and is marked with the record keyword. In addition, we will use the possibility of defining fields directly in the type declaration, which is presented in the code below.

public record struct SupplierKey_Record(string CountryCode, int SubscriptionId) { }

As you can see, the difference in the level of complexity of the code is huge. One line is enough to provide us with everything we had to write by hand.

Performance tests for record struct

Now, we can proceed to performance testing. The method that uses keys in the form of SupplierKey_Record type will be called DictionaryGet_Record. The performance test results for the record struct are shown in Fig. 3.

We can see that the record struct is faster than our structure and we managed to speed up the retrieval of values from the dictionary. Let’s also note that DictionaryGet_Record, like DictionaryGet_WithHashCode_AndEquals, does not allocate memory and the increase in the number of elements causes a linear increase in execution time.

We could continue to make changes to our GetHashCode and Equals methods to achieve similar results, but we will stop there.

We managed to lead to a situation where our structure is efficient, does not cause unnecessary allocations and the time needed to retrieve a single value does not change depending on the number of elements in the dictionary. By conducting more accurate measurements using profilers, or trying to choose a better way to calculate the hash code, we could get closer to the record, but this misses our goal.

Summary

By analyzing a relatively simple case of an ordinary structure with two fields, we managed to understand a large piece of .NET source code. We were able to learn more about the internal implementation of the structures and the reasons why we should follow the generally applicable principles of C# code design. By implementing one interface and overriding the appropriate methods, we achieved a 300x increase in performance.

We also managed to use one of the innovations from recent years in the form of record struct, which allowed us to significantly simplify the code of our structure and achieve even less time needed to retrieve values from the dictionary. This encourages us to keep track of changes made to the new .NET versions and reassures us that the development of the platform is heading in the right direction.

***

If you are interested in C#, also take a look at other articles by our specialists.