title: foreach + break vs linq FirstOrDefault performance difference
body: <p>I have two classes that perform date date range data fetching for particular days.</p>
  
  <pre><code>public class IterationLookup&lt;TItem&gt;
  {
      private IList&lt;Item&gt; items = null;
  
      public IterationLookup(IEnumerable&lt;TItem&gt; items, Func&lt;TItem, TKey&gt; keySelector)
      {
          this.items = items.OrderByDescending(keySelector).ToList();
      }
  
      public TItem GetItem(DateTime day)
      {
          foreach(TItem i in this.items)
          {
             if (i.IsWithinRange(day))
             {
                 return i;
             }
          }
          return null;
      }
  }
  
  
  public class LinqLookup&lt;TItem&gt;
  {
      private IList&lt;Item&gt; items = null;
  
      public IterationLookup(IEnumerable&lt;TItem&gt; items, Func&lt;TItem, TKey&gt; keySelector)
      {
          this.items = items.OrderByDescending(keySelector).ToList();
      }
  
      public TItem GetItem(DateTime day)
      {
          return this.items.FirstOrDefault(i =&gt; i.IsWithinRange(day));
      }
  }
  </code></pre>
  
  <p>Then I do speed tests which show that Linq version is about <strong>5 times slower</strong>. This would make sense when I would store items locally without enumerating them using <code>ToList</code>. This would make it much slower, because with every call to <code>FirstOrDefault</code>, linq would also perform <code>OrderByDescending</code>. But that's not the case so I don't really know what's going on. <strong>Linq should perform very similar to iteration.</strong></p>
  
  <h2>This is the code excerpt that measures my timings</h2>
  
  <pre><code>IList&lt;RangeItem&gt; ranges = GenerateRanges(); // returns List&lt;T&gt;
  
  var iterLookup = new IterationLookup&lt;RangeItems&gt;(ranges, r =&gt; r.Id);
  var linqLookup = new LinqLookup&lt;RangeItems&gt;(ranges, r =&gt; r.Id);
  
  Stopwatch timer = new Stopwatch();
  
  timer.Start();
  for(int i = 0; i &lt; 1000000; i++)
  {
      iterLookup.GetItem(GetRandomDay());
  }
  timer.Stop();
  // display elapsed time
  
  timer.Restart();
  for(int i = 0; i &lt; 1000000; i++)
  {
      linqLookup.GetItem(GetRandomDay());
  }
  timer.Stop();
  // display elapsed time
  </code></pre>
  
  <p>Why do I know it should perform better? Because when I write a very similar code without using these lookup classes, Linq performs very similar to <code>foreach</code> iterations...</p>
  
  <pre><code>// continue from previous code block
  
  // items used by both order as they do in classes as well
  IList&lt;RangeItem&gt; items = ranges.OrderByDescending(r =&gt; r.Id).ToList();
  
  timer.Restart();
  for(int i = 0; i &lt; 1000000; i++)
  {
      DateTime day = GetRandomDay();
      foreach(RangeItem r in items)
      {
          if (r.IsWithinRange(day))
          {
              // RangeItem result = r;
              break;
          }
      }
  }    
  timer.Stop();
  // display elapsed time
  
  timer.Restart();
  for(int i = 0; i &lt; 1000000; i++)
  {
     DateTime day = GetRandomDay();
     items.FirstOrDefault(i =&gt; i.IsWithinRange(day));
  }
  timer.Stop();
  // display elapsed time
  </code></pre>
  
  <p>This is by my opinion highly similar code. <code>FirstOrDefault</code> as much as I know also iterate for only as long until it gets to a valid item or until it reaches the end. And this is somehow the same as <code>foreach</code> with <code>break</code>.</p>
  
  <p>But even iteration class performs worse than my simple <code>foreach</code> iteration loop which is also a mystery because all the overhead it has is the call to a method within a class compared to direct access.</p>
  
  <h2>Question</h2>
  
  <p>What am I doing wrong in my LINQ class that it performs so very slow?<br>
  What am I doing wrong in my Iteration class so it performs twice as slow as direct <code>foreach</code> loop?</p>
  
  <h2>Which times are being measured?</h2>
  
  <p>I do these steps:</p>
  
  <ol>
  <li>Generate ranges (as seen below in results)</li>
  <li>Create object instances for IterationLookup, LinqLookup (and my optimized date range class BitCountLookup which is not part of discussion here)</li>
  <li>Start timer and execute 1 million lookups on random days within maximum date range (as seen in results) by using previously instantiated IterationLookup class.</li>
  <li>Start timer and execute 1 million lookups on random days within maximum date range (as seen in results) by using previously instantiated LinqLookup class.</li>
  <li>Start timer and execute 1 million lookups (6 times) using manual foreach+break loops and Linq calls.</li>
  </ol>
  
  <p>As you can see <strong>object instantiation is not measured</strong>.</p>
  
  <h2>Appendix I: Results over million lookups</h2>
  
  <p>Ranges displayed in these results don't overlap, which should make both approaches even more similar in case LINQ version doesn't break loop on successful match (which it highly likely does).</p>
  
  <pre>
  Generated Ranges:
  
  ID Range        000000000111111111122222222223300000000011111111112222222222
                  123456789012345678901234567890112345678901234567890123456789
  09 22.01.-30.01.                     |-------|
  08 14.01.-16.01.             |-|
  07 16.02.-19.02.                                              |--|
  06 15.01.-17.01.              |-|
  05 19.02.-23.02.                                                 |---|
  04 01.01.-07.01.|-----|
  03 02.01.-10.01. |-------|
  02 11.01.-13.01.          |-|
  01 16.01.-20.01.               |---|
  00 29.01.-06.02.                            |-------|
  
  Lookup classes...
  
  - Iteration: 1028ms
  <b>- Linq: 4517ms   !!! THIS IS THE PROBLEM !!!</b>
  - BitCounter: 401ms
  
  Manual loops...
  
  - Iter: 786ms
  - Linq: 981ms
  - Iter: 787ms
  - Linq: 996ms
  - Iter: 787ms
  - Linq: 977ms
  - Iter: 783ms
  - Linq: 979ms
  </pre>
  
  <h2>Appendix II: GitHub:Gist code to test for yourself</h2>
  
  <p>I've put up a Gist so you can get the full code yourself and see what's going on. Create a <strong>Console</strong> application and copy <em>Program.cs</em> into it an add other files that are part of this gist.</p>
  
  <p>Grab it <a href="https://gist.github.com/1385081" rel="nofollow noreferrer">here</a>.</p>
  
  <h2>Appendix III: Final thoughts and measurement tests</h2>
  
  <p>The most problematic thing was of course LINQ implementatino that was awfully slow. Turns out that this has all to do with delegate compiler optimization. <a href="https://stackoverflow.com/q/8225900/75642">LukeH provided the best and most usable solution</a> that actually made me try different approaches to this. I've tried various different approaches in the <code>GetItem</code> method (or <code>GetPointData</code> as it's called in Gist):</p>
  
  <ol>
  <li><p>the usual way that most of developers would do (and is implemented in Gist as well and wasn't updated after results revealed this is not the best way of doing it):</p>
  
  <pre><code>return this.items.FirstOrDefault(item =&gt; item.IsWithinRange(day));
  </code></pre></li>
  <li><p>by defining a local predicate variable:</p>
  
  <pre><code>Func&lt;TItem, bool&gt; predicate = item =&gt; item.IsWithinRange(day);
  return this.items.FirstOrDefault(predicate);
  </code></pre></li>
  <li><p>local predicate builder:</p>
  
  <pre><code>Func&lt;DateTime, Func&lt;TItem, bool&gt;&gt; builder = d =&gt; item =&gt; item.IsWithinRange(d);
  return this.items.FirstOrDefault(builder(day));
  </code></pre></li>
  <li><p>local predicate builder and local predicate variable:</p>
  
  <pre><code>Func&lt;DateTime, Func&lt;TItem, bool&gt;&gt; builder = d =&gt; item =&gt; item.IsWithinRange(d);
  Func&lt;TItem, bool&gt; predicate = builder(day);
  return this.items.FirstOrDefault(predicate);
  </code></pre></li>
  <li><p>class level (static or instance) predicate builder:</p>
  
  <pre><code>return this.items.FirstOrDefault(classLevelBuilder(day));
  </code></pre></li>
  <li><p>externally defined predicate and provided as method parameter</p>
  
  <pre><code>public TItem GetItem(Func&lt;TItem, bool&gt; predicate)
  {
      return this.items.FirstOrDefault(predicate);
  }
  </code></pre>
  
  <p>when executing this method I also took two approaches:</p>
  
  <ol>
  <li><p>predicate provided directly at method call within <code>for</code> loop:</p>
  
  <pre><code>for (int i = 0; i &lt; 1000000; i++)
  {
      linqLookup.GetItem(item =&gt; item.IsWithinRange(GetRandomDay()));
  }
  </code></pre></li>
  <li><p>predicate builder defined outside <code>for</code> loop:</p>
  
  <pre><code>Func&lt;DateTime, Func&lt;Ranger, bool&gt;&gt; builder = d =&gt; r =&gt; r.IsWithinRange(d);
  for (int i = 0; i &lt; 1000000; i++)
  {
      linqLookup.GetItem(builder(GetRandomDay()));
  }
  </code></pre></li>
  </ol></li>
  </ol>
  
  <h3>Results - what performs best</h3>
  
  <p>For comparison when using iteration class, it takes it approx. <strong>770ms</strong> to execute 1 million lookups on randomly generated ranges.</p>
  
  <ol>
  <li><h1>3 local predicate builder turns out to be best compiler optimized so it performs almost as fast as usual iterations. <strong>800ms</strong>.</h1></li>
  <li><h1>6.2 predicate builder defined outside <code>for</code> loop: <strong>885ms</strong></h1></li>
  <li><h1>6.1 predicate defined within <code>for</code> loop: <strong>1525ms</strong></h1></li>
  <li>all others took somewhere between <strong>4200ms - 4360ms</strong> and are thus considered unusable.</li>
  </ol>
  
  <p>So whenever you use a predicate in externally frequently callable method, define a builder and execute that. This will yield best results.</p>
  
  <p>The biggest surprise to me about this is that delegates (or predicates) may be this much time consuming.</p>