Add List<T>.CopyTo(Span<T>) overloads

[eerhardt]

We have List<T> CopyTo methods that all take an array:

        public void CopyTo(int index, T[] array, int arrayIndex, int count);
        public void CopyTo(T[] array, int arrayIndex);
        public void CopyTo(T[] array);

We should add similar overloads that take in a Span<T>.

public partial class List<T> : System.Collections.Generic.ICollection<T>, System.Collections.Generic.IEnumerable<T>, System.Collections.Generic.IList<T>, System.Collections.Generic.IReadOnlyCollection<T>, System.Collections.Generic.IReadOnlyList<T>, System.Collections.ICollection, System.Collections.IEnumerable, System.Collections.IList
{
+       public void CopyTo(int index, Span<T> span, int count);
+       public void CopyTo(Span<T> span);
}

I know you can work around not having this API by looping over the List<T> yourself. But since List is backed by an array, it is faster to use memcpy (or similar) than it is doing one element at a time. (That is the same reason why we have CopyTo(T[]) in the first place.)

[GSPP]

Maybe we should make a ticket to generally overhaul all collection classes with Span. That seems better than having a trickle of upgrades where each version just adds a few. We need to systematically see through all APIs and upgrade them.

Upgrading everything is necessary anyway, reduces the total amount of work, increases version predictability and helps with API consistency.

[safern]

@eerhardt would it make sense to wait for default interface implementation feature and add it to IList<T> instead? Or would that be a breaking change as well?

[john-h-k]

This would be really useful, when you have spans not backed by an array. It also seems a very easy implementation, and would match the span overloads being added to so many other APIs. I'd be happy to write it if it gets approved

( for what it's worth, I don't think the int index, Span<T> span, int count is necessary - no other APIs have them, and it seems more expected to use the span overload and slice the span yourself instead )

[GrabYourPitchforks]

Note to implementer: be mindful that you might not be able to implement the T[]-based methods in terms of the Span<T>-based method. Array variance and span variance have different semantics, and rewriting one method in terms of the other might inadvertently break edge case scenarios.

[terrajobst]

Video

Wow, that took quite a bit 😄

• Makes sense. We should just make sure that List<T>.CopyTo(someInt, someArray, anotherInt) doesn't magically bind to the span version.
  • While not a breaking having the third parameter having different behavior is bad (arrayIndex vs. count)

public partial class List<T>
{
    // public void CopyTo(int index, T[] array, int arrayIndex, int count);
    // public void CopyTo(T[] array, int arrayIndex);
    // public void CopyTo(T[] array);

    public void CopyTo(Span<T> destination);
    public void CopyTo(int sourceIndex, int count, Span<T> destination);
}

[felipepessoto]

@terrajobst is anyone working on that? I would like to implement it

[safern]

@felipepessoto nobody yet. Please feel free to put up a PR in https://github.com/dotnet/runtime 😄

Assigning this issue to you.

[jkotas]

I know you can work around not having this API by looping over the List yourself. But since List is backed by an array, it is faster to use memcpy (or similar) than it is doing one element at a time.

We have introduced CollectionMarshal.AsSpan to address this and other similar scenarios. You can do this today using:

CollectionMarshal.AsSpan(list).CopyTo(span);

Are these specialized APIs worth it to save the few characters and allow writing just list.CopyTo(span)? Are there enough examples in runtime libraries or in the code out there that will benefit from these APIs?

[GSPP]

@jkotas Can you point me to where I can find CollectionMarshal? I searched the repository and all commits without success.

[felipepessoto]

@GSPP https://github.com/dotnet/runtime/blob/master/src/libraries/System.Private.CoreLib/src/System/Runtime/InteropServices/CollectionsMarshal.cs

I was't finding it too,if you search for CollectionMarshal (singular), GitHub doesn't return any results :)

[safern]

We have introduced CollectionMarshal.AsSpan to address this and other similar scenarios. You can do this today using:

