Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

FindAll vs Where extension-method

I just want know if a "FindAll" will be faster than a "Where" extentionMethod and why?

Example :

myList.FindAll(item=> item.category == 5); 

or

myList.Where(item=> item.category == 5); 

Which is better ?

like image 628
Cédric Boivin Avatar asked Oct 07 '09 13:10

Cédric Boivin


People also ask

Where vs FindAll LINQ?

Where returns an instance of IEnumerable that is executed on-demand when the object is enumerated. FindAll returns a new List<T> that contains the requested elements. FindAll is more like calling Where(...). ToList() on an instance of IEnumerable .

What does FindAll return C#?

Returns the zero-based index of the first occurrence of a value in the List<T> or in a portion of it.


1 Answers

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);     } } 
like image 165
Jon Skeet Avatar answered Sep 19 '22 01:09

Jon Skeet