James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 166 , comments - 1431 , trackbacks - 0

My Links

News

Welcome to my blog! I'm a Sr. Software Development Engineer in the Seattle area, who has been performing C++/C#/Java development for over 20 years, but have definitely learned that there is always more to learn!

All thoughts and opinions expressed in my blog and my comments are my own and do not represent the thoughts of my employer.

Blogs I Read

Follow BlkRabbitCoder on Twitter

Tag Cloud

Article Categories

Archives

Post Categories

.NET

CSharp

Little Wonders

Little Wonders

vNext

C#: LINQ vs foreach - Round 1.

So I was reading Peter Kellner's blog entry on Resharper 5.0 and its LINQ refactoring and thought that was very cool.  But that raised a point I had always been curious about in my head -- which is a better choice: manual foreach loops or LINQ? 
 
The answer is not really clear-cut.  There are two sides to any code cost arguments: performance and maintainability.  The first of these is obvious and quantifiable.  Given any two pieces of code that perform the same function, you can run them side-by-side and see which piece of code performs better.
 
Unfortunately, this is not always a good measure.  Well written assembly language outperforms well written C++ code, but you lose a lot in maintainability which creates a big techncial debt load that is hard to offset as the application ages.  In contrast, higher level constructs make the code more brief and easier to understand, hence reducing technical cost.
 
Now, obviously in this case we're not talking two separate languages, we're comparing doing something manually in the language versus using a higher-order set of IEnumerable extensions that are in the System.Linq library.
 
Well, before we discuss any further, let's look at some sample code and the numbers.  First, let's take a look at the for loop and the LINQ expression.  This is just a simple find comparison:

   1: // find implemented via LINQ
   2: public static bool FindViaLinq(IEnumerable<int> list, int target)
   3: {
   4:     return list.Any(item => item == target);
   5: }
   6:  
   7:  
   8: // find implemented via standard iteration
   9: public static bool FindViaIteration(IEnumerable<int> list, int target)
  10: {
  11:     foreach (var i in list)
  12:     {
  13:         if (i == target)
  14:         {
  15:             return true;
  16:         }
  17:     }
  18:  
  19:     return false;
  20: }

Okay, looking at this from a maintainability point of view, the Linq expression is definitely more concise (8 lines down to 1) and is very readable in intention.  You don't have to actually analyze the behavior of the loop to determine what it's doing.
 
So let's take a look at performance metrics from 100,000 iterations of these methods on a List<int> of varying sizes filled with random data.  For this test, we fill a target array with 100,000 random integers and then run the exact same pseudo-random targets through both searches.

   1: List<T> On 100,000 Iterations
   2:  
   3: Method      Size     Total (ms)  Per Iteration (ms)  % Slower
   4:  
   5: Any         10       26          0.00046             30.00%
   6: Iteration   10       20          0.00023             -
   7: Any         100      116         0.00201             18.37%
   8: Iteration   100      98          0.00118             -
   9: Any         1000     1058        0.01853             16.78%
  10: Iteration   1000     906         0.01155             -
  11: Any         10,000   10,383      0.18189             17.41%
  12: Iteration   10,000   8843        0.11362             -
  13: Any         100,000  104,004     1.8297              18.27%
  14: Iteration   100,000  87,941      1.13163             -

The LINQ expression is running about 17% slower for average size collections and worse for smaller collections.  Presumably, this is due to the overhead of the state machine used to track the iterators for the yield returns in the LINQ expressions, which seems about right in a tight loop such as this.
 
So what about other LINQ expressions?  After all, Any() is one of the more trivial ones.  I decided to try the TakeWhile() algorithm using a Count() to get the position stopped like the sample Pete was using in his blog that Resharper refactored for him into LINQ:

   1: // Linq form
   2: public static int GetTargetPosition1(IEnumerable<int> list, int target)
   3: {
   4:     return list.TakeWhile(item => item != target).Count();
   5: }
   6:  
   7: // traditionally iterative form
   8: public static int GetTargetPosition2(IEnumerable<int> list, int target)
   9: {
  10:     int count = 0;
  11:  
  12:     foreach (var i in list)
  13:     {
  14:         if(i == target)
  15:         {
  16:             break;
  17:         }
  18:  
  19:         ++count;
  20:     }
  21:  
  22:     return count;
  23: }
  24:  

