API for inserting a Span<T> into a List<T> efficiently

[josetr]

EDITED 9/22/2022 by @stephentoub:

namespace System.Collections.Generic
{
    public class List<T>
    {
+        public void AddSpan(ReadOnlySpan<T> span);
+        public void InsertSpan(int index, ReadOnlySpan<T> span);

+        public void CopyTo(Span<T> span);
    }
}

• We can't just add an AddRange overload as it's ambiguous for anything convertible to both span and enumerable, like array. We could alternatively call it AddRange and add overloads as well for arrays and strings.

---

Perhaps an AddRange overload taking a Span<T> can be added to the List class?

var list = new List<byte>();
list.AddRange(new Span<byte>());

Workarounds

foreach(var b in span)
    list.Add(b); // Inefficient only copying one byte at a time

var list = new List<byte>();
var span = new Span<byte>();
list.AddRange(span.ToArray()); Silly allocation

[ahsonkhan]

Do you have a scenario to help motivate this addition (maybe example code today where the workarounds are noticeably inefficient)? Are there other List APIs that fall into this category (for instance what about the List<T> ctor)?

Similarly, we have the CopyTo that takes arrays.

Presumably, there was a reason such APIs didn't meet the bar during the first round:
https://github.com/dotnet/corefx/issues/21281

There are some other namespaces that could likely benefit from Span/Buffer, but we should probably handle separately from this initial push:

• System.Collections. It’s not clear to me to what extent we should add span/buffer-based APIs to collections. CopyTo overloads that take Span<T>?

[DaZombieKiller]

Just to add to the List<T> of workarounds 😛

public static class ListMarshal
{
    static readonly IntPtr _items   = Marshal.OffsetOf(typeof(List<>), "_items");
    static readonly IntPtr _size    = Marshal.OffsetOf(typeof(List<>), "_size");
    static readonly IntPtr _version = Marshal.OffsetOf(typeof(List<>), "_version");

    class RawData
    {
        public byte Data;
    }

    static ref TField GetField<T, TField>(List<T> list, IntPtr offset)
    {
        var raw  = Unsafe.As<RawData>(list);
        return ref Unsafe.As<byte, TField>(ref Unsafe.Add(ref raw.Data, offset));
    }

    public static T[]     GetArray     <T>(List<T> list) =>     GetField<T, T[]>(list, _items);
    public static ref int GetCountRef  <T>(List<T> list) => ref GetField<T, int>(list, _size);
    public static ref int GetVersionRef<T>(List<T> list) => ref GetField<T, int>(list, _version);
}

Which you could turn into the following extension method:

public static class ListExtensions
{
    public static void AddRange<T>(this List<T> self, ReadOnlySpan<T> values)
    {
        if (self.Count + values.Length > self.Capacity)
            self.Capacity = self.Count + values.Length;

        var array = ListMarshal.GetArray(self);
        values.CopyTo(array.AsSpan(self.Count));

        ListMarshal.GetCountRef  (self) += values.Length;
        ListMarshal.GetVersionRef(self)++;
    }
}

Which would be used as follows:

var list = new List<int> { 1, 2, 3, 4 };
var data = new[] { 5, 6, 7, 8 }.AsSpan();
list.AddRange(data);

foreach (var value in list)
    Console.WriteLine(value);

It feels incredibly dirty to do this though, so a proper solution in CoreFX would be greatly appreciated.

[jkotas]

It feels incredibly dirty to do this though

Yes, it is dirty and it does not even work. You will get Type 'System.Collections.Generic.List1[T]' cannot be marshaled as an unmanaged structure; no meaningful size or offset can be computed.exception thrown from theMarshal.OffsetOf` call.

[jkotas]

The best current workaround for this is to roll your own List<T> type that does exactly what you need.

[DaZombieKiller]

It feels incredibly dirty to do this though

Yes, it is dirty and it does not even work. You will get Type 'System.Collections.Generic.List1[T]' cannot be marshaled as an unmanaged structure; no meaningful size or offset can be computed.exception thrown from theMarshal.OffsetOf` call.

Interestingly, it worked perfectly fine while running on Mono (must be an oversight on their part). However on .NET Core I get the error you mentioned. It's fixable by using reflection, although it requires some extra ceremony.

The best current workaround for this is to roll your own List<T> type that does exactly what you need.

