Today MemoryExtensions.IndexOf(..., ReadOnlySpan<char>) is implemented essentially as a loop around an IndexOf for the first character in the pattern and then a SequenceEqual at that position for that pattern:

This is good but not great. In particular it ends up breaking out of the vectorized search loop potentially much more frequently than is necessary and paying the startup overhead for the SequenceEqual each time.

There are better options. For example, the simple algorithm described in Algorithm 1: Generic SIMD searches concurrently for two characters rather than just one, which makes it much less likely to break out of the vectorized loop to early (this is what the Rust sliceslice crate uses; it's also what the Rust memchr crate uses (which is what's now used by its regex engine), though that memchr doesn't just use the first and last characters but instead picks two characters expected to have the lowest frequency of occurrence).

We could also special-case various sizes. The aforementioned memchr, for example, uses Rabin-Karp for small input strings and Two-Way for larger search strings.

cc: @tannergooding, @GrabYourPitchforks