Processor caches keep recently used memory close to execution cores, but cache capacity alone does not determine which data can remain resident. Most general-purpose CPU caches divide storage into sets and give each set a fixed number of slots, commonly called ways.

A memory block maps to a particular set. It can occupy any way inside that set, but it cannot move into an unrelated set merely because that other set has free space. This placement rule makes hardware lookup practical and fast, while creating a distinct source of misses when too many active blocks compete for the same set.

That behavior is cache associativity. It connects address mapping, replacement policy, and workload access patterns to performance.

A cache line is the placement unit

CPU caches transfer and track memory in fixed-size blocks called cache lines. A common line size is 64 bytes, although the exact size is an architectural property.

When code reads one byte that is absent from a cache, hardware normally fetches the containing line. Nearby bytes arrive with it. This spatial granularity means cache placement works with line addresses rather than individual byte addresses.

A simplified line address is

line_address = memory_address / line_size

The cache then uses part of that line address to select a set. The remaining identifying bits are stored as a tag so hardware can tell which memory block currently occupies a way.

Set count and way count divide total capacity

Consider a 32 KiB cache with 64-byte lines and eight ways. It contains 512 line slots in total:

32768 / 64 = 512 lines

With eight ways per set, the cache has 64 sets:

512 / 8 = 64 sets

Each memory line maps to one of those 64 sets. Within its selected set, it has eight possible slots.

The same total capacity could be organized differently. A direct-mapped cache has one way per set. A fully associative cache permits a line to occupy any slot. Set-associative designs sit between those extremes.

More ways provide more placement flexibility, but they also require hardware to compare more candidate tags and choose among more resident lines.

Multiple addresses can compete for one set

For a simple power-of-two cache organization, set selection can be represented conceptually as

set = line_address mod number_of_sets

Real processors can apply additional indexing techniques, especially in larger or shared caches, so this formula is a model rather than a universal implementation rule.

The model still exposes the core effect. If several active memory lines produce the same set index, they compete for that set’s ways.

In the eight-way example, eight competing lines can reside together. Accessing a ninth distinct line mapped to the same set requires a victim to be replaced, even if many slots in other sets are unused.

A later access to the evicted line then misses and must obtain it from another cache level or memory hierarchy location.

Conflict misses can appear below nominal capacity

A working set can be smaller than the advertised cache capacity and still miss frequently. The relevant condition is not only total bytes. Distribution across sets matters.

Suppose a loop repeatedly accesses nine lines that all map to one set of an eight-way cache. The active data occupies only 576 bytes:

9 * 64 = 576 bytes

Yet those nine lines cannot all reside in that set at once. Depending on access order and replacement behavior, the loop can repeatedly evict data that will soon be requested again.

This is a conflict pattern. It differs from a pure capacity miss, where the active data genuinely exceeds the cache’s total usable storage.

Higher associativity reduces many conflict patterns because each set can retain more competing lines. It does not remove finite capacity or guarantee that every access sequence will remain resident.

Replacement policy decides which way becomes available

When a set is full and a new line arrives, the cache needs a victim. Textbook explanations often use least recently used replacement, but processor implementations can use approximations or other policies that reduce hardware cost or improve behavior for common workloads.

Replacement policy matters because associativity only states how many candidate slots exist. It does not state which resident line will be discarded.

Two processors with caches of equal size, line size, and associativity can therefore react differently to the same access sequence if their replacement mechanisms differ. Prefetching and cache inclusivity policies can also alter observed results.

For performance work, associativity is one structural factor rather than a complete cache model.

Strides can create concentrated set pressure

Regular array access can expose set mapping effects. If successive addresses are separated by a stride that repeatedly selects the same small group of sets, a large cache can be used unevenly.

For the simplified 64-set, 64-byte-line example, addresses separated by 4096 bytes differ by 64 cache lines:

4096 / 64 = 64 lines

Under the simple modulo mapping, those lines select the same set. Repeatedly touching enough such locations can exceed the available ways.

Changing data layout, padding, traversal order, or allocation alignment can alter which sets receive pressure. Such changes are workload-specific and should be measured rather than applied mechanically.

Modern address hashing, virtual indexing details, prefetchers, and multiple cache levels can make physical behavior less tidy than the simple example.

More associativity has hardware costs

A one-way cache needs to check one candidate tag after selecting a set. An N-way cache may need to determine which of N candidate tags matches the requested address.

Higher associativity can reduce conflict misses, but additional ways increase tag-comparison work and replacement-state complexity. Designers balance hit rate, access latency, energy, area, and implementation timing.

This tradeoff helps explain the common use of moderate set associativity rather than making every cache fully associative. Full placement freedom is attractive from a miss perspective, but searching a large number of possible entries at CPU-cache speed is expensive.

Different levels can use different associativity because their size, latency target, sharing model, and role in the hierarchy differ.

Capacity, line size, and associativity describe separate properties

Cache specifications often list capacity first, but three values answer different questions:

  • Capacity states the total data storage available.
  • Line size states the transfer and placement granularity.
  • Associativity states how many slots are available within the selected set.

A larger cache can still experience concentrated conflicts. A cache with more ways can still be too small for the working set. A larger line can improve spatial reuse for contiguous data while wasting bandwidth and capacity when neighboring bytes are not used.

Performance analysis needs the access pattern alongside these structural properties.

Measurements should vary layout as well as data size

A benchmark that only sweeps working-set size can reveal cache-level transitions, but it can miss placement sensitivity. Testing different strides, alignments, and data layouts can expose conflict effects.

Hardware performance counters can provide cache-reference and cache-miss data, subject to the events exposed by a given processor. Timing repeated access patterns can also show sharp changes when the number of competing lines exceeds a set’s effective residency.

Microbenchmarks need care. Compiler optimization, prefetching, out-of-order execution, translation caches, page placement, and measurement overhead can all affect results.

The useful conclusion is structural: cache bytes are partitioned by placement rules. A line gets a limited set of possible homes, and heavy competition for those homes can force replacement before the cache is globally full.

CPU Cache Memory Performance