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

Quote:

---

Originally Posted by baxy

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?

---

No, the code doesn't assign anything to vec1, it instead assigns the random int from vec1[i], to the same index as is the value of vec1[i].

For instance, say ( i == 5 ), and ( vec1[i] == 107 ), then the loop is doing the following:

Code:

---

vec2[107] = vec1[5]; // vec1[5] is 107

---

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.

baxy, do you understand how caches work? If you don't, I suggest you find a simple tutorial on how they work.

Quote:

---

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)

Quote:

---

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

vec1 will be optimal since you're doing sequential reads in row order. vec2 will not be optimal since you're jumping around randomly (assuming the indexes of vec1 is random). Hence, it will be very cache unfriendly. Of course, if the entire vec2 + vec1 fits in the cache entirely, it will still be optimal.