title: Why does using the same cache-line from multiple threads not cause serious slowdown?
body: <p>Look at this snippet:</p>
  
  <pre><code>#include &lt;atomic&gt;
  #include &lt;thread&gt;
  
  typedef volatile unsigned char Type;
  // typedef std::atomic_uchar Type;
  
  void fn(Type *p) {
      for (int i=0; i&lt;500000000; i++) {
          (*p)++;
      }
  }
  
  int main() {
      const int N = 4;
  
      std::thread thr[N];
      alignas(64) Type buffer[N*64];
  
      for (int i=0; i&lt;N; i++) {
          thr[i] = std::thread(&amp;fn, &amp;buffer[i*1]);
      }
  
      for (int i=0; i&lt;N; i++) {
          thr[i].join();
      }
  
  }
  </code></pre>
  
  <p>This little program increments four adjacent bytes a lot of times from four different threads. Before, I used the rule: don't use the same cache line from different threads, as cache line sharing is bad. So I expected that a four thread version (<code>N=4</code>) is much slower than a one thread version (<code>N=1</code>).</p>
  
  <p>However, these are my measurements (on a Haswell CPU):</p>
  
  <ul>
  <li>N=1: 1 sec</li>
  <li>N=4: 1.2 sec</li>
  </ul>
  
  <p>So <code>N=4</code> is not much slower. If I use different cache lines (replace <code>*1</code> with <code>*64</code>), then <code>N=4</code> becomes a little faster: 1.1 sec.</p>
  
  <p>The same measurements for atomic access (swap the comments at <code>typedef</code>), same cache line:</p>
  
  <ul>
  <li>N=1: 3.1 sec</li>
  <li>N=4: 48 sec</li>
  </ul>
  
  <p>So the <code>N=4</code> case is much slower (as I expected). If different cache lines used, then <code>N=4</code> has similar performance as <code>N=1</code>: 3.3 sec.</p>
  
  <p>I don't understand the reason behind these results. Why don't I get a serious slowdown the non-atomic, <code>N=4</code> case? Four cores have the same memory in their caches, so they must synchronize them somehow, don't they? How can they run almost perfectly parallel? Why just the atomic case gets a serious slowdown?</p>
  
  <hr>
  
  <p>I think I need to understand how memory gets updated in this case. In the beginning, no cores have <code>buffer</code> in their caches. After one <code>for</code> iteration (in <code>fn</code>), all 4 cores have <code>buffer</code> in their cache-lines, but each core writes a different byte. How do these cache-lines get synchronized (in the non-atomic case)? How does the cache know, which <em>byte</em> is dirty? Or is there some other mechanism to handle this case? Why is this mechanism a lot cheaper (actually, it is almost free) than the atomic-one?</p>