[API Proposal]: CollectionMarshal.AsArraySegment<T>(List<T>) overload

[koszeggy]

Background and motivation

CollectionMarshal currently offers the AsSpan<T>(List<T>) method for List<T>. However, Span<T> cannot be always used, for example when one would use it in a lambda expression or when it should be passed to another thread. Maybe this design was chosen to prevent the callers from storing an optionally long-living reference to the momentary inner state of a List<T>, but maybe the consumers of CollectionMarshal are aware of the consequences.

Concrete example: Multi-threaded IList<T> sorting, where there is a better-performing special handling for List<T>. Unfortunately this special handling is not too effective today. Not just because it's much slower than the array version, but also because it requires an extra implementation, which wouldn't be necessary if I could access the underlying array section as a non-ref struct.

API Proposal

public static class CollectionsMarshal
{
    public static Span<T> AsSpan<T>(List<T>? list);
+   public static ArraySegment<T> AsArraySegment<T>(List<T>? list);
+   [public static Memory<T> AsMemory<T>(List<T>? list);] // Optional
}

Why not (just) Memory<T>?

Memory<T> is a more general concept that can be backed by an array, a string or a memory manager. As List<T> always wraps an array, we can use the more specific ArraySegment<T> here. Also, creating a Memory<T> from an ArraySegment<T> is much more trivial (and more performant) than using the Memory.TryGetArray method.

API Usage

Considering the motivation example again, my code could be rewritten like this:

private static bool DoSort<TKey, TValue>(IAsyncContext context, IList<TKey> keys, IList<TValue> values, int startIndex, int count, IComparer<TKey>? comparer)
{
    // [...]
     switch (list)
     {
        // [...]
        case List<T> genericList:
-            // List<T>: multithreaded sorting is getting faster only from 4 cores. Unfortunately there is no public API to get
-            // the underlying array, and CollectionMarshal.AsSpan cannot be used because spans cannot be passed to other threads.
-            if (isSingleThreadNotCancellable || context.MaxDegreeOfParallelism is >= 1 and < 4)
-                genericList.Sort(startIndex, count, comparer);
-            else
-                SortHelper<T>.Instance.Sort(context, genericList, startIndex, count, comparer);
-            break;

+            if (isSingleThreadNotCancellable)
+                genericList.Sort(startIndex, count, comparer);
+            else
+            {
+                var segment = CollectionsMarshal.AsArraySegment(genericList);
+                SortHelper<T>.Instance.Sort(context, segment.Array, startIndex /*+ segment.Offset - always 0 for a List */, count, comparer);
+            }
+            break;

        // [...]
     }
}

And then I could simply remove the extra implementation for List<T> as it could now use the array path:

private interface ISortHelper<T>
{
    void Sort(IAsyncContext context, IList<T> list, int startIndex, int count, IComparer<T>? comparer);
    void Sort(IAsyncContext context, T[] array, int startIndex, int count, IComparer<T>? comparer);
-   void Sort(IAsyncContext context, List<T> list, int startIndex, int count, IComparer<T>? comparer); // along with the implementations
}

Alternative Designs

No response

Risks

No response

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

[Clockwork-Muse]

However, Span<T> cannot be always used, for example when one would use it in a lambda expression or when it should be passed to another thread.

You can't have the lambda capture it (take a reference to something not passed as a parameter), they work just fine for parameters. You generally want to avoid captures anyways.

Maybe this design was chosen to prevent the callers from storing an optionally long-living reference to the momentary inner state of a List<T>, but maybe the consumers of CollectionMarshal are aware of the consequences.

This isn't a problem because of List, but rather a consequence of how Span is implemented (stack-only memory).

As List<T> always wraps an array, we can use the more specific ArraySegment<T> here.

This isn't actually a guarantee. It's an internal implementation detail, and allowed to change (however unlikely that may be in practice).

Memory<T> is a more general concept that can be backed by an array, a string or a memory manager.... Also, creating a Memory<T> from an ArraySegment<T> is much more trivial (and more performant) than using the Memory.TryGetArray method.

Your API is backwards. You'd take and slice the Memory<T> instance to pass to each thread, and then in each thread get the Span<T> from the Memory<T> slice. You wouldn't involve ArraySegment at all. Or pass the List<T> and the start and end indices, then in each thread get the Span and slice and use it.

