[API Proposal]: Inlined enumerators

[ShadedBlink]

Background and motivation

Today all enumerators have to follow given preset:

class Enumerator<T> {
    bool MoveNext();
    T Current { get; }
}

It works and etc, but it requires to store current value between MoveNext() and Current calls. In case when we iterate over collection using foreach, it results in double storage: one instance in enumerator, another one in immutable variable of foreach. Both variables are equal and are immutable during single iteration.

API Proposal

I believe we can remove the need for intermediate store of the Current value in enumerator's body.

// Direct implementation
class InlineEnumerator<T> {
    bool MoveNext(out T current);
}

interface IInlineEnumerable<T> : IEnumerable<T> {
    IInlineEnumerator<T> GetEnumerator();
}

//Interface implementation, NO MUTUAL INHERITANCE WITH IEnumerator<T>
interface IInlineEnumerator<T> {
    bool MoveNext(out T current);
}

In such case current value is directly written to consumer's variable without the need to store the intermediate value.
Here are my benchmarks on net10.0 for iterable struct of 32 bytes:

Enumerator type	AggressiveInlinining	NoInlining
struct	no noticeable diff	x2-2.5 faster
class	x2 faster	x2.5-3 faster

When it comes to iterable struct of size 64K, InlineEnumerator has almost no performance drop, while normal enumerator suffers a heavy(~99%) performance loss.

API Usage

In case of foreach C# compiler should first check if enumerator has public bool MoveNext(out T current) method or implements IInlineEnumerator<T>. In such case foreach should compile using given method.

struct TestCollection {
    public TestCollection GetEnumerator() => this;

    public bool MoveNext(out object current);
}
void TestMethod(TestCollection arr) {
    foreach (var x in arr) {
        ...
    }
}
// Compiles as
void TestMethod(TestCollection arr) {
    var enumerator = arr.GetEnumerator();
    while (enumerator.MoveNext(out var current)) {
        ...
    }
}

In case of manual iteration(get enumerator then while(MoveNext)), users may check whether inbound IEnumerable<T> is IInlineEnumerable<T> and then use inlined iteration, but they are not obliged to.
Implementation of IInlineEnumerable<T> is optional. It is responsibility of collection's author to get old and new enumeration along.

Alternative Designs

No response

Risks

Existing code should not be affected by these changes unless any enumerator already exposes MoveNext(out ...), however if user already defined it, then it most likely already used via while instead of foreach, I see no other reason for such method to exist on enumerator otherwise.
Thus only remaining risk is desyncing logic among old and inlined enumerator logic.

[dotnet-policy-service]

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

[MihuBot]

I'm a bot. Here are possible duplicate issues (I may be wrong):

• Proposal : IEnumerable iteration performance enhancement csharplang#3138
• Proposal: Improving IEnumerable Performance csharplang#1931
• ValueEnumerator (fast to code and run) csharplang#982

[dotnet-policy-service]

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

[ShadedBlink]

For duplicates:

• Proposal: Improving IEnumerable Performance csharplang#1931 - out of question, their signature returns a value byval, while mine directly writes value to the target address bypassing stack.
• ValueEnumerator (fast to code and run) csharplang#982 - same thing.
• Proposal : IEnumerable iteration performance enhancement csharplang#3138 - as I see it, covariance matter in my proposal is insufficient, since IInlineEnumerator applies only to current code, it is not a part of a contract. If method expects a collection to iterate over, it should declare IEnumerable<T> arg and then decide on how to iterate over it undercover, i.e. check whether arg is IInlineEnumerable<T>. Thus we don't care whether T is covariant or not, since it is responsibility of IEnumerable<T>.

For the iteration when Current is unread, we can just skip it either by using out _ or by fallback to traditional IEnumerator. In my opinion out _ is preferable.

[teo-tsirpanis]

it requires to store current value between MoveNext() and Current calls.

It is possible for implementations to create the current value on the fly when the Currentproperty gets accessed. This is what happens in cases likeList<T>.Enumerator. Doing this in some other cases though would lead to worse performance, like in Enumerable.Select, which would call the delegate every time Current is accessed.

Given that, I'm not sure that the benefits of adding this foundational API would outweigh the significant cost of propagating it through the ecosystem.

[ShadedBlink]

