In C++, which loop order is fast over a float grid[H][W] or its flattened std::vector, and why?
answer
- array of arrays
- the last index varies fastest
- stride 1 versus stride W
- vector of vectors is not a grid
basics
~20 sRow by row: outer loop over r, inner loop over c. A C++ float grid[H][W] is an array of H contiguous rows, so grid[r][c + 1] is the next float in memory, while grid[r + 1][c] is W floats away.
solid answer
~40 s`float grid[H][W]` is an **array of H arrays of W floats**, and every array is contiguous, so the layout is row-major: the **last index varies fastest**. A flattened `std::vector<float>` indexed `grid[r * W + c]` copies that layout on purpose. With `r` outside and `c` inside, the inner loop reads consecutive floats, uses every byte of each cache line and lets the compiler vectorise. Swapping the loops makes every inner step jump `W * sizeof(float)` bytes, so each access lands on a different cache line and, for large `W`, on a different page. A `std::vector<std::vector<float>>` is worse still: each row is its own allocation. C++23's `std::mdspan` defaults to `std::layout_right`, the same row-major order.
code
cpp · 30 lines#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <vector>
constexpr std::size_t H = 2048, W = 2048;
// grid[r * W + c]: the same row-major order a built-in float[H][W] uses.
float sumRowMajor(const std::vector<float>& grid) {
float s = 0;
for (std::size_t r = 0; r < H; ++r)
for (std::size_t c = 0; c < W; ++c) s += grid[r * W + c]; // stride 1
return s;
}
float sumColumnMajor(const std::vector<float>& grid) {
float s = 0;
for (std::size_t c = 0; c < W; ++c)
for (std::size_t r = 0; r < H; ++r) s += grid[r * W + c]; // stride W
return s;
}
int main() {
std::vector<float> grid(H * W, 1.0f);
static float raw[4][3]; // 4 rows of 3 floats, one contiguous block
auto at = [](const float* p) { return reinterpret_cast<std::uintptr_t>(p); };
std::printf("raw[0][1] is %zu bytes after raw[0][0]\n", std::size_t(at(&raw[0][1]) - at(&raw[0][0])));
std::printf("raw[1][0] is %zu bytes after raw[0][0]\n", std::size_t(at(&raw[1][0]) - at(&raw[0][0])));
std::printf("%g %g\n", sumRowMajor(grid), sumColumnMajor(grid));
}go deeper
Recall that the last index varies fastest in a C++ array, so the inner loop should run over the last index.
Explain cache lines, unit stride and vectorisation, and why vector of vectors adds an allocation and a dependent load per row.
Show the fixes when the algorithm needs columns: tiling, a one-off transpose, or a column-major layout chosen from the access pattern.
Treat layout as part of an API's contract: a grid type that owns one buffer and exposes views lets teams change the order without touching callers.
## Why a C++ grid is row-major C++ has no true two-dimensional array type. `float grid[4][3]` declares an **array of 4 elements, each of which is an array of 3 floats**, and the standard defines every array as a contiguously allocated set of its elements. Applying that rule twice gives the layout: - `grid[0][0]`, `grid[0][1]`, `grid[0][2]` are adjacent floats; - `grid[1][0]` follows directly after `grid[0][2]`; - so the **last subscript varies fastest**, which is called **row-major** order. A flattened `std::vector<float> grid(H * W)` indexed `grid[r * W + c]` reproduces exactly that order, and C++23's `std::mdspan` uses `std::layout_right` (also row-major) unless you ask for `std::layout_left`. ## What each loop order does to memory | Loop order | Inner-loop step | Cache lines touched per 16 floats | Vectorisable | |---|---|---|---| | `for r { for c { grid[r * W + c] } }` | 4 bytes | 1 | yes, unit stride | | `for c { for r { grid[r * W + c] } }` | `4 * W` bytes | up to 16 | rarely | With unit stride, one 64-byte cache line serves 16 consecutive floats and the hardware prefetcher streams the next lines ahead of the loop. With stride `W`, each access needs a different cache line; once a row is larger than a page, each access may also need a different TLB entry, and by the time the outer loop comes back for the next column the earlier lines have often been evicted. On a 4096 x 4096 grid on this author's machine the column-order sum took about four times as long as the row-order sum; the ratio varies by CPU, the direction does not. ## Vector of vectors is not a grid `std::vector<std::vector<float>>` looks like a 2-D array but is **H separate allocations** plus an array of H vector headers: 1. each row is contiguous internally, but row r + 1 starts wherever the allocator put it; 2. every access first loads the row's data pointer from the outer vector, a dependent load; 3. rows can have different lengths, so the compiler cannot treat it as one block. For a fixed-size grid, prefer one `std::vector<float>` of `H * W` elements with an index helper, or a `std::mdspan` view over it. ## Indexing helpers that keep the order right Hand-written `r * W + c` arithmetic is where loop-order bugs hide, so wrap it once: - A small grid class with `float& at(std::size_t r, std::size_t c) { return data_[r * width_ + c]; }` documents the order in one place. - C++23 allows an `operator[]` with several parameters, so a grid type can offer `grid[r, c]`; `std::mdspan` already does, over any contiguous buffer. - A `std::mdspan` over a `std::vector<float>`'s `data()` gives multidimensional indexing without owning or copying the data; its default `std::layout_right` keeps the C++ row-major convention, so `m[r, c]` and `m[r, c + 1]` are neighbours in memory. Whatever the wrapper, the rule for the hot loop does not change: the **innermost loop runs over the index that varies fastest in memory**. ## Picking the order when you cannot change the layout Sometimes the algorithm wants columns, for example a vertical blur. Options, roughly in order of effort: - **Swap the loops** if the computation allows it: process all columns of one row before moving on. - **Transpose once**, run the column pass as a row pass, and transpose back when the extra copy is cheaper than the strided reads. - **Tile (block) the loops**: work on a small square of the grid that fits in cache, so the strided accesses inside one tile reuse lines already loaded. - **Store column-major from the start** (`std::layout_left`, or index `c * H + r`) if columns are the hot direction. ## How this shows up in interviews The question is usually a code sample with nested loops and a request to make it faster. A strong answer names the language rule (array of arrays, last index fastest), connects it to cache lines and vectorisation, and spots the `vector<vector<float>>` trap if it appears. Language-neutral cache-line arithmetic belongs to the material on arrays and cache locality; what is specific here is how C++ lays out its arrays.
- Why does int a[3][4]; a[0][5] not portably read a[1][1], even though the memory is right there?Pointer arithmetic is defined only within one array object, and `a[0]` is an array of 4 ints, so index 5 is out of its bounds and the read has undefined behaviour, however the bytes happen to be laid out. Code that wants to walk a grid as one sequence should hold a flat array or `std::vector` and compute `r * W + c` itself.
- When would you choose std::layout_left for a C++23 std::mdspan over a grid?When the hot loops walk columns, or the data comes from or goes to a linear-algebra library that stores matrices column by column. `std::layout_left` makes the first index vary fastest, so the column loop gets unit stride without copying the data.
- C++ leaves the memory order of a two-dimensional array to the compiler.
- A vector of vectors is one contiguous block, just like float grid[H][W].
- Loop order only matters for grids larger than the L3 cache.
- The optimizer always interchanges nested loops into the fast order for you.
- Column-major traversal is faster because the stride lets the prefetcher run ahead.
Assumes C++23 for std::mdspan and its layout policies; the row-major rule for built-in arrays holds in every C++ standard.