Proposal: API changes to Span<T> as part of shipping story

[ahsonkhan]

As part of productizing Span<T> for pre-release - dotnet/corefxlab#1314 / dotnet/corefxlab#1292 - here are the proposed changes that became visible from the use of Span<T> in Kestrel and from design discussions of what APIs are useful versus what aren't ready to be shipped or not useful.

Proposed API Additions

public static class SpanExtensions
{
    public static bool StartsWith<T>(this Span<T> span, ReadOnlySpan<T> value) where T : struct, IEquatable<T>
    public static bool StartsWith(this Span<byte> span, ReadOnlySpan<byte> value);

    public static bool StartsWith<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> value) where T : struct, IEquatable<T>
    public static bool StartsWith(this ReadOnlySpan<byte> span, ReadOnlySpan<byte> value);

    public static void CopyTo<T>(this T[] array, Span<T> span);

    public static ReadOnlySpan<char> AsSpan(this string text);
    public static Span<T> AsSpan<T>(this T[] array);
    public static Span<T> AsSpan<T>(this ArraySegment<T> segment);

    public static Span<byte> AsBytes<T>(this Span<T> source) where T : struct
    public static ReadOnlySpan<byte> AsBytes<T>(this ReadOnlySpan<T> source) where T : struct

    public static int IndexOfAny(this Span<byte> span, byte value0, byte value1);
    public static int IndexOfAny(this Span<byte> span, byte value0, byte value1, byte value2);
    public static int IndexOfAny(this Span<byte> span, ReadOnlySpan<byte> values);
    public static int IndexOfAny(this ReadOnlySpan<byte> span, byte value0, byte value1);
    public static int IndexOfAny(this ReadOnlySpan<byte> span, byte value0, byte value1, byte value2);
    public static int IndexOfAny(this ReadOnlySpan<byte> span, ReadOnlySpan<byte> values);
}

Proposed API Removals

public static class Span
{
    public static Span<byte> AsBytes<T>(this Span<T> source) where T : struct
    public static ReadOnlySpan<byte> AsBytes<T>(this ReadOnlySpan<T> source) where T : struct
    public static Span<TTo> NonPortableCast<TFrom, TTo>(this System.Span<TFrom> source) where TFrom : struct where TTo : struct
    public static ReadOnlySpan<TTo> NonPortableCast<TFrom, TTo>(this System.ReadOnlySpan<TFrom> source) where TFrom : struct where TTo : struct

    public static ReadOnlySpan<char> Slice(this string text);
    public static ReadOnlySpan<char> Slice(this string text, int start);
    public static ReadOnlySpan<char> Slice(this string text, int start, int length);
}

Sample Usage and Rationale

Adding AsSpan and removing Slice:
There is not enough consensus whether a method named Slice should return a Span and not the same type that it extends. Furthermore, we want to be able to wrap an ArraySegment into a Span but having a Slice extension method on ArraySegment that returns Span could conflict with a Slice method that returns an ArraySegment. AsSpan more clearly identifies the usage and does not block the use of Slice as a method name.

string s = "Hello";
ReadOnlySpan<char> span = s.AsSpan().Slice(1, 3);
// Instead of:
string s = "Hello";
ReadOnlySpan<char> span = s.Slice(1, 3);

int[] a = { 91, 92, -93, 94 };
Span<int> span = a.AsSpan();
// Enables a builder pattern approach, rather than having to do:
int[] a = { 91, 92, -93, 94 };
Span<int> span = new Span<int>(a);

// Similarly for ArraySegment
ArraySegment<int> segment = new ArraySegment<int>(a, 1, 2);
Span<int> span = segment.AsSpan();

Removing NonPortableCast:
Are these APIs useful and do we want to ship them? We can add them if they are necessary. Currently, they are only used in Parsing and Encoding for casting from byte to char, exclusively.
Example: https://github.com/dotnet/corefxlab/blob/c9423549a3e37a2b0de953dd20cf30558ebfca13/src/System.Text.Primitives/System/Text/Encoding/Utf16/Utf16TextEncoderLE.cs#L54

