Provide IEnumerable<T> support for Memory<T>

[ahsonkhan]

Rationale

Users should be able to pass Memory<T> to methods that take in IEnumerable<T> similar to array. Currently, this requires calling ToArray() to copy the contents of the Memory<T> into an array for it to work, and is unnecessary.

For example (from @eerhardt): https://github.com/dotnet/corefxlab/blob/master/src/System.Numerics.Tensors/System/Numerics/DenseTensor.cs#L10

public void SomeMethod(DenseTensor<float> tensor)
{
   Memory<float> memory = tensor.Buffer;
   var value = CreateBatch<T>(..., memory.ToArray(), ...);
}

https://github.com/Microsoft/CNTK/blob/master/bindings/csharp/CNTKLibraryManagedDll/ShimApiClasses/ValueShim.cs#L104

public static Value CreateBatch<T>(NDShape sampleShape, IEnumerable<T> batch, DeviceDescriptor device, bool readOnly = false)
{
    T[] batchAsArray = batch.ToArray();
    return CreateBatch<T>(sampleShape, batchAsArray, 0, batchAsArray.Count(), device, readOnly);
}

If Memory<T> implemented IEnumerable<T>, then the ToArray() call would not be required. However, this would cause applications that reference System.Memory and Memory<T> for any scenario to be larger (when compiled AOT). Furthermore, if Memory<T> was an IEnumerable<T>, it might result in a pit of failure as it could lead to users unintentionally using the enumerator to iterate over the data rather than the more performant indexer on Memory.Span (especially for primitive types like Memory<byte>). To discourage unnecessary use of the enumerator but still provide support for the scenarios where you need an IEnumerable, the proposed solution is to add an adapter class and a ToEnumerable extension method on Memory<T>.

As an FYI, Span<T> cannot implement IEnumerable<T> since it is a stack-only, byref type, and casting it to an interface would cause boxing. The compiler will throw and error: 'Span<T>': ref structs cannot implement interfaces

Proposed API

namespace System
{
   public static class MemoryExtensions {
     public static IEnumerable<T> ToEnumerable(this Memory<T> memory);
   }
}

Usage

Taking the above example, it would look as follows:

public void SomeMethod(DenseTensor<float> tensor)
{
   Memory<float> memory = tensor.Buffer;
   var value = CreateBatch<T>(..., memory.ToEnumerable(), ...);
}

Partial Implementation

public static IEnumerable<T> ToEnumerable(this Memory<T> memory) => new MemoryEnumerable<T>(memory);

internal class MemoryEnumerable<T> : IEnumerable<T>
{
    ReadOnlyMemory<T> _memory;

    public MemoryEnumerable(ReadOnlyMemory<T> memory) => _memory = memory;

    public IEnumerator<T> GetEnumerator() => new MemoryEnumerator<T>(_memory);

    IEnumerator IEnumerable.GetEnumerator() => new MemoryEnumerator<T>(_memory);
}

internal class MemoryEnumerator<T> : IEnumerator<T>
{
    ReadOnlyMemory<T> _memory;
    int _index;

    public MemoryEnumerator(ReadOnlyMemory<T> memory) => _memory = memory;

    public T Current => _memory.Span[_index];

    object IEnumerator.Current => _memory.Span[_index];

    public void Dispose()
    {
        throw new NotImplementedException();
    }

    public bool MoveNext()
    {
        _index++;
        return _index <_memory.Length;
    }

    public void Reset()
    {
        _index = 0;
    }
}

cc @eerhardt, @KrzysztofCwalina, @stephentoub, @jkotas, @terrajobst, @karelz, @ericstj

[svick]

Would other collection interfaces make sense too? Like IReadOnlyList<T>?

[stephentoub]

might result in a pit of failure as it could lead to users unintentionally using the enumerator to iterate over the data

How is Memory any more susceptible than IEnumerable on other types like List and T[]?

[eerhardt]

Why can’t Memory{T} implement IEnumerable{T} directly? That way you wouldn’t need to call a method, nor alloc a throw away object.

