Which is faster: Single(predicate) or Where(predicate).Single()

Question

Discussion resulting from this answer has me curious. Which is faster:

someEnumerable.Single(predicate);

or

someEnumerable.Where(predicate).Single();

After all, the first is shorter, more concise, and seems to be purpose-built.

Even ReSharper suggests the former:

I was arguing in the previous post, that they are functionally identical, and should have very similar runtime.

Answer 1

Where(predicate).Single() would be faster than Single(predicate)

Edit: You would expect Single() and Single(predicate) to be coded in similar ways, but that is not the case. Single() finishes as soon as another element is found, but the latter finds all the satisfying elements.

Additional point of interest (original answer) - Where does special optimizations for different kind of collection types, whereas other methods like First, Single and Count do not take advantage of the type of the collection.

So Where(predicate).Single() is able to do some optimizations that Single(predicate) doesn't

Answer 2

There's a design flaw in the Linq-for-objects Single that means:

1. It's pointlessly keeping a tally of the number of matches, rather than finding a match and then throwing if it finds another.
2. It keeps going until it reaches the end of the sequence, even after a third match.
3. It can throw OverflowException; it's unlikely to, but that it can at all is a bug none the less.

https://connect.microsoft.com/VisualStudio/feedback/details/810457/public-static-tsource-single-tsource-this-ienumerable-tsource-source-func-tsource-bool-predicate-doesnt-throw-immediately-on-second-matching-result#

This makes it slightly slower in the case of 0 or 1 match (only the second being the non-error case, of course), and much slower in the case of more than 1 match (the error case).

With other Linq providers, it depends; it tends to be about the same, but it is perfectly possible for a given provider to be less efficient with one or the other and another given provider to be the opposite.

[Edit: This is no longer the case with .NET Core, in which the above description no longer applies. This makes the single call to .Single(pred) very slightly more efficient than .Where(pred).Single().]

Answer 3

I think this is a case of apples vs. oranges.

We have to think how the current implementation of Single(predicate) differs from the following implementation:

public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    return Where(source, predicate).Single();
}

The implementation of Where returns an Enumerable.Iterator that looks like it recognizes the race condition that occurs when MoveNext is called on the same iterator in different threads.

From ILSpy:

switch (this.state)
{
case 1:
    this.enumerator = this.source.GetEnumerator();
    this.state = 2;
    break;
case 2:
    break;
default:
    return false;
}

The current implementation of Single(predicate) and First(predicate) don't handle this condition.

I'm struggling to think of what this means in a real-world scenario, but I'm guessing that the "bug" hasn't been fixed because behavior would be altered in certain multi-threaded scenarios.

Answer 4

Based on the actual implementation for Where(predicate).Single() and Single(predicate), it seems the former actually is lazy, whereas the latter always iterates over the entire IEnumerable. Single() both returns the only element of the enumeration but also tests whether the enumeration has none or has more than one value, which can be achieve simply by asking the next 2 elements of the enumeration at most. Single(predicate) is currently implemented in a way that it needs to iterate over the entire enumeration to confirm whether the predicate is true for one and only one element, thus the performance (and functional, see below) difference.

Although they seem functionally identical, there are cases where not only the performance, but actual functionality are quite different, i.e. infinite enumerations,

public IEnumerable<int> InfiniteEnumeration()
{
    while (true)
    {
        yield return 1;
    }
}

If you run this function using both methods, one will complete correctly; the other one... we might have to wait.

var singleUsingWhere = InfiniteEnumeration().Where(value => value != 0).Single();
var singleUsingSingle = InfiniteEnumeration().Single(value => value != 0);

It is strange Microsoft decided to implement Single(predicate) this way... even Jon Skeet managed to fixed that oversight.

Answer 5

LINQ-to-Objects

Nothing answers a question like this like a benchmark:

(Updated)

class Program
{
    const int N = 10000;
    volatile private static int s_val;

    static void DoTest(IEnumerable<int> data, int[] selectors) {
        Stopwatch s;

        // Using .Single(predicate)
        s = Stopwatch.StartNew();
        foreach (var t in selectors) {
            s_val = data.Single(x => x == t);
        }
        s.Stop();
        Console.WriteLine("   {0} calls to Single(predicate) took {1} ms.",
            selectors.Length, s.ElapsedMilliseconds);

        // Using .Where(predicate).Single()
        s = Stopwatch.StartNew();
        foreach (int t in selectors) {
            s_val = data.Where(x => x == t).Single();
        }
        s.Stop();
        Console.WriteLine("   {0} calls to Where(predicate).Single() took {1} ms.",
            selectors.Length, s.ElapsedMilliseconds);
    }


    public static void Main(string[] args) {
        var R = new Random();
        var selectors = Enumerable.Range(0, N).Select(_ => R.Next(0, N)).ToArray();

        Console.WriteLine("Using IEnumerable<int>  (Enumerable.Range())");
        DoTest(Enumerable.Range(0, 10 * N), selectors);

        Console.WriteLine("Using int[]");
        DoTest(Enumerable.Range(0, 10*N).ToArray(), selectors);

        Console.WriteLine("Using List<int>");
        DoTest(Enumerable.Range(0, 10 * N).ToList(), selectors);

        Console.ReadKey();
    }
}

Somewhat shockingly, .Where(predicate).Single() wins by a factor of about two. I even ran both cases twice to make sure caching, etc. was not a factor.

1) 10000 calls to Single(predicate) took 7938 ms.
1) 10000 calls to Where(predicate).Single() took 3795 ms.
2) 10000 calls to Single(predicate) took 8132 ms.
2) 10000 calls to Where(predicate).Single() took 4318 ms.

Updated Results:

Using IEnumerable<int>  (Enumerable.Range())
   10000 calls to Single(predicate) took 7838 ms.
   10000 calls to Where(predicate).Single() took 8104 ms.
Using int[]
   10000 calls to Single(predicate) took 8859 ms.
   10000 calls to Where(predicate).Single() took 2970 ms.
Using List<int>
   10000 calls to Single(predicate) took 9523 ms.
   10000 calls to Where(predicate).Single() took 3781 ms.