Adding StartsWith:
It enables more readable, cleaner code. The user also does not need to do length checks.

Span<byte> firstSpan = new Span<byte>(first);
ReadOnlySpan<byte> secondSpan = new ReadOnlySpan<byte>(second);

// You can write:
bool b = firstSpan.StartsWith(secondSpan);
// Instead of:
bool b = firstSpan.Slice(0, secondSpan.Length).SequenceEqual(secondSpan);
// You also have to do additional length checks first, i.e.:
bool b = firstSpan.Length >= secondSpan.Length && firstSpan.Slice(0, secondSpan.Length).SequenceEqual(secondSpan);

Adding IndexOfAny:
Used by Kestrel - System.IO.Pipelines.
https://github.com/dotnet/corefxlab/blob/66f021b94e93fe36bc0446d9f23d5a3820dc36df/src/System.IO.Pipelines/ReadCursorOperations.cs#L41
https://github.com/dotnet/corefxlab/blob/66f021b94e93fe36bc0446d9f23d5a3820dc36df/src/System.IO.Pipelines/ReadCursorOperations.cs#L63

// We have:
int index = span.IndexOfAny(byte0, byte1, byte2);
if (index != -1)
{
    result = new ReadCursor(segment, segmentPart.Start + index);
    return span[index];
}

// If we don't have this, the alternative would be, something like:
int index = span.IndexOf(byte0);
index = index == -1 ? span.IndexOf(byte1) : Math.Min(index, span.IndexOf(byte1));
index = index == -1 ? span.IndexOf(byte2) : Math.Min(index, span.IndexOf(byte2));
if (index != -1)
{
    result = new ReadCursor(segment, segmentPart.Start + index);
    return span[index];
}

Adding Copyto:
This is a convenience extension method on array to avoid having to write a Span wrapper around the source array.

var destination = new Span<byte>(new byte[100]);
var source = new byte[] { 1, 2, 3 };
// You can write:
source.CopyTo(destination);
// Instead of:
var sourceSpan = new Span<byte>(source);
sourceSpan.CopyTo(destination);

Another related API proposal: https://github.com/dotnet/corefx/issues/16888

Update:
- Changed AsSpan to SliceAsSpan and added overloads that take index and length.

[jkotas]

Do we also want to turn Fill (and potentially Clear) into extension method? The idea has been bounced around several times.

[ahsonkhan]

cc @davidfowl, @jkotas, @KrzysztofCwalina, @shiftylogic, @terrajobst

[ahsonkhan]

Do we also want to turn Fill (and potentially Clear) into extension method? The idea has been bounced around several times.

Rationale for this from @benaadams, dotnet/corefxlab#1314 (comment)

[benaadams]

Vectorizing Fill would work quite well; which would need to be done outside of coreclr

[davidfowl]

I would advise staying away from string in the short term so remove:

public static ReadOnlySpan<char> AsSpan(this string text);

[ahsonkhan]

I would advise staying away from string in the short term

Can you expand on that? Why stay away from string?

[davidfowl]

Because we haven't done anything with strings and Span up to this point. It's all been pretty light weight and prototypy. Once we add strings to the equation, we'll need lots of other methods on ReadOnlySpan<char> to make it feel like a string (like all the methods that exists on String).

[stephentoub]

Have we given any thought to having a method like TryGetArray(out ArraySegment) on Span. I'm thinking about a case like adding Span support to Stream. For example, if we wanted to add a new Stream.Write(Span) method, we'd need to make it virtual, and while we'd then override it on all of our streams to do the efficient thing, we'd still want the base implementation to be as reasonable as possible. If the Span wraps an array, it'd be best to extract that array/offset/count so we could just then delegate to the existing Write method; if the Span wrapped something else, we could fall back to getting a pooled array, CopyTo'ing the data from the span, etc.

[jkotas]

Have we given any thought to having a method like TryGetArray(out ArraySegment) on Span

It is not possible to implement this method for fast Span.

[stephentoub]

It is not possible to implement this method for fast Span

Not possible ever, today, or just inefficient? There's no way internally to ask whether the stored reference is part of an object and get a reference to that object?