[ahsonkhan]

How is Memory any more susceptible than IEnumerable on other types like List and T[]?

It is just as susceptible. The difference being we can change Memory<T>.

Why can’t Memory{T} implement IEnumerable{T} directly? That way you wouldn’t need to call a method, nor alloc a throw away object.

See Rationale section:

However, this would cause applications that reference System.Memory and Memory<T> for any scenario to be larger (when compiled AOT). Furthermore, if Memory<T> was an IEnumerable<T>, it might result in a pit of failure as it could lead to users unintentionally using the enumerator to iterate over the data rather than the more performant indexer on Memory.Span

[jkotas]

Why can’t Memory{T} implement IEnumerable{T} directly? That way you wouldn’t need to call a method, nor alloc a throw away object.

You always need to alloc a throw away object to get IEnumerable out of memory. If Memory implemented IEnumerable directly, casting to IEnumerable would box.

[eerhardt]

Oh right. I missed that Memory{T} is a struct.

[stephentoub]

Partial Implementation

This is an implementation detail, but we should use the same allocated object as both the enumerable and enumerator in the common case, as is done by the compiler with iterators and in LINQ... this could potentially even just be implemented with an iterator:

public static IEnumerable<T> ToEnumerable(this Memory<T> memory)
{
    for (int i = 0; i < memory.Length; i++) yield return memory.Span[i];
}

[stephentoub]

Span cannot implement IEnumerable since it is a stack-only, byref type, and casting it to an interface would cause boxing

Only tangentially related to this issue, have we considered giving Span an instance or extension GetEnumerator that returns a ref struct Enumerator? And/or have there been any discussions about enabling the compiler to support foreach'ing a span and generating optimal code for that? Just as I can foreach an array and end up with asm equivalent to walking through each element, it'd be nice to be able to do that with span as well, e.g.

foreach (T item in span)
{
    ...
}

being the same as:

for (int i = 0; i < span.Length; i++)
{
    T item = span[i];
    ...
}

EDIT: C# doesn't currently support extension GetEnumerators in foreach; either it would need to be an instance method, or the language would need to be updated to either special-case span or enable extension GetEnumerators.

cc: @VSadov, @MadsTorgersen

[KrzysztofCwalina]

Language support for foreach would be great.

[terrajobst]

Video

Looks good as proposed. MemoryExtensions doesn't exist yet but SpanExtensions will be renamed to it.

[stephentoub]

I opened https://github.com/dotnet/csharplang/issues/1085 for foreach support for Span<T> from the language side of things. We still need to decide if we want to add GetEnumerator instance method to Span<T> and ReadOnlySpan<T>.

[karelz]

FYI: The API review discussion was recorded - see https://youtu.be/HnKmLJcEM74?t=391 (13 min duration)

[KrzysztofCwalina]

@ahsonkhan, should we close this issue now? We added the enumerator.

[EDIT] Editing correct @ahsonkhan by @karelz

[stephentoub]

should we close this issue now? We added the enumerator.

We added one to span. I don't think we added one to memory.

[KrzysztofCwalina]

I assume the one added to Memory would be a by ref struct, i.e. it would cache the span? If yes, I think it's fine to add it. Otherwise I think it's a perf trap.

[stephentoub]

I would assume not, as you'd most likely want to use it with LINQ and other such consumers. And if you did want a byref one, you could instead enumerate .Span.

[VSadov]

We tried the same route with ImmutableArray - add an adapter class and ToEnumerable method (or was it AsList ? ) - we did not like boxing of ImmutableArray. Anyways people despised that so we ended up with IEnumerable anyways.

[ianhays]

Do we still want to add public static IEnumerable<T> ToEnumerable(this Memory<T> memory); even if we also add Memory<T>.GetEnumerator() a la https://github.com/dotnet/coreclr/pull/14922?

[benaadams]

Memory<T> isn't getting .GetEnumerator() and IEnumerable<T> ToEnumerable(this Memory<T> memory) is a performance hole provided for compat (as you can't put a span in a IEnumerator), so is an explicit call. (As far as I understand)

