Optimizations: Memory Optimizations

Memory: Caches

• Access to main memory is slow

• CPU memory cache to speed access up by magnitudes

• Organized in cache lines ~512 bytes each

• Cache hierarchies

Locality of reference

Rules to keep caches hot

• Group data together, so that nearby data is in the same cache line

• Use contiguous memory where possible; for example

  • Aggregation of structures

  • Sequential access in large (multidimensional?) arrays

  • Sorted arrays rather than fragmented tree structures

• Take care that data does not bounce back and forth between cache and main memory (“cache thrashing”)

• ⟶ Locality of reference

Multidimensional Arrays

C Array Definition

int array[4/*rows*/][3/*columns*/];

4x3 Matrix Conceptually, a rectangular matrix

Memory layout Physically, a linear array

Multidimensional Arrays: Cache Thrashing

• Traversing the matrix columns-first is correct

• … but not efficient

for (j=0; j<rows; j++)
    for (i=0; i<columns; i++)
        access(array[i][j]);

Multidimensional Arrays: Forward Indexing

• Always traverse array row-first

• “Forward indexing”

• Best Locality of reference

for (i=0; i<rows; i++)
    for (j=0; j<columns; j++)
        access(array[i][j]);