Are loop counters spatially or temporally local?

Question

Consider this nested loop:

for (i=0 to n)
   for(j=0 to n)
      for (k=0 to n)
         sum := sum +k
      end for
   end for
end for

Do i,j and k have temporal or spatial locality?

I've considered j and k as temporal since they are revisited again in the loop. But I'm confused about i as it does not match the definitions of temporal or spatial.

Answer 1

A set of variables has temporal locality if they are accessed within a relatively short period of time. sum, k and n are all accessed at every iteration of the inner loop; assuming that n is relatively large, i and j are not accessed frequently. So sum, k and n are temporally local, j could be considered temporally local with them but i probably isn't.

Variables have spatial locality if they are stored at addresses that are close together – e.g., close enough to be in the same cache line or, at least, the same page in memory. As such, spatial locality is a property of compiled code, not source code, so it's impossible to say what variables in the code are spatially local: a stupid compiler or memory manager could scatter them to the four corners of the address space. But one would hope that temporally local variables that are accessed repeatedly would be spatially local.

Answer 2

Well for your example let me put it in this way, imagine you have a Cache memory and main memory. code is in main memory now. you are running this code using Temporal locality of reference when your code will run the most frequent variables that are accessed are sum,k and n. these will be in cache for longer period of time since they are accessed in most of the time in the code. it is not the case that variable i,j wont be moved to cache they will be but if they are removed from cache they wont be brought back in until they are not accessed. so in short in case of temporal locality until you don't access wont be moved to cache memory.

If you are using Spatial locality of reference as soon as you read i, all variables will be moved to cache memory since we assume that they are stored one after the other. In spatial locality reference we assume that any thing near to what we are accessing will be accessed very soon so just grab what you see near by it and move to cache. how much to move depends on architecture.