A modern CPU can execute billions of instructions every second. But many of those instructions need data, and that data may not be immediately available.

If the processor had to fetch every value from main memory or storage, it would spend much of its time waiting.

To reduce this delay, computer systems organize data across several layers of storage. Small and fast storage is placed close to the CPU, while larger and slower storage is placed farther away.

This organization is called the memory hierarchy.

From fastest and smallest to slowest and largest, the levels are CPU registers, L1 cache, L2 cache, L3 cache, main memory, and persistent storage.

Each level balances three properties:

The closer data is to the CPU, the faster it can usually be accessed.

Ideally, a computer would have a huge amount of memory that is as fast as a CPU register and as inexpensive as storage.

In practice, such memory does not exist.

Fast memory is expensive and difficult to build in large quantities. Larger memory is more affordable, but it takes longer to access.

The memory hierarchy combines several technologies so that the system appears both fast and spacious.

Frequently used data is kept near the CPU. Less frequently used data remains in larger, slower storage until it is needed.

This design works because programs usually do not access all their data equally. At any moment, they tend to repeatedly use a relatively small portion of their instructions and data.

Registers are small storage locations inside the CPU.

They hold values that the processor needs immediately, such as function arguments, addresses, arithmetic operands, and intermediate results.

Consider:

The CPU may place first and second into registers, add them, and store the result in another register.

Accessing a register is extremely fast because the data is already inside the processor. However, the number of registers is limited.

A program cannot keep all its variables in registers. The compiler decides which values should remain there and which must be stored elsewhere.

Registers form the top of the memory hierarchy: they are the fastest storage available to normal instruction execution, but also the smallest.

Main memory is much slower than the CPU.

To reduce the number of times the processor must wait for RAM, modern CPUs include small amounts of fast memory called cache.

The cache stores copies of recently accessed instructions and data.

When the CPU needs a value, it first checks whether that value is already in the cache.

If it is present, the access is called a cache hit.

If it is not present, the access is a cache miss. The processor must retrieve the data from a lower level, which takes longer.

Both branches return the same value to the program. The difference is time: the hit path finishes in a few cycles, while the miss path can cost hundreds.

Caches are managed mostly by hardware. Applications do not normally issue commands such as “store this variable in L1 cache.”

Instead, the processor automatically moves data between cache and memory according to its caching policies.

L1, L2, and L3 Cache

Modern processors usually contain multiple cache levels.

The L1 cache is the smallest and fastest. It is located very close to each CPU core and is often divided into separate instruction and data caches.

The instruction cache stores recently executed machine instructions. The data cache stores values used by those instructions.

The L2 cache is larger but slightly slower. It provides another opportunity to find data before accessing main memory.

The L3 cache is larger again and is commonly shared between multiple CPU cores.

A simplified lookup looks like this:

The search stops at the first level that holds the data, so most accesses never travel the full path. Each cache level reduces the chance that the CPU must wait for slower memory.

The exact cache layout varies between processors. Some CPUs have additional levels or use different sharing arrangements.

Caches do not normally move individual variables one at a time.

Instead, they transfer fixed-size blocks called cache lines.

A cache line often contains several adjacent bytes from memory. When the CPU reads one value, nearby values are brought into the cache as well.

Suppose an array contains:

When the CPU reads values[0], the cache line may also contain several following elements.

Reading values[1] next can therefore be much faster because the required data may already be present.

This behavior is one reason sequential access is often faster than random access.

Main memory, commonly called RAM, stores the active code and data used by running programs.

When a program starts, its instructions and required data are made available through memory. As the program runs, it uses RAM for its stack, heap, libraries, and other working data.

RAM is much larger than CPU cache, but it is also slower.

The difference matters because the CPU can complete many operations during the time required to fetch data from main memory.

If a program frequently requests data that is not present in the cache, the processor may spend significant time stalled while waiting for memory.

RAM is also volatile. Its contents are lost when power is removed.

Persistent data must therefore be stored elsewhere.

Solid-state drives and hard disk drives provide persistent storage.

They hold executables, databases, documents, images, logs, and other files even after the machine is turned off.

Storage capacity is much larger than RAM, but access is considerably slower.

Before the CPU can directly work with data stored in a file, that data generally needs to be brought into memory.

Data climbs the hierarchy one level at a time. An instruction cannot reach directly into a file on disk, which is why reading a file involves copies through memory before the CPU ever sees the bytes.

The operating system helps coordinate movement between storage and memory. We will explore that process later when studying file systems, paging, and I/O.

For now, the key idea is that storage provides capacity and persistence, while memory and cache provide speed.

The memory hierarchy is effective because programs tend to exhibit locality of reference.

Locality means that memory accesses are not completely random. Programs usually reuse recently accessed data or access nearby locations.

There are two important forms of locality.

Temporal locality

Temporal locality means that recently accessed data is likely to be accessed again soon.

Consider a loop:

The variables total and i are used repeatedly. Keeping them close to the CPU improves performance.

Frequently called functions and repeatedly accessed variables also benefit from temporal locality.

Spatial locality

Spatial locality means that when a program accesses one memory location, it is likely to access nearby locations soon.

Sequential array traversal is a common example:

The array elements are adjacent in memory. Fetching one cache line can make several upcoming elements available.

A linked list may have weaker spatial locality because its nodes can be scattered across memory:

Even if the array and linked list contain the same values, the array may be faster to traverse because its layout uses the cache more effectively.

Two programs can perform the same number of operations but have very different execution times.

Consider a large two-dimensional array:

In C, rows are stored next to each other in memory.

Traversing row by row follows the memory layout:

Traversing column by column jumps between distant locations:

The difference is what each step does to the cache line that was just loaded:

Both versions read the same number of values. However, the row-by-row version usually has better spatial locality and produces fewer cache misses.

This reveals an important performance lesson:

The order in which a program accesses data can matter as much as the number of operations it performs.

Suppose the CPU needs a value that is not available in its registers or caches.

The processor requests the cache line containing that value from a lower memory level.

While the data is being retrieved, the CPU may try to execute other independent instructions. Modern processors can rearrange and overlap work to hide some of the delay.

However, if later instructions depend on the missing value, execution may have to wait.

This delay is called a memory stall.

A program with frequent cache misses may therefore use the CPU inefficiently, even when its algorithm appears simple.

Adding more CPU cores or increasing clock speed does not automatically solve poor memory-access behavior.

Each CPU core commonly has private caches, while some lower cache levels may be shared.

This introduces a challenge when multiple cores access the same data.

Suppose one core updates a value that another core has cached. The processor must ensure that both cores do not continue using inconsistent copies indefinitely.

Modern processors use cache-coherence protocols to coordinate these copies.

The hardware handles most of this automatically, but shared writes can still be expensive because cache lines may need to move between cores.

This becomes important in concurrent programs, especially when several threads frequently update nearby memory.

We will examine cache coherence and false sharing later in the concurrency section.

Developers often focus on how much memory a program uses.

Capacity matters because a program cannot exceed the memory available to it. But access speed also matters.

A data structure that fits comfortably in cache can behave very differently from one that is much larger.

For example, repeatedly searching a small lookup table may be extremely fast because the table stays cached. As the table grows, more accesses may need to reach main memory.

This can cause performance to degrade even when the algorithm and number of operations remain unchanged.

The working data used by a program during a period of execution is often called its working set.

Programs usually perform better when their active working set fits within faster levels of the memory hierarchy.

Create a file named locality.c:

Compile it with optimization enabled:

Run it:

The exact results depend on your machine, but the row-first traversal will often be faster.

Both loops visit every element exactly once. The main difference is how they interact with cache lines.

The row-first loop reads adjacent values, while the column-first loop repeatedly jumps across large regions of memory.

This experiment demonstrates that memory layout and access patterns can have a visible effect on performance.

The memory hierarchy influences many backend workloads.

Databases organize pages and indexes to reduce expensive storage and memory access. In-memory caches attempt to keep frequently requested data closer to the CPU than a database or remote service.

Data-processing systems often process records in batches because sequential access is usually more efficient than following scattered pointers.

Even the choice of data structure can matter. Arrays and compact hash tables often have better locality than object-heavy structures with many separate allocations.

This does not mean every application should be manually optimized for CPU caches. Correctness and maintainability still come first.

However, when a program processes large amounts of data or operates under strict latency requirements, understanding the memory hierarchy helps explain performance that algorithmic complexity alone cannot.

Think of the memory hierarchy as a desk, a nearby cabinet, and a distant archive.

The values currently in registers are like items already in your hands.

Cache contains items placed on the desk because they are likely to be needed soon.

Main memory is the nearby cabinet. It holds much more, but retrieving something takes longer.

Persistent storage is the archive. It holds a large amount of information safely, but accessing it is much slower.

Good performance comes from keeping frequently used data near the CPU and accessing memory in predictable patterns.

The memory hierarchy organizes storage into layers that trade speed for capacity.

Registers are the fastest and smallest level. CPU caches store recently used instructions and data. Main memory holds the active state of running programs, while SSDs and disks provide large, persistent storage.

Caches are effective because programs exhibit temporal and spatial locality. They tend to reuse recently accessed values and access nearby memory locations.

When data is not available in the cache, the CPU may need to wait for a slower memory level. Frequent cache misses can significantly reduce performance.

The most important idea is:

A program runs fastest when the data it needs is already close to the CPU.