Row-Major vs Column-Major Traversal in C++: Why Memory Access Patterns Matter

yash patel — Sat, 14 Nov 2026 06:42:06 +0000

What if I told you that changing the order of two nested loops could make your program 45 times slower, without changing the amount of work it performs?

That's exactly what I observed in a recent C++ benchmarking experiment.

While exploring low-level performance optimization and GPU inference, I wanted to understand how CPUs access memory and why cache locality matters.

So I decided to benchmark two approaches to traversing a 2D matrix:

Row-major traversal
Column-major traversal

The results were quite surprising.

Let's understand what happened.

1. How is a 2D array stored in memory?

Consider a simple 3 × 4 matrix:

int matrix[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

Although we visualize this as a two-dimensional structure, C++ stores it in contiguous memory using row-major order.

Its physical memory layout looks like this:

1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 12

Elements belonging to the same row are stored next to each other.

For a matrix with N columns, the address of an element is calculated as:

Address(A[i][j]) =
Base + (i * N + j) * sizeof(T)

This means moving from A[i][j] to A[i][j+1] accesses the next contiguous element.

But moving from A[i][j] to A[i+1][j] introduces a larger memory jump.

This difference is the foundation of our experiment.

2. The two traversal patterns

Let's compare two ways of accessing the same matrix.

A. Row-major traversal

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        sum += matrix[i * N + j];
    }
}

Here, we traverse each row before moving to the next.

Memory access pattern:

1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 ...

The CPU accesses neighboring memory addresses.

B. Column-major traversal

for (int j = 0; j < N; j++) {
    for (int i = 0; i < N; i++) {
        sum += matrix[i * N + j];
    }
}

Here, we traverse each column before moving to the next.

Memory access pattern:

1 → 5 → 9 → 2 → 6 → 10 ...

Instead of accessing neighboring elements, we jump between rows.

Both approaches perform the same logical accumulation over the same matrix.

However, their memory access patterns are completely different.

3. Why does row-major traversal perform better?

To understand this, we need to understand CPU cache lines.

Modern CPUs have multiple levels of cache (L1, L2 and L3) that provide faster access to data than main memory.

Data is generally transferred between memory and cache in fixed-size blocks called cache lines.

Let's assume:

Cache line size: 64 bytes.
Integer size: 4 bytes.

Therefore:

64 / 4 = 16 integers

One cache line can hold 16 consecutive integers.

What happens during row-major traversal?

When the CPU accesses the first integer, it typically fetches the entire cache line containing that integer.

The next 15 integers are already available in the same cache line.

This allows the CPU to reuse data that has already been fetched.

This behavior is called spatial locality.

What happens during column-major traversal?

Consider an 8192 × 8192 matrix of integers.

Moving from one row to the next while accessing the same column introduces a stride of:

8192 × 4 = 32768 bytes

That's a 32 KB jump between consecutive accesses.

Instead of efficiently consuming neighboring integers from a cache line, the CPU accesses distant memory locations.

This can result in significantly more cache misses and less efficient memory access.

The important distinction:

Row-major traversal benefits from spatial locality, while column-major traversal often suffers from poor spatial locality.

4. Let's benchmark it!

I used a large matrix to make the memory-access differences more visible.

Matrix dimensions:

8192 × 8192

Total elements:

8192 × 8192 = 67,108,864

Since each integer occupies 4 bytes:

67,108,864 × 4 = 256 MiB

Here is the C++ benchmark implementation:

#include <iostream>
#include <vector>
#include <chrono>
#include <cstdint>
#include <iomanip>

using namespace std;
using namespace chrono;

const int N = 8192;

int main() {

    vector<int> matrix(N * N);

    // Initialize matrix
    for (size_t i = 0; i < matrix.size(); i++) {
        matrix[i] = i % 100;
    }

    uint64_t row_sum = 0;
    uint64_t col_sum = 0;

    // Warm-up
    for (size_t i = 0; i < matrix.size(); i++) {
        row_sum += matrix[i];
    }
    row_sum=0;
    // Row-major traversal
    auto start = steady_clock::now();

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            row_sum += matrix[i * N + j];
        }
    }

    auto end = steady_clock::now();

    double row_time =
        duration<double, milli>(end - start).count();

    // Column-major traversal
    start = steady_clock::now();

    for (int j = 0; j < N; j++) {
        for (int i = 0; i < N; i++) {
            col_sum += matrix[i * N + j];
        }
    }

    end = steady_clock::now();

    double col_time =
        duration<double, milli>(end - start).count();

    cout << fixed << setprecision(2);

    cout << "Row-major: " << row_time << " ms\n";
    cout << "Column-major: " << col_time << " ms\n";

    cout << "Slowdown: "
         << col_time / row_time << "x\n";

    cout << "Checksums: "
         << row_sum << ", " << col_sum << "\n";
}

Compile with optimizations:

g++ -O3 -march=native -std=c++17 benchmark.cpp -o benchmark

./benchmark

5. My actual benchmark results

I ran the experiment on my machine using an 8192 × 8192 matrix.

Here are the results:

Traversal	Execution Time
Row-major	9.31 ms
Column-major	422.74 ms

Column-major traversal was 45.41× slower than row-major traversal.

Let's calculate the slowdown:

422.74 / 9.31 = 45.41x

I also verified that both traversals produced the same checksum:

Row-major checksum:    3321887616
Column-major checksum: 3321887616

This confirms that both traversals accumulated the same initialized matrix values.

Why such a significant difference?

The answer lies in memory access patterns.

In row-major traversal, consecutive accesses are to neighboring memory locations. This allows efficient cache-line utilization and benefits from spatial locality.

In column-major traversal, consecutive accesses are separated by 32 KB in this experiment.

This creates a much less favorable access pattern, potentially increasing cache and TLB misses and reducing effective memory bandwidth.

One important clarification: both algorithms logically process the same 256 MiB of matrix data, but the actual memory traffic and cache behavior can differ significantly.

The exact performance difference depends on the processor, cache hierarchy, compiler, memory subsystem and benchmark conditions.

My biggest takeaway: The way we access data can matter just as much as the computation we perform on it.

6. Connecting this to GPU optimization and LLM inference

This is where the experiment becomes particularly interesting to me.

While studying high-performance matrix multiplication (GEMM), I came across a technique called Tiling.

Instead of repeatedly accessing an entire matrix from slower memory, we divide it into smaller blocks.

The GPU loads these blocks into faster memory, such as shared memory, and reuses them for multiple computations.

The general idea:

Load a tile from matrix A.
Load a tile from matrix B.
Perform multiple multiply-accumulate operations.
Reuse the loaded values.
Move to the next tile.

This reduces data movement relative to the amount of computation performed.

The same broader principle appears in:

CPU cache blocking.
CUDA shared-memory tiling.
Triton GEMM kernels.
FlashAttention.
GPU Tensor Core optimization.

Understanding memory locality at the CPU level gives us a foundation for understanding why data movement is such an important part of GPU performance.

One thing I'm learning while exploring inference engineering:

Optimizing computation is only half the story. Understanding how data moves through the hardware is equally important.

This is just the beginning of my journey into systems performance and LLM inference optimization.

More experiments coming soon!

DEV Community: yash patel