title: How not to mess up the cache when working on some long vectors in memory?
body: <p><strong>Premise</strong></p>
  
  <p>I want to do some kind of computation involving <code>k</code> long vectors of data (each of length <code>n</code>), which I receive in main memory, and write some kind of result back to main memory. For simplicity suppose also that the computation is merely</p>
  
  <pre><code>for(i = 0; i &lt; n; i++)
      v_out[i] = foo(v_1[i],v_2[i], ... ,v_k[i])
  </code></pre>
  
  <p>or perhaps</p>
  
  <pre><code>for(i = 0; i &lt; n; i++)
      v_out[i] = bar_k(...bar_2(bar_1(v_1[i]),v_2[i]), ... ),v_k[i])
  </code></pre>
  
  <p>(this is not code, it's pseudocode.) <code>foo()</code> and <code>bar_i()</code> functions have no side-effects. <code>k</code> is constant (known at compile-time), <code>n</code> is known only right before this computation occurs (and it is <em>relatively big</em> - at least a few times larger than the entire L2 cache size and maybe more).</p>
  
  <p>Suppose I am on an single thread on a single core of an x86_64 processor (Intel, or AMD, or what-have-you; the choice does matter, probably). Finally, suppose <code>foo()</code> (resp. <code>bar_i()</code>) is not an intensive computation, i.e. the time to read data from memory and write it back is significant or even dominant relative to the <code>n</code> (resp. <code>k</code>x<code>n</code>) invocations of <code>foo()</code> (resp. <code>bar_i()</code>). </p>
  
  <p><strong>Question</strong></p>
  
  <p>How do I arrange this computation, so as to avoid:</p>
  
  <ul>
  <li>The data from one input vector clearing out cached data for another vector.</li>
  <li>Input vector data clearing out cached output vector data.</li>
  <li>Intermediary results of <code>bar_j(...bar_1(v_1[i])...)</code> remaining in registers or L1 cache if there's enough capacity to hold them there until  the data for v_{j+1}[i] ... v_k[i] arrives and allows us to complete the computation. Same for L2.</li>
  <li>The L1 cache lines of the output vectors being cleared while we intend to continue working on elements in that cache line. Same for L2.</li>
  <li>Under-utilization of memory bandwidth.</li>
  <li>core idle time, to the extent possible.</li>
  <li>Write-read-write-read-write sequences on v_out (which might be very expensive if those writes need to be updated into main memory; the motivation here is that it might be tempting to read just one vector, update the output and repeat).</li>
  </ul>
  
  <p><strong>Notes:</strong></p>
  
  <ul>
  <li>Any rearrangement of the input data counts towards the total computation time. The vectors will not be re-used in the alternate arrangement so it's basically a waste of time.</li>
  <li>If it makes things easier for you to assume alignment, or lack of alignment, that's fine, just say so.</li>
  <li>Computing with the bar_i functions allows more flexibility with the access patters, but creates additional challenges w.r.t. the caching of v_out values.</li>
  </ul>