The Memory Hierarchy and Why Caching Works

Temporal locality means accessing the same memory location again soon. A loop repeatedly reading a lookup entry shows temporal locality. The benefit depends on whether that entry remains available in a fast level. Reuse of a location is different from visiting several neighbouring locations.

A cache line is a fixed block of neighbouring bytes copied into a cache on a miss. A miss means the requested data is absent. In row-major storage, each row's elements are consecutive and rows follow one another. Row-first traversal then visits neighbours; column-first jumps between rows. On large arrays, those jumps can reduce use of each line before eviction. These access patterns do not guarantee a particular speed ratio.

To count misses, specify line size, alignment, initial contents and capacity. Aligned line starts are multiples of the line size in bytes. In a cache holding one line, the first access misses. Another address in that resident line hits. An address in a different line misses and replaces it. Compare complete address sequences, not just drawings. Real runtime also depends on other work and hardware.

Spatial locality means accessing nearby memory locations close together in time. Consecutive one-byte elements occupy addresses differing by 1. Reading them in order uses neighbouring bytes. Array indices alone do not prove this layout: state that the elements are stored consecutively before treating their indices as neighbouring addresses.

In the typical hierarchy used here, total capacity increases from registers to caches, main memory and disk. This is a size ordering, not an access-time measurement. Register storage is limited but close to the execution hardware; larger levels provide room for more data. Particular devices can differ from this typical ordering.

Read the layout before choosing a traversal. Column-major storage puts each column's elements together, so column-first visits neighbours. A drawing's row or column length does not set memory order. For a two-row, three-column example, the columns below occupy consecutive addresses. Access order suggests locality, but does not alone guarantee which traversal will run faster.