[jkotas]

Ok, yes it is possible to do - very inefficiently.

[stephentoub]

Ok, thanks. And I guess so inefficiently that it'd be cheaper to copy all the data out?

[jkotas]

It is linear search: enumerate all GC segments to find the GC segment where the pointer lives, and then enumerate all objects in that segments until you find the one you are looking for. The GC has some existing caches around this that would improve the situation if you ask for the same thing again and again but I am not sure how hard it would be to leverage them outside of GC.

There is point from which it would be profitable. I guess it would be an improvement if you avoid copying 1MB buffer. You would need to measure to find out where the threshold typically is for real workloads.

[davidfowl]

We decided to keep TryGetArray on Buffer instead of span because it was easier to implement and "less pure".

[karelz]

@ahsonkhan please make sure you have the right people who can speak about the APIs in tomorrow's API review meeting (@KrzysztofCwalina should be there)

[terrajobst]

Looks mostly good but we decided that these should be changed:

-    public static ReadOnlySpan<char> AsSpan(this string text);
-    public static Span<T> AsSpan<T>(this T[] array);
-    public static Span<T> AsSpan<T>(this ArraySegment<T> segment);

+    public static ReadOnlySpan<char> SliceAsSpan(this string text);
+    public static ReadOnlySpan<char> SliceAsSpan(this string text, int index);
+    public static ReadOnlySpan<char> SliceAsSpan(this string text, int index, int length);
+
+    public static Span<T> SliceAsSpan<T>(this T[] array);
+    public static Span<T> SliceAsSpan<T>(this T[] array, int index);
+    public static Span<T> SliceAsSpan<T>(this T[] array, int index, int length);
+
+    public static Span<T> SliceAsSpan<T>(this ArraySegment<T> segment);
+    public static Span<T> SliceAsSpan<T>(this ArraySegment<T> segment, int index);
+    public static Span<T> SliceAsSpan<T>(this ArraySegment<T> segment, int index, int length);

[karelz]

@ahsonkhan please update the proposal on the top, so that we do not loose track of it, thanks!

[jkotas]

- AsSpan
+ SliceAsSpan

@terrajobst Could you please briefly explain motivation for this change?

[ahsonkhan]

It is inconsistent to have an AsSpan() method that takes parameters (an index and length). There are performance issues with using s.AsSpan().Slice(1, 3) versus s.SliceAsSpan(1, 3). Therefore, to convey that we are slicing (i.e. getting a subset) and converting to a different type (string to span for example), while keeping performance, we use SliceAsSpan. This also leave Slice (without a suffix) available for the default behavior which would be that slice returns the type it is slicing. Any type conversion outside the default would have SliceToX or SliceAsX.

@terrajobst, let me know if I misspoke or missed something.

[jkotas]

There are performance issues with using s.AsSpan().Slice(1, 3) versus s.SliceAsSpan(1, 3).

Why do you think so?

We have been there before with IndexOf and proved that it does not make sense to fold slicing with other APIs, and that not folding it is actually slightly better in the case of IndexOf. I am pretty sure that similar story will replay itself here if we go, measure and analyze the results. There should no performance penalty for the separate Slice method, assuming the optimizations are working as expected.

Therefore, to convey that we are slicing (i.e. getting a subset)

If I am getting the Span for the whole thing - that I believe is the most common case, I am not slicing anything but I still have the word Slice there. It looks odd to me.

Also, you should think about how this will compose with the eventual language syntax for ranges: s.AsSpan()[1:3] vs. s.SliceAsSpan()[1:3] vs. s.SliceAsSpan(1,3). The first one looks best to me.

[ahsonkhan]

var array = new byte[length];
a) Span<byte> span = array.AsSpan().Slice(length/2, length/2);
b) Span<byte> span = array.SliceAsSpan(length/2, length/2);

public static Span<T> AsSpan<T>(this T[] array)
{
    return new Span<T>(array);
}

public static Span<T> SliceAsSpan<T>(this T[] array, int index, int length)
{
    return new Span<T>(array, index, length);
}

public Span<T> Slice(int start, int length)
{
    if ((uint)start > (uint)_length || (uint)length > (uint)(_length - start))
        ThrowHelper.ThrowArgumentOutOfRangeException();

    return new Span<T>(ref Unsafe.Add(ref _pointer.Value, start), length);
}

In a) you would end up creating a span on the whole range first and then slicing and creating a smaller span.
While in b) you only create one span that is a view over the subset.

I noticed a performance difference:
1088 ms vs 820 ms

public static void TestAsSpan(int length)
{
    Stopwatch sw = new Stopwatch();
    var array = new byte[length];
    Span<byte> span;
    sw.Restart();
    for (int i = 0; i < BaseIterations; i++)
    {
        span = array.AsSpan().Slice(length/2, length/2);
    }
    var time = sw.ElapsedMilliseconds;
    Console.WriteLine(time + " : " + span.Length);
}

public static void TestSliceAsSpan(int length)
{
    Stopwatch sw = new Stopwatch();
    var array = new byte[length];
    Span<byte> span;
    sw.Restart();
    for (int i = 0; i < BaseIterations; i++)
    {
        span = array.SliceAsSpan(length/2, length/2);
    }
    var time = sw.ElapsedMilliseconds;
    Console.WriteLine(time + " : " + span.Length);
}

Disassembly:

    span = array.AsSpan().Slice(length/2, length/2);

00007FFCB87B2237 mov eax,dword ptr [rbx+8]
00007FFCB87B223A mov edx,esi
00007FFCB87B223C mov r8d,edx
00007FFCB87B223F shr r8d,1Fh
00007FFCB87B2243 add r8d,edx
00007FFCB87B2246 mov edx,r8d
00007FFCB87B2249 sar edx,1
00007FFCB87B224B mov r8d,edx
00007FFCB87B224E cmp edx,eax
00007FFCB87B2250 ja 00007FFCB87B22E2
00007FFCB87B2256 sub eax,edx
00007FFCB87B2258 cmp eax,r8d
00007FFCB87B225B jb 00007FFCB87B22E2
00007FFCB87B2261 mov ebp,edx

    span = array.SliceAsSpan(length/2, length/2);

00007FFCB87B296B mov edx,eax
00007FFCB87B296D mov esi,eax
00007FFCB87B296F mov r8d,dword ptr [rbx+8]
00007FFCB87B2973 cmp r8d,esi
00007FFCB87B2976 jb 00007FFCB87B2A06
00007FFCB87B297C sub r8d,esi
00007FFCB87B297F cmp r8d,edx
00007FFCB87B2982 jb 00007FFCB87B2A06

[jkotas]

Thanks for sharing the assembly fragments.

The difference between these two fragments is caused by CSE for length/2. The JIT decided to CSE length/2 in the second case, but not in the first case. It is side-effect of subtle code change. It does not prove that AsSpan+Slice is worse than SliceAsSpan. You just got unlucky. It could have turned the other way around as well.

You should see the difference to disapper if you do the CSE explicitly and not depend on luck:

public static void TestAsSpan(int length)
{
    Stopwatch sw = new Stopwatch();
    var array = new byte[length];
    int halfLength = length/2;
    Span<byte> span;
    sw.Restart();
    for (int i = 0; i < BaseIterations; i++)
    {
        span = array.AsSpan().Slice(halfLength , halfLength);
    }
    var time = sw.ElapsedMilliseconds;
    Console.WriteLine(time + " : " + span.Length);
}

public static void TestSliceAsSpan(int length)
{
    Stopwatch sw = new Stopwatch();
    var array = new byte[length];
    int halfLength = length/2;
    Span<byte> span;
    sw.Restart();
    for (int i = 0; i < BaseIterations; i++)
    {
        span = array.SliceAsSpan(halfLength, halfLength);
    }
    var time = sw.ElapsedMilliseconds;
    Console.WriteLine(time + " : " + span.Length);
}

[jkotas]

I am seeing exact same code for the two - just different registers used:

// a.AsSpan().Slice(halfLength,halfLength)

00007ffd`062a04cc 8b4f08          mov     ecx,dword ptr [rdi+8]
00007ffd`062a04cf 3bf1            cmp     esi,ecx
00007ffd`062a04d1 7748            ja      test!My.Main()+0x9b (00007ffd`062a051b)
00007ffd`062a04d3 2bce            sub     ecx,esi
00007ffd`062a04d5 3bce            cmp     ecx,esi
00007ffd`062a04d7 7242            jb      test!My.Main()+0x9b (00007ffd`062a051b)
00007ffd`062a04d9 8bee            mov     ebp,esi
00007ffd`062a04db ffc2            inc     edx

// a.SliceAsSpan(halfLength,halfLength);

00007ffd`062804cc 8b4f08          mov     ecx,dword ptr [rdi+8]
00007ffd`062804cf 3bce            cmp     ecx,esi
00007ffd`062804d1 7248            jb      test!My.Main()+0x9b (00007ffd`0628051b)
00007ffd`062804d3 2bce            sub     ecx,esi
00007ffd`062804d5 3bce            cmp     ecx,esi
00007ffd`062804d7 7242            jb      test!My.Main()+0x9b (00007ffd`0628051b)
00007ffd`062804d9 8bee            mov     ebp,esi
00007ffd`062804db ffc2            inc     edx

[ahsonkhan]

Fascinating. CSE = common sub-expression elimination.
The difference shrinks to essentially zero (+/- a bit) once I use the local variable for length/2.

Would the same hold true for string.Slice as well vs string.AsSpan?

[jkotas]

Would the same hold true for string.Slice as well vs string.AsSpan?

Yes.

[ahsonkhan]

@karelz, @terrajobst, in light of the info (and perf tests), would it be best to revert back to the originally proposed API (using AsSpan) and not have SliceAsSpan overloads that take index and length?

[ahsonkhan]

@jkotas, I modified my test app (to return the span) and observed the performance difference again.

public static Span<byte> TestAsSpan(int length)
{
    Stopwatch sw = new Stopwatch();
    var array = new byte[length];
    int halfLength = length / 2;
    Span<byte> span;
    sw.Restart();
    for (int i = 0; i < BaseIterations; i++)
    {
        span = array.AsSpan().Slice(halfLength, 10);
    }
    sw.Stop();
    var time = sw.ElapsedMilliseconds;
    Console.WriteLine(time + " : " + span.Length);
    return span;
}

public static Span<byte> TestSliceAsSpan(int length)
{
    Stopwatch sw = new Stopwatch();
    var array = new byte[length];
    int halfLength = length / 2;
    Span<byte> span;
    sw.Restart();
    for (int i = 0; i < BaseIterations; i++)
    {
        span = array.SliceAsSpan(halfLength, 10);
    }
    sw.Stop();
    var time = sw.ElapsedMilliseconds;
    Console.WriteLine(time + " : " + span.Length);
    return span;
}

Output:
1094 : 10
827 : 10

            span = array.AsSpan().Slice(halfLength, 10);

00007FFCB39B24F9 lea rax,[rbp+10h]
00007FFCB39B24FD mov qword ptr [rsp+30h],rax
00007FFCB39B2502 mov eax,dword ptr [rbp+8]
00007FFCB39B2505 mov rdx,qword ptr [rsp+30h]
00007FFCB39B250A cmp edi,eax
00007FFCB39B250C ja 00007FFCB39B25C8
00007FFCB39B2512 sub eax,edi
00007FFCB39B2514 cmp eax,0Ah
00007FFCB39B2517 jb 00007FFCB39B25C8
00007FFCB39B251D movsxd rax,edi
00007FFCB39B2520 add rax,rdx
00007FFCB39B2523 mov qword ptr [rsp+28h],rax
00007FFCB39B2528 mov r14d,0Ah
00007FFCB39B252E mov r15,qword ptr [rsp+28h]

            span = array.SliceAsSpan(halfLength, 10);

