Linq loops could be tighter; causes bug in one obscure case, waste in others.

[JonHanna]

Several looping constructs in the Enumerable class repeatedly set and/or test flags and counts for state changes that are only one-way. I first noticed this as a problem with .NET 3.5 when a bug in my code caused a sequence to repeat incorrectly and a call to Single(Func<TSource, bool> predicate) hanged rather than throwing. It would also have eventually thrown the wrong exception, though it would have taken an infeasible length of time to get that far. The cause was that Single was finding matches, counting how many were found, and then afterwards throwing if that value wasn't 1 rather than finding a match and then verifying there wasn't another.

There are several other cases where loops branch within each loop unnecessarily set or test the same variables repeatedly. There are others where a state that is checked for where they could short-circuit. For example, Min on floating-point values checks for IsNaN because it has to do so to ensure a total ordering, but then continues to loop despite provably having found the minimum value. Adding a check to short-circuit on IsNaN would optimise for the case of a sequence having a NaN value at a cost to those which don't, but here the check is already being made so there is no cost to short-circuiting. Conversely, in Max once a value has been found that is not NaN the continual check of IsNaN is needless.

While the changes in most of these cases are minor, they are by their very nature hit repeatedly, being used in loops in a very heavily used part of the framework. As such, such minor performance improvements are likely to pay off across a wide range of applications.

[AdamSpeight2008]

@hackcraft Are you thinking on the lines of this for Single<T>.

   public static T Single<T>(this IEnumerable<T> source, Func<T,bool> pred )
{

    if (source == null) throw new ArgumentNullException ( nameof( source ) );
    if (pred == null) throw new ArgumentNullException ( nameof( pred ) );
    using( var en = source.GetEnumerator() )
    {
        if( !en.MoveNext() ) throw new Exception(); /* Empty Sequence */
lbl_A:
        if( !pred( en.Current ) )
        {
            if( en.MoveNext() ) goto lbl_A;
            throw new Exception(); /* End of Sequence and no match found */
        }
        /* Match Found */
        var value = en.Current;
lbl_B:
        if( en.MoveNext() )
        {
            if( pred( en.Current ) ) throw new Exception(); /* Another match found */
            goto lbl_B;
        }  
        return value;
    }
}

critics: "GoTo?"
me: "Whatever"

I think it would also be beneficial to see the implementations you are considering.

[JonHanna]

@AdamSpeight2008, it would be more like (forgive a lack of fluency with VB):

Public Shared Function [Single](Of TSource)(source As IEnumerable(Of TSource), predicate As Func(Of TSource, Boolean)) As TSource
  If source Is Nothing Then
    Throw [Error].ArgumentNull("source")
  End If
  If predicate Is Nothing Then
    Throw [Error].ArgumentNull("predicate")
  End If
  Using Dim enumerator As IEnumerator(Of TSource) = source.GetEnumerator()
    While enumerator.MoveNext()
      Dim result As TSource = enumerator.Current
      If predicate(current) Then
        Dim enumerator As IEnumerator(Of TSource)
        While enumerator.MoveNext()
          If predicate(enumerator.Current) Then
            Throw [Error].MoreThanOneMatch()
          End If
        End While
        Return result
      End If
    End While
  End Using
  Throw [Error].NoMatch()
End Function

See the pull request for more.

[AdamSpeight2008]

@hackcraft I rewrote it in C#

[JonHanna]

@AdamSpeight2008 well in C# it would be as per the PR.

[AdamSpeight2008]

@hackcraft My implementation does have the nested loops of yours.

[AdamSpeight2008]

