Memory Hierarchy Performance: Cache Line Alignment and Spatial Locality in Arrays

MEMORY HIERARCHY PERFORMANCE: CACHE LINE ALIGNMENT AND SPATIAL LOCALITY IN ARRAYS In computer science, memory is a hierarchical architecture, ranging from fast, small registers to slower, larger RAM. To optimize performance, developers must write code that maximizes cache utilization. For array processing, this optimization depends on understanding spatial locality. ROW-MAJOR VS. COLUMN-MAJOR MEMORY LAYOUTS A two-dimensional array is represented as a grid in code. However, physical computer memory is a flat, one-dimensional sequence of addresses. Compilers map multidimensional arrays to flat memory using one of two methods: - Row-Major Layout: Array elements are stored row-by-row. This layout is used by C, C++, and Python. - Column-Major Layout: Array elements are stored column-by-column. This layout is used by Fortran and MATLAB. Consider the matrix: [1, 2] [3, 4] In a row-major language like C, this matrix is stored sequentially in memory as: 1, 2, 3, 4 CACHE LINE MECHANICS When a CPU reads the value 1 from RAM, it does not fetch only that integer. Instead, the memory controller retrieves a cache line (typically 64 contiguous bytes) and loads it into the L1 cache. This cache line contains the subsequent values 2, 3, and 4. If your code iterates through the array row-by-row: int sum = 0; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { sum += matrix[r][c]; } } The access pattern matches the memory layout (1, then 2, then 3). The CPU registers a cache hit for almost every iteration, as adjacent elements are already loaded in the cache. If your code iterates through the array column-by-column: for (int c = 0; c < cols; c++) { for (int r = 0; r < rows; r++) { sum += matrix[r][c]; } } The access pattern jumps across memory boundaries (1, then 3, then 2, then 4). For large matrices, these non-sequential jumps cause the CPU to evict cache lines constantly, resulting in cache misses and significant performance degradation. Reference: Ray Dawson, "Programming in ANSI C", Section 5: Arrays.