title: read/write to large array using large loop - execution time concerns
body: <p>So recently I ran into a problem that I thought was interesting and I couldn't fully explain. I've highlighted the nature of the problem in the following code:</p>
  <pre><code>#include &lt;cstring&gt;
  #include &lt;chrono&gt; 
  #include &lt;iostream&gt; 
  
  #define NLOOPS 10
  
  void doWorkFast(int total, int *write, int *read)
  {
      for (int j = 0; j &lt; NLOOPS; j++) {
          for (int i = 0; i &lt; total; i++) {
              write[i] = read[i] + i;
          }
      }
  }
  
  void doWorkSlow(int total, int *write, int *read, int innerLoopSize)
  {
      for (int i = 0; i &lt; NLOOPS; i++) {
          for (int j = 0; j &lt; total/innerLoopSize; j++) {
              for (int k = 0; k &lt; innerLoopSize; k++) {
                  write[j*k + k] = read[j*k + k] + j*k + k;
              }
          }
      }
  }
  
  
  int main(int argc, char *argv[])
  {
      int n = 1000000000;
      
      int *heapMemoryWrite = new int[n];
      int *heapMemoryRead = new int[n];
      
  
      for (int i = 0; i &lt; n; i++)
      {
          heapMemoryRead[i] = 1;
      }
  
      std::memset(heapMemoryWrite, 0, n * sizeof(int));   
  
      auto start1 = std::chrono::high_resolution_clock::now();
  
      doWorkFast(n,heapMemoryWrite, heapMemoryRead);
      
  
      auto finish1 = std::chrono::high_resolution_clock::now();  
      auto duration1 = std::chrono::duration_cast&lt;std::chrono::microseconds&gt;(finish1 - start1); 
  
      for (int i = 0; i &lt; n; i++)
      {
          heapMemoryRead[i] = 1;
      }
  
      std::memset(heapMemoryWrite, 0, n * sizeof(int));
  
      auto start2 = std::chrono::high_resolution_clock::now();
      
      doWorkSlow(n,heapMemoryWrite, heapMemoryRead, 10);
  
  
      auto finish2 = std::chrono::high_resolution_clock::now();  
      auto duration2 = std::chrono::duration_cast&lt;std::chrono::microseconds&gt;(finish2 - start2); 
  
      std::cout &lt;&lt; &quot;Small inner loop:&quot; &lt;&lt; duration1.count() &lt;&lt; &quot; microseconds.\n&quot; &lt;&lt; 
                   &quot;Large inner loop:&quot; &lt;&lt; duration2.count() &lt;&lt; &quot; microseconds.&quot; &lt;&lt; std::endl; 
  
      delete[] heapMemoryWrite;
      delete[] heapMemoryRead;
  }
  </code></pre>
  <p>Looking at the two doWork* functions, for every iteration, we are reading the same addresses adding the same value and writing to the same addresses. I understand that in the <code>doWorkSlow</code> implementation, we are doing one or two more operations to resolve <code>j*k + k</code>, however, I think it's reasonably safe to assume that relative to the time it takes to do the load/stores for memory read and write, the time contribution of these operations is negligible.</p>
  <p>Nevertheless, <code>doWorkSlow</code> takes about twice as long (46.8s) compared to <code>doWorkFast</code> (25.5s) on my i7-3700 using <code>g++ --version</code> 7.5.0. While things like cache prefetching and branch prediction come to mind, I don't have a great explanation as to why <code>doWorkFast</code> is much faster than <code>doWorkSlow</code>. Does anyone have insight?</p>
  <p>Thanks</p>