Odtnhj

I tested the next code with Google Benchmark framework to measure memory access latency with different array sizes:

int64_t MemoryAccessAllElements(const int64_t *data, size_t length) 
 for (size_t id = 0; id < length; id++) 
 volatile int64_t ignored = data[id];
 
 return 0;

int64_t MemoryAccessEvery4th(const int64_t *data, size_t length) 
 for (size_t id = 0; id < length; id += 4) 
 volatile int64_t ignored = data[id];
 
 return 0;

And I get next results (the results are averaged by google benchmark, for big arrays, there is about ~10 iterations and much more work performed for smaller one):

There is a lot of different stuff happened on this picture and unfortunately, I can't explain all changes in the graph.

I tested this code on single core CPU with next caches configuration:

CPU Caches: 
 L1 Data 32K (x1), 8 way associative
 L1 Instruction 32K (x1), 8 way associative
 L2 Unified 256K (x1), 8 way associative
 L3 Unified 30720K (x1), 20 way associative

At this pictures we can see many changes in graph behavior:

1. There is a spike after 64 bytes array size that can be explained by the fact, that cache line size is 64 bytes long and with an array of size more than 64 bytes we experience one more L1 cache miss (which can be categorized as a compulsory cache miss)


2. Also, the latency increasing near the cache size bounds that is also easy to explain - at this moment we experience capacity cache misses

But there is a lot of questions about results that I can't explain:

1. Why latency for the MemoryAccessEvery4th decreasing after array exceeded ~1024 bytes?


2. Why we can see another peak for the MemoryAccessAllElements around 512 bytes? It is an interesting point because at this moment we started to access more than one set of cache lines (8 * 64 bytes in one set). But is it really caused by this event and if it is than how it can be explained?


3. Why we can see latency increasing after passing the L2 cache size while benchmarking MemoryAccessEvery4th but there is no such difference with the MemoryAccessAllElements?

I've tried to compare my results with the results from gallery of processor cache effects and what every programmer should know about memory, but I can't fully describe my results with reasoning from this articles.

Can someone help me to understand the internal processes of CPU caching?

UPD:
I use the following code to measure performance of memory access:

#include <benchmark/benchmark.h>
using namespace benchmark;
void InitializeWithRandomNumbers(long long *array, size_t length) 
 auto random = Random(0);
 for (size_t id = 0; id < length; id++) 
 array[id] = static_cast<long long>(random.NextLong(0, 1LL << 60));
 

static void MemoryAccessAllElements_Benchmark(State &state) 
 size_t size = static_cast<size_t>(state.range(0));
 auto array = new long long[size];
 InitializeWithRandomNumbers(array, size);
 for (auto _ : state) 
 DoNotOptimize(MemoryAccessAllElements(array, size));
 
 delete array;

static void CustomizeBenchmark(benchmark::internal::Benchmark *benchmark) 
 for (int size = 2; size <= (1 << 24); size *= 2) 
 benchmark->Arg(size);
 

BENCHMARK(MemoryAccessAllElements_Benchmark)->Apply(CustomizeBenchmark);
BENCHMARK_MAIN();

You can find slightly different examples in the repository, but actually the basic approach for the benchmark in the question is same.