--- title: Arrays, Structs, and Alignment module: Machine-Level Programming moduleNumber: 1 lessonNumber: 6 order: 106 summary: > How aggregate data lays out in memory. Arrays as base-plus-scaled-index, the row-major ordering of multidimensional arrays, pointer arithmetic in units of the pointed-to type, struct fields at fixed byte offsets, the overlapping storage of unions, and the alignment rules that force padding into a struct. topics: [Machine-Level Programming] sources: - book: Bryant & O'Hallaron ref: "CS:APP — §3.8 Array Allocation and Access; §3.9 Heterogeneous Data Structures" --- C's aggregate types — arrays, structs, unions — are conveniences the compiler flattens into addresses and offsets. An array access is an address computation; a struct field is a fixed displacement; alignment rules sometimes insert invisible padding bytes. This lesson shows how each aggregate becomes memory, which is what lets you read the addressing arithmetic compiled code is full of. ## Arrays are base plus scaled index An array `T A[N]` is `N` contiguously stored elements of type `T`, occupying `N * sizeof(T)` bytes starting at a base address. The address of element `A[i]` is a single multiply-and-add. > **Definition (Array element address).** For an array `A` of `T`-sized elements > with base address $x_A$, element `A[i]` lives at > $$ x_A + i \cdot \mathrm{sizeof}(T). $$ This formula is the scaled-index addressing mode `D(Rb,Ri,S)` from [data movement](/computer-architecture/machine-level-x86-64/data-movement), with `Rb` the base, `Ri` the index `i`, and the scale `S = sizeof(T)` — which is why the hardware's scales are precisely `{1,2,4,8}`, the sizes of the primitive types. $$ % caption: Indexing an int array A[i]. The element address is the base plus i times % caption: 4 bytes; the index 2 reaches element A[2] at base + 8. The cells are % caption: contiguous, each 4 bytes wide. \begin{tikzpicture}[font=\footnotesize, >=stealth, cell/.style={draw, minimum width=13mm, minimum height=8mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \i/\lbl/\off in {0/{A[0]}/0, 1/{A[1]}/4, 3/{A[3]}/12} { \node[cell] at (\i*1.4,0) {\texttt{\lbl}}; \node[font=\scriptsize] at (\i*1.4,-0.7) {+\off};} \node[cell, draw=acc, fill=acc!8] at (2*1.4,0) {\texttt{A[2]}}; \node[font=\scriptsize] at (2*1.4,-0.7) {+8}; \node[anchor=east, font=\scriptsize] at (-0.85,0) {base $x_A$}; \draw[->, acc] (-0.75,0.55) .. controls (-0.4,1.1) and (2.3,1.1) .. (2*1.4,0.5); \node[text=acc, font=\scriptsize] at (2.0,1.15) {$x_A + 8$}; \end{tikzpicture} $$ ```c [arrayidx.c] int get(int *A, long i) { return A[i]; } ``` ```asm [arrayidx.s] get: movl (%rdi,%rsi,4), %eax # eax = A[i]: base %rdi + i*4 ret # int is 4 bytes, so scale 4 ``` ## Multidimensional arrays are row-major C stores a 2-D array `T A[R][C]` in **row-major** order: row 0 in full, then row 1, and so on. The element `A[i][j]` is at row $i$, column $j$, so its address folds the two indices into one offset. $$ % caption: A 3x4 int array in row-major memory. Rows are stored consecutively, so % caption: A[i][j] sits at base + (i*4 + j)*4 bytes; the row stride is 4 ints. \begin{tikzpicture}[font=\footnotesize, cell/.style={draw, minimum width=12mm, minimum height=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % the linear memory, one long row of 12 cells \foreach \i in {0,...,11} \node[cell] at (\i*1.2,0) {}; % highlight A[1][2] = linear index 6 \node[cell, draw=acc, fill=acc!8] at (6*1.2,0) {\texttt{[1][2]}}; % row brackets above \draw[acc] (-0.55,0.55) -- (-0.55,0.9) -- (3.85,0.9) -- (3.85,0.55); \node[text=acc, font=\scriptsize] at (1.65,1.15) {row 0}; \draw[acc] (4.25,0.55) -- (4.25,0.9) -- (8.65,0.9) -- (8.65,0.55); \node[text=acc, font=\scriptsize] at (6.45,1.15) {row 1}; \draw[acc] (9.05,0.55) -- (9.05,0.9) -- (13.45,0.9) -- (13.45,0.55); \node[text=acc, font=\scriptsize] at (11.25,1.15) {row 2}; % linear index labels below a few cells \node[font=\scriptsize] at (0,-0.7) {0}; \node[font=\scriptsize] at (4*1.2,-0.7) {4}; \node[text=acc, font=\scriptsize] at (6*1.2,-0.7) {6}; \node[font=\scriptsize] at (8*1.2,-0.7) {8}; \end{tikzpicture} $$ For `T A[R][C]` the address of `A[i][j]` is $x_A + (i \cdot C + j) \cdot \mathrm{sizeof}(T)$: advance $i$ whole rows of $C$ elements, then $j$ within the row. The **row stride** $C \cdot \mathrm{sizeof}(T)$ is the byte distance from one row to the next, and stepping a row pointer by one row is adding that stride. For example, take `int A[3][4]` based at address `0x200`, and compute `&A[2][3]`. With $C = 4$ columns and $\mathrm{sizeof}(\texttt{int}) = 4$, the linear element index is $i \cdot C + j = 2 \cdot 4 + 3 = 11$, so the byte offset is $11 \cdot 4 = 44 = \mathtt{0x2C}$ and the address is $\mathtt{0x200} + \mathtt{0x2C} = \mathtt{0x22C}$. A compiler emits this as one scaled load once it has the row base: from a pointer to row 2 (at $\mathtt{0x200} + 2 \cdot 16 = \mathtt{0x220}$), the element is `12(%rbase)` since $j \cdot 4 = 12$. $$ % caption: Address of A[2][3] in int A[3][4] based at 0x200. The two indices fold % caption: into the linear index i*C+j = 11; scaling by 4 bytes gives offset 0x2C, % caption: so the element sits at 0x22C. \begin{tikzpicture}[font=\footnotesize, >=stealth, term/.style={draw, minimum width=30mm, minimum height=7mm, inner sep=1pt, align=center}] \definecolor{acc}{HTML}{2348F2} \node[term] (idx) at (0,1.4) {linear index: 2 x 4 + 3 = 11}; \node[term] (off) at (0,0.4) {byte of\/fset: 11 x 4 = \texttt{0x2C}}; \node[term] (base) at (0,-0.6) {base \texttt{0x200}}; \node[term, draw=acc, thick, minimum width=26mm] (addr) at (5.6,0.4) {\texttt{0x200} + \texttt{0x2C} = \texttt{0x22C}}; \draw[->, thick] (idx.east) -- (addr.north west); \draw[->, thick] (off.east) -- (addr.west); \draw[->, thick] (base.east) -- (addr.south west); \end{tikzpicture} $$ ## Pointer arithmetic is typed C scales pointer arithmetic by the pointed-to type automatically. If `p` has type `T *`, then `p + i` is the address `p + i * sizeof(T)`, and `*(p + i)` is identical to `p[i]`. The expressions `A[i]`, `*(A + i)`, and `&A[0] + i` all denote the same element because indexing **is** scaled pointer arithmetic. | C expression | Type | Value | | --- | --- | --- | | `A` | `int *` | $x_A$ | | `A + i` | `int *` | $x_A + 4i$ | | `*(A + i)` | `int` | $\mathrm{M}[x_A + 4i]$ | | `&A[i] - A` | `long` | $i$ (difference in elements, not bytes) | The last row is worth naming: subtracting two `T *` pointers yields the number of **elements** between them, the byte difference divided by `sizeof(T)`. A numeric trace makes the scaling visible. Let a `long *p` (8-byte elements) hold the address `0x2000`. Then `p + 3` is **not** `0x2003` but $\mathtt{0x2000} + 3 \cdot 8 = \mathtt{0x2018}$, because C scaled the `3` by `sizeof(long) = 8`. If a second pointer `q` holds `0x2028`, then `q - p` is not `0x28 = 40` but $40 / 8 = 5$: five `long`s separate them. The compiler emits the scaling silently — `p + 3` compiles to a `lea` of `24(%rdi)`, and `q - p` to a subtract followed by a shift right by 3 (divide by 8). Confusing the byte gap with the element gap is the single most common pointer bug, and the machine level is where the factor of `sizeof(T)` becomes explicit. $$ % caption: Typed pointer arithmetic on long *p = 0x2000. p+3 advances by 3*8 = 24 % caption: bytes to 0x2018, not to 0x2003; and q - p for q = 0x2028 is (0x28)/8 = 5 % caption: elements, the byte gap divided by sizeof(long). \begin{tikzpicture}[font=\footnotesize, >=stealth, cell/.style={draw, minimum width=32mm, minimum height=6.5mm, inner sep=2pt, align=left, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node[cell] (p) at (0,1.1) {$\mathtt{p}=\mathtt{0x2000}$}; \node[cell, draw=acc, text=acc] (p3) at (0,0.35) {$\mathtt{p}+3 = \mathtt{0x2000}+24 = \mathtt{0x2018}$}; \node[cell] (q) at (0,-0.4) {$\mathtt{q}=\mathtt{0x2028}$}; \node[cell, draw=acc, text=acc] (qp) at (0,-1.15) {$\mathtt{q}\text{-}\mathtt{p}$: 40 bytes, 8 each $= 5$ elements}; \end{tikzpicture} $$ ## Structs are fixed field offsets A `struct` packs its fields into one block in declaration order, each at a fixed **byte offset** from the start computed at compile time. Accessing a field is a `mov` at `offset(%base)`. ```c [rec.c] struct rec { int i; // offset 0 int j; // offset 4 long v; // offset 8 int *p; // offset 16 }; ``` ```asm [rec.s] # set r->v = r->i, with r in %rdi movl (%rdi), %eax # eax = r->i (offset 0) movslq %eax, %rax # sign-extend int to long movq %rax, 8(%rdi) # r->v = ... (offset 8) ``` $$ % caption: The struct rec laid out in memory. Each field sits at a fixed byte % caption: offset from the start, fixed at compile time; r->v is just the bytes at % caption: offset 8, which compiles to the operand 8(%rdi). \begin{tikzpicture}[font=\footnotesize, fld/.style={draw, minimum height=8mm, inner sep=2pt, align=center}] \definecolor{acc}{HTML}{2348F2} \node[fld, minimum width=14mm] (i) at (0,0) {\texttt{i}}; \node[fld, minimum width=14mm] (j) at (1.4,0) {\texttt{j}}; \node[fld, minimum width=18mm, draw=acc, fill=acc!8] (v) at (3.2,0) {\texttt{v}}; \node[fld, minimum width=18mm] (p) at (5.4,0) {\texttt{p}}; \node[font=\scriptsize] at (0,-0.7) {0}; \node[font=\scriptsize] at (1.4,-0.7) {4}; \node[font=\scriptsize, text=acc] at (3.2-0.9,-0.7) {8}; \node[font=\scriptsize] at (5.4-0.9,-0.7) {16}; \node[anchor=west, text=acc, font=\scriptsize] at (6.6,0) {$\mathtt{r}$->$\mathtt{v}\ =\ \mathtt{8(\%rdi)}$}; \end{tikzpicture} $$ The compiler turned `r->v` into the constant displacement `8(%rdi)`; field names exist only in the source. Different structs can therefore alias the same field offsets, the basis of how the compiler reads `i`, `j`, `v`, and `p`. ## Alignment forces padding The hardware prefers a primitive of size $K$ to sit at an address that is a multiple of $K$ — `int` (4 bytes) at a multiple of 4, `long` and pointers (8) at a multiple of 8. To honor this the compiler inserts **padding** bytes between fields, and pads the struct's total size up to a multiple of its largest member's alignment so that arrays of the struct stay aligned.[^align] $$ % caption: The alignment rule for a 4-byte int. Starting at address 4 (a multiple % caption: of 4) is aligned; starting at 5 straddles a 4-byte boundary and is % caption: misaligned, which the compiler avoids by padding. \begin{tikzpicture}[font=\footnotesize, by/.style={draw, minimum width=8mm, minimum height=8mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % top row: aligned int at of\/fset 4, span label above the cells \node[anchor=east, font=\scriptsize] at (-0.3,1.2) {aligned}; \foreach \i in {0,...,7} \node[by] at (\i*0.85,1.2) {}; \foreach \i in {4,5,6,7} \node[by, draw=acc, fill=acc!8] at (\i*0.85,1.2) {}; \draw[acc, thick] (4*0.85-0.42,1.72) -- (7*0.85+0.42,1.72); \node[text=acc, font=\footnotesize] at (5.5*0.85,2.05) {\texttt{int} at 4}; % bottom row: misaligned int at of\/fset 5, span label above its cells \node[anchor=east, font=\scriptsize] at (-0.3,-0.3) {misaligned}; \foreach \i in {0,...,7} \node[by] at (\i*0.85,-0.3) {}; \foreach \i in {5,6,7,8} \node[by, draw=red, fill=red!8] at (\i*0.85,-0.3) {}; \draw[red, thick] (5*0.85-0.42,0.22) -- (8*0.85+0.42,0.22); \node[text=red, font=\footnotesize] at (6.5*0.85,0.52) {\texttt{int} at 5}; % boundary tick at multiple of 4 \node[font=\scriptsize] at (0,-1.05) {0}; \node[font=\scriptsize] at (4*0.85,-1.05) {4}; \node[font=\scriptsize] at (8*0.85,-1.05) {8}; \end{tikzpicture} $$ > **Definition (Alignment requirement).** A datum of size $K$ bytes is **aligned** > when its starting address is a multiple of $K$. A struct's alignment is the > maximum over its fields' alignments; the compiler pads field gaps and the trailing > end so every field and every element of an array of the struct is aligned. $$ % caption: Layout of {char c; int i; char d; long v;}. Padding (shaded) follows c % caption: to 4-align i, follows d to 8-align v, giving total size 24 with the % caption: struct itself 8-aligned. \begin{tikzpicture}[font=\footnotesize, by/.style={draw, minimum width=6mm, minimum height=8mm, inner sep=0pt}, pad/.style={draw, minimum width=6mm, minimum height=8mm, inner sep=0pt, fill=acc!10}] \definecolor{acc}{HTML}{2348F2} % byte 0: c \node[by] at (0,0) {\texttt{c}}; % bytes 1-3: padding \foreach \x in {1,2,3} \node[pad] at (\x*0.7,0) {}; % bytes 4-7: int i \foreach \x in {4,5,6,7} \node[by] at (\x*0.7,0) {}; \node[font=\footnotesize] at (5.5*0.7,0.7) {\texttt{i}}; % byte 8: d \node[by] at (8*0.7,0) {\texttt{d}}; % bytes 9-15: padding \foreach \x in {9,10,11,12,13,14,15} \node[pad] at (\x*0.7,0) {}; % bytes 16-23: long v \foreach \x in {16,17,18,19,20,21,22,23} \node[by] at (\x*0.7,0) {}; \node[font=\footnotesize] at (19.5*0.7,0.7) {\texttt{v}}; % byte of\/fset markers below \node[font=\scriptsize] at (0,-0.75) {0}; \node[font=\scriptsize] at (4*0.7,-0.75) {4}; \node[font=\scriptsize] at (8*0.7,-0.75) {8}; \node[font=\scriptsize] at (16*0.7,-0.75) {16}; \node[font=\scriptsize] at (23*0.7,-0.75) {23}; % padding legend \node[pad] at (10*0.7,-1.7) {}; \node[anchor=west, font=\scriptsize, text=acc] at (10.6*0.7,-1.7) {padding}; \end{tikzpicture} $$ Reordering fields from widest to narrowest minimizes padding. The struct above spans 24 bytes; declaring `long v; int i; char c; char d;` packs into 16, because the two `char`s share the trailing slack instead of each triggering its own gap. $$ % caption: The same four fields reordered widest-first. long v fills bytes 0-7, int % caption: i bytes 8-11, and the two chars sit at 12 and 13 with only 2 trailing pad % caption: bytes: 16 bytes total against the 24 of the declaration order. \begin{tikzpicture}[font=\footnotesize, by/.style={draw, minimum width=6mm, minimum height=8mm, inner sep=0pt}, pad/.style={draw, minimum width=6mm, minimum height=8mm, inner sep=0pt, fill=acc!10}] \definecolor{acc}{HTML}{2348F2} % bytes 0-7: long v \foreach \x in {0,...,7} \node[by] at (\x*0.7,0) {}; \node[font=\footnotesize] at (3.5*0.7,0.7) {\texttt{v}}; % bytes 8-11: int i \foreach \x in {8,9,10,11} \node[by] at (\x*0.7,0) {}; \node[font=\footnotesize] at (9.5*0.7,0.7) {\texttt{i}}; % byte 12: c, byte 13: d \node[by] at (12*0.7,0) {\texttt{c}}; \node[by] at (13*0.7,0) {\texttt{d}}; % bytes 14-15: padding \node[pad] at (14*0.7,0) {}; \node[pad] at (15*0.7,0) {}; % offset markers \node[font=\scriptsize] at (0,-0.75) {0}; \node[font=\scriptsize] at (8*0.7,-0.75) {8}; \node[font=\scriptsize] at (12*0.7,-0.75) {12}; \node[font=\scriptsize] at (15*0.7,-0.75) {15}; % padding legend \node[pad] at (5*0.7,-1.7) {}; \node[anchor=west, font=\scriptsize, text=acc] at (5.6*0.7,-1.7) {padding (2 bytes)}; \end{tikzpicture} $$ ## Unions overlap their members A `union` lays all its members at the **same** offset 0, so they share storage and the union's size is its largest member's. Only one member is meaningful at a time; writing one and reading another reinterprets the same bytes, the controlled type-pun behind reading a value's raw representation. ```c [un.c] union u { float f; // 4 bytes, offset 0 int bits; // 4 bytes, offset 0 — same storage as f }; // sizeof(union u) == 4 ``` $$ % caption: A union overlaps its members at offset 0. Both f and bits name the very % caption: same 4 bytes, so the union is only 4 bytes wide; writing one and reading % caption: the other reinterprets the identical bits. \begin{tikzpicture}[font=\footnotesize, >=stealth, byte/.style={draw, minimum width=10mm, minimum height=8mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \i in {0,1,2,3} \node[byte, fill=acc!8] at (\i,0) {}; \node[anchor=east, font=\scriptsize] at (-0.7,0) {4 bytes}; \node[anchor=west, text=acc, font=\scriptsize] at (4.3,0.45) {$\mathtt{f}$ (f\/loat)}; \node[anchor=west, text=acc, font=\scriptsize] at (4.3,-0.45) {$\mathtt{bits}$ (int)}; \draw[->, acc] (4.2,0.45) -- (3.4,0.15); \draw[->, acc] (4.2,-0.45) -- (3.4,-0.15); \node[font=\scriptsize] at (0,-0.7) {0}; \end{tikzpicture} $$ For example, write `u.f = 1.0f` and then read `u.bits`. The `float` 1.0 has the IEEE-754 single-precision encoding `0x3F800000` (sign 0, exponent `01111111`, fraction all zero), so `u.bits` reads back exactly `0x3F800000` — the integer $1065353216$, not `1`. The bytes never changed; only the interpretation did. This is precisely how code inspects a floating-point value's raw representation, and how the classic fast inverse-square-root trick reads a `float`'s bits as an `int` to manipulate its exponent. $$ % caption: Writing u.f = 1.0f and reading u.bits. The 4 bytes hold the IEEE-754 % caption: pattern 0x3F800000; read as a float that is 1.0, read as an int it is % caption: 1065353216. Same storage, two interpretations. \begin{tikzpicture}[font=\footnotesize, >=stealth, cell/.style={draw, minimum width=34mm, minimum height=6.5mm, inner sep=2pt}] \definecolor{acc}{HTML}{2348F2} \node[anchor=east, font=\scriptsize] at (0.2,0.0) {4 bytes:}; \node[cell, fill=acc!8] at (2.6,0.0) {$\mathtt{3F\,80\,00\,00}$}; \node[anchor=west, font=\scriptsize] at (4.6,0.5) {as $\mathtt{f}$ (f\/loat): the value one}; \node[anchor=west, font=\scriptsize, text=acc] at (4.6,-0.5) {as $\mathtt{bits}$ (int): $1065353216$}; \end{tikzpicture} $$ Where a struct's size is the **sum** of its (padded) fields, a union's is the **max** of its members. The two are the additive and the overlapping ways to combine fields into one block. ## Packing, false sharing, and flexible arrays CS:APP explains _why_ the compiler pads; the wider practice is a set of tools and hazards around that padding. The first is the escape hatch: gcc and clang accept `__attribute__((packed))` on a struct to suppress **all** padding, laying fields back to back regardless of alignment. It shrinks the struct — useful for a network packet or on-disk record whose layout is fixed by an external format — but every misaligned field then costs the processor extra work, and on some architectures a misaligned access faults outright. Packing trades space for access cost, the exact inverse of the reordering trick above.[^packed] The subtler hazard is **false sharing**, which the memory-hierarchy literature treats at length. Caches move data in fixed-size **lines** (64 bytes on x86-64). If two threads write two different fields that happen to land in the same cache line, the hardware must ferry the line back and forth between the cores' caches on every write, serializing them even though the fields are logically independent. The fix is alignment turned up rather than down: `alignas(64)` (or `__attribute__((aligned(64)))`) pads a hot per-thread field out to its own cache line so writes stop colliding. Here alignment is not about correctness but about throughput, and it is a standard concern in the performance-engineering chapters that follow the machine level.[^falsesharing] One last idiom the standard supports is the **flexible array member**: a struct whose final field is declared `T arr[];` with no size, so a single `malloc` can allocate the struct's header and a run-length array of trailing elements as one contiguous block. The array's base is just the offset past the header — the same fixed-offset arithmetic as any field — which is why the pattern needs no special support beyond the layout rules this lesson already covers.[^fam] > **Takeaway.** `A[i]` is $x_A + i \cdot \mathrm{sizeof}(T)$, the scaled-index > addressing mode; a 2-D array is **row-major**, so `A[i][j]` is at > $x_A + (i C + j)\,\mathrm{sizeof}(T)$. Pointer arithmetic scales by the > pointed-to type. Struct fields sit at fixed compile-time offsets; **alignment** > (size-$K$ datum at a multiple of $K$) inserts padding, which field reordering can > shrink. A union overlaps its members at offset 0 and is sized by the largest. [^align]: **Bryant & O'Hallaron**, _CS:APP_, §3.9.3 — Data Alignment: the requirement that a primitive of size $K$ start at an address divisible by $K$, satisfied by inter-field and trailing padding. [^packed]: **GNU**, _Using the GNU Compiler Collection (GCC)_, §6.35 Type Attributes — the `packed` attribute suppressing struct padding, and the misaligned-access cost it incurs. [^falsesharing]: **Drepper**, _What Every Programmer Should Know About Memory_ (2007), §3.3.4 and §6.4 — cache-line granularity and false sharing between independent fields co-resident in one 64-byte line, mitigated by per-line alignment. [^fam]: **ISO/IEC 9899:1999 (C99)**, §6.7.2.1 — the flexible array member: a struct whose last member is an incomplete array type, sized at allocation and addressed at the fixed offset past the header.