CPU Cache Locality

In the previous post, we explored how effective cache-friendly code can be.

Reducing pointer dereferences, pointer chasing, and cache misses can dramatically improve application execution times.

We discussed how using structs instead of classes often improves iteration speed, and that accessing data directly is generally faster than traversing long chains of references.

While this is true, it isn't the full story.

Today we'll look beyond pointers and data types to understand why storing related data close together in memory matters so much to modern processors.

We'll see how CPUs automatically preload data before it's needed; why sequential memory access is much faster than random access; and why bulk processing large amounts of data almost always outperforms processing one object at a time.

Welcome to the world of cache locality.

In this article we'll cover:

• Cache Lines
• Spatial Locality
• Temporal Locality
• Bulk Processing Data

Memory Problems

Let's imagine we're building a game.

An auto-shooter inspired by the old Flash classic The Last Stand.

You, the player, sits safely behind a barricade while an endless horde of zombies marches towards you. You must kill the zombies. The zombies must kill you.

At first the implementation is straightforward.

Every zombie is represented by its own ZombieNPC class. Our AI is simple. Zombies walk towards the player; and die when their health reaches 0.

The game is easy to prototype, every enemy is self-contained, and adding new behaviors is straightforward.

This is the benefit of object-encapsulated code. And it's where object-oriented code shines.

For a few dozen enemies, performance is excellent.

Then the horde grows.

One hundred zombies.

One thousand.

Ten thousand.

Suddenly the frame rate is half of what it used to be.

The processor isn't doing more complicated work. It's doing the same thing over and over, just processing more units. So it begs the question:

If we are doing the same thing over and over. Wouldn't our processor be optimized for this?

Simply put, it is.

But, unknowingly, we are working against it.

Cache Lines

If we visualized how our NPC objects, the zombies, are stored in memory we would see that they are spread across our RAM. That's because classes are a reference type.

Each element inside our zombies array doesn't actually contain a zombie. Instead, it contains a reference to one. If you recall, too many of these dereferences results in increased execution times.

Naturally you may think that the frame drop is caused exclusively because of our pointer chasing.

And it's definitely a culprit.

But something else is happening here.

You see, our CPU loads our data into caches, for faster access. When this happens the CPU doesn't load a single object into memory. It loads a cache line.

Whenever we request our data object from RAM, our CPU loads the requested data, AND any data that is stored nearby.

On most desktop processors, a cache line can fit 64 bytes.

What this means for us is that we should try to benefit from caching only the data we need in these cache lines, nothing else.

But right now, every time we access and cache ZombieNPC, because they are scattered through memory, we end up loading a bunch of unrelated data.

We are filling out critical caches with unused data.

So let's improve our code.

This is our current code:

public class ZombieNPC {
	int health;
	float speed;
	float strength;
	
	public Attack() {}
	public Move() {}
	public Die() {}
}

Instead of storing ZombieNPC as a class, we redesign it as a struct:

public struct ZombieNPC {
	int health;
	float speed;
	float strength;
}

And store the values directly inside an array in a parent class ZombieSystem. We also move any behavior into our parent class so it processes every zombie in one loop, instead of per object.

public class ZombieSystem {
	ZombieNPC[] zombies;
	
	public void ProcessAttack() {}
	public void ProcessMovement() {}
	public void ProcessHealth() {}
}

What we've done is create something called Array of Structures (AoS). Literally. An array of structs.

Immediately our memory layout changes and our CPU can fill up the caches with relevant data only. We have successfully improved CPU caching as our zombies are now stored sequentially in memory.

Now we are able to fully utilize our cache lines to load relevant data into memory.

We left outside data out of our processing loop.

Have we achieved maximum efficiency?

Not so fast.

Cache Locality

What we have been witnessing is a blossoming awareness of cache locality, or broadly, memory locality.

The tendency our software has to access the same, or nearby, data, over continuous periods of time.

Everything we talked about both in this post and this one falls under this umbrella.

We are beginning to notice when our data is "too far" from our processor and when it comes "packed" with other irrelevant data.

Cache locality is divided into two more nuanced terms. Spatial locality and temporal locality.

Think of locality as places in memory.

Spatial locality dictates that if our places in memory are closer together, continuously, and with no redirection, our processor can cache our data much more efficiently.

How our data is stored matters.

Temporal locality dictates that if we access the same data over and over, avoiding back and forth, we also increase our cache efficiency.

When we process our data matters.

Applying both types of locality means benefitting from cache locality, and consequently leveraging CPU caching.

Let's go back to our zombie game.

So far our enemies are super simple.

They have speed, health and strength variables.

We can load them into our cache lines without excessive pointer dereferences.

But games are usually not that simple.

In the future we might want to add new variables, and soon, our little struct won't be so little.

Remember how we thought we successfully avoided loading unused data into cache?

That was not exactly true. We got much better at caching and effectively using cache lines. But if you pay attention we are still caching irrelevant data.

Each one of our processing functions, such as ProcessAttack still loads the struct as a whole, but only uses one of the variables we load.

ProcessAttack loads strength along with speed and health. But it does not need the latter two. Our systems still load unused data.

Fortunately the solution is rather simple and intuitive.

We've forsaken classes in all of its glory. Abandoning inheritance, polymorphism, and hierarchies.

Objects didn't make the cut either as hoarders of pointers and jumbled data.

So following this principle let's dismember our struct completely and store each variable type on its own.

public ZombieSystem {
	int[] health;
	float[] speed;
	float[] strength;
	
	public void ProcessAttack() {}
	public void ProcessMovement() {}
	public void ProcessHealth() {}
}

Stop and look at this beautiful piece of mock-up code. Realize how our memory layout is different again.

There are no classes, so we know that our arrays are being stored contiguously in memory.

Each function process only one set of arrays, meaning our cache lines are only filled with relevant data.

That's spatial locality.

We naturally gravitated towards bulk processing. Each function iterates through relevant data only.

Our hot caches get used efficiently and consistently. Instead of flushing for new data.

That's temporal locality.

And this is all cache locality.

Visualizing it is a dead giveaway:

Locality And Data-Oriented Programming

As we dig deep into software-making we start to realize there is no such thing as one solution to a problem.

In this particular case, we've dug so much in search of increased processing times and memory management we came out the other side armed with a completely different way of organizing data.

We've sacrificed readability and object-oriented programming and have entered the realm of Data-Oriented Programming.

The idea that data should be organized around how it is processed, not objects.

But object-oriented programming is not bad.

It's is much easier to prototype, understand, and pass on to new developers.

It solves a different problem.

Maximizing locality, and applying data-oriented principles, solves the problem of memory management, efficiency at scale and CPU caching.

And both should be used accordingly.