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?

Are you perhaps setting the capacity of your list to some high value before you see the memory allocations in IndexOf happen? — , Sep 08 '18 at 10:04
Check how `LRItem` actually implements `Equals`. The culprit might very well be there. — InBetween, Sep 08 '18 at 10:53
Also, if you need a collection that enforces uniqueness, then use a type that already provides that functionality. — InBetween, Sep 08 '18 at 10:54
Contains() has no reason to allocate any memory, but the Add() on the next line does. So make sure you do a Clean and a Rebuild. Wouldn't hurt to manually delete some pdb and dll files first. If this persists it might be very educational to construct a [mcve]. Id does look a litle like a problem in the profiler. — H H, Sep 09 '18 at 16:40

score 4 · Accepted Answer · answered Sep 10 '20 at 11:53

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.

System.Array.IndexOf allocates memory

1 Answers1