Improve Enumerable.SingleOrDefault(predicate) Logic

[Petermarcu]

@seanfisher commented on Sun Nov 05 2017

Improve Enumerable.SingleOrDefault logic

This improves performance for the case where more than one element is found that matches the predicate, especially in large data sets.

General

Hi, I ran across the reference source for Enumerable.cs and was surprised to see an improvement opportunity. I was about to open an issue over there but then read a closed issue where they recommended opening new issues over here instead.

In the current reference source it appears that there is needless looping over the entire enumerable even if the count of elements that match the predicate is greater than one. Here's a quick one-liner example of a short-circuit exit improvement (notice the added line right after checked { count++; }), although I'm sure it could be improved even further:

public static TSource SingleOrDefault<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    if (source == null) throw Error.ArgumentNull("source");
    if (predicate == null) throw Error.ArgumentNull("predicate");
    TSource result = default(TSource);
    long count = 0;
    foreach (TSource element in source)
    {
        if (predicate(element))
        {
            result = element;
            checked { count++; }
            if (count == 2) { break; }
        }
    }
    switch (count)
    {
        case 0: return default(TSource);
        case 1: return result;
    }
    throw Error.MoreThanOneMatch();
}

Let me know if this is the appropriate place for this issue. It could also be that the reference source doesn't reflect exactly what the implementation is doing, because I would expect something like the Enumerable methods would have long-since been hand-tuned for performance.

---

@benaadams commented on Sun Nov 05 2017

It seems to be fixed in corefx?
https://github.com/dotnet/corefx/blob/master/src/System.Linq/src/System/Linq/Single.cs

However, for a performance improvement, you should be able to just open and Issue in the repository that has the source or open a PR change.

Although what reference source shows is the code for full framework/desktop so it could probably still do with this change (or to pick up corefx's Linq code)

---

@Petermarcu commented on Mon Nov 06 2017

I'm going to move this issue to corefx. The outcome here is probably to add a ref count to get this on the list of things to consider porting to .NET Framework.

[Petermarcu]

@AlexGhiondea can you track down which issue or PR we should mark for consideration for porting to .NET Framework to address this?

[JonHanna]

This was done in dotnet/corefx#2350 which is already marked netfx-port-consider.

Some moving around having happened since, the current code can be found https://github.com/dotnet/corefx/blob/master/src/System.Linq/src/System/Linq/Single.cs#L132

[JonHanna]

Incidentally, all of the changes in that PR have observable differences beyond just performance, in that the change to whether the entire sequence is examined or not could be potentially breaking if someone depended on side-effects in predicates or other delegates earlier in the chain (which is poor practice, but that is far from meaning nobody did so), which is why that PR was split off from some other performance improvements. It was decided to take the potential break in corefx (which I was glad of) but it should probably be considered anew when it comes to porting (I for one would be saying I'm a customer who would like to see that change in netfx, fwiw).

[karelz]

Our breaking change bar is much higher on .NET Framework. In general the value has to outweight the risk of breaking application(s). It takes just one broken popular applications to make many customers very unhappy.

[karelz]

I marked it for considering (netfx-port-consider). Now we can close it here as it does not apply to CoreFX anymore.