Arrays, Structs, and Alignment

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.

This formula is the scaled-index addressing mode D(Rb,Ri,S) from 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.

int get(int *A, long i) { return A[i]; }

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.

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}(\text{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=0x2C$ and the address is $0x200+0x2C=0x22C$. A compiler emits this as one scaled load once it has the row base: from a pointer to row 2 (at $0x200+2\cdot 16=0x220$), the element is 12(%rbase) since $j\cdot 4=12$.

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.

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 $0x2000+3\cdot 8=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 longs 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.

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).

struct rec {
    int   i;      // offset 0
    int   j;      // offset 4
    long  v;      // offset 8
    int  *p;      // offset 16
};

# 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)

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.¹

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 chars share the trailing slack instead of each triggering its own gap.

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.

union u {
    float  f;     // 4 bytes, offset 0
    int    bits;  // 4 bytes, offset 0 — same storage as f
};                // sizeof(union u) == 4

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.

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.²

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.³

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.⁴