37

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:

enter image description here

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

Community
  • 1
  • 1
Jonathon Reinhart
  • 132,704
  • 33
  • 254
  • 328
  • I would think, not sure, that Single(predicate) internally calls Where(predicate) to get the working set, so any difference in speed would be negligible. – David Venegoni Jan 17 '14 at 20:01
  • 1
    I believe there is a negligible performance difference and the only reason Resharper suggests it is the conciseness. It would be easy enough to run some benchmarks. – Jace Rhea Jan 17 '14 at 20:02
  • I can't say which is faster but `Where(predicate).Single()` is clearer. – Hamlet Hakobyan Jan 17 '14 at 20:02
  • @JaceRhea (sshh.. that was actually my reason for asking) – Jonathon Reinhart Jan 17 '14 at 20:04
  • 4
    Similar question: [Why is LINQ .Where(predicate).First() faster than .First(predicate)?](http://stackoverflow.com/questions/8663897/why-is-linq-wherepredicate-first-faster-than-firstpredicate) – Tim S. Jan 17 '14 at 20:07
  • 5
    You've written the code both ways. If you want to know which is faster, **run it both ways** and then you'll know. – Eric Lippert Jan 17 '14 at 21:25
  • 1
    @EricLippert I did. See the comment two before yours, and the answer below :-) – Jonathon Reinhart Jan 17 '14 at 21:29
  • 1
    The assumption seems to be so far that we are talking about LINQ to Objects, and strangely the compound expression is faster. However, when applied over a different provider - say entity framework - there's no guarantee this would be the case. I think you need to be more specific about what provider you mean before an empirical answer can be provided. – x0n Jan 17 '14 at 21:30

5 Answers5

39

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.
Community
  • 1
  • 1
Jonathon Reinhart
  • 132,704
  • 33
  • 254
  • 328
  • I'm quite shocked by these results as well. I can't think of a single (no pun intended) reason that Single should be so much slower. – Jace Rhea Jan 17 '14 at 20:05
  • 1
    I'd typically go for the clarity of `Single(x..)` over `Where(x..).Single()`. If performance is an actual issue, you probably want to rewrite it to not use LINQ anyway. – Tim S. Jan 17 '14 at 20:06
  • 7
    Your benchmark doesn't factor in the main purpose of `Single`, to check that there is at most one matching result (this is never the case in your code, or you'd need exception handling). In theory, `.Single(predicate)` should be faster to do this, since it should be able to throw on the second match, rather than enumerating the entire resultset first. – Richard Jan 17 '14 at 20:06
  • 3
    @Richard you're incorrect that the second would enumerate the entire resultset first. LINQ uses lazy evalution, so both examples would enumerate no more items than necessary. – Tim S. Jan 17 '14 at 20:08
  • 2
    @Richard "rather than enumerating the entire resultset first"... but that's not how `Where()` works... it's lazily `yield`ing results as they requested... in this case by `Single()` calling `ToNext()`. – Jonathon Reinhart Jan 17 '14 at 20:08
  • Change your collection from `int[]` to `List` and you will get another result. – Hamlet Hakobyan Jan 17 '14 at 20:14
  • You did this test in Release mode and outside the debugger, right? There is a whole lot of difference between debug and release mode. – Casperah Jan 17 '14 at 20:22
  • @Casperah Release mode: yes, outside debugger: no. Just tried it outside, and both were proportionally faster (as expected - a consistent debugger slowdown.) – Jonathon Reinhart Jan 17 '14 at 20:24
  • @HamletHakobyan Updated to try other enumerable types. – Jonathon Reinhart Jan 17 '14 at 20:31
  • 4
    Now (2018) I test this again and i get other results. In my test the .single(..) was faster as .where(..).single(). But just by a factor below 10% – Horitsu Jul 04 '18 at 08:39
  • 1
    I've re-ran this benchmark with netcore 2.2, and got results similar to @Horitsu: [Benchmark](https://github.com/MarkSFrancis/SingleOrWhere) – marksfrancis Mar 06 '19 at 15:50
9

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

Nick Chapsas
  • 6,872
  • 1
  • 20
  • 29
manojlds
  • 290,304
  • 63
  • 469
  • 417
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.

rae1
  • 6,066
  • 4
  • 27
  • 48
  • Your example isn't truth. Both of them will do almost the same. But the first one in example will throw an exception on second element. And the second one will stuck with infinitive iteration. But it won't complete correctly – Sergey Litvinov Jan 17 '14 at 22:15
  • @SergeyLitvinov - almost the same isn't the same. – qxn Jan 17 '14 at 22:31
  • @ken, if collection has just one item that satisfy predicate, then both of them will behave exactly the same. if it has more than one item, then behavior would be different – Sergey Litvinov Jan 17 '14 at 22:34
  • @SergeyLitvinov I know it won't complete correctly; it won't complete at all. The idea is that the behavior is different, which seems to be an oversight. – rae1 Jan 18 '14 at 03:23
4

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().]

Jon Hanna
  • 110,372
  • 10
  • 146
  • 251
  • 2
    I think your connect bug report is a duplicate of this one raised by Jon Skeet on 28 Jan 2011: https://connect.microsoft.com/VisualStudio/feedback/details/639955 . Here's what Microsoft said about that one "...this issue currently falls just below our bug triage cut line. We're marking the issue Won't Fix..." – Edward Jan 22 '14 at 18:29
  • Thanks @Edward, it is indeed a duplicate, though it misses the error condition. – Jon Hanna Jan 24 '14 at 16:56
  • I was assuming that since Single throws when multiple are found they didnt bother optimizing that condition since it would add an additional logic check per iteration of success conditions. – Marie Apr 30 '19 at 15:59
1

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.

qxn
  • 17,162
  • 3
  • 49
  • 72
  • `Where(predicate)` returns WhereEnumerableIterator that inherits `Iterator` and it has different implementation that you've specified. `case 2` has block that iterates items – Sergey Litvinov Jan 17 '14 at 22:32