Memory Locality is a term in computer science used to denote the temporal or spatial proximity of memory access.

In computers, memory is divided up into a hierarchy in order to speed up data accesses. The lower levels of the memory hierarchy tend to be slower, but larger. Thus, it is to a programmer's advantage to use memory while it is cached in the upper levels of the memory hierarchy and to avoid bringing other data into the upper levels of the hierarchy while displacing data that will be used shortly in the future. This is an ideal, and sometimes cannot be achieved.

Memory Hierarchy (access times are approximations for the purpose of discussion. Actual values and actual numbers of levels in the hierarchy may vary):

• CPU registers (8-32 registers), -- immediate access (0-1 cpu cycles)
• L1 and L2 caches (128K-1MB), -- slightly slower access (10 cpu cycles)
• Main memory (RAM) (128MB-2GB), -- slow access (100 cpu cycles)
• Disk (Swap memory and file system), (1GB-1TB) -- very slow (1000-10,000 cycles)
• Remote Memory (such as other computers or the Internet), (Practically unlimited) -- speed varies.

Modern machines tend to read blocks of lower memory into the next level of the memory hierarchy. If this displaces used memory, the operating system tries to predict which data will be accessed least (or latest) and move it down the memory hierarchy. Prediction algorithms tend to be simple to reduce hardware complexity, though they are becoming somewhat more complicated.

A common example is matrix multiplication:

 for i in 0..n for j in 0..m for k in 0..p C[i][j] = C[i][j] + A[i][k] * B[k][j]; 

When dealing with large matrices, this algorithm tends to shuffle data around too much. Since memory is pulled up the hierarch in consecutive address blocks, in the C language it would be advantageous to refer to several memory addresses that share the same row (spatial locality). By keeping the row number fixed, the second element changes more rapidly. In C and C++, this means the memory addresses are used more consecutively. One can see that since j affects the column reference of both matrices C and B, it should be iterated in the innermost loop (this will fix the row iterators, i and k, while j move across each column in the row). This will not change the mathematical result, but it improves efficiency. By switching the looping order for j and k, the speedup in large matrix multiplications becomes dramatic. (In this case, 'large' means, approximately, more than 100,000 elements in each matrix, or enough addressable memory such that the matrices will not fit in L1 and L2 caches)

Temporal locality can also be improved in the above example by using a technique called blocking. The larger matrix can be divided into evenly sized sub-matrices, so that the smaller blocks can be referenced (multiplied) several times while in memory.

 for (ii = 0; ii < SIZE; ii += BL_SIZE) for (kk = 0; kk < SIZE; kk += BL_SIZE) for (jj = 0; jj < SIZE; jj += BL_SIZE) for (i = ii; i < ii + BL_SIZE; i++) for (k = kk; k < kk + BL_SIZE; k++) for (j = jj; j < jj + BL_SIZE; j++) C[i][j] = C[i][j] + A[i][k] * B[k][j]; 

(Diagrams needed for visualizations)

The temporal locality of the above solution is provided because a block can be used several times before moving on, so that it is moved in and out of memory less often. Spatial locality is improved because elements with consecutive memory addresses tend to be pulled up the memory hierarchy together.