I think we totally missed the addition of the extension methods to CollectionMarshal and this issue was opened before that existed, but that is a good point, it would just be saving people from calling AsSpan on the list. I'm inclined towards not needing to add these APIs anymore.

For the second proposed API where we accept and index and length, ppl would have to slice the span, right?

Also, if we go that route, would it make sense to add extension methods for collection interfaces?

[felipepessoto]

The CollectionsMarshal method is not an extension methods (and is under InteropServices namespace), I think that is part of the reason people doesn't find it, it is not very discoverable.

[eerhardt]

We briefly discussed the CollectionMarshal.AsSpan in the API Review meeting, but it quickly got dismissed since the method isn't discoverable (which is by design of CollectionMarshal.AsSpan).

If we want to start promoting CollectionMarhsal.AsSpan as the best way to copy items from a List<T> to a Span<T>, then I would be fine with not adding this method. But do we want to start promoting it for such a common operation?

Are there enough examples in runtime libraries or in the code out there that will benefit from these APIs?

The place where this API proposal originated was in ML.NET when switching from using Arrays in VBuffer to using Spans.

See

• https://github.com/dotnet/machinelearning/blob/0da7f86616fa62cca157bcd5b7413f46b4cc89e0/src/Microsoft.ML.Core/Utilities/Utils.cs#L181-L198
• https://github.com/dotnet/machinelearning/blob/0da7f86616fa62cca157bcd5b7413f46b4cc89e0/src/Microsoft.ML.Core/Utilities/VBufferUtils.cs#L1357-L1361

[jkotas]

But do we want to start promoting it for such a common operation?

Do you expect this to be a common operation?

The ML.NET examples seems to be modernization glue: Part of the codebase was converted to use Spans, but other part is still on the classic plan. I think CollectionsMarshal is appropriate to use to marshal between two words efficiently. You are right that CopyTo can help in some situations like this, but other situations are still going to require CollectionsMarshal.

Note that these APIs are not 100% pay-for-play. They will make all existing instantiations of List<T> in existing code slightly more expensive.

[eerhardt]

Do you expect this to be a common operation?

CopyTo is a common enough operation that we put it on ICollection with the destination of an Array. Looking at API Port Telemetry, CopyTo(T[], int) is used by ~17% of apps.

The ML.NET examples seems to be modernization glue: Part of the codebase was converted to use Spans, but other part is still on the classic plan.

I'm not sure I follow this statement.

The scenario where this is used is where an unknown number of things need to be put in a Span. You pass around a List<T> adding to it as necessary. Then when you are done you copy it to the destination Span.

They will make all existing instantiations of List in existing code slightly more expensive.

You mean because of the additional code on List<T>? Or some other reason?

[GSPP]

Is there any intention of creating collection interfaces with spans? It seems there could be some more comprehensive overhaul. That's difficult for sure without creating a mess. But maybe that's better than adding a span overload here and there, and dribble it out over many releases.

[jkotas]

The scenario where this is used is where an unknown number of things need to be put in a Span. You pass around a List adding to it as necessary. Then when you are done you copy it to the destination Span.

List<T> does the job, but it is not the most effient tool for this job. For example, we have changed List<T> to ValueListBuilder<T> or other techniques in number of places accross runtime libraries that makes List<T>.CopyTo for this scenario unnecessary. It is what I meant by modernization glue.

You mean because of the additional code on List?

Yes, the extra methods on frequently used generic types are not 100% pay-for-play. In particular, they tend to hurt with full AOT binary sizes. These two methods are small enough that it is not end of the world. We have done similar paper-cuts before. It would be useful to know what "done" looks like as @GSPP pointed out.

[jkotas]

It would be useful to know what "done" looks like

E.g. #1517

[safern]

Given the above discussion and #891 (comment) I'm going to close this issue. If people disagree or have any other thoughts, feel free to add them and we can always re-consider.