[API Proposal]: Improve the performance of enumerating over interface types.

[geeknoid]

Background and motivation

Interface-based programming is encouraged as a best practice. Unfortunately, enumerating collections that are exposed through interface types triggers memory allocations and involves 2 interface calls per item iterated. In other words, enumerating an interface is slow:

List<int> l0 = new List<int>();
IList<int> l1 = new List<int>();

foreach (var x in l0)
{
    // speedy due to List<T>.Enumerator
}

foreach (var x in l1)
{
    // slow due to allocating an enumerator object, and making 2 interface calls
    // (IEnumerator<T>.MoveNext and IEnumerator<T>.Current) for each item
}

API Proposal

Please see https://github.com/geeknoid/AcceleratedEnumeration for a simple model that can deliver considerable perf benefits by avoiding allocations in many cases and cutting down the number of interface calls. The README file in that repo has perf numbers. The code I show provides benefits for most enumerations of IEnumerable, IList, IReadOnlyList, IDictionary, IReadOnlyDictionary, ISet, and IReadOnlySet.

The basic idea is to do something like:

foreach (var x in l.AcceleratedEnum())
{
}

The above works like normal enumeration, just faster. Although the model I show here requires explicit coding by the programmer to leverage, it would be conceivable to build similar tech directly into C# so that enumeration of interface types just gets faster by magic.

Note that my implementation also handles null collections, which is a nice simplification for the developer. You don't need to do an if check before you enumerate.

API Usage

foreach (var x in l.AcceleratedEnum())
{
}

Alternative Designs

As I mentioned above, you can imagine building this ugly stuff straight into the C# compiler. In fact, putting this into the compiler can likely deliver perf benefits by using byref semantics for the enumerator structs, which would avoid copying overhead. This is not possible right now since the C# compiler doesn't know how to deal with enumerators by reference.

Risks

The design intentionally avoids extra error checks, so edge cases will throw different exceptions than in the non-accelerated case. In particular, the implementation of IEnumerator.Current when there isn't anything in the collection throws different exceptions. That could be remedied at the cost of a few cycles.

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

[davidfowl]

@EgorBo @AndyAyersMS Would guarded devirt + DynamicPGO help here? Is that our best avenue?

[huoyaoyuan]

Note that in your AcceleratedEnumerationExtensions.List changed the semantic of enumeration. It saves a lot to not checking for modification during enumeration.

[EgorBo]

@davidfowl @geeknoid with DynamicPGO we devirtualize all calls here but are not able to avoid allocation (boxing) of an Enumerator (happens just once before the loop):

I suspect in order to also optimize that small allocation we need that @AndyAyersMS's idea to use escape analysis.

[geeknoid]

Note that getting rid of the allocation, especially when enumerating empty collections, was the motivation for trying out this idea .

[geeknoid]

Note that in your AcceleratedEnumerationExtensions.List changed the semantic of enumeration. It saves a lot to not checking for modification during enumeration.

@huoyaoyuan Good point, I forgot to bring that up. I've always felt it was an architecture misstep to put in the versioning logic in such low-level abstractions as List and Dictionary, so there's no love lost for me there. But it does change the semantics relative to plain ol' enumeration.

[EgorBo]

Note that getting rid of the allocation, especially when enumerating empty collections, was the motivation for trying out this idea .

well, it's a small allocation that doesn't happen every iteration of that foreach so I personally don't think it is worth any special API while it could be eventually fixed in jit instead.

[geeknoid]

I'm looking at this in the broader context of optimizing our service fleet. Small allocations done dozens or hundreds of times per request add up. We currently have ~300 uses of foreach throughout our code base, and we're just a set of libraries that services build on. So they'll add their own enumeration overhead on top.

I highly doubt this can be systematically addressed by the compiler. There are many cases where an interface is in fact polymorphic in nature and so it can devirtualize. Or the code can potentially be used in LINQ queries and so it has to remain general and allocate an IEnumerable, etc.

