Is this really a case when Linq is faster than a Foreach

Question

If you search is Linq faster the Foreach the answer always is no a foreach is. I also found another stackoverflow question where the question asker had not done a "warmup" so I've included a "warmup" in my code.

My code example for some reason did not act as I expected. I'm thinking what I've done is make the no linq path loop twice--once the first time and once at the sum. Where as the linq example loops only once at the end when it does a sum. What do you think? Is my test flawed or is this a scenario where linq actually buys us a good performance increase?

    public class NumberObject { public Int32 Number { get; set; } }

    public IEnumerable<NumberObject> GetNumbersWithoutLambda()
    {
        IEnumerable<Int32> numberRange = Enumerable.Range(0,10);
        List<NumberObject> numberList = new List<NumberObject>();
        foreach (Int32 item in numberRange)
        {
            numberList.Add(new NumberObject() { Number = item });
        }
        return numberList;
    }

    public IEnumerable<NumberObject> GetNumbersWithLambda()
    {
        IEnumerable<Int32> numberRange = Enumerable.Range(0, 10);
        IEnumerable<NumberObject> numbers = numberRange.
            Select(number => new NumberObject() { Number = number });
        return numbers;
    }

    private void runGetNumbers(Func<IEnumerable<NumberObject>> getNumbersFunction, Int32 numberOfTimesToRun)
    {
        for (int i = 0; i < numberOfTimesToRun; i++)
        {
            IEnumerable<NumberObject> numbers = getNumbersFunction();
            //numbers.Count();
            numbers.Sum(item => item.Number);
            //numbers.Average(item => item.Number);
        }
    }

    [TestMethod]
    public void record_speed_of_GetNumbers()
    {
        Int32 numberOfTimes = 10000000;

        Console.WriteLine("Doing warmup... " +
            TimeMethod(() => runGetNumbers(GetNumbersWithLambda, numberOfTimes)));

        Console.WriteLine("GetNumbersWithoutLambda: " +
            TimeMethod(() => runGetNumbers(GetNumbersWithoutLambda, numberOfTimes)) + " milliseconds");

        Console.WriteLine("GetNumbersWithLambda: " +
            TimeMethod(() => runGetNumbers(GetNumbersWithLambda, numberOfTimes)) + " milliseconds");
    }

    static long TimeMethod(Action methodToTime)
    {
        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();
        methodToTime();
        stopwatch.Stop();
        return stopwatch.ElapsedMilliseconds;
    }

Below is the output from the test:

Doing warmup... 7560

GetNumbersWithoutLambda: 14779 milliseconds

GetNumbersWithLambda: 7626 milliseconds

The interesting this is that the "warmup" run actually does not seem to apply in this case.

Solution 1

LINQ will usually be faster when it can take advantage of deferred execution; as it does here.

As you suspected; foreach fully enumerates the collection in your code. Select just builds a query to do that enumeration.

Then when you call Sum, it enumerates the previously generated collection. We have a total of 2 enumerations for foreach and just one for Select, so it is faster (by a factor of 2!)

There are other examples; Take, and First will stop execution early (a foreach can stop early, but most people don't code it that way).

Basically, use foreach when you actually need to enumerate the whole collection for what you are doing, or when you want to enumerate (consume) a LINQ query. Use LINQ when you are running queries and operations where deferred execution will get you a performance benefit. When that query returns a collection, use foreach to iterate over it.

Solution 2

You are comparing apples and oranges, Linq doesn't use a List<> like your "non-lambda" version does. That list doesn't come for free.

You'll need to write it like this:

public IEnumerable<NumberObject> GetNumbersWithoutLambda() {
    IEnumerable<Int32> numberRange = Enumerable.Range(0, 10);
    foreach (Int32 item in numberRange) {
        yield return new NumberObject() { Number = item };
    }
}

It now takes the same amount of time. And yes, Linq uses iterators as well.

---

That however doesn't hold a candle to the unlinquified version, it is five times faster:

static int sum;   // Ensures summing doesn't get optimized away

private void runGetNumbers2(Int32 numberOfTimesToRun) {
    for (int i = 0; i < numberOfTimesToRun; i++) {
        foreach (var number in Enumerable.Range(0, 10)) {
            sum += number;
        }
    }
}

Make it another three times faster yet by dropping Enumerable.Range:

for (int i = 0; i < numberOfTimesToRun; i++) {
    for (int j = 0; j < 10; ++j) {
        sum += j;
    }
}

Which demonstrates that the state machine that iterators use isn't for free either. Basic premise here is that simple code is fast.

Solution 3

The difference is that even though a List implements IEnumerable, it must be fully populated before the method can return where the Linq method only needs to construct the expression tree before returning.

Consider and time the following:

public IEnumerable<NumberObject> GetNumbersWithLambdaToList()
{
    IEnumerable<Int32> numberRange = Enumerable.Range(0, 10);
    IEnumerable<NumberObject> numbers = numberRange.
        Select(number => new NumberObject() { Number = number });
    return numbers.ToList();
}

public IEnumerable<NumberObject> GetNumbersWithYield()
{
    IEnumerable<Int32> numberRange = Enumerable.Range(0,10);
    foreach (Int32 item in numberRange)
    {
        yield return (new NumberObject() { Number = item });
    }
}

On my machine:

GetNumbersWithoutLambda: 9631 milliseconds
GetNumbersWithLambda: 7285 milliseconds
GetNumbersWithLambdaToList: 12998 milliseconds
GetNumbersWithYield: 9236 milliseconds