Multidimensional Arrays and Row-Major Layout

Part I · Module 9 · Chapter 9.3 · Multidimensional Arrays and Row-Major Layout

1. An Array of Arrays

    int m[2][3] = {{1, 2, 3}, {4, 5, 6}};

Read that as an array of 2 things, each of which is an array of 3 ints. Not "a 2×3 grid" — the grid is a picture you draw on top of it; the type is a nesting.

That reading is worth insisting on because every rule in this chapter falls out of it:

m has type int[2][3]. Both counts are in the type, exactly as Chapter 9.1 §2 said.

m[0] has type int[3] — it is itself an array, and Chapter 9.1's rules apply to it.

m[0][0] has type int.

So indexing twice is indexing once, twice. And since Chapter 9.1 §5 established that a[i] is *(a + i), m[r][c] is *(*(m + r) + c) — one step in units of rows, then one in units of ints.

2. Measured: the Layout Is Row-Major

#include <cstdint>
#include <iostream>

int main()
{
    int m[2][3] = {{1, 2, 3}, {4, 5, 6}};

    std::cout << "sizeof(m)       = " << sizeof(m)       << "   (whole array)\n";
    std::cout << "sizeof(m[0])    = " << sizeof(m[0])    << "   (one row)\n";
    std::cout << "sizeof(m[0][0]) = " << sizeof(m[0][0]) << "   (one element)\n\n";

    const auto base = reinterpret_cast<std::uintptr_t>(&m[0][0]);
    for (int r = 0; r < 2; ++r)
        for (int c = 0; c < 3; ++c)
            std::cout << "  m[" << r << "][" << c << "] = " << m[r][c]
                      << "   offset " << (reinterpret_cast<std::uintptr_t>(&m[r][c]) - base) << " bytes\n";
    return 0;
}

Measured output, zero warnings:

sizeof(m)       = 24   (whole array)
sizeof(m[0])    = 12   (one row)
sizeof(m[0][0]) = 4   (one element)

  m[0][0] = 1   offset 0 bytes
  m[0][1] = 2   offset 4 bytes
  m[0][2] = 3   offset 8 bytes
  m[1][0] = 4   offset 12 bytes
  m[1][1] = 5   offset 16 bytes
  m[1][2] = 6   offset 20 bytes

Three readings.

The sizes nest. 24 = 2 × 12, and 12 = 3 × 4. An array of 2 arrays of 3 ints, with no padding and no header — Chapter 9.1's model, applied twice.

The offsets are 0, 4, 8, 12, 16, 20 — one unbroken run of six ints. There is no gap anywhere, so the "grid" is genuinely a single sequence.

m[1][0] is at offset 12, immediately after m[0][2] at offset 8. That is the whole of row-major order:

Row-major means the last index varies fastest. Walking m[0][0], m[0][1], m[0][2], m[1][0], … visits consecutive bytes. The elements of a row are adjacent; the elements of a column are a row apart.

The decision had to be made and C++ made it this way. Some languages — Fortran, MATLAB — chose the opposite, which is why moving numerical code between them requires attention to exactly this.

3. Three Dimensions Change Nothing

    int cube[2][3][4];

An array of 2 arrays of 3 arrays of 4 ints. Measured:

sizeof(cube)       = 96
sizeof(cube[0])    = 48   (stride of the 1st index)
sizeof(cube[0][0]) = 16   (stride of the 2nd)
offset of cube[1][2][3] = 92 bytes
formula ((1*3 + 2)*4 + 3)*4 = 92

The formula and the measured offset agree exactly. The last index still varies fastest, and each stride is the product of the dimensions to its right: 48 = 3 × 4 × 4, and 16 = 4 × 4.

The general rule, for any number of dimensions:

The last index is the fastest-varying one, and each index's stride is the product of all the dimensions to its right, times the element size.

Nothing new is required. The nesting reading in §1 generalises directly, which is the reason the frozen purpose asks for two and three dimensions in one chapter.

4. Decay, Revisited

Chapter 9.2 established that passing an array loses the length. With more than one dimension it loses only the first.

#include <iostream>
#include <type_traits>

static void takes_2d(int m[][3])        // the first dimension is gone, the 3 stays
{
    std::cout << "  inside, sizeof(m) = " << sizeof(m)
              << "   is int(*)[3] : " << std::boolalpha
              << std::is_same<decltype(m), int(*)[3]>::value << '\n';
    std::cout << "  m[1][2] = " << m[1][2] << "   (indexing still works)\n";
}

