Proposal: Modern IEnumerable<T> abstraction

[dmitriyse]

Motivation

Current IEnumerable<T> abstraction have couple of performance issues:

1. Minimum 4 Virtual Method calls per enumeration:
   • GetEnumerator
   • MoveNext()
   • Current // getter
   • Dispose
2. Two Virtual Method calls per item
3. No any batch processing

Also this abstraction is derived from legacy IEnumerable (pre-generics era of C#) that have very rare usage.

Proposal

    public interface IEnumerable2<out T>
    {
        /// <summary>
        /// Starts the enumeration.
        /// </summary>
        /// <returns>
        /// Returns null if all items have enumerated, or enumerator.
        /// </returns>
        IEnumerator2<T> StartEnumeration(
            Span<T> buf, // Error CS1961. Currently it's impossible, but later covariance can be improved in C#.
                         // Probably WriteOnlySpan should be introduced. Also this buffers can be allocated on the stack.
            out int count, // Amount of actually enumerated items.
            out bool isCompleted // true if all items have enumerated.
            );
    }

    public interface IEnumerator2<out T>: IDisposable
    {
        /// <summary>
        /// Continues the enumeration.
        /// </summary>
        /// <returns>
        /// Amount of actually enumerated items.
        /// </returns>
        int GetNext(
            Span<T> buf, // Error CS1961. Currently it's impossible, but later covariance can be improved in C#.
                         // Probably WriteOnlySpan should be introduced. Also this buffers can be allocated on the stack.
            out bool isCompleted // true if all items have enumerated.
            );
    }

    /// <summary>
    /// Usage example.
    /// </summary>
    public static class Test
    {
        public static void Tst(IEnumerable2<string> strings)
        {
            Span<string> buf = stackalloc string[3];
            var enumerator = strings.StartEnumeration(buf, out var receivedCount, out var isCompleted);
            while (true)
            {
                for (int i = 0; i < receivedCount; i++)
                {
                    // TODO: Work with item.
                    Console.WriteLine(buf[i]);
                }

                if (isCompleted)
                {
                    break;
                }

                receivedCount = enumerator.GetNext(buf, out isCompleted);
            }
        }
    }

IEnumerable2<T> provides the next improvements over current IEnumerable<T>:

1. GetEnumerator and first item enumeration in one method. So if you have zero or few items in the collection it would be only one virtual call per enumeration.
2. No more than one virtual call per item (the same approach like in Proposal: Improving IEnumerable Performance #1931)
3. Zero allocation batch processing

Other related questions:

Probably it's possible join in a single abstraction: 1) Enumeration and 2) Sync/Async channel reader.

[HaloFour]

The design seems a lot more complicated and significantly more limited compared to what you can do with enumerators today. Basing it on Span<T> forces the underlying enumerable to fit a very specific design, one that very few enumerables fit today. If this can only work with strings, arrays and buffers what would the point be? It'd be impossible to base iterators on it, given both the Span<T> requirement and the out parameters for StartEnumeration. And you also completely lose variance, which is something that the CLR enforces, not C#, and that shouldn't be relaxed because it couldn't be done safely and you'd end up with the mistake of array variance that .NET inherited from Java.

[dmitriyse]

I have updated the topic with usag example.

1. Span should be allocated in consumer code and passed to IEnumerable2 as "write-only".
2. Span buffer passed to IEnumerable2 in "Write-Only" mode is logically "out" parameter and logically covariant. But yes it's currently impossible in C# and CLR. This proposal is another one motivation to investigate to covariance restrictions relaxation (Add support for covariance for methods with array-like output #2055).
3. Stack allocation of Span where T is managed object is currently not possible, but it's will be changed after some time (https://github.com/dotnet/coreclr/issues/20253)
4. It should works with any sources not only strings arrays and buffers

[HaloFour]

@dmitriyse

Span should be allocated in consumer code and passed to IEnumerable2 as "write-only".

The concept of "write-only" doesn't exist in .NET.

Span buffer passed to IEnumerable2 in "Write-Only" mode is logically "out" parameter and logically covariant. But yes it's currently impossible in C# and CLR. This proposal is another one motivation to investigate to covariance restrictions relaxation

out parameters are not covariant. They're ref parameters and the caller/callee must agree on the underlying type otherwise you break type safety. Variance of pointers is an even worse idea than variance of arrays, which is considered a mistake in the CLR.

Stack allocation of Span where T is managed object is currently not possible, but it's will be changed after some time

Stack allocation of managed types is being explored by the CLR team, but as an optimization within the JIT. Managed languages won't be able to request this. It requires that the JIT can perform escape analysis on all of the code to which the instance will be passed, which is impossible to do at the compiler level.

You also have the problem of this pattern being entirely unsuitable for iterators due to the use of out parameters.

Requiring multiple CLR changes for a single language change which only seeks to duplicate existing functionality seems unlikely, at best. What's worse, your enumeration pattern requires a second enumeration over the span.

[dmitriyse]

I understand that right now nothing is ready for this pattern, but it's about performance (and it's a long-run target).
Everything is solvable, for this feature. We just need enough motivation.
Just an example:
Covariance for methods with out parameter can be enabled. But type safety can be controller only at C# level, not on CLR level.
This is a kind of difficulties but not a real limitation. It's relatively easy to allow covariance for method with out parameters.
CLR team can solve problems many times harder than this.

It's a matter of time to prove that many things are solvable.

It's better to say currently this feature requeres too many expensive changes.

[theunrepentantgeek]

it's about performance (and it's a long-run target).

I think you're dramatically over-estimating the cost of the existing abstractions.

At worst, the existing abstractions incur an overhead of a few nanoseconds per iteration. Modern processors are very efficient and the current JIT compilers are very good at making effective use of those processors.

If you had a really tight loop that was iterating over a million items, it's possible that the proposed abstractions would save a few milliseconds of execution time.

If the body of the loop is doing any non-trivial computation, any potential saving will be drowned in the statistical noise of measurement.

There are any number of other performance improving proposals (including the linked JIT stack allocation of objects) that will have a performance impact that's literally orders of magnitude greater.

Better algorithms always trump micro-optimizations.

[manofstick]

This might be of interest: dotnet/corefx#34208

[declard]

Abstractions usually come with a cost. In performance-critical parts implementations are used directly

[ZacharyPatten]

@declard
You can use structs as generic arguments to have negligible overhead iteration abstractions. It is a little different code than IEnumerable but it accomplishes the same thing more efficiently when possible. Just fyi

Examples: #2904