title: Is the memory latency slowing the execution on a large dataset?
body: <p>I was having fun with Google Benchmark with this code (compiled in -O3 with GCC):</p>
  <pre><code>#include &lt;iostream&gt;
  #include &lt;thread&gt;
  #include &lt;random&gt;
  #include &lt;benchmark/benchmark.h&gt;
  
  using namespace std;
  
  
  struct PointRecord{
      double latitude, longitude;
      double speed_x, speed_y, speed_z;
      double acceleration_x, acceleration_y, acceleration_z;
      long timestamp;
  };
  
  
  struct PointGpsRecord{
      double latitude, longitude;
  };
  
  
  tuple&lt;double, double&gt; avg_pos_obj_oriented(vector&lt;PointRecord&gt;&amp; data){
      double mean_lon = 0.0;
      double mean_lat = 0.0;
      auto size = data.size();
      for(auto&amp; point : data){
          mean_lat += point.latitude;
          mean_lon += point.longitude;
      }
      return make_tuple(mean_lat / size, mean_lon / size);
  }
  
  static void BM_object_oriented(benchmark::State &amp;state) {
      random_device rnd_device;
      mt19937 rng{rnd_device()};
      uniform_real_distribution&lt;double&gt; dist{-10, 10};
  
      int size = state.range(0);
      vector&lt;PointRecord&gt; points;
      points.reserve(size);
      for(int i = 0; i &lt; size; i++){
          auto point = PointRecord();
          point.latitude = dist(rng);
          point.longitude = dist(rng);
          point.timestamp = 12345678;
          points.push_back(point);
      }
  
  
      for (auto _: state) {
          auto p = avg_pos_obj_oriented(points);
          benchmark::DoNotOptimize(p);
      }
  
      state.SetBytesProcessed(int64_t(state.iterations()) *
                              int64_t(sizeof(double)*2*size));
      state.counters[&quot;BytesProcessed&quot;] = benchmark::Counter(size*sizeof(PointRecord), benchmark::Counter::kDefaults, benchmark::Counter::OneK::kIs1024);
  
  }
  
  
  tuple&lt;double,double&gt; avg_vec_data_oriented(vector&lt;PointGpsRecord&gt;&amp; data, uint size){
      double sum_lat = 0.0;
      double sum_lon = 0.0;
      for(int i = 0; i &lt; size; i++){
          sum_lat += data[i].latitude;
          sum_lon += data[i].longitude;
      }
      return make_tuple(sum_lat/size, sum_lon/size);
  }
  
  static void BM_data_oriented(benchmark::State &amp;state) {
      random_device rnd_device;
      mt19937 rng{rnd_device()};
      uniform_real_distribution&lt;double&gt; dist{-10, 10};
  
      int size = state.range(0);
  
      vector&lt;PointGpsRecord&gt; records;
      records.reserve(size);
  
      for(int i = 0; i &lt; size; i++){
          auto point = PointGpsRecord();
          point.latitude = dist(rng);
          point.longitude = dist(rng);
          records.push_back(point);
      }
  
  
      for (auto _: state) {
          tuple&lt;double,double&gt; avg = avg_vec_data_oriented(records, size);
          benchmark::DoNotOptimize(avg);
      }
  
      int64_t iterations = state.iterations();
      int64_t bytes = sizeof(double) * 2 * size;
  
      state.SetBytesProcessed(iterations * bytes);
      state.counters[&quot;BytesProcessed&quot;] = benchmark::Counter(size*sizeof(PointGpsRecord), benchmark::Counter::kDefaults, benchmark::Counter::OneK::kIs1024);
  
  }
  
  
  BENCHMARK(BM_object_oriented)-&gt;Unit(benchmark::kMicrosecond)-&gt;RangeMultiplier(4)-&gt;Range(64, 1 &lt;&lt; 25);
  BENCHMARK(BM_data_oriented)-&gt;Unit(benchmark::kMicrosecond)-&gt;RangeMultiplier(4)-&gt;Range(64, 1 &lt;&lt; 25);
  
  
  BENCHMARK_MAIN();
  </code></pre>
  <p>With these results:</p>
  <pre><code>Run on (16 X 5000 MHz CPU s)
  CPU Caches:
    L1 Data 32 KiB (x8)
    L1 Instruction 32 KiB (x8)
    L2 Unified 256 KiB (x8)
    L3 Unified 16384 KiB (x1)
  Load Average: 1.29, 1.01, 0.84
  ***WARNING*** CPU scaling is enabled, the benchmark real time measurements may be noisy and will incur extra overhead.
  --------------------------------------------------------------------------------------
  Benchmark                            Time             CPU   Iterations UserCounters...
  --------------------------------------------------------------------------------------
  BM_object_oriented/64            0.039 us        0.039 us     17779654 BytesProcessed=4.5k bytes_per_second=24.5771G/s
  BM_object_oriented/256           0.213 us        0.213 us      3300654 BytesProcessed=18k bytes_per_second=17.8812G/s
  BM_object_oriented/1024          0.906 us        0.906 us       770645 BytesProcessed=72k bytes_per_second=16.8411G/s
  BM_object_oriented/4096           3.84 us         3.84 us       180761 BytesProcessed=288k bytes_per_second=15.902G/s
  BM_object_oriented/16384          18.8 us         18.8 us        37463 BytesProcessed=1.125M bytes_per_second=13.0112G/s
  BM_object_oriented/65536          75.1 us         75.1 us         9406 BytesProcessed=4.5M bytes_per_second=13.008G/s
  BM_object_oriented/262144          529 us          529 us         1355 BytesProcessed=18M bytes_per_second=7.37992G/s
  BM_object_oriented/1048576        3072 us         3072 us          226 BytesProcessed=72M bytes_per_second=5.08572G/s
  BM_object_oriented/4194304       12958 us        12957 us           55 BytesProcessed=288M bytes_per_second=4.82362G/s
  BM_object_oriented/16777216      52470 us        52467 us           13 BytesProcessed=1.125G bytes_per_second=4.76492G/s
  BM_object_oriented/33554432     104667 us       104662 us            7 BytesProcessed=2.25G bytes_per_second=4.77726G/s
  BM_data_oriented/64              0.038 us        0.038 us     18196596 BytesProcessed=1024 bytes_per_second=25.0373G/s
  BM_data_oriented/256             0.211 us        0.211 us      3312330 BytesProcessed=4k bytes_per_second=18.057G/s
  BM_data_oriented/1024            0.898 us        0.898 us       776186 BytesProcessed=16k bytes_per_second=16.9891G/s
  BM_data_oriented/4096             3.64 us         3.64 us       193013 BytesProcessed=64k bytes_per_second=16.7622G/s
  BM_data_oriented/16384            14.6 us         14.6 us        47183 BytesProcessed=256k bytes_per_second=16.7451G/s
  BM_data_oriented/65536            58.3 us         58.3 us        11894 BytesProcessed=1024k bytes_per_second=16.7614G/s
  BM_data_oriented/262144            233 us          233 us         2970 BytesProcessed=4M bytes_per_second=16.7626G/s
  BM_data_oriented/1048576          1131 us         1131 us          611 BytesProcessed=16M bytes_per_second=13.8116G/s
  BM_data_oriented/4194304          4910 us         4910 us          145 BytesProcessed=64M bytes_per_second=12.7299G/s
  BM_data_oriented/16777216        19468 us        19468 us           36 BytesProcessed=256M bytes_per_second=12.8415G/s
  BM_data_oriented/33554432        39500 us        39497 us           17 BytesProcessed=512M bytes_per_second=12.6591G/s
  </code></pre>
  <p>So, we can observe data processing rate decreasing in concurrency with the filling of the various layer of caches.</p>
  <p>I thought that, with various caches, the CPU could sustain a better rate when increasing the size, by prefetching the data. So I have some question: is the RAM definitely being the bottleneck here?</p>
  <p>Is there any way to speed-up the data rate (still on big data)?</p>
  <p>Then, would using some kind of CPU-parallelization not be useful, since the cores would still be not be fed?</p>
  <p>EDIT: also, here it is a OpenMP parallel version and its results:</p>
  <pre><code>tuple&lt;double,double&gt; avg_vec_data_oriented_parallel(vector&lt;PointGpsRecord&gt;&amp; data, uint size){
      double sum_lat = 0.0;
      double sum_lon = 0.0;
  
  #pragma omp parallel for reduction(+:sum_lat, sum_lon)
      for(auto&amp; p: data){
          sum_lat += p.latitude;
          sum_lon += p.longitude;
      }
      return make_tuple(sum_lat/size, sum_lon/size);
  }
  
  static void BM_data_oriented_parallel(benchmark::State &amp;state) {
      random_device rnd_device;
      mt19937 rng{rnd_device()};
      uniform_real_distribution&lt;double&gt; dist{-10, 10};
  
      int size = state.range(0);
  
      vector&lt;PointGpsRecord&gt; records;
      records.reserve(size);
  
      for(int i = 0; i &lt; size; i++){
          auto point = PointGpsRecord();
          point.latitude = dist(rng);
          point.longitude = dist(rng);
          records.push_back(point);
      }
  
  
      for (auto _: state) {
          tuple&lt;double,double&gt; avg = avg_vec_data_oriented_parallel(records, size);
          benchmark::DoNotOptimize(avg);
      }
  
      int64_t iterations = state.iterations();
      int64_t bytes = sizeof(PointGpsRecord) * size;
  
      state.SetBytesProcessed(iterations * bytes);
      state.counters[&quot;BytesProcessed&quot;] = benchmark::Counter(bytes, benchmark::Counter::kDefaults, benchmark::Counter::OneK::kIs1024);
  
  }
  
  
  
  BM_data_oriented_parallel/64             5.39 us         5.38 us       148050 BytesProcessed=1024 bytes_per_second=181.657M/s
  BM_data_oriented_parallel/256            4.25 us         4.24 us       154501 BytesProcessed=4k bytes_per_second=920.244M/s
  BM_data_oriented_parallel/1024           4.43 us         4.42 us       161006 BytesProcessed=16k bytes_per_second=3.44957G/s
  BM_data_oriented_parallel/4096           5.60 us         5.38 us       100000 BytesProcessed=64k bytes_per_second=11.3523G/s
  BM_data_oriented_parallel/16384          5.97 us         5.76 us       104429 BytesProcessed=256k bytes_per_second=42.3808G/s
  BM_data_oriented_parallel/65536          11.2 us         11.0 us        65653 BytesProcessed=1024k bytes_per_second=89.0536G/s
  BM_data_oriented_parallel/262144         31.9 us         31.7 us        18759 BytesProcessed=4M bytes_per_second=123.122G/s
  BM_data_oriented_parallel/1048576         113 us          112 us         5247 BytesProcessed=16M bytes_per_second=139.253G/s
  BM_data_oriented_parallel/4194304        1671 us         1661 us          433 BytesProcessed=64M bytes_per_second=37.6235G/s
  BM_data_oriented_parallel/16777216       7411 us         7406 us           92 BytesProcessed=256M bytes_per_second=33.7556G/s
  BM_data_oriented_parallel/33554432      15007 us        15005 us           47 BytesProcessed=512M bytes_per_second=33.3221G/s
  </code></pre>
  <p>Note that it peaks when the L3 cache is full.</p>