int main()
{
    int m[2][3] = {{1, 2, 3}, {4, 5, 6}};
    std::cout << "in main, sizeof(m) = " << sizeof(m) << "   sizeof(m[0]) = " << sizeof(m[0]) << '\n';
    std::cout << std::boolalpha
              << "decltype(m) is int[2][3] : " << std::is_same<decltype(m), int[2][3]>::value << '\n';
    takes_2d(m);
    return 0;
}

Measured output:

in main, sizeof(m) = 24   sizeof(m[0]) = 12
decltype(m) is int[2][3] : true
  inside, sizeof(m) = 8   is int(*)[3] : true
  m[1][2] = 6   (indexing still works)

The parameter's type is int (*)[3] — a pointer to an array of 3 ints. Read it right to left with Chapter 8.7 §2's rule: m is a pointer to an array of 3 int. The parentheses are load-bearing. Measured: sizeof(int*[3]) is 24 — three pointers — while sizeof(int(*)[3]) is 8, one pointer.

sizeof is 8 — a pointer, as in Chapter 9.2 §3.

And m[1][2] still works. That is the part worth pausing on. Indexing needs to know how far one row is, and the 3 survived, so the row stride (3 × 4 = 12 bytes) is still computable. Only the number of rows was lost, which is the same loss Chapter 9.2 described — the outermost count.

So the declarations int m[][3], int m[2][3] and int (*m)[3] are all the same parameter, with the 2 ignored in the middle one. That is Chapter 9.2 §3's finding generalised: every count except the last is decoration; the last ones are real, because they are needed for the arithmetic.

5. Traversing, and What Order Costs

Two nested loops, two possible orders:

    for (int r = 0; r < R; ++r) for (int c = 0; c < C; ++c) s += big[r][c];   // with the layout
    for (int c = 0; c < C; ++c) for (int r = 0; r < R; ++r) s += big[r][c];   // against it

Identical arithmetic. Identical result. §2's offsets say the first walks consecutive bytes and the second jumps a whole row each step.

Measured on a 4096 × 4096 array of int — 64 MB — at -O2, with the sums verified equal:

Roughly sixty times slower for the same work in a different order. The 9 ms is a cold first run, the same artefact Chapter 6.2 §6 reported.

The reason, in one sentence and no more than one: reading consecutive addresses is much faster than jumping, because the hardware fetches and retains memory in blocks. Why that is true is a hardware subject this curriculum has not established and this chapter will not pretend to; Chapter 25.8 is where measuring before optimising becomes a discipline.

What belongs here is the rule the measurement supports:

Loop in the order the array is stored: the last index in the innermost loop.

6. What to Actually Do

Read int m[2][3] as an array of 2 arrays of 3 — every rule follows from the nesting.

Remember the last index varies fastest, and put it in the innermost loop. Measured: 2 ms against 120.

Read a 2-D parameter as int (*)[3] — a pointer to a row — and keep the parentheses.

Expect every dimension but the last to be ignored in a parameter. int m[][3], int m[2][3] and int (*m)[3] are one parameter.

Pass the row count separately, since it is the one that is lost — Chapter 9.2 §6's rule, applied to the outermost dimension only.

Prefer a container for anything beyond a small fixed grid — Module 11.

Verify a benchmark actually ran. Real data and a volatile sink; a zero is a warning sign.

7. What to Use Instead

The honest position, as in Chapter 9.1 §8 and Chapter 9.2 §8.

A built-in multidimensional array is fine for a small fixed-size grid known at compile time — a 3 × 3 transform, a 4 × 4 lookup table — and it has one real advantage worth keeping in mind: it is contiguous, which is what §5's measurement rewards.

For anything else, Module 11's containers. One warning, because it is the commonest mistake:

std::vector<std::vector<int>> is not a 2-D array. It is a vector of independent vectors, each with its own separately allocated storage, so the rows are not adjacent and §5's advantage is gone. It is convenient and it is a different data structure. When contiguity matters, the usual answer is a single std::vector<int> of R * C elements with the index arithmetic written out — which is exactly §3's formula, done by hand.

Module 11 is where that choice is made properly, and Chapter 9.11 is where choosing a representation becomes the subject.

8. Mistakes Worth Making Once

Reading int m[2][3] as a grid rather than a nesting. The nesting explains the types; the grid explains nothing.

Looping with the first index innermost. Measured: roughly 60× slower for identical work.

Writing int* m[3] for a 2-D parameter. That is an array of 3 pointers; int (*m)[3] is a pointer to an array of 3.

