2D Array Loop Order and Cache Performance in C

You will learn how C stores two-dimensional arrays in memory and why accessing elements in row order is usually much faster. The key idea is cache locality: processors work fastest when code accesses nearby memory locations consecutively.

In C, a two-dimensional array declared as:

int x[4000][4000];

is stored in row-major order. This means all elements of row 0 are stored first, then all elements of row 1, and so on:

x[0][0], x[0][1], x[0][2], ... x[0][3999],
x[1][0], x[1][1], x[1][2], ...

The rightmost index varies fastest in memory. Therefore, x[row][column] is most efficient when the column index changes in the inner loop.

In version 2:

for (j = 0; j < 4000; j++) {
    for (i = 0; i < 4000; i++) {
        x[j][i] = i + j;
    }
}

i changes in the inner loop, so the code writes:

x[j][0], x[j][1], x[j][2], x[j][3], ...

Those elements are adjacent in memory. This is cache-friendly.

In version 1:

for (i = 0; i < ; i++) {
     (j = ; j < ; j++) {
        x[j][i] = i + j;
    }
}

Imagine the array as a bookshelf.

• Each row is one shelf.
• Each integer is a book beside the next book.
• The CPU cache is a small cart that brings in a short run of neighboring books at once.

Version 2 reads or writes one shelf from left to right. When the cart brings books from that shelf, the next books needed are already on the cart.

Version 1 takes one book from the first shelf, then one from the second shelf, then one from the third shelf. It repeatedly travels between shelves and gets little benefit from the neighboring books it brought along.

For a C array x[rows][columns], keep the column index in the inner loop whenever possible.

A C multidimensional array has this general form:

int table[ROWS][COLUMNS];

Access an element with:

table[row][column]

For row-major traversal, the first index belongs in the outer loop and the second index belongs in the inner loop:

#include <stddef.h>

#define ROWS 3
#define COLS 4

int main(void) {
    int table[ROWS][COLS];

    for (size_t row = 0; row < ROWS; row++) {
        for (size_t col = 0; col < COLS; col++) {
            table[row][col] = (int)(row + col);
        }
    }

    return 0;
}

For row == 1, the inner loop visits:

table[1][0], table[1][1], table[1][2], table[1][3]

These values are contiguous in memory.

The same principle applies when reading:

Consider this small array:

int x[2][3];

for (int row = 0; row < 2; row++) {
    for (int col = 0; col < 3; col++) {
        x[row][col] = row * 10 + col;
    }
}

C lays out x in memory in this order:

x[0][0], x[0][1], x[0][2], x[1][0], x[1][1], x[1][2]

Execution proceeds as follows:

1. row is 0 and col is 0; write x[0][0] = 0.
2. col becomes 1; write x[0][1] = 1, immediately after the prior element in memory.
3. col becomes 2; write x[0][2] = 2, again adjacent in memory.

Loop order matters whenever a program repeatedly processes large grids or matrices.

• Image processing: Images are commonly stored as rows of pixels. Processing pixels left to right, then top to bottom, usually has good locality.
• Scientific computing: Simulations store temperatures, pressures, or particle-grid values in 2D and 3D arrays.
• Machine learning: Matrix operations process large numeric arrays, where memory access patterns can strongly affect runtime.
• Game development: Tile maps, terrain data, heat maps, and visibility grids are often traversed row by row.
• Data analysis: Tables represented as contiguous numeric arrays benefit when loops follow their storage layout.
• File and network buffers: Sequential scanning of buffers is generally more cache-friendly than repeatedly jumping through them.

The best loop order depends on the data layout. C built-in arrays are row-major, but some libraries and file formats use different layouts.

In production C code, developers often make data layout and iteration order explicit.

A common pattern is to define dimensions once and traverse rows first:

#define HEIGHT 1080
#define WIDTH 1920