Enumeration is a very common pattern in code, dedicated optimizations to reduce the implicit overhead that enumeration induces is meaningful to the bottom line.

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

Issue Details

---

Background and motivation

Interface-based programming is encouraged as a best practice. Unfortunately, enumerating collections that are exposed through interface types triggers memory allocations and involves 2 interface calls per item iterated. In other words, enumerating an interface is slow:

List<int> l0 = new List<int>();
IList<int> l1 = new List<int>();

foreach (var x in l0)
{
    // speedy due to List<T>.Enumerator
}

foreach (var x in l1)
{
    // slow due to allocating an enumerator object, and making 2 interface calls
    // (IEnumerator<T>.MoveNext and IEnumerator<T>.Current) for each item
}

API Proposal

Please see https://github.com/geeknoid/AcceleratedEnumeration for a simple model that can deliver considerable perf benefits by avoiding allocations in many cases and cutting down the number of interface calls. The README file in that repo has perf numbers. The code I show provides benefits for most enumerations of IEnumerable, IList, IReadOnlyList, IDictionary, IReadOnlyDictionary, ISet, and IReadOnlySet.

The basic idea is to do something like:

foreach (var x in l.AcceleratedEnum())
{
}

The above works like normal enumeration, just faster. Although the model I show here requires explicit coding by the programmer to leverage, it would be conceivable to build similar tech directly into C# so that enumeration of interface types just gets faster by magic.

Note that my implementation also handles null collections, which is a nice simplification for the developer. You don't need to do an if check before you enumerate.

API Usage

foreach (var x in l.AcceleratedEnum())
{
}

Alternative Designs

As I mentioned above, you can imagine building this ugly stuff straight into the C# compiler. In fact, putting this into the compiler can likely deliver perf benefits by using byref semantics for the enumerator structs, which would avoid copying overhead. This is not possible right now since the C# compiler doesn't know how to deal with enumerators by reference.

Risks

The design intentionally avoids extra error checks, so edge cases will throw different exceptions than in the non-accelerated case. In particular, the implementation of IEnumerator.Current when there isn't anything in the collection throws different exceptions. That could be remedied at the cost of a few cycles.

Author:	geeknoid
Assignees:	-
Labels:	api-suggestion, area-System.Runtime, untriaged
Milestone:	-

[AndyAyersMS]

As @EgorBo says above, using PGO to de-abstract things like this is a long-term goal. Not clear how much progress we'll make on this in the next release, as we are still working through .net 7 plans.

@geeknoid if you have realistic polymorphic examples in mind, it would be nice to add those to your perf suite so we can see how well some new ideas we have in mind for PGO might cope.

[geeknoid]

@AndyAyersMS I've got a few examples already in my benchmark. I have IEnumerable implemented on top of different concrete types, or IList implemented on top of different concrete types. If you then write code such as:

void DoSomething(IEnumerable<T> x)
{
}

DoSomething can be called with different implementations of IEnumerable. Now you're already generating different code for different instances of T, so conceivably you could generate different code for different concrete types implementing IEnumerable too. But I suspect a lot of this analysis will peter out at some point and leave you with persistent allocations and some interface based dispatch.

[davidfowl]

FWIW We have LOTS of examples of this in ASP.NET and in dotnet/runtime. I made a set of changes in .NET 6 to remove IEnumerable.GetEnumerator allocations when the backing collection as a T[] (which is always is when using dependency injection). ASP.NET Core uses abstract IList, IReadOnlyList and IEnumerable ALOT. Recently we've been taking advantage of CollectionMarshal.AsSpan to remove enumerator allocations and speed up enumeration over Lists

well, it's a small allocation that doesn't happen every iteration of that foreach so I personally don't think it is worth any special API while it could be eventually fixed in jit instead.

Its worth optimizing it if we can.

@davidfowl @geeknoid with DynamicPGO we devirtualize all calls here but are not able to avoid allocation (boxing) of an Enumerator (happens just once before the loop):

@EgorBo can you explain why that is? I don't quite understand the connection.