Support struct Enumerator for ConcurrentDictionary

[stephentoub]

ConcurrentDictionary enables enumerating the dictionary while other threads are modifying it, making it very useful in a variety of scenarios. But its GetEnumerator allocates an enumerator object. We can't change the return type of GetEnumerator, but we can at least expose an enumerator struct to enable enumeration without allocating.

Proposal:

namespace System.Collections.Concurrent
{
    public class ConcurrentDictionary<TKey, TValue>
    {
        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator(); // existing

        public struct Enumerator // new
        {
            public Enumerator(ConcurrentDictionary<TKey, TValue> dictionary);
            public bool MoveNext();
            public KeyValuePair<TKey, TValue> Current { get; }
        }
    }
}

Example usage:

private static ConcurrentDictionary<string, int> s_dict = new ConcurrentDictionary<string, int>();
...
var enumerator = new ConcurrentDictionary<string, int>.Enumerator(s_dict);
while (enumerator.MoveNext())
{
    Use(enumerator.Current);
}

[karelz]

@stephentoub is Future ok? Or do you think we should push it into 2.1?

[stephentoub]

Future is fine

[davidfowl]

Is this difficult to do? I'd love to measure our broadcast performance scenario with this. We currently filed this issue https://github.com/aspnet/SignalR/issues/1796 to try and work around allocating the enumerator per message (which we're currently doing).

[Joe4evr]

We can't change the return type of GetEnumerator, but we can at least expose an enumerator struct to enable enumeration without allocating.

Isn't the compiler (and/or JIT) already smart enough to emit direct calls for struct enumerators? 🤔

Unless you meant that changing from a class to a struct enumerator is a binary breaking change, in which case.... Would it be suitable to quirk instead?

I just wouldn't like have having to remember to use the more verbose syntax over the simplicity of foreach for one specific collection type to keep GC pressure down.

[stephentoub]

Is this difficult to do?

No, the iterator just needs to be rewritten manually.

Unless you meant that changing from a class to a struct enumerator is a binary breaking change

Correct. Changing the GetEnumerator signature is a breaking change.

Would it be suitable to quirk instead?

No, not for API signature changes.

[stephentoub]

Is this difficult to do?

@davidfowl, e.g. something like this:
stephentoub/corefx@d11bdcd

[terrajobst]

I'm not sure I like it because it seems heavy-handed and the consuming code cannot use foreach.

@jaredpar is there any way we could change the compiler rules for IEnumerable to prefer a struct-based enumerator when GetEnumerator() is already taken? I suspect we'll have this problem in other areas too. @bartonjs suggested that we could add another property/method that returns a struct that provides a struct-based GetEnumerator() method. Again, feels heavy-handed...

[jaredpar]

is there any way we could change the compiler rules for IEnumerable ...

No

This is one of the most used patterns in .NET. Changing the compiler rules for how we bind existing IEnumerable is a back compat issue.

[stephentoub]

This has probably been discussed before, but is there anything reasonable we could do in the runtime to make it a non-breaking change to change a signature from:

public IEnumerator<T> GetEnumerator() { ... }

to

public Enumerator GetEnumerator() { ... }

public struct Enumerator : IEnumerator<T> { ... }

such that code compiled against the former would "just work" with an implementation containing the latter? Then code compiled against the new signature would get the allocation benefit but code compiled against the older signature would still work.

cc: @jkotas

[jkotas]

You can have both Enumerator GetEnumerator() and IEnumerator<T> GetEnumerator() methods in the IL. It is just that you cannot do that in C# today. It is possible to hack it via IL rewriting, e.g. the implementation can contain both methods, but reference assembly just the new one. The problem with introducing such non-standard overload in the implementation is that it would break reflection or scripting scenarios.

The other possible approach is to wait for the JIT to get better and optimize out the allocation in the current less than ideal pattern for you.

[svick]

@jkotas

It is possible to hack it via IL rewriting, e.g. the implementation can contain both methods, but reference assembly just the new one.

Wouldn't that mean that if you upgrade to the newer reference assembly, code that does any kind of type inference will start behaving differently? E.g.:

var e = cdict.GetEnumerator(); // is the type of e Enumerator or IEnumerator<T>?

void F<T>(T x) {}
F(cdict.GetEnumerator()); // is the inferred T Enumerator or IEnumerator<T>?

I think that's an unacceptable breaking change.

[jkotas]

This is a general problem with introducing overloads. If the new overload has same behavior as the old one (ie it is unlikely to change the behavior of existing code silently), I believe it has been considered as an acceptable option. It has been treated on case by case.

[terrajobst]

Video

The options listed here are all somewhat unfortunate (that is, they suck for various reasons :-)).

One compromise would be to add a new method called GetEnumerator2() and change the compiler to support foreach-ing enumerators and code would like this:

var dict = new ConcurrentDictionary<string, int>();
// add stuff

foreach (var kv in dict.GetEnumerator2())
{
    Use(enumerator.Current);
}

The established patterns for struct-based alternative is ValueXxx, like ValueTuple or ValueTask but in this case value might be a bad idea due to the generic parameter TValue.

@jaredpar, are you still supportive of this change to the compiler?
@stephentoub, are you OK with the resulting usage?

[svick]

@terrajobst How is that better than a method like GetStructEnumerable() that returns a struct whose GetEnumerator() returns the struct enumerator (which you called "heavy-handed" before)?

With GetStructEnumerable():

• You don't need to change the language (or the compiler).
• The usage stays the same as with GetEnumerator2 (you just change the name of the called method).
• The API surface does become larger, but if that's an issue, you could combine the enumerable and the enumerator into a single type.
• Performance should not be worse, since the additional call should be inlineable.

[jaredpar]

are you still supportive of this change to the compiler?

I'm personally comfortable with the idea of allowing foreach on IEnumerator<T>. It's a language change though hence has to go through LDM. Happy to represent the issue though.