Where does this LINQ performance come from?

Question

I made a function to recursively find the first or default item that fit a condition (first code block).

Resharper suggested me to change few lines in only one LINQ line (second code block).

I was wondering if the Resharper suggestion would give me same performance and same memory footprint. I made a test for the performance (3rd code block). The result is just what I expected. Why the difference is so large ?

8156 milliseconds
Laure
23567 milliseconds
Laure LINQ

Where does come from that difference ??? Why results are not the same?... or at least, closer ?

public static T RecursiveFirstOrDefault<T>(this T item, Func<T, IEnumerable<T>> childrenSelector, Predicate<T> condition)
    where T : class // Hierarchy implies class. Don't need to play with "default()" here.
{
    if (item == null)
    {
        return null;
    }

    if (condition(item))
    {
        return item;
    }

    foreach (T child in childrenSelector(item))
    {
        T result = child.RecursiveFirstOrDefault(childrenSelector, condition);
        if (result != null)
        {
            return result;
        }
    }

    return null;
}

But Resharper suggested me to convert the foreach block to a LINQ query as follow:

public static T RecursiveFirstOrDefaultLinq<T>(this T item, Func<T, IEnumerable<T>> childrenSelector, Predicate<T> condition)
    where T : class // Hierarchy implies class. Don't need to play with "default()" here.
{
    if (item == null)
    {
        return null;
    }

    if (condition(item))
    {
        return item;
    }

    // Resharper change:
    return childrenSelector(item).Select(child => child.RecursiveFirstOrDefaultLinq(childrenSelector, condition)).FirstOrDefault(result => result != null);
}

Test:

private void ButtonTest_OnClick(object sender, RoutedEventArgs e)
{
    VariationSet varSetResult;
    Stopwatch watch = new Stopwatch();

    varSetResult = null;
    watch.Start();
    for(int n = 0; n < 10000000; n++)
    {
        varSetResult = Model.VariationRef.VariationSet.RecursiveFirstOrDefault((varSet) => varSet.VariationSets,
            (varSet) => varSet.Name.Contains("Laure"));
    }
    watch.Stop();
    Console.WriteLine(watch.ElapsedMilliseconds.ToString() + " milliseconds");
    Console.WriteLine(varSetResult.Name);

    watch.Reset();

    varSetResult = null;
    watch.Start();
    for(int n = 0; n < 10000000; n++)
    {
        varSetResult = Model.VariationRef.VariationSet.RecursiveFirstOrDefaultLinq((varSet) => varSet.VariationSets,
            (varSet) => varSet.Name.Contains("Laure"));
    }
    watch.Stop();
    Console.WriteLine(watch.ElapsedMilliseconds.ToString() + " milliseconds");
    Console.WriteLine(varSetResult.Name + " LINQ");

}

I have to go for today... Hope to answer properly about tests: x86, Release on a 12 core machine, windows 7, Framework.Net 4.5,

My conclusion:

In my case it is ~3x faster in non linq version. Readability is better in LINQ but who care WHEN it is in a library where you should only remember what it does and how to call it (in this case - not a general absolute case). LINQ is almost always slower than good coded method. I would personnaly flavor:

• LINQ: Where performance is not really an issue (most cases) in specific project code
• Non Linq: Where performance is an issue in specific project code, and where used in a library and where code should be stable and fixed where usage of the method should be well documented and we should not really need to dig inside.

Answer 1

Here are some reasons there's a difference between non-LINQ and LINQ code performance:

1. Every call to a method has some performance overhead. Information has to be pushed onto the stack, the CPU has to jump to a different instruction line, etc. In the LINQ version you are calling into Select and FirstOrDefault, which you are not doing in the non-LINQ version.
2. There is overhead, both time and memory, when you create a Func<> to pass into the Select method. The memory overhead, when multiplied many times as you do in your benchmark, can lead to the need to run the garbage collector more often, which can be slow.
3. The Select LINQ method you are calling produces an object that represents its return value. This also adds a little memory consumption.

why is the difference so large?

It's actually not that large. True, LINQ takes 50% longer, but honestly you're talking about only being able to complete this entire recursive operation 400 times in a millisecond. That's not slow, and you're unlikely to ever notice the difference unless this is an operation you're doing all the time in a high-performance application like a video game.