Confused between Temporal and Spatial locality in real life code

Question

I was reading this question, I wanted to ask more about the code that he showed i.e

for(i = 0; i < 20; i++)
    for(j = 0; j < 10; j++)
        a[i] = a[i]*j;

The questions are,

1. I understand temporal locality, I think that references to i and j should be temporal locality. Am I right?
2. I also understand spatial locality, as the question I linked answers that references to a[i] should be spatial locality. Am I right?

3. The person said,

   "The inner loop will call same memory address when accessing a[i] ten times so that's an example for temporal locality I guess. But is there spatial locality also in the above loop?"

   I don't agree with his guess. As the references generated by a[i] should be spacial locality (They will be referencing the next element in the block). Am I right?

Answer 1

First off, references to var can be temporally local or spatially local not temporal locality, which is improper grammar. Minor point.

Now, on to your questions.

1. The principle of Temporal locality states that two instructions reference the same location within a relatively short timeframe. For example, in the code given, a[i] is referenced frequently, with instructions like a[i] = a[i] * 2 and a[i] = a[i] * 3 being executed very close together. If we are looking at this scope, we could say that references to j and a[i] are temporally local. References to i are also temporally local, because i is referenced every time a[i] is. However, if the last line of the given code read something like a[j] = a[j] * j, then references to i would not be temporally local, at least in the scope of the inner loop^[1].

2. The principle of Spatial locality states that two instructions reference contiguous memory locations. References to a[i] are a good example of this, as one can assume (most of the time) that a[0] and a[1] will be next to each other in memory.

3. The first two basically cover this, but the quoted text is correct, and the code also demonstrates spatial locality.

[1] - Generally, when you are talking about locality, it will be in the context of a given level in the memory hierarchy, whether it be RAM or the L1 cache or what have you. In all but the most limited sense, references to both i and j are temporally local.

Answer 2

The outer loop is an example of spacial locality. It sequentially increments the address the inner for-loop calls.

The inside loop demonstrates temporal locality. The exact same memory address is accessed ten times in a row, and multiplied by j each time.

As for your first two questions, both i and j (loop counters) are very good examples of temporal locality.

Locality is a measure applied by the cache to minimize the calls to memory. If an instruction needs to know the value of a memory address which is not already in the cache, it will access the memory and store all surrounding memory locations in the cache as well.

Answer 3

Lets start with defining both Temporal and Spatial Locality.

Temporal Locality - Temporal locality means current data or instruction that is being fetched may be needed soon. So we should store that data or instruction in the cache memory so that we can avoid again searching in main memory for the same data and thus saving time.

Spatial Locality - Spatial locality means instruction or data near to the current memory location that is being fetched, may be needed soon in near future.

sum = 0;
for (i = 0; i < arr.length; i++)
  sum += arr[i];
return sum;

Now looking at this example, Here variable sum is being used again and again which shows Temporal Locality and then the values of array arr is being accessed in order i.e arr[0], arr[1], arr[2] ,... and so on and which shows Spatial locality as arrays are Contiguous(adjacent) memory blocks so data near to current memory location is being fetched.

Now looking at this example

for(i = 0; i < 20; i++)
    for(j = 0; j < 10; j++)
        a[i] = a[i]*j;

Here we see temporal locality as a[i] in second loop is being used again and again and then variable j is being accessed in order which shows Spatial Locality.

Answer 4

Writing this answer as I didn't get it even after reading the other answers on this question, a few other questions and wikipedia (that's more confusing.)

I think we spend a lot of time and energy to understand the terminology which is bit confusing/complex in this case. I found it easier to understand when I didn't pay any heed to the terms 'spacial' and 'temporal'.

Let's start with the basics.

Let's try to understand what the cache is - a place which is quicker to access than the main memory. That's cool. But this place is limited and expensive, so one should use it wisely. But how would you (or OS) decide what to put in cache and what not to put? There should be some way to know what would we need in the future.. ah future predictions! ( Minority Report! Ring some bells?).

There should be some way to determine what would the program need in future. Using common sense and the code, we can say that some parts of the code are repetitive in nature - example - loops! If there is a variable i inside a loop you know it's going to get accessed in near future again and again. This is the principle behind temporal locality. i can be brought into cache as it is temporally local.

In another area if the code is using any linear data structure (example: an Array) and that too in a loop with an increment in the index, then it's easy to see that although the current need is only 3rd location (for example) of this data structure, very soon the next locations would also be needed because the index increases by 1 for that linear data structure. So it would be great if we bring in the data in the next few locations as well. This is the principle behind spacial locality. Next few locations can be brought into cache as they are spacially local.

The concept of locality is basically to identify the data and instructions to bring in cache so that we can reduce the cache misses and utilize this special place effectively.