In last week’s tips for using collections like List<T>, we saw how struct types are sometimes boxed resulting in GC allocations. This week we’ll see how to avoid boxing and learn some of the clever tricks that .NET collection types use to make this possible.

The Problem

Last week we saw an example of how List<T> and Dictionary<TKey, TValue> will box struct types when performing common operations such as calling the Contains method:

struct IntStruct
{
    public int Value;
}
 
bool TestList(List<IntStruct> list, IntStruct s)
{
    return list.Contains(s); // Boxing inside the Contains method
}
 
int TestDictionary(Dictionary<IntStruct, int> dict, IntStruct s)
{
    return dict[s]; // Boxing inside the indexer
}

This resulted in 60 bytes of GC allocation for Dictionary and 80 bytes for List:

Struct Keys GC

We’d like to avoid these GC allocations for all the usual reasons such as the performance spikes that a GC collect can cause.

Inside Collections

To see how to avoid boxing, we need to understand how methods like List<T>.Contains work. To do that, we can decompile the mscorlib.dll that Unity puts in the PROJECTNAME_OS_BackUpThisFolder_ButDontShipItWithYourGame directory when we do a build. Free tools such as ILSpy and dotPeek make this easy. Here’s what ILSpy shows for List<T>.Contains:

public bool Contains(T item)
{
    if (item == null)
    {
        for (int i = 0; i < _size; i++)
        {
            if (_items[i] == null)
            {
                return true;
            }
        }
        return false;
    }
    EqualityComparer<T> @default = EqualityComparer<T>.Default;
    for (int j = 0; j < _size; j++)
    {
        if (@default.Equals(_items[j], item))
        {
            return true;
        }
    }
    return false;
}

Our IntStruct type can’t be null, so we’re really just looking at the second part of the function. Let’s start by looking at the Equals method:

public abstract bool Equals(T x, T y);

EqualityComparer is an abstract class, so Equals is implemented in derived classes. To see those, let’s look at the EqualityComparer<T>.Default property:

[Serializable]
[TypeDependency("System.Collections.Generic.ObjectEqualityComparer`1")]
public abstract class EqualityComparer<T> : IEqualityComparer, IEqualityComparer<T>
{
    private static volatile EqualityComparer<T> defaultComparer;
 
    public static EqualityComparer<T> Default
    {
        get
        {
            EqualityComparer<T> equalityComparer = defaultComparer;
            if (equalityComparer == null)
            {
                equalityComparer = (defaultComparer = CreateComparer());
            }
            return equalityComparer;
        }
    }
}

It turns out the Default property uses the defaultComparer field as a cached value. The first time the property is called, it creates this field with CreateComparer so let’s look at that method:

private static EqualityComparer<T> CreateComparer()
{
    RuntimeType runtimeType = (RuntimeType)typeof(T);
    if (runtimeType == typeof(byte))
    {
        return (EqualityComparer<T>)new ByteEqualityComparer();
    }
    if (runtimeType == typeof(string))
    {
        return (EqualityComparer<T>)new InternalStringComparer();
    }
    if (typeof(IEquatable<T>).IsAssignableFrom(runtimeType))
    {
        return (EqualityComparer<T>)RuntimeType.CreateInstanceForAnotherGenericParameter(typeof(GenericEqualityComparer<>), runtimeType);
    }
    if (runtimeType.IsGenericType && runtimeType.GetGenericTypeDefinition() == typeof(Nullable<>))
    {
        RuntimeType runtimeType2 = (RuntimeType)runtimeType.GetGenericArguments()[0];
        if (typeof(IEquatable<>).MakeGenericType(runtimeType2).IsAssignableFrom(runtimeType2))
        {
            return (EqualityComparer<T>)RuntimeType.CreateInstanceForAnotherGenericParameter(typeof(NullableEqualityComparer<>), runtimeType2);
        }
    }
    if (runtimeType.IsEnum)
    {
        switch (Type.GetTypeCode(Enum.GetUnderlyingType(runtimeType)))
        {
        case TypeCode.Int16:
            return (EqualityComparer<T>)RuntimeType.CreateInstanceForAnotherGenericParameter(typeof(ShortEnumEqualityComparer<>), runtimeType);
        case TypeCode.SByte:
            return (EqualityComparer<T>)RuntimeType.CreateInstanceForAnotherGenericParameter(typeof(SByteEnumEqualityComparer<>), runtimeType);
        case TypeCode.Byte:
        case TypeCode.UInt16:
        case TypeCode.Int32:
        case TypeCode.UInt32:
            return (EqualityComparer<T>)RuntimeType.CreateInstanceForAnotherGenericParameter(typeof(EnumEqualityComparer<>), runtimeType);
        case TypeCode.Int64:
        case TypeCode.UInt64:
            return (EqualityComparer<T>)RuntimeType.CreateInstanceForAnotherGenericParameter(typeof(LongEnumEqualityComparer<>), runtimeType);
        }
    }
    return new ObjectEqualityComparer<T>();
}

Here we see a lot of reflection starting with typeof(T) and proceeding to various calls such as IsAssignableFrom. This method has special cases for built-in types like int and string as well as core .NET concepts like Nullable<T>. When none of the special cases matches, it falls back to the most general tool: ObjectEqualityComparer. This is what we saw in the profiler that resulted in GC allocations. Why? Let’s look at its Equals to find out:

public override bool Equals(T x, T y)
{
    if (x != null)
    {
        if (y != null)
        {
            return x.Equals(y);
        }
        return false;
    }
    if (y != null)
    {
        return false;
    }
    return true;
}

The important line here is x.Equals(y) which calls the object.Equals method. This requires x to be boxed to object which results in a GC allocation.

Workaround

Now that we’ve seen that we’re falling into the most general case and using ObjectEqualityComparer, let’s revisit CreateComparer and see if there is a special case that would allow us to avoid the boxing. First, we can ignore all the types that don’t fit our IntStruct such as int, string, and Nullable<T>. That leaves us with the possibility of IEquatable<T>:

if (typeof(IEquatable<T>).IsAssignableFrom(runtimeType))
{
    return (EqualityComparer<T>)RuntimeType.CreateInstanceForAnotherGenericParameter(typeof(GenericEqualityComparer<>), runtimeType);
}

Our type currently doesn’t implement this interface, but we could easily change that:

struct IntStruct : IEquatable<IntStruct>
{
    public int Value;
 
    public bool Equals(IntStruct other)
    {
        return Value == other.Value;
    }
}

With this in place, CreateComparer will now call RuntimeType.CreateInstanceForAnotherGenericParameter. Let’s take a quick look at it:

internal static object CreateInstanceForAnotherGenericParameter(Type genericType, RuntimeType genericArgument)
{
    return ((RuntimeType)MakeGenericType(genericType, new Type[1]
    {
        genericArgument
    })).GetDefaultConstructor().InternalInvoke(null, null);
}
 
[MethodImpl(4096)]
private static extern Type MakeGenericType(Type gt, Type[] types);

This begins with a call to MakeGenericType, but that’s implemented in native code so we’ll skip it. Then there are calls to GetDefaultConstructor and InternalInvoke to invoke the constructor. The result is an object which CreateComparer casts to an EqualityComparer<T>. That cast makes sense since the Type being created is GenericEqualityComparer<> which derives from EqualityComparer<T>:

[Serializable]
internal class GenericEqualityComparer<T> : EqualityComparer<T> where T : IEquatable<T>
{
    public override bool Equals(T x, T y)
    {
        if (x != null)
        {
            if (y != null)
            {
                return x.Equals(y);
            }
            return false;
        }
        if (y != null)
        {
            return false;
        }
        return true;
    }
}

Finally, we come to the implementation of Equals that we want. This one also uses x.Equals(y) but there is a where T : IEquatable<T> constraint which means the compiler will choose IEquatable<T>.Equals(T) instead of object.Equals(object). Since there’s no need to have an object, there’s no need to box the IntStruct and no GC allocation!

Dictionary

With our call to List<T>.Contains fixed, we can turn our attention to the Dictionary<TKey, TValue> indexer. Here’s how it looks:

public TValue this[TKey key]
{
    get
    {
        int num = FindEntry(key);
        if (num >= 0)
        {
            return entries[num].value;
        }
        throw new KeyNotFoundException();
    }
}

FindKey does all the work, so let’s see it:

private int FindEntry(TKey key)
{
    if (key == null)
    {
        throw new ArgumentNullException("key");
    }
    if (buckets != null)
    {
        int num = comparer.GetHashCode(key) & 0x7FFFFFFF;
        for (int num2 = buckets[num % buckets.Length]; num2 >= 0; num2 = entries[num2].next)
        {
            if (entries[num2].hashCode == num && comparer.Equals(entries[num2].key, key))
            {
                return num2;
            }
        }
    }
    return -1;
}

This contains two relevant calls: comparer.GetHashCode and comparer.Equals. Both use comparer, which is a field:

private IEqualityComparer<TKey> comparer;

It’s assigned in the constructor:

public Dictionary(int capacity, IEqualityComparer<TKey> comparer)
{
    if (capacity < 0)
    {
        throw new ArgumentOutOfRangeException("capacity", capacity, "Non-negative number required.");
    }
    if (capacity > 0)
    {
        Initialize(capacity);
    }
    this.comparer = (comparer ?? EqualityComparer<TKey>.Default);
}

Once again we see EqualityComparer<TKey>.Default, just like in List<T>.Contains. This means making IntStruct implement IEquatable<IntStruct> will fix the same Equals issue with Dictionary too. The same solution also works for GetHashCode because GenericEqualityComparer also wraps that function:

public override int GetHashCode(T obj)
{
    return obj?.GetHashCode() ?? 0;
}

All that’s left for us to do is to implement GetHashCode in our IntStruct type:

struct IntStruct : IEquatable<IntStruct>
{
    public int Value;
 
    public bool Equals(IntStruct other)
    {
        return Value == other.Value;
    }
 
    public override int GetHashCode()
    {
        return Value.GetHashCode();
    }
}
Conclusion

By implementing IEquatable<T> and overriding GetHashCode in our structs, we’ve avoided all GC allocations in container types like List<T> and Dictionary<TKey, TValue>. We’re still left with an abstract method call for every Equals and GetHashCode, so this isn’t a solution that provides ultimate performance. It’s a lot better than boxing though, so we have improved matters considerably. Finally, keep in mind that EqualityComparer<TKey>.Default is public and therefore available for use in your own generic code to avoid boxing and GC allocations.