FindAll vs Where extension-method

by

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);
    }
}

More Related Contents:

  1. Distinct() with lambda?
  2. Get All instead of FirstOrDefault
  3. Does C# have extension properties?
  4. Why can’t an anonymous method be assigned to var?
  5. Mutating the expression tree of a predicate to target another type
  6. Timeout Pattern – How bad is Thread.Abort really?
  7. What Advantages of Extension Methods have you found? [closed]
  8. Lambda variable capture in loop – what happens here? [duplicate]
  9. Weak event handler model for use with lambdas
  10. Anonymous Types – Are there any distingushing characteristics?
  11. Multiple Order By with LINQ [duplicate]
  12. Extension methods syntax vs query syntax
  13. What are C# lambda’s compiled into? A stackframe, an instance of an anonymous type, or?
  14. Why can I not edit a method that contains an anonymous method in the debugger?
  15. What’s the point of a lambda expression?
  16. “Nested foreach” vs “lambda/linq query” performance(LINQ-to-Objects) [closed]
  17. Entity Framework – Cannot convert lambda expression to type ‘string’ because it is not a delegate type
  18. Cannot use a lambda expression as an argument to a dynamically dispatched operation without first casting it to a delegate or expression tree type
  19. Is it possible to implement mixins in C#?
  20. How to merge a list of lists with same type of items to a single list of items?
  21. Ambiguous call between two C# extension generic methods one where T:class and other where T:struct
  22. Can I use extension methods and LINQ in .NET 2.0 or 3.0?
  23. Why doesn’t VS 2008 display extension methods in Intellisense for String class
  24. How do I dynamically create an Expression predicate?
  25. How to use Expression Tree to safely access path of nullable objects?
  26. Expression for Type members results in different Expressions (MemberExpression, UnaryExpression)
  27. Is it possible to extend arrays in C#?
  28. Why can’t I call an extension method as a static method when using static import?
  29. How do I translate an expression tree of one type to a different expression type?
  30. Convert DataTable to Generic List in C#

Leave a Comment