We often conceptualize data as 2D grids (spreadsheets, image pixels, game boards) or 3D volumes (voxel terrain, MRI scans). However, physical computer memory (RAM) is strictly one-dimensional — a linear sequence of byte addresses from 0 to N.
How does a 2D matrix M[R][C] get mapped onto a 1D physical RAM address space?
Row-Major vs Column-Major Order
There are two primary conventions for flattening a multidimensional grid into 1D memory:
Grid:
Row 0: [ A, B, C ]
Row 1: [ D, E, F ]
1. Row-Major Order (C, C++, Java, Kotlin, Python NumPy default)
Consecutive elements of the same row are placed adjacent in memory:
Memory layout: [ A, B, C, D, E, F ]
^-------^ ^-------^
Row 0 Row 1
2. Column-Major Order (Fortran, MATLAB, R, OpenGL)
Consecutive elements of the same column are placed adjacent in memory:
Memory layout: [ A, D, B, E, C, F ]
^----^ ^----^ ^----^
Col 0 Col 1 Col 2
The Row-Major Mapping Formula
For a 2D matrix with dimensions Rows × Cols:
To access element at row r and column c:
1D Index = (r × Cols) + c
RAM Address(M[r][c]) = Base Address + [((r × Cols) + c) × Element Size]
Example Calculation
For a matrix of 3 × 4 integers (Cols = 4, Element Size = 4 bytes), base address 0x1000:
To find M[2][1] (3rd row, 2nd column):
- 1D Index = (2 × 4) + 1 = 8 + 1 = 9
- Address = 0x1000 + (9 × 4) = 0x1000 + 36 = 0x1024
The Performance Impact of Traversal Order
Understanding row-major layout has profound consequences for loop performance.
Fast Traversal (Row-by-Row, Cache Friendly)
// Iterating row by row matches physical memory sequence!
for (r in 0 until rows) {
for (c in 0 until cols) {
sum += matrix[r][c] // Consecutive memory reads -> 100% cache hits
}
}
Slow Traversal (Column-by-Column, Cache Hostile)
// Iterating column by column jumps across memory by 'cols * 4' bytes every iteration!
for (c in 0 until cols) {
for (r in 0 until rows) {
sum += matrix[r][c] // Strided memory jump -> frequent cache misses!
}
}
In large matrices (e.g., 4000 × 4000), the row-by-row loop can run 5x to 15x faster than the column-by-column loop solely due to CPU cache behavior.
Jagged Arrays (Arrays of Arrays)
In Java and Kotlin, a 2D array (Array<IntArray>) is not guaranteed to be a single flat memory block. It is an array of references, where each row is an independently allocated 1D array in the heap:
matrix (pointer array):
[ ptr0, ptr1, ptr2 ]
| | |
v v v
[A,B] [C,D,E] [F] <- Rows can have different lengths!
For high-performance graphics, game engines, or machine learning, engineers prefer a single 1D array (IntArray(rows * cols)) and manually apply the formula r * cols + c to guarantee contiguous memory allocation.
Summary
- Multidimensional arrays must be mapped onto linear 1D physical memory.
- Row-Major places rows back-to-back using the formula:
index = (r * cols) + c. - Always traverse matrices in row-major order (outer loop rows, inner loop columns) to maximize CPU cache performance.