Row-major layout

Why this matters

A two-dimensional array is a table with rows and columns. Images are grids of pixels. Game maps are grids of tiles. Many dynamic programming solutions fill a table of answers, one cell at a time. People draw these tables on paper, and the code is easier to read when it uses the same picture.

Computer memory is not a table. It is one long row of numbered bytes, the same kind of row that the earlier lessons in this module used for a single int. A two-dimensional array has to be placed in that one row somehow. C++ places it in an order called row-major layout. Row-major means the first row is stored first, then the second row, then the third, and each row is stored from its first column to its last column.

This lesson explains that rule. It shows how to find any cell from its row and column number. It then shows why the order of the loops in your program changes how fast the program runs, even when the loops do the same arithmetic. The next lesson in this module covers how the size of a struct is decided. The cache locality lesson later in this module explains the speed result in more depth.

Memory is one line

Start with a small table with three rows and four columns:

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

On paper the numbers form three lines of four numbers each. In memory there is no line break and no grid. The twelve numbers sit side by side with no gap, in this order:

row 0 cells, then row 1 cells, then row 2 cells
1 2 3 4 | 5 6 7 8 | 9 10 11 12

The vertical bars are only for reading. They are not in memory. Each int takes 4 bytes on the machine where this lesson was tested, which is a common size for int. So the whole table takes 3 times 4 times 4, which is 48 bytes.

The table below lists four cells. The position column counts how many numbers come before a cell in memory. The byte offset column counts how many bytes come before it.

Look at the cell grid[1][0]. It is the first number of the second row, and it sits at position 4. Four numbers come before it, which are the four numbers of the first row. That is the whole idea. A row is stored after the row above it, so the position of a cell depends on how many full rows come before it, plus how far along its own row it is.

The formula

The position of any cell follows one rule:

position = row * number_of_columns + column

For this table number_of_columns is 4. Check grid[2][1]. The position is 2 times 4 plus 1, which is 9. Counting from zero, position 9 holds the tenth number, which is 10. Look back at the table of memory above. The value at grid[2][1] is 10.

The byte offset is the position times the size of one element:

byte offset = position * sizeof(int) = (row * number_of_columns + column) * 4

sizeof is an operator that gives the size of a type in bytes. You will see it again in the struct padding lesson.

When you write grid[r][c], the compiler does this arithmetic for you. The expression grid[r][c] means the same as going to the start of the array, moving forward by the position, and reading the value there. The first program below shows the same memory read two ways.

Worked example 1: one array, two views

This program builds the 3 by 4 table and reads the same memory two ways. It uses the pointer rule from the pointer arithmetic lesson, where p + 1 moves to the next element.

#include <cstddef>
#include <iostream>
#include <iterator>
 
int main() {
    int grid[3][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
    };
 
    std::cout << "sizeof(grid) = " << sizeof(grid) << " bytes\n";
    std::cout << "sizeof(grid[0]) = " << sizeof(grid[0]) << " bytes\n";
    std::cout << "rows = " << std::size(grid) << ", columns = " << std::size(grid[0]) << "\n\n";
 
    const int* flat = &grid[0][0];
    std::cout << "Walking the same memory with one index:\n";
    for (int i = 0; i < 12; ++i) {
        std::cout << flat[i] << ' ';
    }
    std::cout << "\n\n";
 
    std::cout << "Element offsets from grid[0][0]:\n";
    for (int r = 0; r < 3; ++r) {
        for (int c = 0; c < 4; ++c) {
            std::cout << "grid[" << r << "][" << c << "] -> element offset "
                      << (&grid[r][c] - flat) << ", byte offset "
                      << (&grid[r][c] - flat) * sizeof(int) << '\n';
        }
    }
    std::cout << '\n';
 
    std::cout << "grid[1] points to the same place as flat + 4: "
              << std::boolalpha << (grid[1] == flat + 4) << '\n';
    std::cout << "grid[2][1] equals flat[2 * 4 + 1]: "
              << (grid[2][1] == flat[2 * 4 + 1]) << '\n';
    return 0;
}

Compile it with g++ -std=c++20 -Wall rowmajor1.cpp -o rowmajor1 and run it. The output is:

