[API Proposal]: Add ImmutableArray.Contains overload that accepts an IEqualityComparer<T>

[ChrML]

Background and motivation

I recently had a significant inner-loop performance regression when I added an optional IEqualityComparer<T> to my API. I found out that the reason was that I added the optional comparer argument to the Contains invocation on a ImmutableArray<T>.

Apparently there is no such overload, so it the call was directed from:

public readonly struct ImmutableArray<T>
{
    // ...
    public bool Contains(T item)
    // ...
}

And fell back to the much slower Linq extension:

public static class Enumerable
{`
    // ...
    public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value, IEqualityComparer<TSource>? comparer);
    // ...
}

This caused a significant amount of boxing to IEnumerable<T> each time Contains was called. Most methods in the API at the moment contain overloads that accept an optional IEqualityComparer<T>?, so it was quite surprising that this API did not.

See: https://docs.microsoft.com/en-us/dotnet/api/system.collections.immutable.immutablearray-1.contains?view=net-6.0

API Proposal

namespace System.Linq;

public static partial class ImmutableArrayExtensions
{
    public static bool Contains<T>(this ImmutableArray<T> immutableArray, T item, IEqualityComparer<T>? comparer)
    {
        var self = immutableArray;
        return self.IndexOf(item, 0, self.Length, equalityComparer) >= 0;
    }
}

API Usage

ImmutableArray<string> items = ImmutableArray.Create("abc", "DEF");
Assert.True(items.Contains("Abc", StringComparer.InvariantCultureIgnoreCase));
Assert.True(items.Contains("Def", StringComparer.InvariantCultureIgnoreCase));

Alternative Designs

No response

Risks

This has a really low risk of breaking something. It should increase the overall performance when Contains is used where the programmer was not aware of this issue.

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Background and motivation

I recently had a significant inner-loop performance regression when I added an optional IEqualityComparer<T> to my API. I found out that the reason was that I added the optional comparer argument to the Contains invocation on a ImmutableArray<T>.

Apparently there is no such overload, so it the call was directed from:

public readonly struct ImmutableArray<T>
{
    // ...
    public bool Contains(T item)
    // ...
}

to Linq's:

public static class Enumerable
{`
    // ...
    public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value, IEqualityComparer<TSource>? comparer);
    // ...
}

This caused a significant amount of boxing to IEnumerable<T> each time Contains was called. Most methods in the API at the moment contain overloads that accept an optional IEqualityComparer<T>?, so it was quite surprising that this API did not.

See: https://docs.microsoft.com/en-us/dotnet/api/system.collections.immutable.immutablearray-1.contains?view=net-6.0

API Proposal

public readonly struct ImmutableArray<T>
{
    // ...
    public bool Contains(T item, IEqualityComparer<T>? equalityComparer)
    {
        var self = this;
        return self.IndexOf(item, 0, self.Length, equalityComparer) >= 0;
    }
    // ...
}

API Usage

ImmutableArray<string> items = ImmutableArray.Create("abc", "DEF");
Assert.True(items.Contains("Abc", StringComparer.InvariantCultureIgnoreCase));
Assert.True(items.Contains("Def", StringComparer.InvariantCultureIgnoreCase));

Alternative Designs

No response

Risks

This has a really low risk of breaking something. It should increase the overall performance when Contains is used where the programmer was not aware of this issue.

Author:	ChrML
Assignees:	-
Labels:	api-suggestion, area-System.Collections, untriaged
Milestone:	-

[eiriktsarpalis]

Given that it is fairly common for concrete collections to fall back to slower LINQ methods, I'm not necessarily convinced that it's sufficient justification to add another overload in ImmutableArray<T>. There's codegen overhead to adding more methods to generic types, and as you're pointing out it's fairly trivial to express this overload as an extension method.

[ChrML]

Given that it is fairly common for concrete collections to fall back to slower LINQ methods, I'm not necessarily convinced that it's sufficient justification to add another overload in ImmutableArray<T>. There's codegen overhead to adding more methods to generic types, and as you're pointing out it's fairly trivial to express this overload as an extension method.

Yes, the required functionality is already present in ImmutableArray.IndexOf, so this can easily be expressed as an extension method.

However that argument would also apply to the single-argument Contains method already present.

[Joe4evr]

Is it not an option to add this overload to the set of LINQ extensions specialized for ImmutableArray<T>?

[ChrML]

Is it not an option to add this overload to the set of LINQ extensions specialized for ImmutableArray<T>?

I think that's the best option.

[eiriktsarpalis]

SGTM, given there's precedent. @ChrML could you update your API proposal to use that namespace?

Tagging subscribers to this area: @dotnet/area-system-linq
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Background and motivation

I recently had a significant inner-loop performance regression when I added an optional IEqualityComparer<T> to my API. I found out that the reason was that I added the optional comparer argument to the Contains invocation on a ImmutableArray<T>.

Apparently there is no such overload, so it the call was directed from:

public readonly struct ImmutableArray<T>
{
    // ...
    public bool Contains(T item)
    // ...
}

to Linq's:

public static class Enumerable
{`
    // ...
    public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value, IEqualityComparer<TSource>? comparer);
    // ...
}

This caused a significant amount of boxing to IEnumerable<T> each time Contains was called. Most methods in the API at the moment contain overloads that accept an optional IEqualityComparer<T>?, so it was quite surprising that this API did not.

See: https://docs.microsoft.com/en-us/dotnet/api/system.collections.immutable.immutablearray-1.contains?view=net-6.0

API Proposal

public readonly struct ImmutableArray<T>
{
    // ...
    public bool Contains(T item, IEqualityComparer<T>? equalityComparer)
    {
        var self = this;
        return self.IndexOf(item, 0, self.Length, equalityComparer) >= 0;
    }
    // ...
}

API Usage

ImmutableArray<string> items = ImmutableArray.Create("abc", "DEF");
Assert.True(items.Contains("Abc", StringComparer.InvariantCultureIgnoreCase));
Assert.True(items.Contains("Def", StringComparer.InvariantCultureIgnoreCase));

Alternative Designs

No response

Risks

This has a really low risk of breaking something. It should increase the overall performance when Contains is used where the programmer was not aware of this issue.

Author:	ChrML
Assignees:	-
Labels:	api-suggestion, area-System.Collections, area-System.Linq
Milestone:	Future