@teo-tsirpanis as it is already mentioned, IInlineEnumerable is an optional feature that marks that enumerable is worth inlining. It is up to outer code to decide on which approach is more applicable. For your case with .Select() with unread Current like in .Select().Count() the .Count() method just should never use the IInlineEnumerable implementation and fallback to old IEnumerable instead. It will use old enumerator with no performance toil in comparison to current behaviour. Meanwhile .Where() always needs a Current value(it takes it as well in current approach), so it should always use IInlineEnumerable - no need to store Current in enumerator since we have to use it right now.
I think I understood the main point on how to decide which enumerator to use: if you definitely read Current in your code, then IInlineEnumerator is your choice - even if you call MoveNext(), you are guaranteed to use a Current anyway, so it is safe to create value right now. Otherwise you should use IEnumerator, since instantiating Current may lead to excessive computation.

IInlineEnumerable is a very agile approach due to the fact that each IInlineEnumerable is IEnumerable in the first place - you are not forced to inline it, you just have an ability to. For example, foreach should always use IInlineEnumerable approach when present(unless iteration variable is unread) since value is always instantiated. Meanwhile extension methods like in System.Linq may decide this themself.

[AndyAyersMS]

Can you share your benchmarking setup?

[ShadedBlink]

My setup is mostly for reference. Polish it and check it yourself to get more accurate results.

Config:

//#define newenumerator
//#define class
//#define inline
//#define smallsize64
//#define smallsize128
//#define ultrasize

Type definitions:

	public struct IteratorCurrent {
		public long dummy1;
		public long dummy2;
		public long dummy3;
		public long I;
#if smallsize64
		public unsafe fixed byte dummy[(1 << 6) - 32];
#elif smallsize128
		public unsafe fixed byte dummy[(1 << 7) - 32];
#elif ultrasize
		public unsafe fixed byte dummy[1 << 16];
#endif
	}

#if class
	public class Iterator {
#else
	public struct Iterator {
#endif
		private int i;
		public Iterator GetEnumerator() => this;

#if newenumerator
#if inline
		[MethodImpl(MethodImplOptions.AggressiveInlining)]
#else
		[MethodImpl(MethodImplOptions.NoInlining)]
#endif
		public bool MoveNext(out IteratorCurrent current) {
			if (i++ < 10) {
				current = new() { dummy1 = ~i, dummy2 = 1 << i, dummy3 = 2 << i, I = i };
				return true;
			}
			Unsafe.SkipInit(out current);
			return false;
		}
#else
		private IteratorCurrent current;

#if inline
		[MethodImpl(MethodImplOptions.AggressiveInlining)]
#else
		[MethodImpl(MethodImplOptions.NoInlining)]
#endif
		public bool MoveNext() {
			if (i++ < 10) {
				current = new() { dummy1 = ~i, dummy2 = 1 << i, dummy3 = 2 << i, I = i };
				return true;
			}
			Unsafe.SkipInit(out current);
			return false;
		}

		public IteratorCurrent Current {
#if inline
			[MethodImpl(MethodImplOptions.AggressiveInlining)]
#else
			[MethodImpl(MethodImplOptions.NoInlining)]
#endif
			get => current;
		}
#endif
	}

Benchmark code:

						var iterator = new Iterator(); // New iterator instance for each test to check GC affection.
#if newenumerator
						while (iterator.MoveNext(out var l)) {
#else
						foreach (var l in iterator) {
#endif
							// Multiple calls to variable to ensure variable allocation.
							ii56 += l.I;
							ii57 += Math.Max(l.I, l.dummy1);
						}

[huoyaoyuan]

The interface-based design doesn't seem related to "inline". The core challenge of IEnuemerable<T> is the two-level virtual dispatch for IEnumerable<T> and IEnumerator<T>.

[ShadedBlink]

@huoyaoyuan you confuse it with method inlining. The idea of IInlineEnumerable is that IInlineEnumerator doesn't contain Current value in itself, so you can't obtain it twice. For example, you can check Enumerable.Select() method, it returns multiple different enumerator types, where every type contains a _current. It is meant to allow user to call Current multiple times without regeneration of Current value.
IInlineEnumerator removes Current from enumerator, no value is stored in enumerator, instead it is directly written to outer code in the variable specified in MoveNext(out T current). Thus we keep IInlineEnumerator lower in size and call one method less during iteration, which also saves us performance due to two-level dispatch in case of interfaces, where no method inlining is possible(see table in proposal on disabled inlining for performance difference).

@teo-tsirpanis , there is no on the fly value generation in embedded System.Linq.Enumerable.Select(). Every enumerator returned inherits Iterator<T> which declares a base T _current field. Also we won't degrade performance on double Current calls, since IInlineEnumerator<T> has no means to get Current again - you get it only once during MoveNext(), then it is up to you to store for subsequent read.