Computer Science Deep Dive
by Sergey Okinchuk
Many Cores, SIMD and AcceleratorsThe Memory Hierarchy

Chapter Four · Memory and Its Hierarchy

Memory and Its Hierarchy

The cost model of Chapter 1 charged every memory read one step. This chapter replaces that flat memory with the real one, in six topics: the latency ladder the rest of the book cites, caches and locality, the stack and the heap, garbage collection, memory safety, and the cases where the ladder overrules Big-O.

6 topics

A modern processor can do several hundred instructions' worth of work in the time it waits for one number from RAM. Most programs that feel slow on fast hardware spend their time waiting for memory, not computing. Whether a read costs one nanosecond or a hundred depends on where the data happens to be, and that depends on the order the program touches it, which the source code rarely makes obvious.

The chapter starts by building the latency ladder, from registers to a cross-continent round trip, as orders of magnitude with their sources. Later chapters cite it whenever they say "a cache miss" or "a round trip". It then shows how caches turn access order into speed, measured in Python as well as in theory, and follows memory through its life: handed out by an allocator, reclaimed by a collector, and misused when a language leaves reclamation to a person.

It ends where it was heading from the first page. Lantern's shortest postings lists are searched faster by a plain scan than by a tree with a better Big-O, and the reason is the ladder. The lesson is not that Big-O is wrong, but that it counts steps while the machine charges for distance.

The life of a value in memory, and where each topic sits
Allocatedstack or heap
→
Readthrough the caches
→
Reclaimedwhen unreachable
→
Misusedpast the end

Topics in This Chapter

Topic 01
The Memory Hierarchy
The book's latency ladder, from a register at a third of a nanosecond to a cross-continent round trip at 150 milliseconds, with sources, a human-time scale, and why latency is not bandwidth.
Memory
Topic 02
Caches and Locality
The 64-byte cache line, locality, row versus column order, what the prefetcher can and cannot guess, and a shuffled Python list that sums four times slower.
Memory
Topic 03
The Stack and the Heap
Two ways to get memory: a pointer bump or an allocator. Size classes, fragmentation, where Python puts every object, and why a worker keeps its peak memory.
Memory
Topic 04
Garbage Collection
Reachable, not used. Reference counting and tracing, cycles, generations and CPython 3.15's collector, pauses in the tail, and the leaks a collector cannot see.
Memory
Topic 05
Memory Safety
Unchecked indexes and dangling pointers, overflows and use-after-free, why about 70% of serious security bugs are this kind, and where a Python service is still exposed.
Memory
Topic 06
When Big-O Lies
Constants, small n and the memory hierarchy: a 40-id postings list that a scan searches faster than a tree, and the rule to analyse first and measure second.
Memory