Can ReadOnlySpan.Contains with ReferenceEqualityComparer be vectorized?

[verdie-g]

In #110197, static bool Contains<T>(this ReadOnlySpan<T> span, T value, IEqualityComparer<T>? comparer = null) was introduced but looking at the implementation

runtime/src/libraries/System.Private.CoreLib/src/System/MemoryExtensions.cs

Lines 2221 to 2283 in c02569b

	public static unsafe int IndexOf<T>(this ReadOnlySpan<T> span, T value, IEqualityComparer<T>? comparer = null)
	{
	if (typeof(T).IsValueType && (comparer is null || comparer == EqualityComparer<T>.Default))
	{
	if (RuntimeHelpers.IsBitwiseEquatable<T>())
	{
	if (sizeof(T) == sizeof(byte))
	return SpanHelpers.IndexOfValueType(
	ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)),
	Unsafe.BitCast<T, byte>(value),
	span.Length);
	if (sizeof(T) == sizeof(short))
	return SpanHelpers.IndexOfValueType(
	ref Unsafe.As<T, short>(ref MemoryMarshal.GetReference(span)),
	Unsafe.BitCast<T, short>(value),
	span.Length);
	if (sizeof(T) == sizeof(int))
	return SpanHelpers.IndexOfValueType(
	ref Unsafe.As<T, int>(ref MemoryMarshal.GetReference(span)),
	Unsafe.BitCast<T, int>(value),
	span.Length);
	if (sizeof(T) == sizeof(long))
	return SpanHelpers.IndexOfValueType(
	ref Unsafe.As<T, long>(ref MemoryMarshal.GetReference(span)),
	Unsafe.BitCast<T, long>(value),
	span.Length);
	}
	return IndexOfDefaultComparer(span, value);
	static int IndexOfDefaultComparer(ReadOnlySpan<T> span, T value)
	{
	for (int i = 0; i < span.Length; i++)
	{
	if (EqualityComparer<T>.Default.Equals(span[i], value))
	{
	return i;
	}
	}
	return -1;
	}
	}
	else
	{
	return IndexOfComparer(span, value, comparer);
	static int IndexOfComparer(ReadOnlySpan<T> span, T value, IEqualityComparer<T>? comparer)
	{
	comparer ??= EqualityComparer<T>.Default;
	for (int i = 0; i < span.Length; i++)
	{
	if (comparer.Equals(span[i], value))
	{
	return i;
	}
	}
	return -1;
	}
	}
	}

I noticed that this following code would be not vectorized

string str1 = "abc";
string str2 = "def";
string[] array = [str1, str2];
array.Contains(str1, ReferenceEqualityComparer.Instance);

Is that a GC limitation that reference search can't be vectorized or this optimization was not considered yet?

[EgorBo]

string[] is basically an array of pointers (dynamically changed pointers due to the GC nature) - there is nothing you can vectorize here given in most cases you need to perform full string equality for each array element. Reference equality rarely kicks in as a fast path in the real world. Btw the string equality itself is vectorized (for Ordinal/OrdinalIgnoreCase + ASCII).

[verdie-g]

I used string just as an example of a reference type.

I'm currently investigating a CPU issue where loading many db rows (~300K) using EF Core, 3 minutes of CPU is spent here
https://github.com/dotnet/efcore/blob/14b439c0bcf7cb81899457e4cbd14640cc365578/src/EFCore/Metadata/Internal/ClrCollectionAccessor.cs#L239-L248.

I was hoping that using ReadOnlySpan.Contains could help but it appears not be to vectorized.

Reference equality rarely kicks in as a fast path in the real world.

If technically possible, would you say the ratio (extra LOC) / benefits is too low?

[EgorBo]

If technically possible, would you say the ratio (extra LOC) / benefits is too low?

it's not possible. You basically want to take some string "A" (needle), populate a vector with "A"'s address e.g. { 0xAAAABBBB, 0xAAAABBBB ... 0xAAAABBBB }. and then run search. What if GC relocates strings at any point of time or two equal strings have different addresses? It won't update values in SIMD registers today (well, even if it could, it wouldn't be able to figure out that it needs to update the broadcasted values as well).

So your search becomes opportunistic, it might help if you want to run some quick vectorized O(N) search and if it finds nothing - run slow O(N). But it doesn't sound great to be the generic implementation as it's a big penalty for the "long sequence doesn't contain the element" case (or it does, but the equal strings have different addresses).

[verdie-g]

What if GC relocates strings at any point of time or two equal strings have different addresses?

I see, that was one of my concern. Thanks for your answer.