Bytes and addresses

Every diagram you have ever seen of a program, whether objects pointing at objects, trees, linked lists, or tensors, is a fiction drawn on top of something much dumber. To a machine-level program, memory is one very large array of bytes, and every byte is identified by a unique number: its address. The set of all possible addresses is the address space. There is nothing else down there: no types, no objects, no rows or columns, just bytes at addresses.¹

The byte, 8 bits, is the smallest unit you can address. You cannot ask memory for a single bit; bits come in named 8-packs, and every value in every program you've ever run is some run of these packs.²

A pointeris not a mysterious C concept; it is an index into this array, stored as an ordinary integer. The machine's word size is exactly the size of that integer: on a 64-bit machine, addresses are 64-bit values, which is why sizeof(void*)is 8 and why the address space tops out at 2⁶⁴ bytes: 16 exabytes, about 1.84 × 10¹⁹. When people say "a 64-bit machine," this is what the 64 bits are for: naming locations in the byte array.³

One more thing the sources are blunt about, and it's the punchline of this whole chapter: the compiler tracks types, but the machine code it emits has no information about data types at all. At runtime, everything, whether data, instructions, or pointers, is just blocks of bytes.⁴ Everything this curriculum does later, from caches to coalescing to KV caches, happens to ranges of this array. If you can picture the array, you can picture all of it.

The byte array stores bytes; types live only in the eye of the beholder. When a program declares int x, the compiler reserves 4 consecutive bytes and writes the value's two's-complement bit pattern into them. A float reserves 4 bytes with a completely different encoding; a double, 8; a char, exactly 1; a pointer, the full 8-byte word.⁵Cast a pointer and you can read the same 4 bytes back as either type: the bytes don't change, only the interpretation does.⁶

Two conventions pin down exactly where a multi-byte value lives. First: it is stored as a contiguous run of bytes, and its address is the smallest address in the run: a 4-byte int at address 0x100 occupies 0x100 through 0x103. Second: the order of bytes within the run is a genuine hardware choice. Little-endian machines store the least significant byte first (at the lowest address); big-endian machines store the most significant byte first.⁷

In practice you will live on little-endian: x86 is exclusively little-endian, and while ARM hardware is technically bi-endian, both Android and iOS run it little-endian only.⁸

SourcesCS:APP 3e §2.1.2–2.1.3 · pp. 75–84

An array is the byte array's native data structure. The declaration T A[N] does exactly two things: it allocates one contiguous region of L · N bytes (where L is the size of type T), and it makes Aa name for the region's starting address. Element i lives at address + L · i. Full stop: that formula is the entire implementation.⁹

The hardware is built for this: x86-64 computes base + 4·i and loads the result in a single instruction, movl (%rdx,%rcx,4),%eax, with hardware scaling for element sizes 1, 2, 4, and 8. No lookup table, no magic, one add and one shift baked into the addressing mode.¹⁰C's pointer arithmetic is the same formula wearing different syntax: A[i] is defined as *(A+i), and adding an integer to a pointer secretly scales it by L.¹¹

Two-dimensional arrays are the same trick applied twice. C stores T D[R][C] in row-major order, all of row 0, then all of row 1, so element D[i][j] sits at address + L(C · i + j). Memorize the shape of that formula: the row index is multiplied by the whole row width. Walk j and you move 4 bytes at a time; walk i and you leap 4C bytes at a time. Both are one multiply and one add, but they generate wildly different address sequences, the difference that chapter 0.6 will turn into a 25× runtime gap.¹²

A struct is adjacency with mixed sizes: all fields live in one contiguous region, in declaration order, and a pointer to the struct is the address of its first byte. The compiler knows each field's byte offset at compile time and bakes it into the instruction as a constant displacement: r->j compiles to "load 4 bytes at address-of-r + 4." The machine code contains no field names, no field types; offsets are all that survive compilation.¹³(The alignment gaps the compiler sometimes inserts between fields are chapter 0.7's subject.)

SourcesCS:APP 3e §3.8.1–3.8.3 · pp. 291–295CS:APP 3e §3.9.1 · pp. 301–303