Skip to main content
Email Password   helpLost your password?

Introduction

This article will discuss performance differences between a LINQ loop and a regular For loop, as a way to practice using Visual Studio 2008, Linq and unit tests for the first time.

Background

LINQ (Language INtegrated Query) is Microsoft's new .NET addition to the language and allows formulating queries in an SQL-like syntax. It's particularly useful when traversing data sets, XML DOM trees and collections.

I first came across Visual Studio 2008, and LINQ in particular, during this year's Tech Ed at Orlando.

A nice developer from Microsoft described and demoed it for me (at that time, it was only available for VB.NET, but a C# version came out with beta 2). That developer insisted that LINQ is not just for data sets or complex objects, but can also be used for simple loops.

I decided to put his theory to the test, as a way to learn the new technology: I wrote a simple program that searches for odd numbers in an array, and compared the time it took a regular loop to the time it took a Linq loop, to come up with the right answers.

While this article was written several months ago, I waited for the RTM version of VS 2008 and .NET 3.5 to arrive, before publishing it.

Along the way, I got to learn LINQ more deeply and using VS 2008 unit testing capabilities.

As the project grew, I've added a third loop (ForEach) to the mix. I then decided to output it all to a CSV file and analyze the results in Excel.

The Logic

  1. The program allocates an array, with n elements and fills it with numbers
  2. It then calls each of a GetAverage on each of the 3 functions
  3. GetAverage calls each function a 1000 times (configurable)
  4. It measures the time it takes a function to go through n elements and calculates an average.
    Measurements are derived using Daniel Strigl's High Performance System Timer
  5. Averages to n elements are displayed (or outputted to a file) for each function
  6. the entire code runs 5 times, to ensure average consistency

Using the Code

This is a bare-bones application. It runs as a console application and has no UI.
The only configurable parts in it are:

  1. numElements - how many elements in the array
  2. numIterations - how many times is each algorithm called, to calculate an average
  3. Application output can go to a file or to the standard output (screen) - just comment the right lines

The Harness

Here's the Main function:

static void Main(string[] args)
{
  StreamWriter file = new StreamWriter("results.txt");
  file.WriteLine("Elements\tFor loop\tForEach Loop\tLinq Loop");
  //Console.WriteLine("Elements\tFor loop\tForEach Loop\tLinq Loop");
  for (int i = 0; i < 5; i++)
  {
    int numElements = 1000 * (int)Math.Pow(10, i);
    FillArray(numElements);
    file.WriteLine("{0:#,#}\t{1:0.0000000000}\t{2:0.0000000000}\t{3:0.0000000000}", 
      numElements, GetAverage(GetOdd), GetAverage(GetOddForEach), GetAverage(GetOddLinq));
    //Console.WriteLine("{0:#,#}\t{1:0.0000000000}\t{2:0.0000000000}\t{3:0.0000000000}", 
      numElements, GetAverage(GetOdd), GetAverage(GetOddForEach), GetAverage(GetOddLinq));
  }
  //Console.ReadLine();
  file.Close();
}

As you can see, all it does is call the GetAverage function, passing the algorithm function as a parameter.

The GetAverage looks like this:

private static double GetAverage(func f)
{
  double averageDuration = 0.0;
  for (int i = 0; i < numIterations; i++)
  {
    pt.Start();
    int odd = f();
    pt.Stop();
    //Console.WriteLine("Time difference: {0}", pt.Duration);
    averageDuration += pt.Duration;
  }
  averageDuration /= numIterations;
  return averageDuration;
}

As you can see, not too complicated: it starts a timer, calls function f() stops the timer and accumulates the time. It does so numIterations times and returns the average. I really liked the idea of submitting a function name as a parameter, as it abstracted the design and will let me build on it in the future.

The Algorithms

Essentially, all 3 functions use simple O(n) search algorithms: The GetOdd is the most straightforward: 

private static int GetOdd()
{
  int counter = 0;
  for(int n = 0; n < theArray.Length; n++)
  {
    if (theArray[n] % 2 == 1)
    {
      counter++;
    }
  }
  return counter;
}

The GetOddForEach:

