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

@stephentoub

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

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>?

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.

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.

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

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>.

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.

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.

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>).

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.

@jaredpar

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.

Navigation Menu

Repository navigation

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

18 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

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

Description

Activity

ahsonkhan commented on Mar 21, 2019

DaZombieKiller commented on Mar 21, 2019

jkotas commented on Mar 21, 2019

jkotas commented on Mar 21, 2019

DaZombieKiller commented on Mar 21, 2019

18 remaining items

stephentoub commented on Sep 23, 2022

eiriktsarpalis commented on Sep 23, 2022

tfenise commented on Sep 23, 2022

stephentoub commented on Sep 23, 2022

terrajobst commented on Sep 27, 2022

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions