Multidimensional Arrays and Row-Major Ordering

Start with the problem

Programmers often visualize a 2D array as a spreadsheet grid: rows stacked vertically, columns aligned horizontally.

While this visual model aids algorithm design, hardware memory is strictly linear. RAM is a flat, one-dimensional ribbon of byte addresses from zero to gigabytes.

Consider two functions that sum every number in an identical 4096 by 4096 integer matrix:

#define ROWS 4096
#define COLS 4096
int matrix[ROWS][COLS];
 
/* Version A: Row-first traversal */
long long sum_rows(void) {
    long long total = 0;
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            total += matrix[i][j];
        }
    }
    return total;
}
 
/* Version B: Column-first traversal */
long long sum_cols(void) {
    long long total = 0;
    for (int j = 0; j < COLS; j++) {
        for (int i = 0; i < ROWS; i++) {
            total += matrix[i][j];
        }
    }
    return total;
}

Both functions execute the exact same number of iterations (4096 x 4096 = 16,777,216 additions). Both read the exact same values.

When benchmarked, Version A finishes in roughly 15 milliseconds, while Version B takes over 180 milliseconds—more than ten times slower.

Now consider another common compiler failure:

void display_matrix(int **table, int r, int c);
 
int grid[4][4];
display_matrix(grid, 4, 4); /* Warning: passing argument from incompatible pointer type */

If an engineer ignores the compiler warning and runs the binary, the program crashes with a segmentation fault on the first access.

Why did swapping loop variables i and j degrade performance by an order of magnitude? And why is a 2D array fundamentally incompatible with a double pointer int **?

To write performant systems code, you must understand row-major ordering, the linear address translation formula, and how multidimensional arrays decay into array pointers.

How the idea works

C flattens multidimensional arrays into linear memory using row-major ordering.

In row-major order, consecutive elements of the same row are placed immediately next to each other in physical RAM. Only when an entire row finishes does the next row begin.

Logical 2D View: int grid[2][3]
          Col 0    Col 1    Col 2
Row 0:  [  10  ] [  20  ] [  30  ]
Row 1:  [  40  ] [  50  ] [  60  ]
 
Physical 1D Memory Layout:
Base ──► [ 10 ][ 20 ][ 30 ] [ 40 ][ 50 ][ 60 ]
         └───── Row 0 ────┘ └───── Row 1 ────┘
Address: 0x00   0x04   0x08   0x0C   0x10   0x14

1. The Row-Major Indexing Formula

For any 2D array declared as T grid[R][C]:

• R is the number of rows.
• C is the number of columns.
• T is the element type.

To locate element grid[i][j], the compiler does not look up a row index table. It calculates the linear offset directly using arithmetic:

Linear Element Index = (i * C) + j
Byte Address = Base Address + (((i * C) + j) * sizeof(T))

In the trace above:

1. grid contains 2 rows and 3 columns of 4-byte integers.
2. Accessing grid[1][2] evaluates row index i = 1 and column index j = 2.
3. The linear offset is (1 * 3) + 2 = 5 elements.
4. Multiplying by sizeof(int) (4 bytes) produces a 20-byte offset (0x14).
5. Adding 20 to base address 0x7ffd00 arrives at address 0x7ffd14, where value 60 is loaded into register EDX.

Notice that the formula requires the column count C, but does not require the row count R. To step to the next row, the compiler must know how many elements each row contains.

2. Multidimensional Pointer Decay

As established in the previous lesson, an array expression decays into a pointer to its first element.

In a 2D array int grid[2][3], the elements of grid are not integers; they are 1D arrays of 3 integers (int[3]).

Therefore, when grid decays, it does not become an int * or an int **. It decays into:

int (*row_ptr)[3]; /* Pointer to an array of 3 integers */

• int *arr[3] is an array of 3 separate integer pointers.
• int (*arr)[3] is a single pointer targeting an entire contiguous array of 3 integers.

When you increment row_ptr:

row_ptr = row_ptr + 1;

The pointer skips an entire row of 3 integers, advancing the memory address by 3 * sizeof(int) = 12 bytes.

3. Passing Multidimensional Arrays to Functions

Because the compiler needs the column width C to compute (i * C) + j, function declarations must specify all dimensions except the first:

/* Valid parameter signatures: */
void process_2d(int matrix[][4], int rows);
void process_2d(int (*matrix)[4], int rows);
 
/* Invalid signature: compiler cannot compute row strides */
void process_2d(int matrix[][]); /* COMPILE ERROR */

In modern C (C99 and later), you can pass dynamically sized 2D arrays using Variable-Length Array (VLA) parameter syntax, provided the dimension arguments precede the array:

void process_dynamic_vla(int rows, int cols, int matrix[rows][cols]) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            matrix[i][j] = 0; /* Compiler uses passed cols parameter for stride */
        }
    }
}

4. Flat 2D vs. Jagged Pointer Arrays (int **)

A contiguous 2D array is structurally distinct from a pointer-to-pointer array:

Contiguous 2D Array: int grid[2][3]
Memory: [ 10 ][ 20 ][ 30 ][ 40 ][ 50 ][ 60 ] (One continuous allocation)
 
