Thread: Understanding how cache works

Hi,

I have a basic question regarding how cache memory works.

Let say I have a vector that does not fit into my cach memory (too large.) and this vector contains random numbers (ints) that are sampled from a set which is of the size equal to the size of my vector.

Now I traverse my vector from 0 towards the end and each time i come accross a value I insert it into another vector on a position defined by the value itself.

Code:

vector<int> vec1(n); // full of rand numbers from 0 to n 
vector<int> vec2(n); // empty

for(int i =0; i < n ; i++){
  vec2[vec1[i]] = vec1[i];
}

Is this a cach friendly code? Does vec2 fill the cach each time it is called upon ?? I understand that when I iterate tzhrough vec1 i fill L1 but if i call another vector as i do in the above example does it clear my L1 and fills it with vec2 and so on or not?? what happenes? what is the underlying mechanics??

thnx

b

Caches read in lines at a time so go for spatial locality and then temporal locality. So you tell us, are all your reads done close to each other? If not, do you reuse the same address a lot?

Keep in mind, there is cachegrind.

Originally Posted by MutantJohn

Caches read in lines at a time so go for spatial locality and then temporal locality. So you tell us, are all your reads done close to each other? If not, do you reuse the same address a lot?

Keep in mind, there is cachegrind.

Hi, so as you can see in th obove code my reads are close to each other in vec1 but not on vec2, moreover there is no temporal locality on vec2 since under a uniform distribution model (which is assumend under "random ints") each location in vec2 will be accessed once.

I mean i understand that accessing 2d array (for example) on a row based principle:

Code:

A[i][i] (ram) + A[i][i+1] (cash) + A[i][i+2] (cash) + A[i+1][i] (ram) + A[i+1][i+1] (cash) + A[i+1][i+2] (cash)

is cash friendly but :

Code:

A[i][i] (ram) + A[i+1][i] (ram) + A[i][i+1] (ram) + A[i+1][i+1] (ram) ...

is not. However what I am confused about is the above case (exactly) will vec1 be constantly in my cash or not?? (or maybe I completly missed the point regarding how cash works)

Originally Posted by MutantJohn

Keep in mind, there is cachegrind.

I didn't know about this one.... I believe cachegrind did the trick in resolving my confusions

thnx