Locality of reference

From Helpful
Revision as of 12:54, 26 April 2023 by Helpful (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
This article/section is a stub — probably a pile of half-sorted notes and is probably a first version, is not well-checked, so may have incorrect bits. (Feel free to ignore, or tell me)


In a lot of real-world programs, there are recognizable patterns to the way you access resources.

For example, RAM accesses and disk accesses are often quite predictable, in different ways, which means you as a coder can get some cheap optimizations just from sitting down and thinking a few minutes.

It also the reason certain hardware caches (or software caches) can go a long way.


Locality of reference is this idea, in the generic sense.

We care about the more specific cases of it.


The simplest to understand is temporal locality, the idea that if a memory location is accessed, chances are decent the exact same will be accessed again soon, e.g. because it's a common variable.


Another common one is spatial locality, the idea that if a location is accessed, it is likely that the one next to it will be accessed very soon.

In particular disks are often read out in reasonably-sized sequential chunks, so the disk and/or OS may readahead, caching the next few megabytes. (In pathological cases this is structurally worse - so then you disable it - but in most cases it's neutral to positive)


RAM access from execution have more complex patterns, but are also so central and happening literally all the time that memory locality is treated as a special case (of, mostly, spatial locality).

The design/layout of hardware caches like L1 and L2 is a study in itself. You can read up on why e.g. cache lines are the concept that they are, and how it relates to DDR bursts in current practice, and more.


Branch locality is another interesting result from execution. It's what happens when code jumps going to one of very few targets (and does this regularly). This isn't necessarily closeby (spatial), depending on the size of the code and amount of outcomes.

It's more related to temporal, since in the shorter term, demand-driven cacheing means it's likely to still be cached.

But it also argues that compilers keeping hot code close together are going to put less load on caches, so probably lead to faster execution.

(Also related to branch prediction, though that is more about keeping CPU pipelines busy)


Sequential locality is when you can assume or detect a pattern like sequential data reading.

Spatial would cover part of that, but not e.g. at the edges of cache lines or for larger-interval accesses.(verify)


See also: