The Processor Cache

The previous two lessons placed two facts side by side: the processor operates only on registers, and a main memory access can take hundreds of clock cycles. If these two facts were combined directly, the processor would spend nearly all its time waiting.

This lesson’s subject is the layer that closes that gap: the cache. The cache is managed by hardware and is invisible to the program; but the program’s behavior determines whether the cache does its job. This is why, despite being an invisible layer, it must be understood.

The Locality Principle

The cache’s operation rests on a single observation: programs’ memory accesses are not random. Two tendencies are observed.

Temporal locality: An address accessed recently is likely to be accessed again soon. A loop counter is read and written on every iteration throughout the loop.

Spatial locality: If an address has been accessed, neighboring addresses are likely to be accessed too. A loop that walks an array from start to end reads consecutive addresses in order; because instructions also sit consecutively in memory, instruction flow shows the same tendency.

The cache exploits both tendencies: it keeps recently used data (temporal) and fetches a datum’s neighbors along with it when requested (spatial).

The Cache Line

The exchange between cache and main memory is not carried out one byte at a time. The unit of transfer is the cache line; its width varies by hardware and is typically tens of bytes.

This has a direct consequence: when a byte is requested, the entire line it belongs to is fetched. Reading one four-byte integer and reading the sixteen integers that share its line cost the same in terms of memory traffic.

An access yields one of two outcomes:

• Hit: The requested data is in the cache; access is fast.
• Miss: The data is not in the cache; a line is fetched from a lower layer, and the processor waits during that time.

Fetching a new line while the cache is full requires evicting an existing one. Which line gets evicted is decided by the eviction policy; the most common approach evicts the line that has gone unused the longest. The same principle recurs in every layer where the concept of caching appears — database caches, content delivery networks, browser caches.

Layers

The cache is not a single unit; it consists of layers graded from speed toward capacity. The layer closest to the core is the smallest and fastest; moving outward, capacity grows and latency increases. The lower layers are usually shared across cores.

This layering fills the middle of the memory hierarchy introduced in the previous lesson. Numeric values vary by hardware; what does not vary is the principle that each layer is a slower, larger copy of the one above it.

There is one more distinction: in most designs, instructions and data are kept in separate caches at the level closest to the core. Instruction flow and data flow have different access patterns, and neither is meant to evict the other’s lines.

The Consequence of Access Pattern

The locality principle explains why two programs doing the same work can perform differently. Consider summing a two-dimensional table. The table is stored in memory row by row: a row’s elements sit at consecutive addresses, and the row below it starts one row’s length further along.

Traversing by row reads consecutive addresses. The first access misses and fetches the whole line; the following accesses hit.

Traversing by column skips one row’s length on every step. Only one element of the fetched cache line is used; the rest can be evicted unused.

Both loops perform the same number of additions; the difference lies in memory traffic. This difference can be computed without measuring time: by counting the number of cache lines fetched.

LINE_BYTES = 64          # example cache line width
ELEMENT_BYTES = 8        # width of one integer
N = 1024                 # N x N table

elements_per_line = LINE_BYTES // ELEMENT_BYTES      # elements per line: 8

# By row: all eight elements of each fetched line are used.
by_row = N * N // elements_per_line

# By column: consecutive accesses are N * ELEMENT_BYTES bytes apart.
# If the table does not fit in the cache, only one element of the fetched line is used.
by_column = N * N

print(by_row, by_column)            # 131072 1048576
print(by_column / by_row)           # 8.0

For the same number of additions, the amount of data moved differs by a factor of eight, and that factor is the number of elements that fit in a cache line. As elements shrink, the factor grows: sixteen for four-byte elements, sixty-four for one-byte elements.

This calculation does not directly yield the actual duration. The measured difference is determined together with prefetching, address translation, and the memory controller’s behavior. In interpreted languages, the per-element interpretation cost masks most of the difference; the locality effect is therefore measured most clearly in languages that store elements contiguously and carry no per-element interpretation cost.

Write Policies

So far, reading has been described. Writing requires an additional decision: when is modified data transferred to the lower layer?

In the write-through policy, every write is applied to both the cache and the lower layer. The layers are consistent at every moment; the cost is that every write reaches the slow layer.

In the write-back policy, writing is done only to the cache; the line is marked dirty and is written to the lower layer only when evicted. Successive writes to the same line collapse into a single transfer; in exchange, the lower layer carries a stale value for a while.

The same two options appear in every layer where caching is used; database and application caches refer to them by the same names.

Multi-core systems raise an additional problem: a copy of the same memory line can sit in more than one core’s cache. When one core modifies its copy, the copies held by the others become invalid. Hardware maintains this consistency through an inter-core protocol. The visible consequence is that threads running on different cores writing frequently to the same cache line degrade performance, even when the data is not logically shared.

Consequences Visible to the Program

The cache cannot be controlled directly, but data layout and access order can be chosen. The common traits of cache-friendly code are:

• Contiguous layout. Arrays that store elements contiguously produce fewer misses than structures whose elements sit in separate locations linked by pointers. This is the performance dimension of the linked-list-versus-array comparison in the data structures course.
• Matching access order to layout order. Data is placed in the order it will be read.
• Keeping hot data small. If the data touched on every iteration of a loop fits in one cache layer, the loop draws only hits throughout.
• Not carrying unused fields. Unused fields inside a structure reduce the amount of useful data per line.

None of these principles requires premature optimization. The meaningful order is: correct and readable code first, then measurement, then applying these principles where the measurement points.

Summary

• The cache is a hardware-managed intermediate layer that closes the speed gap between the processor and main memory.
• Its operation rests on the locality principle: temporal locality predicts that recently used data will be used again, spatial locality that neighboring addresses will be accessed.
• The unit of transfer is the cache line; when a byte is requested, the entire line is fetched.
• Hits are fast, misses are costly; when the cache is full, the eviction policy decides which line is removed.
• Two loops doing the same work run in different times depending on access pattern; sequential access is faster than jumping access.
• The cache cannot be controlled directly; what can be controlled is data layout and access order.

Next Step

Up to this point, the processor has been treated as a closed system executing instructions in an order it determines itself. But the outside world — the keyboard, the disk, the network interface, the timer — demands the processor’s attention. The next lesson covers how that demand is communicated and how the flow is interrupted.