Foundations · Module 1
How data lives in memory
Bytes, addresses and the cache: the physical facts every data structure is built on.
Every data structure is, in the end, a pattern of bytes at addresses, and every algorithm is a sequence of reads and writes to them. This module covers the physical facts the rest of the track builds on: how numbers are stored in bits, what a pointer really holds, why data in one block behaves so differently from data scattered across memory, and why the processor's caches make reading neighbors almost free.
- 1Bits, bytes and number representationEvery value a program stores is a row of bits. How integers are laid out in bytes, how negative numbers work, and why adding 1 can turn a huge number negative.13 min
- 2Memory addresses and pointersMemory is one long row of numbered bytes. A pointer is a variable that holds one of those numbers, and following it is how every linked structure works.12 min
- 3Contiguous and scattered dataData either sits in one unbroken block, where an address can be computed, or in separate pieces joined by pointers, where it has to be followed. Most data structures are a choice between the two.12 min
- 4Caches: why neighbors are fastMain memory is about a hundred times slower than the processor. Caches hide that by fetching 64 bytes at a time, which makes reading neighbors almost free and jumping around expensive.14 min