title: Reason for collapse of memory bandwidth when 2KB of data is cached in L1-cache
body: <p>In a self-educational project I measure the bandwidth of the memory with help of the following code (here paraphrased, the whole code follows at the end of the question):</p>
  
  <pre><code>unsigned int doit(const std::vector&lt;unsigned int&gt; &amp;mem){
     const size_t BLOCK_SIZE=16;
     size_t n = mem.size();
     unsigned int result=0;
     for(size_t i=0;i&lt;n;i+=BLOCK_SIZE){           
               result+=mem[i];
     }
     return result;
  }
  
  //... initialize mem, result and so on
  int NITER = 200; 
  //... measure time of
     for(int i=0;i&lt;NITER;i++)
         resul+=doit(mem)
  </code></pre>
  
  <p><code>BLOCK_SIZE</code> is choosen in such a way, that a whole 64byte cache line is fetched per single integer-addition. My machine (an Intel-Broadwell) needs about 0.35 nanosecond per integer-addion, so the code above could saturate a bandwith as high as 182GB/s (this value is just an upper bound and is probably quite off, what is important is the ratio of bandwidths for different sizes). The code is compiled with <code>g++</code> and <code>-O3</code>.</p>
  
  <p>Varying the size of the vector, I can observe expected bandwidths for L1(*)-, L2-, L3-caches and the RAM-memory:</p>
  
  <p><a href="https://i.stack.imgur.com/5Uyr5.png" rel="noreferrer"><img src="https://i.stack.imgur.com/5Uyr5.png" alt="enter image description here"></a></p>
  
  <p>However, there is an effect I'm really struggling to explain: the collapse of the measured bandwidth of L1-cache for sizes around 2 kB, here in somewhat higher resolution:</p>
  
  <p><a href="https://i.stack.imgur.com/5Y6YX.png" rel="noreferrer"><img src="https://i.stack.imgur.com/5Y6YX.png" alt="enter image description here"></a></p>
  
  <p>I could reproduce the results on all machines I have access to (which have Intel-Broadwell and Intel-Haswell processors). </p>
  
  <p><strong>My question:</strong> What is the reason for the performance-collapse for memory-sizes around 2 KB?</p>
  
  <p>(*) I hope I understand correctly, that for L1-cache not 64 bytes but only 4 bytes per addition are read/transfered (there is no further faster cache where a cache line must be filled), so the plotted bandwidth for L1 is only the upper limit and not the badwidth itself.</p>
  
  <p><strong>Edit</strong>: When the step size in the inner for-loop is chosen to be </p>
  
  <ul>
  <li>8 (instead of 16) the collapse happens for 1KB </li>
  <li>4 (instead of 16) the collapse happens for 0.5KB</li>
  </ul>
  
  <p>i.e. when the inner loop consists of about 31-35 steps/reads. That means the collapse isn't due to the memory-size but due to the number of steps in the inner loop.</p>
  
  <p>It can be explained with branch misses as shown in <a href="https://stackoverflow.com/a/53754136/5769463">@user10605163's great answer</a>.</p>
  
  <hr>
  
  <p>Listing for reproducing the results</p>
  
  <p><code>bandwidth.cpp</code>:</p>
  
  <pre><code>#include &lt;vector&gt;
  #include &lt;chrono&gt;
  #include &lt;iostream&gt;
  #include &lt;algorithm&gt;
  
  
  //returns minimal time needed for one execution in seconds:
  template&lt;typename Fun&gt;
  double timeit(Fun&amp;&amp; stmt, int repeat, int number)
  {  
     std::vector&lt;double&gt; times;
     for(int i=0;i&lt;repeat;i++){
         auto begin = std::chrono::high_resolution_clock::now();
         for(int i=0;i&lt;number;i++){
            stmt();
         }
         auto end = std::chrono::high_resolution_clock::now();
         double time = std::chrono::duration_cast&lt;std::chrono::nanoseconds&gt;(end-begin).count()/1e9/number;
         times.push_back(time);
     }
     return *std::min_element(times.begin(), times.end());
  }
  
  
  const int NITER=200;
  const int NTRIES=5;
  const size_t BLOCK_SIZE=16;
  
  
  struct Worker{
     std::vector&lt;unsigned int&gt; &amp;mem;
     size_t n;
     unsigned int result;
     void operator()(){
          for(size_t i=0;i&lt;n;i+=BLOCK_SIZE){           
               result+=mem[i];
          }
     }
  
     Worker(std::vector&lt;unsigned int&gt; &amp;mem_):
         mem(mem_), n(mem.size()), result(1)
     {}
  };
  
  double PREVENT_OPTIMIZATION=0.0;
  
  
  double get_size_in_kB(int SIZE){
     return SIZE*sizeof(int)/(1024.0);
  }
  
  double get_speed_in_GB_per_sec(int SIZE){
     std::vector&lt;unsigned int&gt; vals(SIZE, 42);
     Worker worker(vals);
     double time=timeit(worker, NTRIES, NITER);
     PREVENT_OPTIMIZATION+=worker.result;
     return get_size_in_kB(SIZE)/(1024*1024)/time;
  }
  
  
  int main(){
  
     int size=BLOCK_SIZE*16;
     std::cout&lt;&lt;"size(kB),bandwidth(GB/s)\n";
     while(size&lt;10e3){
         std::cout&lt;&lt;get_size_in_kB(size)&lt;&lt;","&lt;&lt;get_speed_in_GB_per_sec(size)&lt;&lt;"\n";
         size=(static_cast&lt;int&gt;(size+BLOCK_SIZE)/BLOCK_SIZE)*BLOCK_SIZE;
     }
  
     //ensure that nothing is optimized away:
     std::cerr&lt;&lt;"Sum: "&lt;&lt;PREVENT_OPTIMIZATION&lt;&lt;"\n";
  }
  </code></pre>
  
  <p><code>create_report.py</code>:</p>
  
  <pre><code>import sys
  import pandas as pd
  import matplotlib.pyplot as plt
  
  input_file=sys.argv[1]
  output_file=input_file[0:-3]+'png'
  data=pd.read_csv(input_file)
  
  labels=list(data)    
  plt.plot(data[labels[0]], data[labels[1]], label="my laptop")
  plt.xlabel(labels[0])
  plt.ylabel(labels[1])   
  plt.savefig(output_file)
  plt.close()
  </code></pre>
  
  <p>Building/running/creating report:</p>
  
  <pre><code>&gt;&gt;&gt; g++ -O3 -std=c++11 bandwidth.cpp -o bandwidth
  &gt;&gt;&gt; ./bandwidth &gt; report.txt
  &gt;&gt;&gt; python create_report.py report.txt
  # image is in report.png
  </code></pre>