Explore switching MultipartReaderStream to use IndexOf

[stephentoub]

MultipartReaderStream currently uses a Boyer-Moore substring search implementation as part of finding the next boundary:

aspnetcore/src/Http/WebUtilities/src/MultipartReaderStream.cs

Lines 279 to 294 in 53aad98

	var matchBytesLengthMinusOne = matchBytes.Length - 1;
	var matchBytesLastByte = matchBytes[matchBytesLengthMinusOne];
	var segmentEndMinusMatchBytesLength = segment1.Offset + segment1.Count - matchBytes.Length;
	matchOffset = segment1.Offset;
	while (matchOffset < segmentEndMinusMatchBytesLength)
	{
	var lookaheadTailChar = segment1.Array![matchOffset + matchBytesLengthMinusOne];
	if (lookaheadTailChar == matchBytesLastByte &&
	CompareBuffers(segment1.Array, matchOffset, matchBytes, 0, matchBytesLengthMinusOne) == 0)
	{
	matchCount = matchBytes.Length;
	return true;
	}
	matchOffset += _boundary.GetSkipValue(lookaheadTailChar);
	}

We should check to see whether this is still more beneficial than just using the vectorized:
https://github.com/dotnet/runtime/blob/7b91fd42a64732681472afc8d5a52c5bc5eb0c8a/src/libraries/System.Private.CoreLib/src/System/MemoryExtensions.cs#L1694

Regex used to use Boyer-Moore as well, and in .NET 7 deleted its use of Boyer-Moore entirely, instead just using IndexOf, for significant gains in most cases. See https://devblogs.microsoft.com/dotnet/regular-expression-improvements-in-dotnet-7/#leading-vectorization for details.

[sebastienros]

@BrennanConroy close?

[BrennanConroy]

No, we still fallback to Boyer-Moore for substring matching if needed.
We can look into vectorized substring matching to replace Boyer-Moore. But that requires more work since there isn't an API in the runtime for this that I'm aware of.

[stephentoub]

We can look into vectorized substring matching to replace Boyer-Moore. But that requires more work since there isn't an API in the runtime for this that I'm aware of.

str.IndexOf(substr) is vectorized. What are you referring to?

[BrennanConroy]

Partial substring matching. Given "abcd" as the input and we're searching for "cde", we want to match on "cd".

[stephentoub]

Partial substring matching. Given "abcd" as the input and we're searching for "cde", we want to match on "cd".

Why is that needed? Just for when the substring is straddling segments so you want to match "cd" at the end of one and "e" at the beginning of the next?

Because

aspnetcore/src/Http/WebUtilities/src/MultipartReaderStream.cs

Lines 277 to 295 in 53aad98

	// case 1: does segment1 fully contain matchBytes?
	{
	var matchBytesLengthMinusOne = matchBytes.Length - 1;
	var matchBytesLastByte = matchBytes[matchBytesLengthMinusOne];
	var segmentEndMinusMatchBytesLength = segment1.Offset + segment1.Count - matchBytes.Length;
	matchOffset = segment1.Offset;
	while (matchOffset < segmentEndMinusMatchBytesLength)
	{
	var lookaheadTailChar = segment1.Array![matchOffset + matchBytesLengthMinusOne];
	if (lookaheadTailChar == matchBytesLastByte &&
	CompareBuffers(segment1.Array, matchOffset, matchBytes, 0, matchBytesLengthMinusOne) == 0)
	{
	matchCount = matchBytes.Length;
	return true;
	}
	matchOffset += _boundary.GetSkipValue(lookaheadTailChar);
	}
	}

looks like it's doing a full substring search, not partial. That's what I was commenting on for this issue.

[BrennanConroy]

Because we're reading off the network and can have part of the payload available. That way we can give the user the maximum available data that can't match the boundary we're looking for. We could possibly just not do that part which would let us get rid of the boyer-moore code. Idk how important it is. That's also part of what should be evaluated for finishing this issue.

https://github.com/dotnet/aspnetcore/blob/53aad9807f89c57c48b164adcecdb9010f09f8cf/src/Http/WebUtilities/src/MultipartReaderStream.cs#L297C67-L297C67
You left off case 2

Edit: But I guess at a minimum we can remove case 1 now?

[stephentoub]

Edit: But I guess at a minimum we can remove case 1 now?

That's what I'm saying, yes.

You left off case 2

Purposefully :) Checking for a partial match at the end is worst-case O(N^2) where N is the length of the needle rather than the haystack.

[BrennanConroy]

Edit: But I guess at a minimum we can remove case 1 now?

That's what I'm saying, yes.

Ok sure :) but it'd be nice if we can remove all of boyer-moore too. Gets rid of an array alloc and populating the array in the ctor, plus should be faster due to vectorization.

[stephentoub]

Why does case 2 require Boyer-Moore?