Jagged Pointer Array: int *table[2]
Memory:
table ──► [ ptr0 ][ ptr1 ] (Array of pointers)
             │       │
             ▼       ▼
          [10, 20] [30, 40, 50, 60] (Separate arrays)

In int **table, evaluating table[i][j] requires two separate memory accesses:

1. Dereference table + i to fetch a pointer from memory.
2. Dereference that fetched pointer plus offset j to read the integer.

In a contiguous int grid[2][3], there is no intermediate pointer array. The CPU computes the address mathematically and executes a single memory read. Passing grid to a function expecting int ** causes the function to interpret the raw integer values of the first row (10 and 20) as memory addresses, crashing when it attempts to dereference them.

Why it is correct

Understanding CPU cache architecture explains why row-major traversal runs ten times faster than column traversal.

Spatial Locality and Cache Line Prefetching

Processors do not transfer memory from RAM in 4-byte increments. They fetch data in 64-byte blocks called cache lines.

When your code reads matrix[0][0], the CPU loads that 4-byte integer plus the next 15 consecutive integers (matrix[0][1] through matrix[0][15]) into the high-speed L1 data cache.

Row-Major Traversal:
Step 0: Read matrix[0][0] ──► Cache Miss! Loads matrix[0][0..15] from DRAM.
Step 1: Read matrix[0][1] ──► Cache Hit! (Already in L1 cache, 1 cycle)
Step 2: Read matrix[0][2] ──► Cache Hit!
...
Step 15: Read matrix[0][15] ──► Cache Hit!
Result: 1 cache miss for every 16 reads.

Now consider column-major traversal on a 4096 x 4096 matrix:

Column-Major Traversal:
Step 0: Read matrix[0][0] ──► Cache Miss! Loads matrix[0][0..15].
Step 1: Read matrix[1][0] ──► Strides ahead by 16,384 bytes! Cache Miss!
Step 2: Read matrix[2][0] ──► Strides ahead by 16,384 bytes! Cache Miss!
Result: Cache miss on EVERY single read.

Because each column step jumps 16 kilobytes ahead, every read lands on an un-cached memory page. The hardware prefetcher cannot predict the access pattern, forcing the CPU execution pipeline to stall for hundreds of cycles on nearly every addition.

What it costs

Memory architecture choices for matrices introduce significant structural trade-offs:

Memory Overhead of Jagged Arrays

To store an R x C grid of integers using int **, a program needs:

• Integer elements: R x C x 4 bytes.
• Pointer array: R x 8 bytes (on 64-bit platforms).
• Additional storage for each row, which may be scattered in memory.

For a 1000 x 10 matrix:

• Contiguous layout: 40,000 bytes.
• Jagged layout: 40,000 bytes of data plus 8,000 bytes for row pointers, before accounting for any separate row storage.

Pitfalls and variations

Pitfall 1: Confusing Array of Pointers with Pointer to Array

Because operator precedence groups brackets [] before pointer dereferences *, parentheses drastically alter type declarations:

int *lookup[4];  /* Array of 4 separate integer pointers */
int (*matrix)[4]; /* Single pointer to a contiguous array of 4 integers */

• sizeof(lookup) on a 64-bit system evaluates to 32 bytes (4 x 8).
• sizeof(matrix) evaluates to 8 bytes (a single memory address).

Pitfall 2: Scattered Row Storage

The following fixed-size example demonstrates the layout without introducing dynamic allocation:

A row-pointer table can refer to separately declared arrays:

int row0[4] = {10, 20, 30, 40};
int row1[4] = {50, 60, 70, 80};
int *grid[2] = {row0, row1};

The rows are not guaranteed to be adjacent in memory. Accessing grid[i][j] first loads a row pointer and then accesses the selected element, so it has an extra level of indirection compared with int matrix[2][4].

For comparison, a contiguous array can still be accessed through row pointers:

int data[2][4] = {{10, 20, 30, 40}, {50, 60, 70, 80}};
int *rows[2] = {data[0], data[1]};
 
/* rows[i][j] uses the same contiguous storage as data[i][j]. */

Runtime-sized matrices require dynamic allocation, which is covered later in the C track. The key distinction here is the layout: separate row storage can fragment memory, while a true 2D array keeps all elements contiguous.

Where it is used

Row-major layout and contiguous flattening govern critical systems:

• Image Processing & Framebuffers: Digital images are stored as row-major flat buffers. In an RGB framebuffer, pixel (x, y) is accessed as buffer[(y * width + x) * 3]. Image filters iterate across rows to take full advantage of SIMD vector units.
• BLAS & LAPACK Linear Algebra Libraries: Core numerical libraries that power scientific computing and machine learning run matrix multiplications using row-major (or column-major in Fortran) strides, structuring inner loops into blocked tiles to fit entirely within L1/L2 CPU caches.
• GPU Texture Mapping & Shaders: Graphics processing units transfer textures to hardware video RAM as linear row-major streams, translating coordinate UV mappings into memory offsets using hardware-level address calculation units.

In the next lesson, we will see how character arrays function as text streams: exploring null-terminated C strings, buffer boundaries, and secure string manipulation.