title: Does C# store arrays larger than 512 longs (4096 bytes) differently?
body: <p>I did some benchmarks with collection types implemented in the .NET Framework.</p>
  
  <p>From the Reference Source I know that <code>List&lt;T&gt;</code> uses an array to store contents. To avoid resizing the array with every insertion, the <a href="http://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,9808f1f5ef16c436" rel="noreferrer">array length gets doubled</a> every time the free space runs out.</p>
  
  <p><a href="https://i.stack.imgur.com/BCcxL.png" rel="noreferrer"><img src="https://i.stack.imgur.com/BCcxL.png" alt="Size - Time diagram for &lt;code&gt;List&lt;T&gt;.Add&lt;/code&gt;"></a></p>
  
  <p>Now my benchmark would insert random <code>long</code> values into a <code>List</code> (see the figure above for the size - time - graph). There are obvious "lag spikes" at lists sizes like 128 or 256 where the internal array has to be re-allocated. But at a size of 512 (and 128, though?), there seems to be a really big lag and the time it takes to insert one item is durably increased.</p>
  
  <p>In my understanding, the graph should be strictly constant, except the occasions where the internal array needs to be reallocated. Are there any reasons for this behavior, perhaps related to  the CLR or Windows memory management / memory fragmentation?</p>
  
  <p>The benchmarks were executed as 64bit application on a Windows 10 / i7-3630QM machine (source code as seen below). Because one single add operation wouldn't be measurable, I create 1000 lists and add one item each for every list size.</p>
  
  <pre><code>for (int i = 1; i &lt;= MaxCollectionSize; i++)
  {
      // Reset time measurement
      TestContainer.ResetSnapshot();
  
      // Enable time measurement
      TestContainer.BeginSnapshot();
      // Execute one add operation on 1000 lists each
      ProfileAction.Invoke(TestContainer);
      TestContainer.EndSnapShot();
  
      double elapsedMilliseconds = (TestContainer.GetElapsedMilliSeconds() / (double)Stopwatch.Frequency) * 1000;
      // ...
  }
  </code></pre>
  
  <p><strong>EDIT</strong>: I double checked my results and yes, they are reproducible. I increased the number of collections tested from 1000 to 10000, and the result is now much more smooth (see image below). The spikes from resizing the internal array are now clearly visible. And yet the steps in the graph remain - this is a divergence with the expected O(1) complexity that an array insert should be if you ignore the resizing.</p>
  
  <p>I also tried to trigger a GC collection before each <code>Add</code> operation and the graph remained exactly the same.</p>
  
  <p>As for the concerns about the creation of delegate objects: All my delegates (like <code>ProfileAction</code>) are instance properties that remain assigned during one complete test cycle, in this case 10000 lists with 1000 add operations each.</p>
  
  <p><a href="https://i.stack.imgur.com/U1QOS.png" rel="noreferrer"><img src="https://i.stack.imgur.com/U1QOS.png" alt="enter image description here"></a></p>