What is the difference between a multidimensional array int A[N][M] and a multilevel (pointer) array int *A[N]?
Multidimensional is one contiguous block reached by a single address calculation; multilevel is an array of pointers, so each access needs an extra memory load to follow a pointer first.
![Side by side: int A[N][M] as one contiguous block with a single load, versus int *A[N] as an array of pointers chasing separately allocated rows with two loads.](/quizzes/REVE1/translation-to-assembly/img/multidim-vs-multilevel.svg)
* int A[N][M]: one block, one load. int *A[N]: a pointer array, pointer-chased in two loads, rows may differ. *
The C source A[i][k] looks identical for both, but the machine code is very different:
| Aspect | Multidimensional int A[N][M] |
Multilevel int *A[N] |
|---|---|---|
| Storage | One contiguous block | Array of pointers + separately allocated rows |
| Access | MEM[A + 4*(k + M*i)] |
MEM[ MEM[A + 8*i] + 4*k ] |
| Row sizes | All rows identical length | Rows can have different lengths |
| Memory accesses | One | Two (load the row pointer, then the element) |
Multidimensional — single scaled load:
lea (%rdi,%rdi,4), %rax # rax = i*5 (part of computing the flat index)
mov A(,%rax,8), %rax # one memory access
Multilevel — pointer chase:
mov A(,%rdi,8), %rax # 1st access: get the row pointer A[i]
mov (%rax,%rsi,4), %rax # 2nd access: get (A[i])[k]
Tradeoff: the multilevel form costs an extra dereference per access (worse for tight loops, cache-unfriendly), but it allows ragged arrays (jagged rows) and rows that can be NULL or resized independently — which a fixed rectangular A[N][M] cannot.
Go deeper:
Row- and column-major order (Wikipedia) — row-major storage of nested arrays.- Array data structure (Wikipedia) — arrays vs arrays-of-pointers.