[API] Add MemoryExtensions.Contains

[GrabYourPitchforks]

Proposal:

public static class MemoryExtensions {
    bool Contains<T>(this Span<T> span, T value);
    bool Contains<T>(this ReadOnlySpan<T> span, T value);
    bool Contains<T>(this Span<T> span, T value, IEqualityComparer<T> comparer);
    bool Contains<T>(this ReadOnlySpan<T> span, T value, IEqualityComparer<T> comparer);
}

This is different from the IndexOf method in that we can perform certain optimizations if we know you don't need the exact index of where the value was found. There are a few places in the framework that would benefit from this.

https://github.com/dotnet/corefx/blob/f0a032e4a1c8a848574a5db3e69e8a6fa0aae91e/src/System.Net.Primitives/src/System/Net/IPAddressParser.cs#L19

https://github.com/dotnet/coreclr/blob/8ec9bdfd53220b555f0b19eebd6a2c4ab5dab8bf/src/mscorlib/shared/System/Guid.cs#L430

https://github.com/dotnet/corefxlab/blob/c3624ba2c5f4fc4926ef64e5e35f2f6e895df6eb/src/System.Buffers.Experimental/System/Buffers/BufferExtensions.cs#L101

https://github.com/dotnet/coreclr/blob/22f1bc00d018a49f9550ee3b564f5f7737960b0d/src/mscorlib/shared/System/Version.cs#L342

[ahsonkhan]

We already have Contains for T = char (for ReadOnlySpan). Do we need a generic API? The examples you provided showcase only T = byte and char (which is already covered).

[GrabYourPitchforks]

Yes, the intent was for this to be generic, with specializations for T = byte / char / other "integral" type when no comparer is specified.

[ygc369]

@ahsonkhan
It would be better to have a generic API.

[GrabYourPitchforks]

Looked through the code a bit more. The current API is Contains(this ReadOnlySpan<char> span, ReadOnlySpan<char> value, StringComparison comparison), i.e., substring searching. The API under proposal here is for locating individual matching elements, not substrings.

[AlexRadch]

I do not understand the advantages of Contains over IndexOf? I do not think that Contains will be significant faster then IndexOf.

[GrabYourPitchforks]

@AlexRadch In vectorized code paths, IndexOf needs to back up once it has found a match so that it can figure out where the match occurred. If the caller cares only that a match was found but not where the match occurred then the Contains method can skip this extra step. We'll confirm before we commit, but in other similar APIs this has offered measurable savings.

[AlexRadch]

We have start offset and current offset how simple subtraction can draw back performance?

[vcsjones]

We have start offset and current offset how simple subtraction can draw back performance?

IndexOf works by examining multiple items at the same time for certain types like byte using SIMD hardware acceleration, like a windowing function.

https://github.com/dotnet/corefx/blob/f391820c4808bcb02c7b3dd88b684f36a0a98b6a/src/Common/src/CoreLib/System/SpanHelpers.Byte.cs#L172

It examins n-number of bytes at a time, depending on the size of the Vector. Once it has found a place where vector.equals is non-zero, it has to look at each individual byte of the resulting vector to determine where in that specific chunk of data it actually is.

The last part is what should be removed with this API. If all we care about is a yes or no answer instead of where specifically, it can save examining individual elements.

[benaadams]

Also

https://github.com/aspnet/KestrelHttpServer/blob/6551eae321cd6306b485906ea47e8d41e932d65b/src/Kestrel.Core/Internal/Http/HttpParser.cs#L399

and

https://github.com/aspnet/KestrelHttpServer/blob/153020ef8a81aa6b4c6efebd83a8b04863e4d40d/src/Kestrel.Core/Internal/Infrastructure/HttpUtilities.cs#L127

[grant-d]

I am considering working on this, but trying to understand the code. There's one section that confuses me:
https://github.com/dotnet/corefx/blob/f391820c4808bcb02c7b3dd88b684f36a0a98b6a/src/Common/src/CoreLib/System/SpanHelpers.Byte.cs#L163
I get that the JIT will shake free this unreachable code on a non-vectorized platform. But if the platform does support it, then the preceding sequential loops have already found the search term anyway. Why run the vector, is it not redundant? In other words, both the sequential and vectorized code will be reachable and (unless I misunderstand) run in series.

[benaadams]

The block above the SequentialScan: label shortens nLength for the first pass; and is used to align the input for the vector loop (processing the unaligned data in the sequenial loop):
https://github.com/dotnet/corefx/blob/f391820c4808bcb02c7b3dd88b684f36a0a98b6a/src/Common/src/CoreLib/System/SpanHelpers.Byte.cs#L107-L111
Once it passes the vector loop; it then jumps back to the SequentialScan: label to finish anything that didn't fit in a Vector size

[grant-d]

Ah. That makes sense now - thanks

[grant-d]

@jkotas has advised that the PR (referenced above) should be submitted to the CoreCLR repo, not CoreFX.

[grant-d]

Replacement PR 19863 created in CoreCLR.
Should this issue be moved there too?

[vcsjones]

Should this issue be moved there too?

API proposals that go through the API review process are always issues in the CoreFx repository.