private static int GetOddForEach()
{
  int counter = 0;
  foreach (int n in theArray)
  {
    if (n % 2 == 1)
    {
        counter++;
    }
  }
  return counter;
}

and finally, the GetOddLinq using the new Linq syntax:

private static int GetOddLinq()
{
  var odd = from n in theArray
      where n % 2 == 1
      select n;
  return odd.Count();
}

You first notice the new keyword var (was someone thinking of JavaScript while designing this?). It defines a new IEnumerable collection that will contain the results of the LINQ query. The query itself looks a bit like a reversed SQL query (select is in the end), but it's still readable.

For more on Linq's syntax and samples, try the official LINQ project page.

The Results

I've run this program on several computers and VMs. I've tried it on Windows XP, Vista and 2008 RC1. I tried running it on a busy machine, or on a completely vacant machine. Finally, I've tested debug and release versions. The numbers may change, but the trend remains the same:

Screenshot - resultstable.png

Measurements are in seconds. Column E shows the percentage of time added by Linq compared to For: Fi = (Di - Bi)/Di.

Of course, once you have the raw data, you can analyze it however you want, such as generate a graph:

Screenshot - resultsgraph.png

Note: as mentioned results have been pretty consistent, and Linq had 75-85% overhead, in almost every test. But in debug version, LINQ took even longer to complete the task, while For and ForEach remained essentially the same.

My only guess is that LINQ has some instrumentation built into it, to allow for easier debugging � thus it's slower in debug builds.

Unit Testing

A huge chunk of the Tech Ed sessions was dedicated to testing and in particular, how easy it is to add unit tests in VS 2008. And indeed, it didn't take long. Right click anywhere in the source and select "Create Unit Tests...". A wizard will take you through selecting the functions you want to test in your project and would eventually create a test project and add it to the solution.

The test projects comes ready with the right references and a set of accessors � allowing the unit test functions access to all members of the original class � even the private ones.

So how do you test this code? Here's the unit test for the function that creates the array: 

/// <summary>
///A test for FillArray
///</summary>
[TestMethod()]
[DeploymentItem("LinqTest.exe")]
public void FillArrayTest()
{
  int n = 10; // TODO: Initialize to an appropriate value
  Program_Accessor.FillArray(n);
  Assert.AreEqual(n, Program_Accessor.theArray.Length);
}

Pretty simple, isn't it? Essentially, you are using the Program_Accessor to gain access to the LinqTest.exe assembly. Upon calling the FillArray function for n elements, you assert that the size of the array should now be n.

Now, let's test one of the search functions (the tests for all are the same � a unit test does not care about the internal logic of the function, just about the results). 

/// <summary>
///A test for GetOddLinq
///</summary>
[TestMethod()]
[DeploymentItem("LinqTest.exe")]
public void GetOddLinqTest()
{
  int expected = 1; // In every 2 numbers, one is odd
  int actual;
  Program_Accessor.FillArray(2);
  actual = Program_Accessor.GetOddLinq();
  Assert.AreEqual(expected, actual);
}

Here I cheated. Knowing that my array will be filled with consecutive numbers, I know that any 2 adjacent cells I pick will contain 1 odd number. So, we build a 2 cell array, fill it and compare the number of odd numbers returned from GetOddLinqTest with the expected result. In a variant of the program, where the array is filled with random numbers, you'd have to change this function, to get the right expected.

Note: random numbers will not change the measurement results, as we always have to scan the entire array.

Now, run all the unit tests prior to building the solution (or click CTRL+R,A) and, hopefully, you'll see all green:
Screenshot - Unittests.jpg

History

Version 1.00 released on 12/5/2007

Version 1.01 released on 12/14/2007

Update

