Why is LINQ faster in this example

Question

I wrote the following to test the performance of using foreach vs LINQ:

private class Widget
{
    public string Name { get; set; }
}

static void Main(string[] args)
{
    List<Widget> widgets = new List<Widget>();
    int found = 0;

    for (int i = 0; i <= 500000 - 1; i++)
        widgets.Add(new Widget() { Name = Guid.NewGuid().ToString() });

    DateTime starttime = DateTime.Now;

    foreach (Widget w in widgets)
    {
        if (w.Name.StartsWith("4"))
            found += 1;
    }

    Console.WriteLine(found + " - " + DateTime.Now.Subtract(starttime).Milliseconds + " ms");

    starttime = DateTime.Now;
    found = widgets.Where(a => a.Name.StartsWith("4")).Count();

    Console.WriteLine(found + " - " + DateTime.Now.Subtract(starttime).Milliseconds + " ms");

    Console.ReadLine();
}

I get something like following output:

31160 - 116ms
31160 - 95 ms

In every run, LINQ outperforms foreach by around 20%. It was my understanding that the LINQ extension methods used standard c# under the covers.

So why is LINQ faster in this case?

EDIT:

So I changed my code to use stopwatch instead of datetime and still get the same results. If I run the LINQ query first then my results show LINQ to be about 20% slower then foreach. This has to be some sort of JIT warmnup issue. My question is how do I compensate for JIT warmup in my test case?

Have you tried reversing the order of the tests? You may well be seeing JIT timing. It's generally better to run the test once first to warm up the system, *then* run it again and time it. Also, use Stopwatch. See http://ericlippert.com/tag/benchmarks/ — Jon Skeet, Jun 17 '13 at 12:54
Jon, I think you are right. How can I change my code to filter out JIT timing and get real numbers? — Coltech, Jun 17 '13 at 13:00
He told you -- run the tests without timing, then re-run the tests using the Stopwatch class (more accurate). — Jaime Torres, Jun 17 '13 at 13:03
Don't forget to run in `Release` mode instead of `Debug` mode. It can make differences. — Vitor Canova, Jun 17 '13 at 13:07
Also, don't forget to run multiple tests and average them correctly. Your computer could have hiccuped because Adobe was polling for an update during one of the runs causing a millisecond delay from the OS. Silly as all this sounds, such is the fickle nature of micro performance timing on interrupt-driven systems. — Adam Houldsworth, Jun 17 '13 at 13:14
...and remember to run the tests outside Visual Studio or by calling "Debug -> Start without debugging" even when you are in release mode. — digEmAll, Jun 17 '13 at 13:21
@Coltech To warm the code up, simply run it once before starting a test run such that any called methods etc will be JIT compiled before the test run starts. When I do this I just have the code under test in another method, then call the method once before of my timing loop and then as you would inside the timing loop. — Adam Houldsworth, Jun 17 '13 at 13:21
As an aside - a for loop will iterate faster over a `List` than a foreach loop. This is not true with arrays, with arrays it will be the same. — jackmott, Mar 27 '17 at 02:46

score 15 · Accepted Answer · edited Jun 17 '13 at 15:53

15

It's because you do not have a warmup. If you reverse your cases you will get excatly the opposit result:

31272 - 110ms
31272 - 80 ms

Start adding a warmup and use a stopwatch for better timing.

Running the test with warmup:

        //WARM UP:
        widgets.Where(a => a.Name.StartsWith("4")).Count();

        foreach (Widget w in widgets)
        {
            if (w.Name.StartsWith("4"))
                found += 1;
        }

        //RUN Test
        Stopwatch stopwatch1 = new Stopwatch();
        stopwatch1.Start();

        found = widgets.Where(a => a.Name.StartsWith("4")).Count();
        stopwatch1.Stop();

        Console.WriteLine(found + " - " + stopwatch1.Elapsed);

        found = 0;
        Stopwatch stopwatch2 = new Stopwatch();
        stopwatch2.Start();

        foreach (Widget w in widgets)
        {
            if (w.Name.StartsWith("4"))
                found += 1;
        }
        stopwatch2.Stop();

        Console.WriteLine(found + " - " + stopwatch2.Elapsed);

result:

31039 - 00:00:00.0783508
31039 - 00:00:00.0766299

edited Jun 17 '13 at 15:53

yoozer8

7,361
7
58
93

answered Jun 17 '13 at 13:10

Peter

27,590
8
64
84

2

You've basically rephrased Jon Skeet's comment (with less details, "warmup" vs JIT). You should add examples and more explanations... – ken2k Jun 17 '13 at 13:12
Thanks. I will use stopwatch instead of datetime. Could you define what you mean by "warmup"? – Coltech Jun 17 '13 at 13:12
You're testing the same method both times, and you're still using DateTime to get timings... – ken2k Jun 17 '13 at 13:22
Using this code and replace datetime with stopwatch yielded expected results. Thanks! – Coltech Jun 17 '13 at 13:28
Changed the datetime to stopwatch implementation – Peter Jun 17 '13 at 14:32

score 2 · Answer 2 · edited Jun 17 '13 at 14:27

2

I did some profiling a while back, comparing the following:

LINQ to Objects with/without Regex
Lambda Expressions with/without Regex
Traditional iteration with/without Regex

What I found out was that LINQ, Lambda and Traditional iteration were pretty much the same always, but the real timing difference was in the Regex expressions. Only adding the Regex made the evaluation slower (a LOT slower). (Details here: http://www.midniteblog.com/?p=72)

What you are seeing above is probably due to the fact that you are doing both tests in the same code block. Try commenting one out, timing it, then commenting the other out. Also, make sure you are running a release build, not in the debugger.

edited Jun 17 '13 at 14:27

svick

236,525
50
385
514

answered Jun 17 '13 at 13:03

edtheprogrammerguy

5,957
6
28
47

What does this question have to do with regex? – svick Jun 17 '13 at 14:27
It is just part of the profiling example. Feel free to ignore the Regex part. – edtheprogrammerguy Jun 17 '13 at 14:30

Why is LINQ faster in this example

2 Answers2

Linked