Answers · How a program runs
Why does every program I run see the same memory addresses?
In shortA pointer's number is a private label for a block of memory, not a physical chip location, so two programs can use the same label for different places.
The number a pointer prints is a virtual address. It is an index into a private translation map, not a location on the RAM chips, so two processes can hold the same number and write through it without touching each other.
The number is an index
Take a concrete address. If a process prints 0x0000000000401000, that is 4,198,400 in decimal: 0x400000 is 4,194,304 and 0x1000 is 4,096. Most machines use 4,096-byte blocks. The low twelve bits are the offset, because ; here they are zero. The rest is the block number, 4,198,400 / 4,096 = 1,025. The map has an entry for block 1,025, not for each byte. In process A that entry names one hardware block. In process B it names another. The printed number is identical; the entry it indexes is not.
Here is the address the program holds, is the block number, is the block size, and is the offset inside the block. Because is a power of two, the split costs no arithmetic: the low twelve bits of the address are and pass through translation untouched, while everything above them is and gets looked up. The map therefore needs one entry per 4,096 bytes rather than one per byte, which is 4,096 times smaller. It also means one translation can serve 4,096 consecutive bytes.
Why the physical guess fails
The natural guess is that the printed number is a physical RAM address, so two processes using 0x401000 should collide. If that were true, one process writing through the pointer would change the other process's data, and a wild pointer could reach anything on the machine. Neither happens because the processor never uses the number raw. It consults the map belonging to whichever process is currently running, finds the hardware block, and only then issues the read or write. The number is a name in a namespace, and each process has its own namespace.
A flat table with one entry per block would still be too large for a 64-bit address space. So the map is a tree. A common split uses four levels of nine bits plus the twelve-bit offset: bits. Nine bits index 512 entries. Each entry is eight bytes, so one table is bytes, exactly one block. At each level the hardware reads one entry and follows its pointer. Nothing is searched and nothing is compared; each step is a direct index.
On a cache miss the processor reads the level 1 table, then level 2, then level 3, then level 4, and only then reads the data. That is four table reads before the fifth read that gets the value. If every load did that, the machine would be several times slower than it needs to be. A small cache of recent translations sits in front of the walk and answers almost every load. Sequential access does one translation per 4,096 bytes and then thousands of free accesses; a stride of 4,096 bytes does a translation every time. The bytes read are the same, the number of translations is not.
The indirection is not a tax that somebody forgot to remove. Isolation falls out of it: a process cannot name a block that is not in its map, so another process's data has no address it can use. Sharing is the same mechanism seen from the other side: two maps can hold entries naming one hardware block, which is why forty processes running one library can share a single copy of its code. A heap can grow by adding entries that point at whatever blocks are free, without moving what is already there. A memory-mapped file is read by dereferencing a pointer, with entries that start out pointing nowhere and are filled in when touched.
Where the sameness stops
Two processes are not guaranteed to print the same virtual address. Address randomisation can give each run a different base, so the numbers may differ while both remain virtual. Disable that hardening and two copies of one program often do print the same number again. A 32-bit machine uses fewer levels, and huge pages collapse part of the tree, so the arithmetic changes; it does not make the pointer physical. What changes is the label and the cost of a miss, not the fact that the label is resolved through a private map.
Worth keeping
- A virtual address is an index into a per-process map, so the same number can name different physical memory in two processes.
- Translation works in 4,096-byte blocks, so a sequential walk does one lookup per block rather than one per byte.
- A page-table walk can cost four memory reads before the data read, which is why a small translation cache exists.
Where this goes next
This question is one step of Memory, All the Way Down, a course that works through its subject from the beginning. The page that teaches this part of it is The Address Is Not the Address, and it reads the whole way through whether or not you have an account.
What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.
Read that pageThe whole courseOther questions people ask about this
- Why does reading one byte from memory load 64 bytes?Memory hardware moves data in fixed sixty-four-byte blocks, so a one-byte read fetches the whole block; the extra bytes cost almost nothing because reaching the memory row costs most of the time.
- How does the CPU avoid walking the page table on every single memory access?A small cache of recent translations, called the TLB, is checked on every memory access; a hit skips the page-table walk, and a miss walks once then stores the result.
- Why does 2 + 3 * 4 equal 14 and not 20?The multiplication is done first: three times four makes twelve, and only then is the two added, giving fourteen. Reading left to right would give twenty.
- How many samples does a profiler need before a percentage in the report means anything?It depends on how many samples landed on that line: you need a few hundred samples on the line you care about, because the relative error is roughly one over the square root of that count.
- If I make one part of my program twice as fast, how much faster does the whole program get?Less than twice as fast: only the share of run time you actually touch can improve, so the untouched remainder caps the gain, often at a few per cent.
- Why can two threads that each work correctly still give the wrong answer?Each thread reads the shared value and writes it back in two separate steps, so the other thread can run in between and one increment silently overwrites the other.