Once again, the LINQ expression is much shorter, easier to read, and should be easier to maintain over time, reducing the cost of technical debt.  So I ran these through the same test data:

   1: List<T> On 100,000 Iterations
   2:  
   3: Method      Size     Total (ms)  Per Iteration (ms)  % Slower
   4:     
   5: TakeWhile   10       41          0.00041             128%
   6: Iteration   10       18          0.00018             -
   7: TakeWhile   100      171         0.00171             88%
   8: Iteration   100      91          0.00091             -
   9: TakeWhile   1000     1604        0.01604             94%
  10: Iteration   1000     825         0.00825             -
  11: TakeWhile   10,000   15765       0.15765             92%
  12: Iteration   10,000   8204        0.08204             -
  13: TakeWhile   100,000  156950      1.5695              92%
  14: Iteration   100,000  81635       0.81635             -
Wow!  I expected some overhead due to the state machines iterators produce, but 90% slower?  That seems a little heavy to me.  So then I thought, well, what if TakeWhile() is not the right tool for the job?  The problem is TakeWhile returns each item for processing using yield return, whereas our for-loop really doesn't care about the item beyond using it as a stop condition to evaluate.

So what if that back and forth with the iterator state machine is the problem?  Well, we can quickly create an (albeit ugly) lambda that uses the Any() along with a count in a closure (if a LINQ guru knows a better way PLEASE let me know!), after all , this is more consistent with what we're trying to do, we're trying to find the first occurence of an item and halt once we find it, we just happen to be counting on the way.  This mostly matches Any().

   1: // a new method that uses linq but evaluates the count in a closure.
   2: public static int TakeWhileViaLinq2(IEnumerable<int> list, int target)
   3: {
   4:     int count = 0;
   5:     list.Any(item =>
   6:         {
   7:             if(item == target)
   8:             {
   9:                 return true;
  10:             }
  11:  
  12:             ++count;
  13:             return false;
  14:         });
  15:     return count;
  16: }

 
Now how does this one compare? 

   1: List<T> On 100,000 Iterations
   2:  
   3: Method         Size     Total (ms)  Per Iteration (ms)  % Slower
   4:  
   5: TakeWhile      10       41          0.00041             128%
   6: Any w/Closure  10       23          0.00023             28%
   7: Iteration      10       18          0.00018             -
   8: TakeWhile      100      171         0.00171             88%
   9: Any w/Closure  100      116         0.00116             27%
  10: Iteration      100      91          0.00091             -
  11: TakeWhile      1000     1604        0.01604             94%
  12: Any w/Closure  1000     1101        0.01101             33%
  13: Iteration      1000     825         0.00825             -
  14: TakeWhile      10,000   15765       0.15765             92%
  15: Any w/Closure  10,000   10802       0.10802             32%
  16: Iteration      10,000   8204        0.08204             -
  17: TakeWhile      100,000  156950      1.5695              92%
  18: Any w/Closure  100,000  108378      1.08378             33%
  19: Iteration      100,000  81635       0.81635             -

Much better!  It seems that the overhead of TakeAny() returning each item and updating the state in the state machine is drastically reduced by using Any() since Any() iterates forward until it finds the value we're looking for -- for the task we're attempting to do.
 
So the lesson there is, make sure when you use a LINQ expression you're choosing the best expression for the job, because if you're doing more work than you really need, you'll have a slower algorithm.  But this is true of any choice of algorithm or collection in general.
   
Even with the Any() with the count in the closure it is still about 30% slower, but let's consider that angle carefully.  For a list of 100,000 items, it was the difference between 1.01 ms and 0.82 ms roughly in a List<T>.  That's really not that bad at all in the grand scheme of things.  Even running at 90% slower with TakeWhile(), for the vast majority of my projects, an extra millisecond to save potential errors in the long term and improve maintainability is a small price to pay.  And if your typical list is 1000 items or less we're talking only microseconds worth of difference.
 
It's like they say: 90% of your performance bottlenecks are in 2% of your code, so over-optimizing almost never pays off.  So personally, I'll take the LINQ expression wherever I can because they will be easier to read and maintain (thus reducing technical debt) and I can rely on Microsoft's development to have coded and unit tested those algorithm fully for me instead of relying on a developer to code the loop logic correctly.
 
If something's 90% slower, yes, it's worth keeping in mind, but it's really not until you start get magnitudes-of-order slower (10x, 100x, 1000x) that alarm bells should really go off.  And if I ever do need that last millisecond of performance?  Well then I'll optimize JUST THAT problem spot.  To me it's worth it for the readability, speed-to-market, and maintainability.

 

Technorati Tags: , , ,

Print | posted on Friday, April 23, 2010 6:54 AM | Filed Under [ My Blog C# Software .NET Fundamentals ]

Powered by: