FindAll vs Where extension-method

c#, extension-methods, lambda

Solution

Well, `FindAll` copies the matching elements to a new list, whereas `Where` just returns a lazily evaluated sequence - no copying is required.

I'd therefore expect `Where` to be slightly faster than `FindAll` even when the resulting sequence is fully evaluated - and of course the lazy evaluation strategy of `Where` means that if you only look at (say) the first match, it won't need to check the remainder of the list. (As Matthew points out, there's work in maintaining the state machine for `Where`. However, this will only have a fixed memory cost - whereas constructing a new list may require multiple array allocations etc.)

Basically, `FindAll(predicate)` is closer to `Where(predicate).ToList()` than to just `Where(predicate)`.

Just to react a bit more to Matthew's answer, I don't think he's tested it quite thoroughly enough. His predicate happens to pick half the items. Here's a short but complete program which tests the same list but with three different predicates - one picks no items, one picks all the items, and one picks half of them. In each case I run the test fifty times to get longer timing.

I'm using `Count()` to make sure that the `Where` result is fully evaluated. The results show that collecting around half the results, the two are neck and neck. Collecting no results, `FindAll` wins. Collecting all the results, `Where` wins. I find this intriguing: all of the solutions become slower as more and more matches are found: `FindAll` has more copying to do, and `Where` has to return the matched values instead of just looping within the `MoveNext()` implementation. However, `FindAll` gets slower faster than `Where` does, so loses its early lead. Very interesting.

Results:

FindAll: All: 11994
Where: All: 8176
FindAll: Half: 6887
Where: Half: 6844
FindAll: None: 3253
Where: None: 4891

(Compiled with /o+ /debug- and run from the command line, .NET 3.5.)

Code:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

class Test
{
    static List<int> ints = Enumerable.Range(0, 10000000).ToList();

    static void Main(string[] args)
    {
        Benchmark("All", i => i >= 0); // Match all
        Benchmark("Half", i => i % 2 == 0); // Match half
        Benchmark("None", i => i < 0); // Match none
    }

    static void Benchmark(string name, Predicate<int> predicate)
    {
        // We could just use new Func<int, bool>(predicate) but that
        // would create one delegate wrapping another.
        Func<int, bool> func = (Func<int, bool>) 
            Delegate.CreateDelegate(typeof(Func<int, bool>), predicate.Target,
                                    predicate.Method);
        Benchmark("FindAll: " + name, () => ints.FindAll(predicate));
        Benchmark("Where: " + name, () => ints.Where(func).Count());
    }

    static void Benchmark(string name, Action action)
    {
        GC.Collect();
        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < 50; i++)
        {
            action();
        }
        sw.Stop();
        Console.WriteLine("{0}: {1}", name, sw.ElapsedMilliseconds);
    }
}

Problem

Original source