[ianhays]

Memory isn't getting .GetEnumerator() as you can't put a span in a IEnumerator

isn't that exactly what we're already doing right here (though as Enumerator, not IEnumerator)? Or did you mean that you can't put a Memory into the Enumerator (which makes sense because it's not by-ref)?

[stephentoub]

isn't that exactly what we're already doing right here

No, that's a ref struct, and it doesn't implement IEnumerator<T>, and that's for Span<T>, not Memory<T>. That's just implementing a pattern that's bindable to foreach by the C# compiler, no interfaces involved.

even if we also add Memory.GetEnumerator() a la dotnet/coreclr#14922?

We're not adding an IEnumerable<T> implementation to Memory<T>, as that likely ends up being more expensive than a ToEnumerable method. Consider a method that accepts an IEnumerable<T>. If Memory<T> (a struct) implemented IEnumerable<T>, passing the struct to that method would box it, resulting in an allocation; then when that method calls GetEnumerator and gets back an IEnumerator<T>, that'd be a second allocation. In contrast, with a ToEnumerable method, the IEnumerable<T> that's returned can also implement IEnumerator<T>, such that the instance you get back can be the sole allocation in the 99% case where the enumerable is enumerated once.

[ianhays]

Thanks @stephentoub, I've got some better context now. Your comments in The API Review video on this topic helped too :)

[ianhays]

There's pushback in dotnet/corefx#26284 about this being implemented as an extension method so I closed it so we can decide for sure what the API shape will look like and where the API should live (MemoryMarshal? Some new class?)

cc: @KrzysztofCwalina

[jhudsoncedaron]

Got here trying to pass a Memory<char> to .All() linq method. Maybe not the most brilliant way to go about it. Ended up inlining the whole thing.

[terrajobst]

Looks we didn't like the API we approved.

@GrabYourPitchforks, could take a look and make a proposal?

[joshudson]

I looked at the existing proposal and understand why it wasn't liked. I then called up the actual code of ReadOnlyMemory and studied the Span property.

In my opinion, the only reasonable implementation is to pin _object in memory via a fresh GCHandle and return a struct iterator from GetEnumerator() that implements IEnumerable via an actual pointer, and uses Dispose() to release the pin on _object. This results in no allocations and only one type ladder at loop startup, and only one allocation to pass it to a linq function. I suppose another implementation is possible that basically involves re-implementing the guts of Span but it's more dangerous than GCHandle.

