title: Surprising performance differences: List.Constains,SortedList.ContainsKey,DataRowCollection.Contains,DataTable.Select, DataTable.FindBy
body: <p>Originally i wanted to ask for the fastest way to query a Datatable for a special row.</p>
  
  <p>I have tested 5 different methods for their performance with a surprising(for me) result.</p>
  
  <p>Background:
  I have created a View in a MS Sql-Server 2005 Database. This view has current a total count of 6318 rows. Because i must check very often if a given id exists in this view, i wondered what is the most efficient way to do. I created a DataAdapter in a strongly typed dataset which returns all rows and fills a Datatable.
  My first approach was to create a shared generic List(of Int32) and fill it with the ID's from the view once on Application start. Then use <a href="http://msdn.microsoft.com/en-us/library/bhkz42b3%28VS.80%29.aspx" rel="nofollow noreferrer">List.Contains</a> to check if the current ID is in this List. Because all rows are distinct i wondered if its not faster to use a SortedList and its <a href="http://msdn.microsoft.com/en-us/library/system.collections.sortedlist.containskey.aspx" rel="nofollow noreferrer">ContainsKey</a>-metod. 
  Then i checked also the performance of direct access to the Datable with its <a href="http://msdn.microsoft.com/en-us/library/system.data.datatable.select%28VS.80%29.aspx" rel="nofollow noreferrer">Select-Method</a>, its automatically generated(when column is defined as primary-key) <a href="http://msdn.microsoft.com/en-us/library/y06xa2h1%28VS.80%29.aspx" rel="nofollow noreferrer">FindBy-method</a> and last but not least the <a href="http://msdn.microsoft.com/en-us/library/system.data.datarowcollection.contains.aspx" rel="nofollow noreferrer">DatarowCollection.Contains</a>-Method.
  So i have 5 Methods to check if my ID is in that View(or mapped List/SortedList). </p>
  
  <p>I measured their performance with the <a href="http://msdn.microsoft.com/en-us/library/system.diagnostics.stopwatch.aspx" rel="nofollow noreferrer">System.Diagnostics.StopWatch</a> and got some interesting results. I thought the SortedList.ContainsKey must be faster than the List.Contains because they're distinct and sorted but the opposite is true.
  But the most surprising for me was that the DataRowCollection.Contains-Method(that i first had forgotten) is by far the fastest. It is even 50 times faster than the dataTable.FindBy-method.</p>
  
  <ol>
  <li>What caused these differences?</li>
  <li>Have i forgotten a better way?</li>
  <li>Is my measurement method correct(i think i better should loop them and take that values)?</li>
  <li>Are the values transferrable or dependent on the size of the Datatable/Collection?</li>
  <li>After my update(1000000 iterations) ContainsKey is the fastest. Is this because i always check for the same id or in general? Is there some kind of SortedList without the overhead of a Dictionary's KeyValue-Pair?</li>
  </ol>
  
  <p><strong>Results</strong> [for 1000000 iterations*]</p>
  
  <ul>
  <li>Timespan 1 = <a href="http://msdn.microsoft.com/en-us/library/system.collections.sortedlist.containskey.aspx" rel="nofollow noreferrer">SortedList.ContainsKey</a> = Ø 0.65634 [<strong>238.1095</strong>] ms</li>
  <li>Timespan 2 = <a href="http://msdn.microsoft.com/en-us/library/bhkz42b3%28VS.80%29.aspx" rel="nofollow noreferrer">List.Contains</a> = Ø 0.06802 [<strong>57045.37955</strong>] ms</li>
  <li>Timespan 3 = <a href="http://msdn.microsoft.com/en-us/library/y06xa2h1%28VS.80%29.aspx" rel="nofollow noreferrer">DataTable.FindByIdData</a>(auto-generated method) = Ø 0.31580 [<strong>1542.62345</strong>] ms</li>
  <li>Timespan 4 = <a href="http://msdn.microsoft.com/en-us/library/system.data.datatable.select%28VS.80%29.aspx" rel="nofollow noreferrer">DataTable.Select</a> = Ø 0.27790 [<strong>26029.39635</strong>] ms</li>
  <li><p>Timespan 5 = <a href="http://msdn.microsoft.com/en-us/library/system.data.datarowcollection.contains.aspx" rel="nofollow noreferrer">DataRowCollection.Contains</a> = Ø 0.00638 [<strong>1202.79735</strong>] ms</p>
  
  <pre><code>1.)
  Timespan 1: 0,6913 ms
  Timespan 2: 0,1053 ms
  Timespan 3: 0,3279 ms
  Timespan 4: 0,1002 ms
  Timespan 5: 0,0056 ms
  
  2.)
  Timespan 1: 0,6405 ms
  Timespan 2: 0,0588 ms
  Timespan 3: 0,3112 ms
  Timespan 4: 0,3872 ms
  Timespan 5: 0,0067 ms
  
  3.)
  Timespan 1: 0,6502 ms
  Timespan 2: 0,0588 ms
  Timespan 3: 0,3092 ms
  Timespan 4: 0,1268 ms
  Timespan 5: 0,007 ms
  
  4.)
  Timespan 1: 0,6504 ms
  Timespan 2: 0,0586 ms
  Timespan 3: 0,3092 ms
  Timespan 4: 0,3893 ms
  Timespan 5: 0,0063 ms
  
  5.)
  Timespan 1: 0,6493 ms
  Timespan 2: 0,0586 ms
  Timespan 3: 0,3215 ms
  Timespan 4: 0,386 ms
  Timespan 5: 0,0063 ms
  
  
  
  Timespan 1: 0,6913 0,6405 0,6502 0,6504 0,6493 = Ø 0,65634
  Timespan 2: 0,1053 0,0588 0,0588 0,0586 0,0586 = Ø 0,06802
  Timespan 3: 0,3279 0,3112 0,3092 0,3092 0,3215 = Ø 0,31580
  Timespan 4: 0,1002 0,3872 0,1268 0,3893 0,3860 = Ø 0,27790
  Timespan 5: 0,0056 0,0067 0,0070 0,0063 0,0063 = Ø 0,00638
  </code></pre></li>
  </ul>
  
  <p>And for the sake of completeness part of the <strong>VB.Net source</strong>:          </p>
  
  <pre><code>Dim applies As Boolean
  Dim clock As New System.Diagnostics.Stopwatch
  
  clock.Start()
  For i As Int32 = 1 To 1000000
      applies = sortedListAC17NextClaims.ContainsKey(myClaim.idData)
  Next
  clock.Stop()
  Dim timeSpan1 As String = "Timespan 1: " &amp; clock.Elapsed.TotalMilliseconds.ToString &amp; " ms"
  
  clock.Reset()
  clock.Start()
  For i As Int32 = 1 To 1000000
      applies = listAC17NextClaims.Contains(myClaim.idData)
  Next
  clock.Stop()
  Dim timeSpan2 As String = "Timespan 2: " &amp; clock.Elapsed.TotalMilliseconds.ToString &amp; " ms"
  
  clock.Reset()
  clock.Start()
  For i As Int32 = 1 To 1000000
      applies = Not MyDS.AC17NextClaims.FindByIdData(myClaim.idData) Is Nothing
  Next
  clock.Stop()
  Dim timeSpan3 As String = "Timespan 3: " &amp; clock.Elapsed.TotalMilliseconds.ToString &amp; " ms"
  
  clock.Reset()
  clock.Start()
  For i As Int32 = 1 To 1000000
      applies = MyDS.AC17NextClaims.Select("idData=" &amp; myClaim.idData).Length &gt; 0
  Next
  clock.Stop()
  Dim timeSpan4 As String = "Timespan 4: " &amp; clock.Elapsed.TotalMilliseconds.ToString &amp; " ms"
  
  clock.Reset()
  clock.Start()
  For i As Int32 = 1 To 1000000
      applies = MyDS.AC17NextClaims.Rows.Contains(myClaim.idData)
  Next
  clock.Stop()
  Dim timeSpan5 As String = "Timespan 5: " &amp; clock.Elapsed.TotalMilliseconds.ToString &amp; " ms"
  </code></pre>
  
  <ul>
  <li><p><strong>UPDATE:</strong>
  I have changed my results and the source above. In squared brackets are the values for 1000000 iterations. Now the result is completely different. The fastest method now is definitely is the ContainsKey of the SortedList.</p></li>
  <li><p><strong>UPDATE 2:</strong>
  I forgot the alternative to use <a href="http://msdn.microsoft.com/en-us/library/3f90y839.aspx" rel="nofollow noreferrer">List.BinarySearch</a>.
  This seems to be fastest for me:</p>
  
  <pre><code>clock.Start()
  For i As Int32 = 1 To 1000000
      applies = listAC17NextClaims.BinarySearch(myClaim.idData) &gt; -1
  Next
  clock.Stop()
  </code></pre>
  
  <p>needs only 219.1805 ms to perform 1000000 iterations and hence is the fastest without the overhead of a SortedList-KeyValue-Pair.
  I can use it without to sort the list because the DataAdapter filled the datatable with an Order By clause.</p></li>
  </ul>