System.Array.IndexOf allocates memory

Question

I've been profiling my code and found that System.Array.IndexOf is allocating a fair bit of memory. I've been trying to find out how come this happens.

public struct LRItem
{
    public ProductionRule Rule { get; } // ProductionRule is a class
    public int Position { get; }
}

// ...

public List<LRItem> Items { get; } = new List<LRItem>();

// ...

public bool Add(LRItem item)
{
    if (Items.Contains(item)) return false;

    Items.Add(item);
    return true;
}

I'm assuming the IndexOf is called by Items.Contains because I don't think Items.Add has any business checking indices. I've tried looking at the reference source and .NET Core source but to no avail. Is this a bug in the VS profiler? Is this function actually allocating memory? Could I optimize my code somehow?

Answer 1

I know this is probably a bit late, but in case anyone else has the same question...

When List<T>.Contains(...) is called, it uses the EqualityComparer<T>.Default to compare the individual items to find what you've passed in[1]. The docs say this about EqualityComparer<T>.Default:

The Default property checks whether type T implements the System.IEquatable interface and, if so, returns an EqualityComparer that uses that implementation. Otherwise, it returns an EqualityComparer that uses the overrides of Object.Equals and Object.GetHashCode provided by T.

Since your LRItem does not implement IEquatable<T>, then it falls back to using Object.Equals(object, object). And because LRItem is a struct, then it will end up being boxed as an object so it can be passed in to Object.Equals(...), which is where the allocations are coming from.

The easy fix for this is to take a hint from the docs and implement the IEquatable<T> interface:

public struct LRItem : IEquatable<LRItem>
{
    // ...

    public bool Equals(LRItem other)
    {
        // Implement this
        return true;
    }
}

This will now cause EqualityComparer<T>.Default to return a specialised comparer that does not need to box your LRItem structs and hence avoiding the allocation.

[1] I'm not sure if something's changed since this question was asked (or maybe it's a .net framework vs core difference or something) but List<T>.Contains() doesn't call Array.IndexOf() nowadays. Either way, both of them do defer to EqualityComparer<T>.Default, which means that this should still be relevant in either case.