Spatial vs. Temporal locality

Question

I understand the definitions of the terms, but I am having trouble applying their concepts to code. For an exercise, we are asked to describe if the following code is spatial or temporal:

for (int i=0; i<10; i++) {
    printf(some_array[i]);
}

I feel like this is spatial locality because when one index of the array is accessed, the next index memory location will be accessed as soon as the loop iterates. Is this the correct way to look at it? What determines if code is temporal versus spatial? More examples would be great.

possible duplicate of [Analyse code for spatial and temporal locality](http://stackoverflow.com/questions/4092019/analyse-code-for-spatial-and-temporal-locality) — Mitch Wheat, Aug 31 '11 at 23:53
The use of 'printf' of an example for the topic of cacheing and memory accesses is a really poor choice. The overhead of `printf` is enormous compared to where the elements of `some_array` are. In addition, it's really a bad idea to `printf` from a non const format string. What happens if `some_array[0] = "%s"`? Better to do `printf("%s",some_array[i])` or `puts(some_array[i])`. — Mark Lakata, Aug 29 '14 at 17:45

score 11 · Accepted Answer · answered Aug 31 '11 at 23:55

11

It's a bit of a silly exercise, really. Code is not temporal or spatial.

But temporal locality implies that you're going to access the same address multiple times, relatively closely in time. You're not doing that here (unless you count accessing i, I guess), so by a process of elimination, you could conclude that this must be spatial locality.

More precisely, you're accessing some_array[0], then some_array[1], etc. etc. These are close together in address space, so yes, this may be "relying" on spatial locality.

answered Aug 31 '11 at 23:55

Oliver Charlesworth

267,707
33
569
680

isn't the code benefited from temporal locality in the loop ? – phoxis Sep 01 '11 at 04:41
@phoxis: IMO, no. See my comment to dario_ramos's answer. – Oliver Charlesworth Sep 01 '11 at 07:42
i mean the "code", means the machine code will benefit from temporal locality, as the loop section opcodes gets used repeatedly, if they are brought in the instruction cache, and not removed until a period (determined by cache replacement policies). – phoxis Sep 01 '11 at 16:35
@phoxis: Oh, I see. Yes, you're right; I was only considering data cache. – Oliver Charlesworth Sep 01 '11 at 16:55

score 5 · Answer 2 · answered Sep 01 '11 at 00:32

In the context of hardware cache memory, which is where these concepts usually come up, the analysis is not usually done on a memory address basis, so to speak. Locality is analyzed by access to memory blocks, those which are transferred between cache and main memory.

If you think of it that way, your code has both temporal and spatial locality. When your code reads some_array[0], if its address is not found in the cache, it is read from main memory and the whole block which contains it is copied to the cache. It replaces some other block following a certain policy: MRU, for example.

Then, when you access some_array[1] a short time later, its block is already in cache, so read time will be smaller. Notice that you accessed the same block, and in a small amount of time. So you have both spatial and temporal locality.

Cache memory takes advantage of spatial and temporal locality to provide faster memory access. On the other hand, whether your code can take advantage of this is a whole different issue altogether. Nevertheless, the compiler will do most of the optimizations for you, so you should only concern yourself with this after finding a bottleneck in a profile session. In Linux environments, Cachegrind is great for this.

I'm not sure this is temporal locality. By your definition, it would be impossible to have spatial locality without also gaining temporal locality (i.e. the two would be inseparable). To me, temporal locality refers to accessing the **same** address multiple times, irrespective of the cache characteristics. This doesn't happen in the OP's code. — Oliver Charlesworth, Sep 01 '11 at 07:39
What if you access the same memory block every 20 minutes? (For example, polling shared memory to control some resource). That's just spatial, not temporal. It probably wouldn't benefit from the cache if, in those 20 minutes, other processes accessed memory and had the block removed — dario_ramos, Sep 01 '11 at 12:27
@dario: But by that definition, spatial locality is never useful on its own! — Oliver Charlesworth, Sep 01 '11 at 16:56

score 2 · Answer 3 · answered Jul 11 '13 at 22:00

This code has temporal locality in the instruction cache because you're repeating the code with each loop (assuming your optimizer did not unroll the loop). It also has spacial locality in the data cache because if you access array element i you will soon access elements i+1, i+2, etc. If your data cache line size is 16 bytes and your array is 32-bit integers, then your data cache also loaded elements 1, 2, and 3 when you asked for element 0 (assuming our array started at a cache line boundary).

Tuxdude · Answer 4 · 2011-09-01T19:08:27.947

The code only has spatial locality but no temporal locality - in the context of cache memory accesses.

While loading data into the cache, a whole line/block is loaded - hence subsequent accesses to the exact same memory location as well as addresses which are also part of the same block in the cache would have fast access times.

There are ways to optimize your code such that as much amount of reads are from the cache instead of directly from main memory: 1. If you can access all the nearby memory addresses by just taking advantage of the first cache-miss, and before this block is evicted out of the cache - then you make use of spatial locality. 2. If you access the same memory location as many times as required by your program before the block in the cache gets evicted - then you take advantage of temporal locality.

Examples like matrix multiplication would have both temporal and spatial locality.

Spatial vs. Temporal locality

4 Answers4

Linked