Linq vs Loop performance

The StackOverflow question Convince me to move to .net 3.5 (from 2.0) piqued my curiosity when against one answer the commenter wrote:

This does come at a cost tho: ox.no/posts/linq-vs-loop-a-performance-test/…

I followed the link to find out, and found a benchmark that is, in my opinion, flawed.

Why?

  • Original benchmark can't make up it's mind whether to use Arrays or Lists. In the Linq test, it uses arrays exclusively, but in the Loop version it uses both a list and an array.
  • The test was run with Visual Studio 2008 beta - this means it was running against a debug build of the .NET framework, and it's well known that Microsoft leaves debugging tests and other monitoring tools active in those builds. That's why the EULA on betas prohibits performance testing.
  • Use of DateTime.Now for measuring duration. IIRC, this is only accurate to 50ms or so.

For comparison purposes, I've run my own tests.

I started with the same benchmark code, and made the following changes:

  • I've used Lists throughout.
  • Using .NET 3.5 SP 1
  • Using Stopwatch for timing

Here's my code:

        public void RunTest()
        {
            const int SIZE = 10000;
            const int RUNS = 100000;
 
            var ints = new List<int>(SIZE);
            for (int i = 0; i < SIZE; i++)
                ints.Add(i);
 
            Stopwatch timer = new Stopwatch();
            timer.Start();
            for (int t = 0; t < RUNS; ++t)
            {
                var less = (from int i in ints
                            where i < 10
                            select i).ToList();
            }
            timer.Stop();
 
            Trace.WriteLine(
                string.Format(
                    "LINQ: {0}, avg. {1}",
                    timer.Elapsed,
                    new TimeSpan(timer.ElapsedMilliseconds / RUNS)));
 
            timer.Reset();
            timer.Start();
            for (int t = 0; t < RUNS; ++t)
            {
                var less = new List<int>();
                foreach (var i in ints)
                    if (i < 10)
                        less.Add(i);
            }
            timer.Stop();
 
            Trace.WriteLine(
                string.Format(
                    "Loop: {0}, avg. {1}",
                    timer.Elapsed,
                    new TimeSpan(timer.ElapsedMilliseconds / RUNS)));
        }

And my results:

LINQ: 00:00:38.8147774, avg. 00:00:00
Loop: 00:00:16.3512963, avg. 00:00:00

Analysis

Yes, Linq is slower - but the difference is less than a factor of 3, not greater than 50 as originally claimed.

Note however the scale: I ran 100,000 runs of a test involving a loop of 10,000 iterations - that's 1,000,000,000 iterations - a billion.

The Linq version took 38 seconds all up, so that's 38 nanoseconds per loop. Similarly, the loop version took just 16 nanoseconds per loop.

If profiling shows you that looping is the dominant factor in your code - that saving 22 nanoseconds per loop is going to be significant, then go ahead and use foreach instead of Linq.

Out here in the real world though, I don't think the difference is significant for 99.99% of code.

Conclusion

Selecting foreach instead of Linq is a micro-optimization that will almost certainly make no material difference.

Blog Tags: 

Comments

Linq slower but doing the ToList()

I wonder if the ToList() doesn't affect the linq performance... it's use to work with IEnumerable objects...

Deferred Execution

The ToList() is necessary for the benchmark, because of the deferred execution model of Linq. Until something chooses to iterate through the sequence, nothing is calculated.