00007FFCB39B2C85 mov eax,dword ptr [rbp+8]
00007FFCB39B2C88 cmp eax,edi
00007FFCB39B2C8A jb 00007FFCB39B2D4A
00007FFCB39B2C90 sub eax,edi
00007FFCB39B2C92 cmp eax,0Ah
00007FFCB39B2C95 jb 00007FFCB39B2D4A
00007FFCB39B2C9B lea rax,[rbp+10h]
00007FFCB39B2C9F movsxd rdx,edi
00007FFCB39B2CA2 add rax,rdx
00007FFCB39B2CA5 mov qword ptr [rsp+20h],rax
00007FFCB39B2CAA mov r14d,0Ah
00007FFCB39B2CB0 mov r15,qword ptr [rsp+20h]

[karelz]

Flipping back to api-ready-for-review, until we have clear green light from @KrzysztofCwalina @jkotas @terrajobst ... there are signs of approval of the original API shape in emails, but it is not 100% clear to me ... let's also update the top post when we're done with approvals.

[nietras]

Do we also want to turn Fill (and potentially Clear) into extension method? The idea has been bounced around several times.

Currently, the slow Span Fill/Clear member methods use internal knowledge of Span to have two code paths:

• ref based for managed memory
• pointer based for unmanaged or pinned memory

Changing to extension methods one would have to revert to "ref based" only or perhaps using pinning to change to pointer if needed. The drawback being that ref based code isn't always as performant as pointer based as far as I can tell. However, as it seems pinning is done by default for almost all perf sensitive Span extension methods anyway (IndexOf comes to mind), one could argue that a pinning based extension method implementation would be fine. Pinning seems to be a minimal concern... so given that, these could probably be moved to being extension methods. But one could make the same argument for any Span method then, including CopyTo etc.

[jkotas]

@karelz The original API proposal looks good to me as a whole. Also, the large part of the proposal is non-contentious so @ahsonkhan can certainly proceed with implementing that.

[karelz]

Thanks @jkotas! I let @KrzysztofCwalina and @terrajobst to make the final call here.

[benaadams]

Extensions for the methods like clear allow specialization; so a Clear method could be defined differently. Whether its to use vectors; or if for a custom user struct all the values should be set to -1 rather than zero it would allow that; equally for Fill using vectors for the base numeric types.

CopyTo am less sure about; but don't think there would be an overall harm making it an extension?

[KrzysztofCwalina]

All the APIs in the proposal except AsSpan are solid (good to go). As for AsSpan, we should get to the bottom of the performance difference. The assembly @jkotas provided look suspicious to me. It does look like it's doing any slicing. The new assembly @ahsonkhan provided shows differences, but I wonder if these matter.

[ahsonkhan]

@KrzysztofCwalina, I talked with @russellhadley, and the assembly/performance difference I reported above is due to a JIT issue caused by register spilling. The JIT team will work on fixing this.

[jkotas]

It does look like it's doing any slicing.

It does all the bounds checks required by slicing. The test is not accessing the sliced data so you do not see the pointer to the data getting materialized. The JIT figured out correctly that it is useless to materialize it. In both cases.

provided shows differences

They show different register allocation. Minor deficiency in the JIT optimizations. Not something to optimize the API design around.

[karelz]

@terrajobst are you ok to fast-track the API approval? Given that is has been discussed in yesterday's meeting and both @jkotas and @KrzysztofCwalina agree with the original proposal ...

[ahsonkhan]

From @terrajobst, "I’d be much in favor of keeping the original API shape i.e. AsSpan().Slice(). It keeps the semantics we want, which is that different primitive types (might) define slicing differently without having to qualify the slicing method."

So, he has approved.

[karelz]

Thanks for pointing it out, I missed that as it was over email and not here :( ... tracking multiple sources :(

[karelz]

Approved as originally proposed.

[ahsonkhan]

Question: When does an API proposal issue get closed? The APIs have been updated according to this proposal already. Should this issue get closed?

[jkotas]

Yes.

[Mirandatz]

Please, do not remove NonPortableCast.

I just found this method and I'm using it with cryptography algorithms (converting byte arrays to ulongs or uints).
It's concise, performant enough and doesn't require me to change the build options to allow unsafe code (I was using pointers before).

If anything, please give it more love.

[jkotas]

It was not removed. It was renamed to MemoryMarshal.Cast