void brighten(unsigned char image[HEIGHT][WIDTH]) {
    for (size_t row = 0; row < HEIGHT; row++) {
        for (size_t col = 0; col < WIDTH; col++) {
            if (image[row][col] < 255) {
                image[row][col]++;
            }
        }
    }
}

For dynamically allocated contiguous storage, code may use a one-dimensional buffer and calculate an index:

size_t index = row * width + col;
pixels[index] = value;

This makes the row-major layout explicit. A cache-friendly traversal still keeps col in the inner loop:

for (size_t row = 0; row < height; row++) {
    for (size_t col = 0; col < width; col++) {
        pixels[row * width + col] = 0;
    }
}

For expensive matrix algorithms, developers may also use (processing small rectangular tiles) so a working region fits in cache. That is useful after simple row-wise traversal is already correct and performance measurements show it is needed.

Assuming x[i][j] and x[j][i] are interchangeable

They access different elements unless the matrix is symmetric and the dimensions allow both indices.

/* Different locations in general */
x[i][j] = 1;
x[j][i] = 2;

Swap loop order without changing the meaning by changing only which loop is outer or inner, as in the original examples.

Believing the first index is contiguous

For a C array declared as x[ROWS][COLS], the elements x[row][0], x[row][1], and x[row][2] are adjacent. Elements x[0][col] and x[1][col] are separated by COLS integers.

Using a pointer-to-pointer as if it were a contiguous 2D array

This is not a valid replacement:

int **matrix;

An int ** usually represents pointers to separately allocated rows. It does not have the same type or guaranteed layout as int matrix[ROWS][COLS].

• C stores T array[ROWS][COLS] in row-major order.
• array[row][col + 1] is adjacent to array[row][col].
• The rightmost array index should usually change in the inner loop.

for (size_t row = 0; row < rows; row++) {
    for (size_t col = 0; col < cols; col++) {
        use(array[row][col]);
    }
}

• Address idea for int x[ROWS][COLS]:

address of x[row][col] ≈ base + ((row * COLS) + col) * sizeof(int)

• Moving to the next row at the same column skips COLS elements.
• Sequential access improves cache-line use and usually helps hardware prefetching.
• For dynamic contiguous storage, use buffer[row * cols + col].
• Benchmark optimized code carefully: make the computed result observable.
• Check the layout of external libraries; not every matrix is row-major.

Why is the second loop order faster in C?

C stores a two-dimensional array row by row. The second version changes the column index in the inner loop, so it accesses adjacent memory locations and uses CPU cache lines efficiently.

Does C store every 2D array contiguously?

A true array such as int x[10][20] is contiguous. An int ** with separately allocated rows is not necessarily contiguous across rows.

What does row-major order mean?

It means all columns of the first row are stored first, followed by all columns of the next row. For x[row][col], col is the contiguous direction.

Will loop order always make a noticeable difference?

No. Small arrays may fit in cache, and compilers and processors can reduce some penalties. For large arrays, repeated work, and memory-bound code, the difference can be substantial.

Is the slower version incorrect?

No. Both versions assign the same value to every element of this square array. They differ primarily in the order in which memory is visited.

Should I always put the second index in the inner loop?

For ordinary C multidimensional arrays, that is usually the best default. If your data uses a different layout, follow that layout's contiguous dimension instead.

Why can a benchmark produce unexpected results with optimization enabled?

If the program never uses the written array, the compiler may legally remove stores that have no observable effect. Make the calculation's output observable before drawing conclusions.

• CPU cache — Explains why nearby memory accesses are cheaper than distant ones.
• Cache locality — The general principle behind efficient memory-access patterns.
• Row-major order — The storage order used by C multidimensional arrays.
• Column-major order — A contrasting layout used by some languages and numerical libraries.
• Pointer arithmetic — Helps explain row * columns + column indexing in flat buffers.
• Dynamic memory allocation — Needed when matrix dimensions are known only at runtime.
• Loop optimization — Includes loop interchange, blocking, and compiler vectorization.
• Benchmarking C programs — Helps avoid incorrect measurements caused by compiler optimization.