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 < 4000; i++) {
    for (j = 0; j < 4000; j++) {
        x[j][i] = i + j;
    }
}

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

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

Each next element is in a different row. A row contains 4000 integers, so consecutive writes are separated by:

4000 × sizeof(int)

On systems where int is 4 bytes, that is typically 16,000 bytes between accesses. This pattern skips over much of memory instead of using nearby values already loaded into the CPU cache.

Caches load memory in small contiguous blocks called cache lines. Sequential access makes good use of each loaded line. Strided access, such as version 1, often loads a cache line but uses only one integer from it before moving far away. It can also put more pressure on the CPU's address-translation cache, called the TLB.

The result is that version 2 usually needs fewer costly memory accesses and runs faster.

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:

long sum = 0;

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

Use descriptive names such as row and col to make the intended access order clear.

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.
4. The inner loop ends. row becomes 1.
5. col starts at 0; write x[1][0] = 10, which follows the end of row 0 in memory.
6. The process continues across row 1.

Now reverse the loop roles:

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

The access order becomes:

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

For a large array, each move from x[row][col] to x[row + 1][col] jumps over an entire row. That is the costly access pattern in version 1 of the question.

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 blocking (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.

When benchmarking loop order, ensure the result is used. If the compiler can prove that array writes are never observed, an optimizing build may remove some or all of the work.

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].

If you need one contiguous dynamic matrix, allocate one flat block:

int *matrix = malloc(rows * cols * sizeof *matrix);
if (matrix == NULL) {
    return 1;
}

matrix[row * cols + col] = 42;
free(matrix);

Benchmarking code that the compiler removes

This can be misleading:

static int x[4000][4000];
/* Write x, but never read it afterward. */

With optimization enabled, the compiler may remove work whose result cannot affect observable behavior. Read and use a result, such as a checksum, or inspect generated code when performing serious benchmarks.

Overusing volatile for benchmarks

volatile can prevent some optimizations, but it changes normal memory-access behavior and is not a general performance-testing solution. Prefer a meaningful result that the program must use.

Optimizing before measuring

Loop order can matter greatly for large arrays, but exact results vary by CPU, compiler, optimization level, cache sizes, and array dimensions. Profile realistic code rather than relying only on a tiny synthetic test.

C, C++, and typical C-style contiguous matrices use row-major order. Some numerical environments and libraries use column-major order. Always match the traversal order to the layout actually used by your data structure.

Loop order is not the only performance factor. Compilers may vectorize loops, hardware may prefetch predictable patterns, and small arrays may fit entirely in cache. However, contiguous access is a strong default for large data.

• 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.