The Memory Hierarchy

Throughout this chapter, I’ve discussed caches that are used to store data that is pulled from an external source such as the Internet. However, caches are used in many other contexts as well, including in the hardware of our computers. In fact, understanding how this hardware works can enable us to write more efficient day-to-day code. So, let’s talk hardware.

It’s generally understood that a computer has memory. A computer’s memory is where a computer stores all its data, from entire files to the tiny variables we create with our code. However, our computer doesn’t simply store all data in one huge container. Instead, a computer’s memory is partitioned into a number of different levels. And here’s the interesting thing: each level has a different speed at which it offers up data. Some levels of memory provide data at blazing speeds, while other levels are relatively slower at letting the computer access data.

In a digital utopia, all levels of memory would be as fast as possible. One major reason why this is not the case is that the fastest memory costs a lot of money. That is, the fastest memory technology available at any given moment in time is relatively expensive. If the computer’s entire memory was made up of that technology, the computer’s cost would be prohibitive. So, in the real world, computers are built so that they have some levels of memory that are, indeed, extremely fast, but other levels that are slower.

Now, the trick here is this: any piece of software only needs a limited amount of data at any given time. For example, most software doesn’t usually interact with every single file on your computer and certainly not all at the same time.

Along these lines, think about the code you write day-to-day. Often, your code works with a mere handful of variables at a given point in time. Now, we want our software to run quickly, so the computer stores these variables in the fastest levels of memory. While these fast levels of memory are made of expensive technology, the costs are kept down by making these levels small. That is, they only store a relatively small amount of data. But that’s fine since that’s all the data your software currently needs access to.

All the other files on our computer—which our software doesn’t need to access at the moment—can live in cheaper, slower memory levels. Because these slow levels are cheaper, we can afford to make them large and capable of storing large amounts of data.

This system, in which our computer contains a combination of small-but-fast memory levels in addition to large-but-slow memory levels, is known as the memory hierarchy. The memory hierarchy is often visualized as a pyramid, like this:

The top levels of the pyramid contain only a small amount of data, but are made of expensive technology that offers up data at blazing speeds. As you move down the pyramid, each level has increased storage capacity but is also somewhat slower since the slower levels are made of cheaper hardware.

Let’s briefly walk through each level, starting from the bottom.

The Memory Hierarchy Levels

The bottommost level isn’t truly a level of memory inside the computer. It refers to data that is external to your computer, such as the web. However, it’s often included in the description of the memory hierarchy, so I threw it in there as well.

The Filesystem

The next level up is the filesystem on your computer, which is where all those files like photos, music, and book reports live. Those files can all live in this slow memory level until you access them with an app like a photo viewer, music player, or word processor. For the record, the filesystem is also sometimes called the hard drive, or the hard disk, or simply the disk.

Main Memory

Here’s where things get interesting. When you do open, say, your photo-viewer app, this app will load a photo from the filesystem into the next level up of the memory hierarchy. This level is sometimes called main memory or random access memory or simply RAM for short. I’ll use each of these terms interchangeably.

The key thing to understand here is this: generally, most code doesn’t interact directly with files in the file system. Instead, the software first loads data from the filesystem into main memory and then interacts with the data in main memory. Indeed, if the data is being modified, at some point these changes will be written back to the filesystem. But in the short term, a computer processes data that is within main memory (or the higher levels of the memory hierarchy, which I’ll get to soon).

Now, when you close your app, all this data gets cleared from RAM. Hopefully, you saved your changes! If you did, this data will live on in the filesystem until you need to access it again. It’s important to be cognizant of the size of your RAM. Even if you have a large hard drive, the amount of data your code can process at once can be no larger than your main memory.

If you see an ad for a computer with, say, 32GB memory and 1TB storage, this means that the main memory can store up to 32 gigabytes of data, and that the filesystem can store up to 1 terabyte of data. A terabyte is 1,000 gigabytes, which is way larger than the 32GB of main memory, but that terabyte is only going to store your filesystem. Your code, on the other hand, won’t be able to process more than 32GB at once. And if you have other software running at the same time, some of that 32GB is already being utilized by those other applications, so your code has even less than 32GB to work with.

In short, don’t create a variable that tries to hold a massive amount of data unless you know that the computer has enough RAM to handle it. Later, in Chapter 7, I’ll discuss how to handle situations where you do have to work with massive data like that.

Cache Levels

Software doesn’t only interact with the main memory level; the computer has a few levels that are even faster than RAM. These levels, which are the top four levels of the memory hierarchy pyramid, act as caches, albeit in a slightly different way than how I’ve described caches until now. Let me explain.

Say that your code loads an array of one million integers from a file (in the file system) and stores the array in a variable. Once this happens, this array will live somewhere inside main memory.

Now, suppose that your code iterates over the array to perform some computation, such as getting the total sum of the integers. At this point, your computer may take, for example, the first 1000 integers and copy them from RAM to the L3 cache. The reason it does this is that the L3 cache is made of faster technology than RAM. So, when the computer iterates over these integers, it can do so more quickly.

The only reason the computer doesn’t load the entire array into the L3 cache is that the L3 cache is too small to hold them all. So, what the computer does is load the first 1000 integers into the L3 cache and then, after iterating over them, it evicts them and loads the next 1000 integers from RAM into L3. The computer then iterates over them and then evicts them to load the next 1000 integers. The computer repeats this process until it’s iterated over all the array’s integers.

Note that the numbers I’m using, such as one million and 1000, are examples; every computer model stores different amounts of data in their various cache levels.

Previously, I described a web cache as being a location for holding data from an external and slower source, such as the Internet, so that we can access the data more quickly in the future. In the current context, the L3 cache is holding data from an internal but slower source—in this case, RAM—so that it can process the data more quickly. The goal of both caches, though, is the same: to move data from a slower location to a faster location. Like all caches, your computer’s cache levels all have eviction policies. The policy may be LRU or something else; it all depends on the computer model.

Much of the time, the computer does all this caching without you being aware of it. The computer figures out what data your code is processing right now and moves it into the appropriate cache levels.

Not every type of computer is exactly the same, but most computers have multiple cache levels, such as L1, L2, and L3. Each of these caches serves as a cache for the level below it. So, for example, the computer might copy 1000 integers into L3, and of those, 100 integers into L2, and of those, 10 integers into L1. Again, these numbers are all just examples.

CPU Registers

The CPU registers act as a cache as well. In fact, it’s the fastest of all caches because it’s made of the most expensive technology. Accordingly, it’s also the smallest of all the caches. You can think of the CPU registers as being the “L0” cache.

It turns out that understanding these concepts can allow you to write faster code. Let’s see how.