[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.

[ghost]

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?

[ghost]

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

[Joe4evr]

If OP isn't going to update, then I'll place the revised proposal real quick:

namespace System.Linq
{
    public static partial class ImmutableArrayExtensions
    {
        public static bool Contains<T>(this ImmutableArray<T> immutableArray, T value, IEqualityComparer<T>? comparer);
    }
}

[ChrML]

I have updated the proposal to what we have discussed here. Sorry for that it took so long.

[Joe4evr]

Question for whenever this comes to review: I recall that some time ago the review team made a blanket policy that System.Linq.Queryable should be kept in sync with (most) methods in System.Linq.Enumerable. Does it make sense to extend that policy to keep ImmutableArrayExtensions in sync as well?

[bartonjs]

Looks good as proposed, except we changed from an extension method to an instance method (as this is an overload of the existing Contains(T)). This seems generally applicable to any struct that is IEnumerable that provides a Contains(T) without a Contains(T, IEqualityComparer<T>)... but we couldn't find a second one during the meeting.

namespace System.Collections.Immutable;

public static partial struct ImmutableArray<T>
{
    public bool Contains(T item, IEqualityComparer<T>? comparer);
}