How Multi-Dimensional Arrays Are Stored in C

In the C programming language, multi-dimensional arrays are stored as a single, continuous block of memory using a layout known as row-major order. Even though programmers conceptualize these structures as grids, matrices, or higher-dimensional hypercubes, computer memory (RAM) is strictly linear. C flattens multi-dimensional arrays by storing elements row by row, where the rightmost index changes the fastest. Understanding this sequential layout is essential for calculating pointer offsets, ensuring memory safety, and writing performance-optimized, cache-friendly code.

The Mechanics of Row-Major Order

C employs row-major ordering for all multi-dimensional arrays. In this system, elements of the first row are placed consecutively in memory, followed immediately by the elements of the second row, continuing sequentially until the final row.

Consider a two-dimensional array defined as:

int matrix[2][3] = {
    {10, 20, 30},
    {40, 50, 60}
};

Although visualized as a 2x3 table, the compiler allocates a contiguous block of six consecutive integers (2 * 3 = 6). In memory, the array elements are laid out in this exact sequential order:

[10] [20] [30] [40] [50] [60]

Here, matrix[0][0] is stored at the lowest memory address, followed by matrix[0][1], matrix[0][2], matrix[1][0], matrix[1][1], and finally matrix[1][2]. The rightmost subscript changes first as you traverse through memory sequentially.

Address Calculation for 2D Arrays

The compiler computes the exact physical byte address of any given element matrix[i][j] using a deterministic formula. The compiler must know the column size at compile time to calculate the correct stride:

\[\text{Address of } matrix[i][j] = \text{Base Address} + (i \times \text{Number of Columns} + j) \times \text{sizeof(type)}\]

  • Base Address: The starting memory address of the array (&matrix[0][0]).
  • \(i \times \text{Number of Columns}\): Skips past all preceding rows.
  • \(+ j\): Offsets into the target row to locate the specific column.
  • \(\text{sizeof(type)}\): The size in bytes of the underlying data type (e.g., 4 bytes for a standard 32-bit int).

Because the array is contiguous, a standard 1D pointer can traverse the entire structure:

int *ptr = &matrix[0][0];
for (int k = 0; k < 6; k++) {
    printf("%d ", *(ptr + k)); // Outputs: 10 20 30 40 50 60
}

Higher-Dimensional Arrays

The same principle scales recursively to three or more dimensions. In higher dimensions, the rightmost index continues to vary the fastest, while the leftmost index varies the slowest.

For a three-dimensional array:

int tensor[2][3][4];

The data is laid out as two blocks of [3][4] matrices. The sequence of elements in memory proceeds as:

  1. tensor[0][0][0], tensor[0][0][1], tensor[0][0][2], tensor[0][0][3]
  2. tensor[0][1][0], tensor[0][1][1], ...
  3. ... moving through block 0, and then repeating for block 1 starting at tensor[1][0][0].

The memory offset calculation for tensor[i][j][k] is:

\[\text{Address} = \text{Base Address} + \Big( (i \times D_2 \times D_3) + (j \times D_3) + k \Big) \times \text{sizeof(type)}\]

Where \(D_2\) and \(D_3\) represent the sizes of the second and third dimensions, respectively.

Performance Implications: Cache Locality

Because of the sequential row-major layout, the order in which loops iterate over multi-dimensional arrays significantly impacts CPU cache performance. Modern processors fetch memory into cache lines in contiguous chunks.

Iterating through an array row-by-row (row-major traversal) accesses memory sequentially:

// Optimal: Sequential access matches memory layout (Spatial Locality)
for (int i = 0; i < ROWS; i++) {
    for (int j = 0; j < COLS; j++) {
        process(matrix[i][j]);
    }
}

Conversely, iterating column-by-column causes the program to jump across large memory strides:

// Suboptimal: Strided access causes frequent CPU cache misses
for (int j = 0; j < COLS; j++) {
    for (int i = 0; i < ROWS; i++) {
        process(matrix[i][j]);
    }
}

Accessing elements out of sequence forces the CPU to constantly reload cache lines, introducing significant latency in compute-heavy applications. Adhering to C's natural linear row-major layout is critical for achieving optimal runtime efficiency.