sizeof(grid) = 48 bytes
sizeof(grid[0]) = 16 bytes
rows = 3, columns = 4
 
Walking the same memory with one index:
1 2 3 4 5 6 7 8 9 10 11 12 
 
Element offsets from grid[0][0]:
grid[0][0] -> element offset 0, byte offset 0
grid[0][1] -> element offset 1, byte offset 4
grid[0][2] -> element offset 2, byte offset 8
grid[0][3] -> element offset 3, byte offset 12
grid[1][0] -> element offset 4, byte offset 16
grid[1][1] -> element offset 5, byte offset 20
grid[1][2] -> element offset 6, byte offset 24
grid[1][3] -> element offset 7, byte offset 28
grid[2][0] -> element offset 8, byte offset 32
grid[2][1] -> element offset 9, byte offset 36
grid[2][2] -> element offset 10, byte offset 40
grid[2][3] -> element offset 11, byte offset 44
 
grid[1] points to the same place as flat + 4: true
grid[2][1] equals flat[2 * 4 + 1]: true

Three things in this output matter.

The first is sizeof(grid). The whole table is 48 bytes, and one row is 16 bytes. Dividing the two gives the number of rows, 3. The std::size function does the same division for you, and the program uses it to print the row count.

The second is the list of offsets. Each step along a row adds 4 bytes. Each step to the next row adds 16 bytes, which is 4 cells times 4 bytes. The element offset and the byte offset are the same count measured in different units.

The third is the pair of true lines. The name grid[1] names the second row, which is an array of four int values. When it is used in an expression, it turns into a pointer to its first int. That is the same decay rule from the pointer arithmetic lesson. So grid[1] and flat + 4 point to the same place.

Worked example 2: why row-by-row loops are faster

The layout matters for speed. The computer does not read one number at a time from memory. It reads a block of nearby bytes into a small, fast store close to the processor, called the cache. A block of memory that is loaded into the cache is called a cache line. On most current desktop and laptop processors a cache line is 64 bytes, which is 16 int values.

If the next number you need is in the same cache line, it is already close to the processor, and the read is quick. If the next number is in a different cache line, the processor has to wait while the new block is loaded from main memory. Waiting is far slower than reading from the cache.

This means a loop that walks memory in the order it is stored is fast. A loop that jumps around is slow. In row-major memory, going row by row walks memory in order. Going column by column jumps forward by a whole row each step.

The next program fills a 4096 by 4096 table, which is about 64 MB of int values, and runs each sum twice. The first sum goes row by row. The second goes column by column. Both sums must be the same, so the only difference is speed.

#include <chrono>
#include <iostream>
 
constexpr int N = 4096;
 
// About 64 MB. Static storage keeps it off the call stack.
static int matrix[N][N];
 
long long sum_row_by_row() {
    long long total = 0;
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            total += matrix[r][c];
        }
    }
    return total;
}
 
long long sum_column_by_column() {
    long long total = 0;
    for (int c = 0; c < N; ++c) {
        for (int r = 0; r < N; ++r) {
            total += matrix[r][c];
        }
    }
    return total;
}
 
template <typename F>
void run(const char* name, F f) {
    auto start = std::chrono::steady_clock::now();
    long long total = f();
    auto stop = std::chrono::steady_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start).count();
    std::cout << name << ": sum " << total << ", " << ms << " ms\n";
}
 
int main() {
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            matrix[r][c] = (r * 31 + c * 7) % 100;
        }
    }
    run("row by row   ", sum_row_by_row);
    run("column by column", sum_column_by_column);
    run("row by row   ", sum_row_by_row);
    run("column by column", sum_column_by_column);
    return 0;
}

This timing program was built with g++ -std=c++20 -Wall -O2. The -O2 flag turns on optimization, which makes the compiler produce faster code. Use the same flags when you compare two versions, or the comparison means nothing. The output on the test machine, an x86-64 Linux computer with g++ 15.2.0, was:

row by row   : sum 830472180, 6 ms
column by column: sum 830472180, 36 ms
row by row   : sum 830472180, 3 ms
column by column: sum 830472180, 35 ms