This is the IL produce by my implementation.

    .method public hidebysig static 
        !!T Single<T> (
            class [mscorlib]System.Collections.Generic.IEnumerable`1<!!T> source,
            class [mscorlib]System.Func`2<!!T, bool> pred
        ) cil managed 
    {
        .custom instance void [mscorlib]System.Runtime.CompilerServices.ExtensionAttribute::.ctor() = (
            01 00 00 00
        )
        // Method begins at RVA 0x2050
        // Code size 128 (0x80)
        .maxstack 2
        .locals init (
            [0] class [mscorlib]System.Collections.Generic.IEnumerator`1<!!T>,
            [1] !!T,
            [2] !!T
        )

        IL_0000: ldarg.0
        IL_0001: brtrue.s IL_000e
        IL_0003: ldstr "source"
        IL_0008: newobj instance void [mscorlib]System.ArgumentNullException::.ctor(string)
        IL_000d: throw
        IL_000e: ldarg.1
        IL_000f: brtrue.s IL_001c
        IL_0011: ldstr "pred"
        IL_0016: newobj instance void [mscorlib]System.ArgumentNullException::.ctor(string)
        IL_001b: throw
        IL_001c: ldarg.0
        IL_001d: callvirt instance class [mscorlib]System.Collections.Generic.IEnumerator`1<!0> class [mscorlib]System.Collections.Generic.IEnumerable`1<!!T>::GetEnumerator()
        IL_0022: stloc.0
        IL_0023: ldloc.0
        IL_0024: callvirt instance bool [mscorlib]System.Collections.IEnumerator::MoveNext()
        IL_0029: brtrue.s IL_0031
        IL_002b: newobj instance void [mscorlib]System.Exception::.ctor()
        IL_0030: throw
        IL_0031: ldarg.1
        IL_0032: ldloc.0
        IL_0033: callvirt instance !0 class [mscorlib]System.Collections.Generic.IEnumerator`1<!!T>::get_Current()
        IL_0038: callvirt instance !1 class [mscorlib]System.Func`2<!!T, bool>::Invoke(!0)
        IL_003d: brtrue.s IL_004d
        IL_003f: ldloc.0
        IL_0040: callvirt instance bool [mscorlib]System.Collections.IEnumerator::MoveNext()
        IL_0045: brtrue.s IL_0031
        IL_0047: newobj instance void [mscorlib]System.Exception::.ctor()
        IL_004c: throw
        IL_004d: ldloc.0
        IL_004e: callvirt instance !0 class [mscorlib]System.Collections.Generic.IEnumerator`1<!!T>::get_Current()
        IL_0053: stloc.1
        IL_0054: ldloc.0
        IL_0055: callvirt instance bool [mscorlib]System.Collections.IEnumerator::MoveNext()
        IL_005a: brfalse.s IL_0070
        IL_005c: ldarg.1
        IL_005d: ldloc.0
        IL_005e: callvirt instance !0 class [mscorlib]System.Collections.Generic.IEnumerator`1<!!T>::get_Current()
        IL_0063: callvirt instance !1 class [mscorlib]System.Func`2<!!T, bool>::Invoke(!0)
        IL_0068: brfalse.s IL_0054
        IL_006a: newobj instance void [mscorlib]System.Exception::.ctor()
        IL_006f: throw
        IL_0070: ldloc.1
        IL_0071: stloc.2
        IL_0072: leave.s IL_007e
        IL_0074: ldloc.0
        IL_0075: brfalse.s IL_007d
        IL_0077: ldloc.0
        IL_0078: callvirt instance void [mscorlib]System.IDisposable::Dispose()
        IL_007d: endfinally
        IL_007e: ldloc.2
        IL_007f: ret

        Try IL_0023-IL_0074 Finally IL_0074-IL_007e
    } // end of method C::Single

[JonHanna]

Mine doesn't have a truly nested loop; once it enters the inner loop, it will never go through the outer loop again. Refactor yours to take out the needless empty-sequence check (empty sequence will naturally hit on the same path as no matches anyway) and to avoid goto (I'm not fanatic about avoiding goto but if there's a logically equivalent alternative I'll go with it) and you have the same as mine.

[AdamSpeight2008]

SingleOrDefault<T>
Why isn't this written in terms of Single<T>?

public static T SingleOrDefault<T>(this IEnumerable<T> source, Func<T,bool> pred )
{

    if ( source == null ) throw new ArgumentNullException(nameof(source));
    if (   pred == null ) throw new ArgumentNullException(nameof(pred));
    try
    {
      return Single<T>(source, pred );
    }
    catch( Exception e)
    {
     return default(T);
    }
}

[leppie]

@AdamSpeight2008 : Unlike the JVM, caught exceptions are not cheap on the CLR. Also it would annoy me and many other people seeing a first-chance exception every time something is not found. Also, a specific exception need to be caught. What happens when some legit exception is thrown (network or say file system or even a null reference in the predicate)? Just silently swallow it?

[JonHanna]

Worse. What if an enumerable is backed on something that throws InvalidOperationException? The exception would have to be examined in yet further detail. Not impossible (have an internal type derived from IOE and test for it specifically) but even then there are possible hang-ups; what if an enumerable internally calls Single() on another enumerable).