Anyone know any speed differences between Where and FindAll on List. I know Where is part of IEnumerable and FindAll is part of List, I'm just curious what's faster.
+6
A:
The FindAll method of the List<T> class actually constructs a new list object, and adds results to it. The Where extension method for IEnumerable<T> will simply iterate over an existing list and yield an enumeration of the matching results without creating or adding anything (other than the enumerator itself.)
Given a small set, the two would likely perform comparably. However, given a larger set, Where should outperform FindAll, as the new List created to contain the results will have to dynamically grow to contain additional results. Memory usage of FindAll will also start to grow exponentially as the number of matching results increases, where as Where should have constant minimal memory usage (in and of itself...excluding whatever you do with the results.)
jrista
2010-02-14 05:31:31
The exception is where you actually do want to have a list afterwards (maybe you need to call `Count` or change members, or iterate through it more than once). While `Where()` beats `FindAll()`, `FindAll()` beats `Where().ToList()`.
Jon Hanna
2010-09-30 09:41:24
+1
A:
.FindAll() should be faster, it takes advantage of already knowing the List's size and looping through the internal array with a simple for loop. .Where() has to fire up an enumerator (a sealed framework class called WhereIterator in this case) and do the same job in a less specific way.
Keep in mind though, that .Where() is enumerable, not actively creating a List in memory and filling it. It's more like a stream, so the memory use on something very large can have a significant difference. Also, you could start using the results in a parallel fashion much faster using there .Where() approach in 4.0.
Nick Craver
2010-02-14 05:32:33
The WhereEnumerableIterator, rather than WhereIterator, is actually used unless you involve index in the where clause. WhereEnumerableIterator is considerably more efficient than WhereIterator. In the case of List<T>, it incurs the cost of an extra method call (which should be inlined in release code), but does not need to dynamically resize an internal list as part of its processing. The efficiency of Where should outperform FindAll in all but the smallest lists (anything larger than 4 results will result in one or more resizings.)
jrista
2010-02-14 05:46:43
In the case of calling Where on an Array or List<T>, there are two additional internal iterator classes, WhereArrayIterator and WhereListIterator, which are optimized for those two cases. Generally speaking, calling Where should be more efficient than calling FindAll.
jrista
2010-02-14 05:49:51
@jrista - I **completely** missed the case stack in the `.Where()` overload returning those, thanks! Looking through that code I agree, .Where should have, at worst, equal performance but almost always better. Also, SO would be useless if not for people taking the extra time to educate others, e.g. you and these comments, +1 for teaching me something.
Nick Craver
2010-02-14 13:24:15
+1
A:
Where is much, much faster than FindAll. No matter how big the list is, Where takes exactly the same amount of time.
Of course Where just creates a query. It doesn't actually do anything, unlike FindAll which does create a list.
Jonathan Allen
2010-02-14 05:34:49
This may be technically true, but I think it's pretty clear the OP is asking about performance in the context of actually enumerating the result, not the naked method call itself.
Dan Tao
2010-07-15 12:36:47
A:
The answer from jrista makes senses. However, the new list adds the same objects, thus just growing with reference to existing objects, which should not be that slow. As long as 3.5 / Linq extension are possible, Where stays better anyway. FindAll makes much more sense when limited with 2.0
Eric
2010-07-15 12:31:41