Spatial and temporal locality for dummies

For the purpose of this article, think of a computer as a filing system. There is a big cabinet of drawers that hold instructions (ROM/RAM), another big cabinet of drawers that hold data (RAM), and a filing clerk (CPU).

Consider an example. The computer belongs to the CEO of a company that sells widgets. He needs to calculate how much money he needs to pay out to his employees. So the instructions say things like:

  1. Open up drawer #76 and get card #4. It’ll be a card for an employee.
  2. Open up drawer #80 and get card #1. That’s the card you’re using to keep track of the total.
  3. Add the salary of the employee card to the total card, and write down the result.
  4. Put the employee card back.
  5. Put the total card back.
  6. Proceed to the next instruction.

With these instructions, the filing clerk will be running back and forth, going up and down the ladder, getting cards and putting them back. Jeez! How slow! How exhausting!

Could we do better?

Temporal locality

Notice that in every single instruction, the filing clerk needs to access the total card. This is an example of temporal locality because it involves accessing the same piece of data frequently over a short period of time.

Think about it like this. In the graphs below, every line represents the filing clerk accessing a particular piece of data (eg. total). On the left, there is temporal locality. On the right, there isn’t.

“Temporal” means “time” and “locality” means “close to”. See how on the left, the data accesses are “close to each other in time”, and on the right they aren’t?

It doesn’t take a genius to figure out a solution to this temporal locality problem. If you have accessed the total card every time, for the past 15 instructions… maybe you could go out on a limb and guess that you’ll need it for the 16th instruction too? Maybe you could just keep it next to you instead of going back and forth, putting it in and taking it out of its drawer?

Spatial locality

Suppose that the instructions have the filing clerk accessing employee cards from left to right, top to bottom:

This is called spatial locality because it involves accessing cards that are close to one another as opposed to jumping around from one area to the next. Eg. you just accessed card number three. The next one you have to access is card number four, which is right next to the one you just accessed.

What would you do if you were a filing clerk and you noticed some spatial locality in the instructions you were receiving? Well, if you just used cards 3, 4 and 5, and your current instruction is asking you to get card 6… maybe you could just go ahead and grab cards 6–20. The subsequent instructions will probably require you to use them, so why not just grab them all now while you’re up there on the ladder, rather than going back and forth?

Educated guessing

Notice that the “solutions” to spatial and temporal locality involve educated guesses.

In spatial locality, the past five instructions may have been using cards 1–5… but you don’t know that the next instruction will use card 6. You don’t know that the next 15 instructions will use cards 6–20. It seems likely, though, so you make an educated guess.

In temporal locality, the past 60 instructions may have required you to use the total card, but you don’t know that the 61st instruction will also require you to use it. It seems likely though, so you make an educated guess.

Real computers

Of course in real computers, there’s no filing clerk running around. There’s just cold metal and electricity. In our analogy, a human filing clerk is probably smart enough to notice these locality trends and catch on, but a real CPU needs to be programmed to do this. A real CPU doesn’t just decide to do things on its own.

So how do we program the CPU to notice these trends? And where exactly can we store things?

As a programmer, you don’t actually need to know the answers to these questions. All you really need to know is that if you write code that has spatial and temporal locality, some lower level code that someone else wrote will take advantage of the locality and make things run faster.

But if you’re curious, check out the following:

Utilizing locality in your programs

Here is an example of code with locality:

sum = 0;
for (i = 0; i < n; i++)
sum += a[i];
return sum;

There is temporal locality because sum is accessed again and again and again and again (with a few pauses on line 2).

There is spatial locality because we have an array a, and we access elements of the array in order. Eg. we access element 0, then element 1, then element 2, so on and so forth. Each of these elements is right next to one another in memory:

See https://stackoverflow.com/a/9936656/1927876 for a good contrast of code that takes advantage of locality with code that doesn’t take advantage of locality.

Instructions

When thinking about locality, it’s important to think about the instructions as well as the data. By default, programs execute one instruction after another after another, in order. Hey, there’s spatial locality!

However, when you call a function, the instructions for the function are somewhere else (because we want the function to be reusable), so we have to jump around, which decreases the spatial locality:

Premature optimization

In practice, locality usually doesn’t have a notable effect on your program’s speed. Be sure to consider whether it’s worth sacrificing your time and your code’s readability to improve performance. Remember: