About using structures as a key in Dictionary<TKey,TValue>

Rarely, but it happened that in my work I had to use structures as a key for the dictionary. There are a few subtleties, which I would like to talk about.

Suppose you have a structure that you want to use as a dictionary key. As an example, I'll make two, to show how much of a problem it can be, especially when you use this structure everywhere in the project. 

Both will contain the usual uint, a 32-bit unsigned integer with a range of values from 0 to 4,294,967,295. For normal tasks will be enough. Finally, let's compare the performance of the dictionary with two structures and a unit.

public struct FastID
{
   private readonly uint _id;

    public FastID(uint id)
    {
        _id = id;
    }
}
public struct SlowID
{
    private readonly uint _id;

    public SlowID(uint id)
    {
        _id = id;
    }
}

In order to be able to compare objects of these structures with each other, you definitely need to implement one of the interfaces of comparison. And here it often happens that developers make a mistake. They implement the interface IComparable instead of IEquatable<T>. To avoid such mistake you need to understand the difference in the interfaces purposes.

• IEquatable checks if two objects are equal
• IComparable imposes a common order on the objects being compared.

Very briefly, IEquatable will tell you that 5 is not equal to 7, while IComparable would tell you that 5 comes before 7. That's the difference. Also note that IComparable is not Generic-type, so the entity implementing it must take into account that you potentially have to compare objects of any type, as opposed to IEquatable<T> which clearly defines type of objects you're comparing. It allows to avoid boxing of structures while comparing and therefore greatly increases productivity

For FastID we implement IEquatable<T> and for SlowID IComparable. Let's create dictionaries with keys from these structures, as well as with key uint, for performance comparison and measure the whole thing by benchmark.

public struct FastID : IEquatable<FastID>
{
    private readonly uint _id;

    public FastID(uint id)
    {
        _id = id;
    }

    public bool Equals(FastID other)
    {
        return _id == other._id;
    }

    public override bool Equals(object? obj)
    {
        return obj is FastID other && Equals(other);
    }

    public override int GetHashCode()
    {
        return (int)_id;
    }
}

public struct SlowID : IComparable
{
    private readonly uint _id;

    public SlowID(uint id)
    {
        _id = id;
    }

    public int CompareTo(object? obj)
    {
        if (obj is SlowID other)
        {
            return _id.CompareTo(other._id);
        }

        return 1;
    }

    public override bool Equals(object? obj)
    {
        return obj is SlowID other && _id == other._id;
    }

    public override int GetHashCode()
    {
        return (int)_id;
    }
}

Let's create a small test class Demo and run a keyword sampling test from a dictionary of 1 million elements, so that the difference is indicative.

public class Demo
{
    private Dictionary<FastID, string> TestDictFastID = new();
    private Dictionary<uint, string> TestDictUint = new();
    private Dictionary<SlowID, string> TestDictSlowID = new();

    public Demo()
    {
        for (uint i = 0; i < 1000000; i++)
        {
            TestDictFastID.Add(new FastID(i), i.ToString());
            TestDictSlowID.Add(new SlowID(i), i.ToString());
            TestDictUint.Add(i, i.ToString());
        }
    }

    [Benchmark]
    public void TestWithSlowID()
    {
        string testValue;
        for (uint i = 0; i < 1000000; i++)
        {
            testValue = TestDictSlowID[new SlowID(i)];
        }
    }

    [Benchmark]
    public void TestWithFastID()
    {
        string testValue;
        for (uint i = 0; i < 1000000; i++)
        {
            testValue = TestDictFastID[new FastID(i)];
        }
    }

    [Benchmark]
    public void TestWithUInt()
    {
        string testValue;
        for (uint i = 0; i < 1000000; i++)
        {
            testValue = TestDictUint[i];
        }
    }
}

Let's run the whole thing and see what happens. Under Release, of course.

public class Program
{
    public static void Main(String[] args) 
    {
        var results = BenchmarkRunner.Run<Demo>();
        Console.ReadKey();
    }
}

As you can see, IComparable is about 2 times slower than IEquatable. The difference between the structure and the unit is not very big, even at a million iterations.

References:
An explanation of why it is important to override comparison methods for structures.