Implementation shortcut: Memory<T>.GetEnumerator() => ((ReadOnlyMemory<T>this).GetEnumerator();

This is theoretically within my capacity to implement.

[joshudson]

So this is my API proposal.

partial class System.Memory<T>: IReadOnlyCollection<T> {
    public struct IReadOnlyMemory<T>.Enumerator GetEnumerator();
    int IReadOnlyCollection<T>.Count => Length;
    IEnumerator<T> IEnumerator<T> GetEnumerator() => GetEnumerator();
    IEnumerator IEnumerator.GetEnumerator() => GetEnumerator();
}

partial class System.Memory<T>: IReadOnlyCollection<T> {
    public struct Enumerator GetEnumerator();
    int IReadOnlyCollection<T>.Count => Length;
    IEnumerator<T> IEnumerator<T> GetEnumerator() => GetEnumerator();
    IEnumerator IEnumerator.GetEnumerator() => GetEnumerator();

    public struct Enumerator() : IEnumerable<T> {
        public bool MoveNext();
        public T Current { get ; }
        public void Reset();
    }
}

Rationale for IReadOnlyCollection<T>: It's just IEnumerable<T> + Count and it's a convenient flag interface for an enumerable that's not expected to change out from under the caller while the caller retains a reference to it. With this proposed implementation, it's about as good as an Array for being enumerated so there's no downside.

[stephentoub]

the only reasonable implementation is to pin _object in memory via a fresh GCHandle and return a struct iterator from GetEnumerator() that implements IEnumerable via an actual pointer, and uses Dispose() to release the pin on _object

GCHandles are relatively expensive, using one in a struct-based enumerator would make it too easy to accidentally not free one or double-free one, and you can't have pointers to arbitrary Ts (any T is possible in Memory<T>, not just unmanaged types).

If we want to add an enumerator for this, it'll simply access .Span[i] on each iteration. If we want to specialize the implementation for T[] in an attempt to optimize for a common case, that could be done as well, assuming performance data proved it out.

e.g. pseudo code with an iterator:

static IEnumerable<T> Iterate<T>(ReadOnlyMemory<T> memory)
{
    if (MemoryMarshal.TryGetArray(memory, out ArraySegment<T> segment))
    {
        T[] array = segment.Array;
        int end = segment.Offset + segment.Count;
        for (int i = segment.Offset; i < end; i++)
        {
            yield return array[i];
        }
    }
    else
    {
        for (int i = 0; i < memory.Length; i++)
        {
            yield return memory.Span[i];
        }
    }
}

[joshudson]

using one in a struct-based enumerator would make it too easy to accidentally not free one

In which case essentially all of the GCHandle sample code is really unsafe.

    var gc = GCHandle.Alloc(...);
    try {
        // Stuff here
    } finally {
        gc.Free();
    }

Is splittable in .NET Framework (.NET Core can't split it in any way I know). And most of the sample code doesn't even use finally blocks.

I had gotten part-way through the design of an enumerator that uses a string or an array (there's only 3 things it can be) before abandoning it. Maybe that's just better.

[stephentoub]

In which case essentially all of the GCHandle sample code is really unsafe

I don't understand the claim. The above as a pattern isn't unsafe (if by "splittable in .NET Framework" you mean because of thread aborts, then yes, the code would need to be changed to be reliable in the face of aborts, moving the Alloc call into the try and testing the state of gc in the finally block, but 99.999% of code isn't thread-abort-safe, and it's incredibly hard to make it such, which is why they no longer exist in core).

My point was that if you have a struct-based Enumerator whose ctor creates a GCHandle and whose Dispose frees the handle, then a) the consumer of the Enumerator may fail to call Dispose on the struct and now you have a leak, or b) the consumer of the Enumerator may make a copy of the struct and then Dispose each, and now you have a double-free of a GCHandle.

[joshudson]

Given the samples as they were, I was under the impression that GCHandle had to work by being found by the GC tracer. As I said, most of the samples don't have finally blocks so the GCHandles don't get freed on the inner code taking any exception.

[stephentoub]

most of the samples don't have finally blocks so the GCHandles don't get freed on the inner code taking any exception

Which samples?

[joshudson]

Starting from https://docs.microsoft.com/en-us/dotnet/api/system.runtime.interopservices.gchandle?view=netcore-3.1

[stephentoub]

Yes, that sample should be tweaked, at the very least to move the callback allocation to before the Alloc call.

[joshudson]

So what do you think of an implementation that looks like this? I started this path earlier and tossed when I thought of the pointer idea that's going to be more trouble than its worth.

struct Enumerator {
    private T[] srcArray;
    private string srcString;
    private Utf8String srcUtf8String;
    private int start; // For Reset()
    private int offset;
    private int stop;

    bool MoveNext() { if (offset == stop) return false; /* prevent overflow */ return (++offset != stop); }
    T Current => {
         if (srcArray is object) return srcArray[offset];
         if (srcString is object) return (T)srcString[offset]; /* T is char so cast should disappear at runtime */
         if (srcUtf8String is object) return (T)srcUtf8String[offset];
         throw new InvalidOperationException("...");
    }
}

If you're just going to enumerate by accessing the span and paying for the type ladder every time, I can do that in my own extension method.

[stephentoub]

So what do you think of an implementation that looks like this?

That logic effectively already exists (in a more optimized form) in the Span property. It'd be better to just keep things simple and use .Span[i] rather than trying to replicate the logic in Current.

[GrabYourPitchforks]

If the goal is to pass a ROM<T> to a LINQ method, any struct-based enumerator is going to end up being boxed anyway. I'd honestly rather implement a MemoryExtensions.ToEnumerable extension method which returns an IEnumerable<T>. The implementation of the IEnumerable<T> can be dynamically chosen based on what the ROM<T> is actually backed by: an array, a string, or something else. The method would be documented as "yup, this allocates the enumerator, but the scenario was that you're going to pass it to LINQ anyway, so... 🤷‍♀️."

public static class MemoryExtensions
{
    public static IEnumerable<T> ToEnumerable(this ReadOnlyMemory<T> memory);
}

[joshudson]

@GrabYourPitchforks : That's where we started at the top of the issue and the API team rejected it. So I acted on the reason that was found, that is it's a trap if you enumerate it directly.

[GrabYourPitchforks]

@joshudson Not quite. The implementation I suggested is different and should avoid the performance concerns. I suggested deconstructing the Memory<T> instance at the call to ToEnumerable(), which means that the deconstruction cost occurs upfront when the enumerator is created - not on each call to MoveNext. The public API would look identical to what has already been approved.

Things get complicated if you're backed by a MemoryManager<T> instead of a string or a T[], and enumerating an instance of that would still incur some overhead. But that shouldn't represent the majority case.

[AqlaSolutions]

Any news?

[terrajobst]

@GrabYourPitchforks are you driving this? If not, who should be?

[GrabYourPitchforks]

@terrajobst I'm not currently driving this because it seems to be low-priority. The salient point in this issue that people really reacted to was Steve's comment at https://github.com/dotnet/runtime/issues/23950#issuecomment-339383091, and we did indeed eventually get foreach support over Span<T> instances.

If the consensus is that we should add this API, I'm very much partial to my most recent comments starting at https://github.com/dotnet/runtime/issues/23950#issuecomment-721924499, as I think those largely address the performance trap that people were concerned with.

[terrajobst]

Sounds good.

[CodingMadness]

Hey guys,

so we can do: foreach on spans, and AFAIK .NET makes a promise to use Duck-Typing for such constructs, like GetPinnableReference() to be used in fixed(....) but why is the compiler not smart enough (.NET 6.0 ) to infer that Span is duck-typed to an IEnumerable without implementing it

Cause when an extension method takes a T, where T : IEnumerable>T>, it could use internal Duck-Typing to infer, the type actually does the same as it being an IEnumerable.

Would be really nice if .NET could make ducktyping a thing, i mean coding all these LINQ things will be quite ugly :D

[jkotas]

why is the compiler not smart enough (.NET 6.0 ) to infer that Span is duck-typed to an IEnumerable without implementing it

C# compiler does infer that in .NET 6. foreach works on Span for several years. More discussion on this is captured in https://github.com/dotnet/csharplang/blob/main/meetings/2017/LDM-2017-12-04.md#foreach-for-span-and-readonlyspan . The discussion on duck-typing is more appropriate for https://github.com/dotnet/csharplang repo.

[CodingMadness]

C# compiler does infer that in .NET 6. foreach works on Span for several years.

I already said that, good Sir, namely below: @jkotas

so we can do: foreach on spans

This is a good thing, its just, we cannot make use of the Enumerable-LINQ-Extension methods sadly, cause the Compiler still strictly wants the callee of these methods to be of type IEnumerable.

That is my Dilemma

[stephentoub]

cause the Compiler still strictly wants the callee of these methods to be of type IEnumerable.

The C# compiler couldn't fabricate a wrapper IEnumerable for the same reason Span doesn't implement IEnumerable: it's a ref struct that can't be boxed or otherwise copied to the heap.

[CodingMadness]

@stephentoub yea ok, wanted just to get sure on this! Thanks and have a good and healthy Week!

[Joe4evr]

@Shpendicus For what it's worth: SpanLinq

[CodingMadness]

@Joe4evr i think they are on a really good track, I also saw a nuget package called: NoAlloc maybe you can try that one aswell 🗡️