Your numbers will differ, because processors, memory speed and background work all change the result. The pattern should still hold: the same sum, but the column walk took about 6 to 12 times longer in this run.

The reason is the cache line. In the row walk, reading matrix[r][0] brings in a cache line that also holds the next 15 numbers, so the next 15 reads are fast. In the column walk, the next read is 16384 bytes away, which is 4096 numbers times 4 bytes. It lands in a different cache line, so most reads wait for memory. The table is far bigger than the cache, so the column walk does not reuse the same cache lines on the next pass either.

A program does not have to be large for this to matter. The effect grows with the size of the table. A small table may fit in the cache, and then the two orders run at similar speed.

Worked example 3: a grid in one flat vector

Real programs often do not use C-style two-dimensional arrays, because the size is fixed at compile time. A common choice is one std::vector that holds all the cells, with the formula from earlier written as a helper. The class below does that. It also returns a row as a std::span, which is a light view of part of an existing range. A span does not copy the numbers. It points at them.

#include <cstddef>
#include <iostream>
#include <span>
#include <vector>
 
// A grid stored as one flat vector, row after row.
class Grid {
public:
    Grid(std::size_t rows, std::size_t cols)
        : rows_(rows), cols_(cols), cells_(rows * cols, 0) {}
 
    int& at(std::size_t r, std::size_t c) { return cells_[r * cols_ + c]; }
    int at(std::size_t r, std::size_t c) const { return cells_[r * cols_ + c]; }
 
    // One row is a contiguous slice of the flat storage.
    std::span<const int> row(std::size_t r) const {
        return std::span<const int>(cells_).subspan(r * cols_, cols_);
    }
 
    std::size_t rows() const { return rows_; }
    std::size_t cols() const { return cols_; }
 
private:
    std::size_t rows_;
    std::size_t cols_;
    std::vector<int> cells_;
};
 
int main() {
    Grid g(3, 4);
    for (std::size_t r = 0; r < g.rows(); ++r) {
        for (std::size_t c = 0; c < g.cols(); ++c) {
            g.at(r, c) = static_cast<int>(r * 10 + c);
        }
    }
 
    std::cout << "at(1, 2) = " << g.at(1, 2) << '\n';
    std::cout << "flat index of (1, 2) = " << 1 * g.cols() + 2 << '\n';
 
    for (std::size_t r = 0; r < g.rows(); ++r) {
        long long sum = 0;
        for (int value : g.row(r)) {
            sum += value;
        }
        std::cout << "row " << r << " sum = " << sum << '\n';
    }
 
    std::cout << "row 2 values:";
    for (int value : g.row(2)) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';
    return 0;
}

The output is:

at(1, 2) = 12
flat index of (1, 2) = 6
row 0 sum = 6
row 1 sum = 46
row 2 sum = 86
row 2 values: 20 21 22 23

The at function is the formula from this lesson in one line. The row function uses subspan to take exactly cols_ numbers, starting at the position where row r begins. Because the storage is one block, a loop over a row reads memory in order, which is the fast pattern from worked example 2.

A common alternative is std::vector<std::vector<int>>, a vector of vectors. It is easy to write, and grid[r][c] looks the same as the C-style array. But each inner vector allocates its own block of memory. The rows are not guaranteed to sit next to each other, so the speed benefit of walking row by row is not guaranteed either. A flat vector with the formula keeps every cell in one block.

Common mistakes

The mistakes below come from real compiler runs with g++ 15.2.0 and the -Wall flag.

Passing a two-dimensional array to a function with the wrong type

A beginner often writes a function that takes int**, which means a pointer to a pointer to int. A two-dimensional array is not that type. The array decays into a pointer to its first row, which is a pointer to an array of four int values. The compiler refuses the call:

rowmajor_mistakes.cpp:18:16: error: cannot convert 'int (*)[4]' to 'int**'
   18 |     show_wrong(grid, 3);
      |                ^~~~

The message names both types. int (*)[4] is "pointer to an array of 4 int", which is the real type of grid. The fix is to declare the parameter with the same row length:

void show(int grid[][4], int rows) {
    for (int r = 0; r < rows; ++r) {
        std::cout << grid[r][0] << '\n';
    }
}