I'd normally recommend this too, but it's not an option when you're dealing with a third party API taking a List<T>.

[ghost]

Due to lack of recent activity, this issue has been marked as a candidate for backlog cleanup. It will be closed if no further activity occurs within 14 more days. Any new comment (by anyone, not necessarily the author) will undo this process.

This process is part of the experimental issue cleanup initiative we are currently trialing in a limited number of areas. Please share any feedback you might have in the linked issue.

[ghost]

This issue will now be closed since it had been marked no recent activity but received no further activity in the past 14 days. It is still possible to reopen or comment on the issue, but please note that the issue will be locked if it remains inactive for another 30 days.

[Raymonf]

Since this is now closed (I didn’t see the comment by the bot from 2 weeks ago), what is the preferred solution for doing this while avoiding the allocation that would come from ToArray()? Does one exist?

[eiriktsarpalis]

@Raymonf to my knowledge the only known workarounds are the ones listed in the OP. In the future it might be possible to do this using the CollectionsMarshall.AsSpan method, however we're still missing a method for presizing lists (cf. #55217). In pseudocode it would look as follows:

public static void AddRange<T>(this List<T> list, ReadOnlySpan<T> items)
{
    int initialCount = list.Count;
    list.Resize(initialCount + items.Length); // !!! NB this method is currently not implemented
    Span<T> buffer = CollectionsMarshal.AsSpan(list);
    items.CopyTo(buffer.Slice(initialCount));
}

[MihaZupan]

@eiriktsarpalis how come we're closing this? Was there a decision to reject the proposal altogether?

[stephentoub]

#1530 (comment)

[MihaZupan]

I guess the question is "why was no-recent-activity added"

[eiriktsarpalis]

See #60288 for context.

[stephentoub]

I updated the top post. I think we should add this. List<T> is the primary growable array type we push people to use, and ReadOnlySpan<T> is now a critically-important data type; you should be able to add the latter to the former efficiently.

[eiriktsarpalis]

Are there opportunities for adding other span overloads? At quick glance, a constructor accepting ROS<T> and a CopyTo(Span<T>) overload seem like obvious candidates.

[tfenise]

Adding the proposed overload public void AddRange(ReadOnlySpan<T> collection); (as well as InsertRange) would be a source code breaking change, because there would be an ambiguity when passing a T[] as the argument collection. Potential solutions include introducing another overload taking a T[] as parameter, or adding the proposed overload as an extension method, or maybe renaming the proposed overload (but we may want an argument of type T[] to go through the overload with parameter ReadOnlySpan<T> instead of IEnumerable<T>).

[stephentoub]

Are there opportunities for adding other span overloads? At quick glance, a constructor accepting ROS and a CopyTo(Span) overload seem like obvious candidates.

CopyTo would be reasonable. It does have a workaround today, which is that someone can use CollectionsMarshal.AsSpan to get a span for the list, and then CopyTo with that as the source... there's no good workaround today for AddRange.

A ctor is going to have the same ambiguity problem that tfenise calls out, and we can't workaround that with a name.

[terrajobst]

Video

• We should talk to @jaredpar / @dotnet/ldm about whether his proposal for "binary compatibility only" could be used here to avoid having to add new method group. We could also make them extension methods in which case they wouldn't cause ambiguities but only be used for spans. That being said, given that F# and VB wouldn't have the hypothetical feature so we probably would do the extension method for a core type anyway.
• There is another concern about generic instantiations and lack of pay-for-play for methods only used for some Ts.

This would be the desired API:

namespace System.Collections.Generic;

public partial class List<T>
{
    public void AddRange(ReadOnlySpan<T> span);
    public void InsertRange(int index, ReadOnlySpan<T> span);
    public void CopyTo(Span<T> span);
}

If we go down the extension method route, it would look like this:

namespace System.Collections.Generic;

public static class CollectionExtensions
{
    public static void AddRange<T>(this List<T> list, ReadOnlySpan<T> source);
    public static void InsertRange<T>(this List<T> list, int index, ReadOnlySpan<T> source);
    public static void CopyTo<T>(this List<T> list, Span<T> destination);
    // We discussed this but decided against this until there is a need.
    // public static bool TryCopyTo<T>(this List<T> list, Span<T> destination);
}

We're inclined to approve the extension method shape and simultaneously work with the compiler team to see whether we can use a language feature to avoid using the extension methods.