Following the suggestions received in the comments, 2 corrections were implemented, to improve measurment accuracy:

  1. Per Dennis Dollfus's suggestion, the LINQ function now looks like this:
    private static int GetOddLinq()
{
  //per Dennis Dollfus's suggestion on CodeProject 12/14/2007
  int oddNumbers = theArray.Count(n => n % 2 == 1);
  return oddNumbers;
}
  2. Per kckn4fun's suggestion, results are accumulated into a StringBuilder and only written to file/console in the end. The new Main function looks like this:
    static void Main(string[] args)
{ 
    //use of StringBuilder to avoid file noise suggested by kckn4fun on 
    //CodeProject 12/14/2007 
    StringBuilder sb = new StringBuilder(); 
    sb.AppendLine("Elements\tFor loop\tForEach Loop\tLinq Loop"); 
    for (int i = 0; i < 5; i++) 
    { 
        int numElements = 1000 * (int)Math.Pow(10, i);
        FillArray(numElements); 
        sb.AppendLine(string.Format(
          "{0:#,#}\t{1:0.0000000000}\t{2:0.0000000000}\t{3:0.0000000000}", 
            numElements, GetAverage(GetOdd), GetAverage(GetOddForEach), 
            GetAverage(GetOddLinq))); 
     } 
     Console.ReadLine();
     WriteFile(sb.ToString());
}

The new results look like this:

Screenshot - resultstable2.png

Screenshot - resultsgraph2.png

As you can see, performance is slightly better � but the tren remains.

Final note

This program is, by no means, a thorough analysis of LINQ's general performance. I'm sure its behavior in traversing complex data sets and XML DOM trees is much better. I never set out to prove anything, just play a little bit with the new environment.

Feel free to use the program and its results however you choose. The way I designed it, it's easier to plug in more complex logic and still get measurements.

You must Sign In to use this message board.
 
 
Per page   
 FirstPrevNext
GeneralMod is expensive for finding odd numbers Pin
mikecarr		8:30 24 Aug '09  
GeneralRe: Mod is expensive for finding odd numbers Pin
Guy Vider		8:37 24 Aug '09  
GeneralRe: Mod is expensive for finding odd numbers Pin
mikecarr		9:21 24 Aug '09  
QuestionStopwatch class Pin
James Hugard		14:07 9 Jan '08  
AnswerRe: Stopwatch class Pin
Guy Vider		19:00 9 Jan '08  
GeneralA (semi, but probably not) interesting observation [modified] Pin
martin_hughes		7:57 22 Dec '07  
AnswerRe: A (semi, but probably not) interesting observation Pin
Guy Vider		21:27 22 Dec '07  
GeneralRe: A (semi, but probably not) interesting observation Pin
martin_hughes		5:13 23 Dec '07  
NewsNew code and measurements added! Pin
Guy Vider		6:15 22 Dec '07  
GeneralDon't worry be happy Pin
Dewey		19:06 21 Dec '07  
GeneralRe: Don't worry be happy Pin
Guy Vider		6:07 22 Dec '07  
GeneralOverhead measure error Pin
Ruy Ganeff		7:16 14 Dec '07  
GeneralRe: Overhead measure error Pin
Guy Vider		16:57 14 Dec '07  
GeneralAnother flaw in logic Pin
kckn4fun		3:59 13 Dec '07  
GeneralRe: Another flaw in logic Pin
Guy Vider		16:49 14 Dec '07  
GeneralAnother linq solution ? Pin
Denis Dollfus		0:25 13 Dec '07  
GeneralRe: Another linq solution ? Pin
Guy Vider		16:47 14 Dec '07  
GeneralLet's take a look at this! [modified] Pin
unbornchikken		23:06 14 Dec '07  
GeneralRe: Let's take a look at this! Pin
Guy Vider		6:09 15 Dec '07  
GeneralRe: Let's take a look at this! [modified] Pin
unbornchikken		11:14 16 Dec '07  
GeneralTest is bit incorrect Pin
Vladimir Sh		19:21 12 Dec '07  
GeneralI agree Pin
kckn4fun		3:57 13 Dec '07  
GeneralRe: Test is bit incorrect Pin
Guy Vider		16:46 14 Dec '07  
GeneralRe: Test is bit incorrect Pin
Arun James		0:54 1 Oct '09  
GeneralIt's just not fair. Pin
unbornchikken		18:28 12 Dec '07  
Last Visit: 3:02 21 Nov '09     Last Update: 3:02 21 Nov '09 12 Next »


Last Updated 21 Dec 2007 | Advertise | Privacy | Terms of Use | Copyright © CodeProject, 1999-2009