IEnumerable question: Best performance?

Question

Quick question:

Which one is faster?

foreach (Object obj in Collection)
{
     if(obj.Mandatory){ ... }
}

or

foreach (Object obj in Collection.FindAll(o => o.Mandatory))
{
...
}

and if you know a faster suggestion, i'd be pleased to know.

Thank you

Solution 1

The following test code prints the system ticks (1 tick = 100 nanoseconds) for iterating through 10 million objects. The FindAll is slowest and the for loop is fastest as expected.

But the overhead of the iteration is measured in nanoseconds per item even in the worst case. If you're doing anything significant in the loop (e.g. something which takes a microsecond per item), then the speed difference of the iteration is completely insignificant.

So for the love of Turing don't forbid foreach in your coding guidelines now. It doesn't make any practical difference, and the LINQ statements sure are easier to read.

   public class Test
   {
      public bool Bool { get; set; }
   }

   class Program
   {

      static void Main(string[] args)
      {
         // fill test list
         var list = new List<Test>();
         for (int i=0; i<1e7; i++)
         {
            list.Add(new Test() { Bool = (i % 2 == 0) });
         }

         // warm-up
         int counter = 0;
         DateTime start = DateTime.Now;
         for (int i = 0; i < list.Count; i++)
         {
            if (list[i].Bool)
            {
               counter++;
            }
         }

         // List.FindAll
         counter = 0;
         start = DateTime.Now;
         foreach (var test in list.FindAll(x => x.Bool))
         {
            counter++;
         }
         Console.WriteLine(DateTime.Now.Ticks - start.Ticks); // prints 7969158

         // IEnumerable.Where
         counter = 0;
          start = DateTime.Now;
         foreach (var test in list.Where(x => x.Bool))
         {
            counter++;
         }
         Console.WriteLine(DateTime.Now.Ticks - start.Ticks); // prints 5156514

         // for loop
         counter = 0;
         start = DateTime.Now;
         for (int i = 0; i < list.Count; i++)
         {
            if (list[i].Bool)
            {
               counter++;
            }
         }
         Console.WriteLine(DateTime.Now.Ticks - start.Ticks); // prints 2968902


      }

Solution 2

If your Collection is a List<T> then FindAll is implemented by creating a new List<T> and copying all items that match the predicate. This is obviously slower than just enumerating the collection and deciding for each item if the predicate holds.

If you're using .NET 3.5 you can use LINQ which will not create a copy and and is similar to your first example:

foreach (object obj in someCollection.Where(o => o.Mandatory))
{
    ...
}

Note this isn't necessarily the fastest solution. It's just easy to see that a method that allocates memory and enumerates a collection is slower than a method that only enumerates a collection. If performance is critical: measure it.

Solution 3

The first will be somewhat faster.

In the second case, you're using List<T>.FindAll to create a temporary list that matches your criteria. This copies the list, then iterates over it.

However, you could accomplish the same thing, with the same speed as your first option, by doing:

foreach (Object obj in Collection.Where(o => o.Mandatory))
{
}

This is because Enumerable.Where uses streaming to return an IEnumerable<T>, which is generated as you iterate. No copy is made.

Solution 4

The fastest you could ever get without parallelizing the enumeration into multiple threads taking accounts of number of processors, etc:

for (int i = 0; i < Collection.Count; i++)
{
    var item = Collection[i];
    if (item.Mandatory) { ... }
}

I would recommend you though to always use Linq instead of writing for or foreach loops because in the future it will become so intelligent that it will actually be capable of distributing the work over processors and take into account hardware specific things (see PLinq) and it will eventually be faster than if you wrote the loops yourself: declarative vs imperative programing.

Solution 5

FindAll is just syntactic sugar. For example:

    List<string> myStrings = new List<string>();
    foreach (string str in myStrings.FindAll(o => o.Length > 0))
    {

    }

Compiles to:

List<string> list = new List<string>();
if (CS$<>9__CachedAnonymousMethodDelegate1 == null)
{
    CS$<>9__CachedAnonymousMethodDelegate1 = new Predicate<string>(MyClass.<RunSnippet>b__0);
}
using (List<string>.Enumerator enumerator = list.FindAll(CS$<>9__CachedAnonymousMethodDelegate1).GetEnumerator())
{
    while (enumerator.MoveNext())
    {
        string current = enumerator.Current;
    }
}

public List<T> FindAll(Predicate<T> match)
{
    if (match == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
    }
    List<T> list = new List<T>();
    for (int i = 0; i < this._size; i++)
    {
        if (match(this._items[i]))
        {
            list.Add(this._items[i]);
        }
    }
    return list;
}

private static bool <RunSnippet>b__0(string o)
{
    return (o.Length > 0);
}

View more solutions