Caches and Locality
A processor never fetches one byte from RAM. It fetches the whole 64-byte line that contains it and keeps the line in cache, in case the program wants it, or its neighbours, again soon. A program that uses what it fetched runs at cache speed. A program that jumps around pays the RAM rung of the latency ladder, about 100 nanoseconds, on nearly every access.
Two loops that do the same arithmetic over the same data can differ several times in speed for this reason alone, and Big-O cannot see the difference: both loops are O(n). This topic shows where the difference comes from, how large it gets, and where it hides inside a Python program.
The Cache Line
Memory moves between RAM and the caches in fixed blocks called cache lines. A line is 64 bytes on almost every x86 and ARM core, and 128 bytes on Apple's M-series chips. Reading one 8-byte integer therefore brings its seven neighbours into the cache along with it, whether the program wants them or not.
The cache has room for a limited number of lines. When it is full, bringing in a new line evicts one that has not been used recently. So a line stays close only while the program keeps coming back to it, and the next read of anything in that line costs a nanosecond instead of a hundred.
Temporal and Spatial Locality
Caches pay off for two habits that programs have. Temporal locality means that what you touched, you touch again soon: a loop counter, the top of the stack, a dictionary consulted on every request. Spatial locality means that what you touch next sits beside what you touched last: the next element of an array, the next field of a record.
A cache pays off only to the degree a program has both habits. A program with neither, one that reads scattered addresses once each, runs at RAM speed however fast its core is. The core is not slow; it is waiting.
Row by Row, Column by Column
Take a grid of 4,096 by 4,096 floating-point numbers, 8 bytes each. That is 128 mebibytes, far larger than any cache, stored the usual way: row 0 from start to end, then row 1, and so on. Summing it row by row reads the values in the order they sit in memory, so every 64-byte line fetched supplies eight values in a row.
Summing it column by column does the same additions in a different order. Consecutive reads are now one full row apart, 4,096 values of 8 bytes, which is 32 kibibytes forward in memory each step. The walk uses one value from each line it fetches, and by the time it comes back for that line's second value, 4,096 reads later, the line has usually left the fastest cache. The column walk can fetch up to eight times as many lines from the slower levels, for identical arithmetic.
On CPython 3.15, summing that 128-mebibyte grid held in the standard library's array module, with each row or column taken as one slice so that the inner loop runs in compiled code, took 0.21 seconds by rows and 0.47 seconds by columns, in repeated runs. Same values, same additions: more than twice as slow, from the order alone.
The Prefetcher and Its Limits
The hardware tries to hide the latency. A prefetcher watches the stream of addresses a core requests, and when they march forward by a steady step it starts fetching the next lines before they are asked for. That is why a sequential scan runs near the memory's bandwidth rather than paying its latency on every line, as the previous topic's ladder distinguished.
The prefetcher cannot guess an address that is stored inside the data it is waiting for. In a linked list (Chapter 5) or a tree (Chapter 6), the address of the next node is written in the current node, so the core cannot even ask for node two until node one has arrived. Each hop pays the full trip down the ladder, one after another, and no hardware trick overlaps them.
Where Python Hides It
A Python list holds pointers to objects that live elsewhere on the heap (Chapter 5), so iterating over it touches two places per element: the pointer array, which is contiguous, and the object it points to, which is wherever the allocator put it. Objects created one after another usually sit next to each other in memory, so iterating a list in creation order walks memory mostly forward. Shuffle the same list and every element sends the processor to a different place.
nums = [i for i in range(1000, 1000 + n)] # objects allocated in order shuffled = nums[:] random.shuffle(shuffled) # same objects, new order sum(nums) # n = 1,000,000: 3.35 ms sum(shuffled) # n = 1,000,000: 13.9 ms
The listing builds a list of integers, copies it, and shuffles the copy, so both lists hold exactly the same integer objects, only in a different order. On CPython 3.15, summing a million of them took 3.35 milliseconds in creation order and 13.9 milliseconds shuffled, about four times slower. At ten million it was 33 against 220 milliseconds, more than six times. At a hundred thousand integers, which fit in cache, there was no difference at all.
Not every Python loop shows the full effect. A pure-Python double loop over the grid, indexing one value at a time, was only about 1.5 times slower by columns, because the interpreter's own work per step (Chapter 13), tens of nanoseconds, is paid in both orders and dilutes the cache misses. The effect appears at full strength wherever the inner loop is compiled code: built-in functions such as sum, slices, and NumPy, which stores its arrays in row order by default.
Row Stores, Column Stores and DataFrames
The same query over the same table runs at different speeds depending on layout. A row store keeps each row's fields together, which suits fetching one whole record. A column store, the layout most analytics databases use, keeps each column contiguous. Summing one column of a billion-row table then streams only that column's bytes, while a row store drags every other field of every row through the cache to reach it.
A pandas DataFrame is columnar for the same reason. Iterating it row by row in Python throws away both advantages at once: the contiguous column and the compiled loop that walks it. The rule that follows is short. Walk data in the order it is stored, and keep the data a hot loop needs next to each other.
- "Two loops with the same Big-O over the same data cost the same." The order of access decides how many lines come from RAM. The column walk over a large row-major grid does the same additions and can fetch eight times as many lines; measured on CPython 3.15, it ran more than twice as slow.
- "Reading one integer transfers one integer." The whole 64-byte line moves. A lookup that uses 8 bytes of every line it fetches wastes seven eighths of the memory traffic.
- "Threads writing different variables cannot slow each other down." Caches stay consistent line by line, so two counters that share one line bounce it between cores on every write. This is called false sharing, and it can make two threads slower together than one thread alone.
- "Cache effects are for C programmers." NumPy and pandas feel them fully, and even summing a shuffled Python list of a million integers took four times longer than summing the same list in creation order.
- "A benchmark on a small array predicts the big one." A thousand-element array lives in L1. At a hundred million elements the same loop runs from RAM, three rungs lower, and the per-element cost can grow several times.
- Walk data in the order it is stored: row-major arrays by rows, columnar frames by columns. The prefetcher rewards a steady forward stride.
- Keep the fields a hot loop reads together, and the fields it skips elsewhere. Every byte of a fetched line should earn its trip.
- Hold large numeric data in contiguous arrays rather than lists of objects. Every pointer hop is a potential cache miss.
- Benchmark with data larger than the last-level cache. Otherwise the measurement is of the cache, not of the algorithm.
Knowledge Check
A program sums a 4,096 by 4,096 grid of 8-byte floats stored row by row. One version loops over rows in the outer loop, the other over columns. Which is faster, and roughly why?
- The column loop, because it spreads the reads evenly over memory
- The row loop, because each fetched line supplies eight values in order
- Neither, because both perform exactly the same number of additions
- The row loop, because it performs fewer additions than the other one
Why does the hardware prefetcher speed up a scan of an array but not a walk along a linked list?
- The prefetcher only works on data that is already in the L1 cache
- Linked lists are stored on disk, and prefetchers only cover RAM
- The next node's address is inside the node that has not arrived yet
- Arrays are read by the operating system, and lists by the program itself
Two threads each increment their own counter, and the two counters sit next to each other in memory. The program runs slower than with one thread. What is the most likely cause?
- The two threads are secretly incrementing the very same variable
- Incrementing a counter needs the operating system every time
- Each thread flushes the whole cache when it starts running
- Both counters share one cache line, which moves between cores
An analytics query sums one column of a table with a billion rows and forty columns. Why does a column store answer it faster than a row store?
- A column store compresses every value down to a single bit
- It streams only that column's bytes instead of every field of every row
- A column store keeps the entire table in the processor's L1 cache
- Row stores must sort the table before they can add any values up
A benchmark sums a 1,000-element array and reports 1 nanosecond per element. Production arrays hold 100 million elements. What should the team expect?
- The same 1 nanosecond per element, since the loop is O(n) either way
- A faster loop per element, because the prefetcher needs time to warm up
- A slower loop per element, because the data no longer fits in any cache
- A crash, because arrays of that size exceed what a process may allocate
You got correct