(How you'd get a Memory from a List is left as an exercise for the reader, but probably involves a copy and copy back)

Personally, if I was going to be designing a multi-threaded sorting library, my API would be using Memory<T> as the preferred input.

[koszeggy]

You can't have the lambda capture it (take a reference to something not passed as a parameter), they work just fine for parameters. You generally want to avoid captures anyways.

Generally I would agree, but as I mentioned I occasionally need to pass the (slices of the) span to a new thread. There is no API today that accepts a Span<T> as a parameter that is invoked on another thread. Parameterized Thread and ThreadPool invocations work with delegates or can pass a state as an object, which is a no-go for spans. So the last resort would be using captures, but for spans this is not working for obvious reasons.

This isn't a problem because of List, but rather a consequence of how Span is implemented (stack-only memory).

Maybe I wasn't quite clear. I meant the design choice of returning a Span rather than an ArraySegment.

Your API is backwards. You'd take and slice the Memory<T> instance to pass to each thread, and then in each thread get the Span from the Memory<T> slice. You wouldn't involve ArraySegment at all. Or pass the List<T> and the start and end indices, then in each thread get the Span and slice and use it.

No, the public API is for IList<T>, whereas the List<T> handling is just one of the few special treatments for performance reasons. Functionally it wouldn't be needed. So thank you for your suggestion, I know how I can get the Span of a Memory instance but if I could retrieve the Memory<T> from List<T>, then I wouldn't have created this issue in the first place.

How you'd get a Memory from a List is left as an exercise for the reader, but probably involves a copy and copy back

Which I cannot accept as it kills the whole point of performant special handling

Personally, if I was going to be designing a multi-threaded sorting library, my API would be using Memory<T> as the preferred input.

That would be quite limiting compared to IList<T>. It can be added as an additional overload but that's not the point here. The point is that exposing an ArraySegment<T> from List<T> would be a trivial API. My use case was just one possible example, nothing more. And whereas casting an ArraySegment to Memory or Span is trivial (also performance-wise), it's quite the opposite the other way around.

[davidfowl]

Pass the list and a Range to each of the threads then delay the call to AsSpan to each of the worker threads.

[Clockwork-Muse]

Pass the list and a Range to each of the threads then delay the call to AsSpan to each of the worker threads.

Right, this was my other suggestion.

[koszeggy]

Pass the list and a Range to each of the threads then delay the call to AsSpan to each of the worker threads.

Though I could do this, it wouldn't let me get rid of the duplicate List<T> handling¹ whereas the recommended API could be added painlessly.

This isn't actually a guarantee. It's an internal implementation detail, and allowed to change (however unlikely that may be in practice).

I didn't react to this one first. The fact that List<T> is backed by an array is documented very thoroughly. And by introducing CollectionsMarshal.AsSpan an even stronger implementation detail has already been exposed: namely that the items in the backing array are always contiguous, which actually shouldn't be necessarily the case.

Footnotes

1. Before mentioning, I know I could force using a unified Memory handling for the array and list paths where the list version could use a memory manager (which introduces more allocations and unnecessary complexity). Whereas allowing a clean access to the array segment would be both cleaner and faster. ↩

[huoyaoyuan]

#87210 #90141 #101914 #105179

It's quite intentional to not allow a persist-able view to be marshalled. It will be invalidated by manipulations to the list.

[tannergooding]

I didn't react to this one first. The fact that List is backed by an array is documented very thoroughly.

This is a point in time implementation detail, not a guarantee. The actual guarantee (which was fixed when we decided to expose the AsSpan unsafe helper) is simply that it is some form of contiguous memory that will be dynamically resized as appropriate. List<T> is itself not thread safe as well, so the number of actions you can do in multithreading scenarios is limited and error prone. Exclusive read access is safe, but any type of mutation becomes potentially dangerous.

The intended design is that you operate on the List<T> itself and in the rare case you need the extra perf or to do something highly specialized the CollectionsMarshal.AsSpan gives you a limited lifetime view of the backing memory, which still has the general issues where mutating the list while such a view exists is dangerous and being generally not thread-safe by itself.

Exposing something like AsArraySegment is then undesirable because it forces the implementation to forever use T[] and disallows future optimizations such as using some other form of contiguous allocation. One such example is a theoretical new Array<T, TMetadata>, which allows the additional fields (such as int _size and int _versions) to be tracked inline with the _items field, making resizing operations atomic.

Exposing something like AsMemory is then undesirable because it can be persisted and doesn't have a known/fixed lifetime, which is inherently dangerous and error-prone since calling most methods on the original List<T> can result in a new array being created and the Memory<T> no longer tracking the contents of the List<T>, but rather some point in time snapshot.

The best option in such scenarios is to pass through the List<T> and call CollectionsMarshal.AsSpan per entry. If you want to make it more generic, you can pass through an IList<T>, ICollection<T>, or IEnumerable<T> and opportunistically have an if (input is List<T> list) { OverloadThatHandlesSpan(CollectionsMarshal.AsSpan(list)); } acceleration path, much as is done internally in LINQ or other functions today.

[koszeggy]

It's quite intentional to not allow a persist-able view to be marshalled. It will be invalidated by manipulations to the list.

So my assumption was right: "Maybe this design was chosen to prevent the callers from storing an optionally long-living reference to the momentary inner state of a List<T>", though I also added "but maybe the consumers of CollectionMarshal are aware of the consequences." I'm sad to learn that you are adamant so I cannot really simplify the special handling for a List<T>.

and opportunistically have an if (input is List<T> list) { OverloadThatHandlesSpan(CollectionsMarshal.AsSpan(list)); } acceleration path, much as is done internally in LINQ or other functions today.

Sigh. Please read my opening post. Normally it would be OK just "as is done in LINQ or other functions today", except that OverloadThatHandlesSpan(Span<T>) cannot be called from a different thread. So no, I still have to go on with the OverloadJustForListBecauseNeitherArraySegmentNorMemoryIsAccessibleSoThereIsNoOtherWayToRecursivelyCallPerformantSortMethodFromAnotherThread(List<T>) implementations (though it has the somewhat shorter DoSort(List<T>, ...) name in my actual implementation).

#87210 #90141 #101914 #105179

This just highlights that such an API would make sense to a lot of developer. But never mind, I closed the issue as I can live with the code duplicates, I just would have liked to get rid of them if possible.

[tannergooding]

except that OverloadThatHandlesSpan(Span) cannot be called from a different thread

It can, you just have to move where the span is created.

Which is to say, you cannot do:

var span = CollectionsMarshal.AsSpan(list);

var thread = new Thead(() => {
    OverloadThatHandlesSpan(span);
});
thread.Start();

However, you can trivially do:

var thread = new Thread(() => {
    var span = CollectionsMarshal.AsSpan(list);
    OverloadThatHandlesSpan(span);
});
thread.Start();

You can likewise follow similar principles via Parallel.For (allowing dividing the list item handling across threads), tasks, or other considerations.

You don't need a specific void Sort(IAsyncContext context, List<T> list, int startIndex, int count, IComparer<T>? comparer); variant, because the existing void Sort(IAsyncContext context, IList<T> list, int startIndex, int count, IComparer<T>? comparer); works fine.

Realistically you just need 2 implementations, one that takes Span<T> and works on the thread itself already on. and one that operates on IList<T> which can do considerations like multithreading, specialization, and other considerations. Any other overloads (T[], List<T>, etc) are then optional and can defer to the other implementations, effectively just bypassing checks if you believe its common enough to warrant it but ultimately deferring to one of the two core implementations (which operates on the raw span or on a raw IList<T> of unknown type).

[koszeggy]

@tannergooding Thank you for your thoughts.

Realistically you just need 2 implementations [...]

Generally you are right about using just IList<T> and doing the special handling at the moment when I actually need to access the ranges (and that's how I started), but my performance tests results showed that doing this at such a bottom level has a significant overhead. So yes, the top-level API uses IList<T> only (and a couple of my special value-type collections), and I do the branching almost at root level for the best performance.

The List<T> branch doesn't use spans ATM but as my libraries target a wide range of platforms starting with .NET Framework 3.5, it will be just another special handling inside the list special handling just for .NET5+ targets.

I still will try a few approaches before releasing this version so nothing is final yet. Again, thank you for your last supportive answer.