CODEWITHSUNDEEP
c++
Jason Liu
Jason Liu

Reputation: 818

caching - RAM access times

Consider two loops over an array:

int *arr = new int[1024 * 1024];
// Loop1
for (int i = 0; i < n; i++) arr[i] *= 3;
// Loop2
for (int i = 0; i < n; i += 16) arr[i] *= 3;

As they both are O(n) in big O notation, however, they have the same number of RAM access. i.e. same number of cache misses.

Why would they have the same number of RAM access? Wouldn't loop 2 has less RAM access according to after each visit i is incremented by 16?

Upvotes: 0

Views: 90

Answers (1)

aneesh jose
aneesh jose

Reputation: 381

Cache is always accessed / managed with the granularity of a line. There will be more than one element in a cache line. I think your cache line can hold 16 elements or more and hence one RAM access will load all the adjacent elements to cache and further RAM access is not required for the next 16 bytes.

Upvotes: 3

Related Questions