The number of columns must be in the parameter type, because the compiler needs it to compute the position of grid[r][c].

Leaving out the column count

The next mistake is writing a parameter with no column count at all. The compiler needs to know how big each row is, so it rejects the declaration:

rowmajor_mistake2.cpp:3:15: error: declaration of 'grid' as multidimensional array must have bounds for all dimensions except the first
    3 | void show(int grid[][], int rows) {
      |               ^~~~

The first message says the rule exactly. g++ also prints two follow-on errors for the same line, so read the first one. Only the first size may be left out. Every size after it must be written, as in int grid[][4].

Writing the sizes with a comma

Some beginners write int bad[3,4], copying the way a maths book writes a cell. C++ does not accept a comma there:

rowmajor_mistakes.cpp:19:14: error: expected ']' before ',' token
   19 |     int bad[3,4] = {};
      |              ^

g++ also prints two follow-on errors about bad, which usually go away once the first is fixed.

Each size needs its own pair of brackets: int bad[3][4] = {};.

Swapping the row and the column

Nothing in the language stops you from writing grid[c][r] when you meant grid[r][c]. The compiler does not check the index against the size at run time. If c goes up to 3 in a 3 by 4 array, then grid[3][0] reads memory after the end of the array. The result is undefined behaviour in C++ terms, which means the program may print a wrong number, print a number that looks right by chance, or crash. The fix is to name the variables so that the row comes first, and to keep the bounds of each loop matched to the array's row count and column count.

Writing a column-first loop

A loop that goes for (c...) for (r...) is not wrong. It gives the right sum. It is just slower on a large table, as worked example 2 showed. C++ stores two-dimensional arrays row by row, so put the row index on the outside and the column index on the inside.

Practice

Exercise 1. In the array int a[5][7];, how many bytes lie between a[0][0] and a[2][3]?

Show the answer

The position of a[2][3] is 2 times 7 plus 3, which is 17. Each int is 4 bytes, so the byte offset is 17 times 4, which is 68 bytes.

Exercise 2. In the 3 by 4 table from worked example 1, which row and column hold position 9 when you count from zero?

Show the answer

Divide 9 by 4. The quotient is 2, which is the row, and the remainder is 1, which is the column. So the cell is grid[2][1], and its value is 10.

Exercise 3. Given double m[6][3];, what does sizeof(m) return on a machine where double is 8 bytes, and how many rows does std::size(m) report?

Show the answer

The array has 6 times 3 equals 18 elements of 8 bytes each. That is 144 bytes. std::size(m) returns the first dimension, which is 6. A test program printed double m[6][3]: sizeof = 144, rows = 6.

Exercise 4. Using the Grid class from worked example 3, write a function long long column_sum(const Grid& g, std::size_t c) that adds one column, walking down the rows. Fill a 3 by 4 grid with the values 1 to 12 in order, using value = r * 4 + c + 1, and print the sums of columns 0 and 3.

Show the answer

long long column_sum(const Grid& g, std::size_t c) {
    long long total = 0;
    for (std::size_t r = 0; r < g.rows(); ++r) {
        total += g.at(r, c);
    }
    return total;
}

The column 0 values are 1, 5 and 9, so the sum is 15. The column 3 values are 4, 8 and 12, so the sum is 24. A test run printed 15 and 24. This loop reads one number per row, so it jumps by a whole row each step. For a small grid that does not matter. For a large grid it is the slow pattern from worked example 2.

Exercise 5. The loop for (std::size_t c...) for (std::size_t r...) total += m[r][c]; runs over a 4096 by 4096 array m. Does it walk memory in the order the cells are stored? Explain in one or two sentences.

Show the answer

No. The inner loop changes the row, so each step moves forward by one full row of the table. Each read lands in a different cache line. Swapping the two loops makes the inner loop change the column, which walks memory in order.

Summary

• A two-dimensional array is stored in memory as one row after another, which is called row-major layout.
• The position of cell [r][c] is r times the number of columns, plus c, counted from zero.
• The array type must include every size except the first, so the compiler can compute that position.
• The processor reads memory in cache lines, so walking memory in order is much faster than jumping around it.
• A flat std::vector with the position formula keeps all cells in one block, while a vector of vectors does not.