C# - For vs Foreach - Huge performance difference

Question

i was making some optimizations to an algorithm that finds the smallest number that is bigger than X, in a given array, but then a i stumbled on a strange difference. On the code bellow, the "ForeachUpper" ends in 625ms, and the "ForUpper" ends in, i believe, a few hours (insanely slower). Why so?

  class Teste
{
    public double Valor { get; set; }

    public Teste(double d)
    {
        Valor = d;
    }

    public override string ToString()
    {
        return "Teste: " + Valor;
    }
}

  private static IEnumerable<Teste> GetTeste(double total)
    {
        for (int i = 1; i <= total; i++)
        {
            yield return new Teste(i);
        }
    }
    static void Main(string[] args)
    {
        int total = 1000 * 1000*30 ;
        double test = total/2+.7;

        var ieTeste = GetTeste(total).ToList();


        Console.WriteLine("------------");

        ForeachUpper(ieTeste.Select(d=>d.Valor), test);
        Console.WriteLine("------------");
        ForUpper(ieTeste.Select(d => d.Valor), test);
        Console.Read();
    }

    private static void ForUpper(IEnumerable<double> bigList, double find)
    {
        var start1 = DateTime.Now;

        double uppper = 0;
        for (int i = 0; i < bigList.Count(); i++)
        {
            var toMatch = bigList.ElementAt(i);
            if (toMatch >= find)
            {
                uppper = toMatch;
                break;
            }
        }

        var end1 = (DateTime.Now - start1).TotalMilliseconds;

        Console.WriteLine(end1 + " = " + uppper);
    }

    private static void ForeachUpper(IEnumerable<double> bigList, double find)
    {
        var start1 = DateTime.Now;

        double upper = 0;
        foreach (var toMatch in bigList)
        {
            if (toMatch >= find)
            {
                upper = toMatch;
                break;
            }
        }

        var end1 = (DateTime.Now - start1).TotalMilliseconds;

        Console.WriteLine(end1 + " = " + upper);
    }

Thanks

Solution 1

IEnumerable<T> is not indexable.

The Count() and ElementAt() extension methods that you call in every iteration of your for loop are O(n); they need to loop through the collection to find the count or the nth element.

Moral: Know thy collection types.

Solution 2

The reason for this difference is that your for loop will execute bigList.Count() at every iteration. This is really costly in your case, because it will execute the Select and iterate the complete result set.

Furthermore, you are using ElementAt which again executes the select and iterates it up to the index you provided.

Comments

[sll]

Regardign Count() worth noting that it depends on an actual collection type, if it implements ICollection with Count property Count() will use it

[Daniel Hilgarth]

@sll: That's true for ElementAt, too. The big differences will go away if the OP would add a .ToArray() after the Select.

[WoF_Angel]

Funny thing is that this means that an algorithm like quicksort/binarysearch can easily be outmatched by a simple foreach, when the source collection is an enumerable.

[SLaks]

@WoF_Angel: To state that more correctly, you should not use for with arbitrary IEnumerable<T>s.

[Groo]

@WOF_Angel: it's the other way around actually: algorithms like quicksort and binary search depend on the collection to be indexable in order to provide their promosed time complexity. Using an enumerable will never make such an algorithm go faster (well, actually any iteration over a collection will pretty much always be faster using a plain array/for loop).