Believing the 2 in void f(int m[2][3]) is checked. It is ignored, exactly as in Chapter 9.2 §3.

Forgetting to pass the row count. It is the one dimension decay discards.

Expecting std::vector<std::vector<int>> to be contiguous. Each row is separately allocated.

Trusting a benchmark that reports 0 ms. The loops were probably deleted.

9. What You Should Be Able to Say Now

1. int m[2][3] is an array of 2 arrays of 3 ints — a nesting, not a grid.
2. m[0] has type int[3], so Chapter 9.1's rules apply to it.
3. m[r][c] is *(*(m + r) + c) — Chapter 9.1 §5's rule applied twice.
4. Measured: sizeof 24 / 12 / 4 — the sizes nest with no padding and no header.
5. Measured: offsets 0, 4, 8, 12, 16, 20 — one unbroken run; m[1][0] immediately follows m[0][2].
6. Row-major means the last index varies fastest. Rows are adjacent; columns are a row apart.
7. Three dimensions change nothing: each index's stride is the product of the dimensions to its right, times the element size.
8. Decay loses only the first dimension. Measured: the parameter is int (*)[3], sizeof is 8, and m[1][2] still works because the row stride survived.
9. So every count but the last is decoration in a parameter — int m[][3], int m[2][3] and int (*m)[3] are one thing.
10. The parentheses matter: int* m[3] is an array of pointers.
11. Measured: the same sum over 64 MB took 2 ms along rows and 116–128 ms along columns — roughly 60×.
12. The mechanism is locality, stated in one sentence because that is as far as the measurement goes.
13. My first attempt measured 0 ms both ways — all-zero data, loops deleted at -O2. Real data plus a volatile sink fixed it.
14. std::vector<std::vector<int>> is not contiguous; a single std::vector with index arithmetic is, and Module 11 is where that choice is made.

10. Exercises

Exercise 1 — name the types. For int m[2][3], give the type of: (a) m (b) m[0] (c) m[0][0] (d) &m[0] (e) m as a function argument.

Exercise 2 — compute the offsets. For int g[3][4], give the byte offset from the start of: (a) g[0][0] (b) g[0][3] (c) g[1][0] (d) g[2][2]. Then give sizeof(g) and sizeof(g[1]).

Exercise 3 — three dimensions. For int cube[2][3][4], give sizeof(cube), the stride of the first index in bytes, and the offset of cube[1][2][3].

Exercise 4 — which dimension survives? For void f(int m[][5]), say the parameter's real type, what sizeof(m) returns, what information was lost, and why indexing still works.

Exercise 5 — order the loops. Write the nested loops that sum int big[1024][1024] in the fast order, say which index is innermost, and state the measured factor between the two orders.

Exercise 6 — fix the benchmark. A colleague's timing loop over a zeroed array reports 0 ms for both orders. Give the two changes needed and say what the original was actually measuring.

Exercise 7 — choose the structure. For each, choose a built-in 2-D array, a std::vector<std::vector<int>>, or a single std::vector<int> with index arithmetic, and justify: (a) a 4×4 transform fixed at compile time (b) an image whose dimensions are read from a file and which is scanned row by row (c) a ragged table whose rows have different lengths.

11. Summary

• int m[2][3] is an array of 2 arrays of 3 — a nesting; every rule follows.
• Measured: sizes 24 / 12 / 4 nest exactly; offsets 0, 4, 8, 12, 16, 20 form one unbroken run.
• Row-major: the last index varies fastest. m[1][0] immediately follows m[0][2].
• Any number of dimensions: a stride is the product of the dimensions to the right.
• Decay loses the first dimension only. Measured: int (*)[3], sizeof 8, indexing still works.
• Every count but the last is decoration in a parameter, and the parentheses matter.
• Measured: 64 MB summed in 2 ms along rows, 116–128 ms along columns — about 60×.
• My first benchmark measured 0 ms both ways — zeroed data, loops deleted. Real data plus volatile fixed it.
• A built-in grid is fine when fixed and small, and it is contiguous.
• std::vector<std::vector<int>> is not contiguous; Module 11 and Chapter 9.11 own the choice.

Every array so far has held numbers, and the type of the elements has not mattered to any rule in these three chapters. One element type does change things, and not because the language treats it specially. A char array used to hold text acquires a convention that nothing in the type system enforces: the text is taken to end at the first zero byte, so the array's length and the text's length become two different numbers that can disagree. The next chapter is that convention, what it costs, and the catalogue of ways the terminating byte fails to be there — one of which the compiler cannot see and a sanitizer reports from inside the standard library.