Investigate ways to optimize Span.Fill and Span.Clear for small buffers

[ahsonkhan]

We need to reduce the overhead of calling Span and ReadOnlySpan Fill and improve its performance for small buffers so that it can be used in common scenarios.

See additional context:
dotnet/corefx#26598 (comment)
dotnet/corefx#26289 (comment)

Edit: As part of this change, investigate and remove the TODOs:
https://github.com/dotnet/corefx/blob/79d708b2faf8a75089b1873fbb101b0a957c1fbd/src/System.Memory/src/System/SpanHelpers.Clear.cs#L69
https://github.com/dotnet/corefx/blob/79d708b2faf8a75089b1873fbb101b0a957c1fbd/src/System.Memory/src/System/SpanHelpers.Clear.cs#L105

https://github.com/dotnet/coreclr/blob/22f1bc00d018a49f9550ee3b564f5f7737960b0d/src/mscorlib/shared/System/Span.NonGeneric.cs#L707

cc @dotnet/corefxlab-contrib, @jkotas, @stephentoub

[GrabYourPitchforks]

We should look at Span<T>.Clear() at the same time.

[GrabYourPitchforks]

I know this issue specifically deals with small buffers, but do we know the calling patterns for how these APIs are likely to be used? For example, is it likely that Span<T>.Fill(...) will ever be called when T is a reference type (not simply a contains-references type)? Is the common use case that T will be a fully blittable type?

[jkotas]

I think it going to be most frequently used with spans of primitive types (byte, char, int), but it needs to work for all types.

[GrabYourPitchforks]

I investigated Span.Clear for small buffers of blittable T. Was able to get significant performance improvements for buffer sizes <= 16 bytes (approx.), but at the expense of making Clear slower for larger buffers. Will keep investigating, but the regressions for larger buffers is steering me away from my current thinking.

One alternative is to expose a specialty API SmallClear which is optimized for smaller buffers and which defers to Clear for larger buffers. The API would only be for callers who really need this in perf-critical code paths and who already know that their spans are small enough to benefit from this. We'd need to mark this non-browseable or hide it behind a package so that we don't needlessly confuse the 99.9% developer audience.

[jkotas]

Where is the regression for larger buffers coming from?

[jkotas]

expense of making Clear slower for larger buffers

There is always step or bend in the performance curve where implementation switches to a different strategy. It should get amortized for larger buffers pretty quickly.

[GrabYourPitchforks]

Where is the regression for larger buffers coming from?

@jkotas Currently Span.Clear and Span.ClearWithoutReferences get inlined into their caller, which means that the caller (user code) directly invokes JIT_Memset or MemoryNative::Clear, depending on the size of the span.

When I was experimenting with optimizing for small buffers the code looked like the following.

private static void ClearWithoutReferences(/* ... */) {
    if (length > 4096) { goto PInvoke; }
    else if (length > 16) { goto JIT_Memset; }
    else {
        /* optimize for small cases */
    }
}

The modified ClearWithoutReferences was large enough where it was no longer inlined into its caller. So now not only is there an additional if check, but the call stack goes caller -> ClearWithoutReferences -> JIT_Memset. This was showing up in the microbenchmark and regressing performance by around 30% at the boundary.

I should note that the microbenchmark was using a fully primed branch predictor.