Space and the Time-Space Trade

Memory is the second price of every algorithm, and on a real server it is the one with a hard ceiling. A slow job finishes late. A job that runs out of memory does not finish at all: the operating system kills it. Much of practical performance work is a trade between the two prices: spend memory on a lookup table, a cache or an index to buy time, or spend time recomputing to save memory.

The numbers Python actually charges make the trade concrete. They are larger than most engineers expect, and they explain a good share of the out-of-memory kills that arrive at 3 a.m.

Space Is a Cost Like Time

An algorithm's space cost is the extra memory it needs beyond its input, stated in Big-O the same way as time. Summing a list needs O(1) extra space: one running total, whatever the length. Sorting a copy needs O(n). A recursive function needs one stack frame per level of recursion, which Chapter 3 explains, so recursing a million levels deep needs a million frames.

The difference from time is what happens at the limit. Exceeding a time budget makes a program late. A machine has a fixed amount of memory, and exceeding it does not slow the program down gracefully. It ends it.

What Python Charges per Item

Every Python value is a full object with a header, so it costs far more than the bytes of the value itself. On a 64-bit build of CPython 3.15, an integer such as 1,000 takes 28 bytes and a float takes 24. A list does not hold its values directly. It holds an 8-byte pointer to each one, and each value lives in its own object elsewhere in memory.

Measured on CPython 3.15, a list of a million such integers takes about 40 megabytes: 8 for the pointers and about 32 for the integer objects. A packed array of 64-bit integers holding the same million values takes 8 megabytes, because it stores the numbers themselves side by side. A dictionary mapping a million integers to a million integers comes to about 106 megabytes. Object overhead, not the values, dominates Python's memory use.

Buying Time With Space

The most common trade spends memory to avoid repeated work. A lookup table computes answers once and then reads them: a 256-entry table answers "how many bits are set in this byte" in one read instead of eight tests. A cache keeps recent results of expensive operations. An index, like Lantern's, stores a second copy of the data arranged for one kind of question, so that answering it becomes a lookup instead of a scan.

Each of these turns repeated work into one read. Each also costs memory that has to be sized, and each has to be kept correct when the data it was built from changes.

Memoization

Memoization means remembering a function's results by its arguments, so that a second call with the same arguments returns the stored answer instead of recomputing it. The textbook case is the naive recursive Fibonacci function, which recomputes the same smaller values over and over. Computing the thirtieth Fibonacci number that way makes 2,692,537 calls. With its results remembered, it computes each of the 31 values once.

def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)   # fib(30): 2,692,537 calls

from functools import cache

@cache
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)   # each value computed once

The two definitions above are identical except for one decorator from the standard library. The first recomputes every subproblem each time it is needed, and its call count roughly doubles with each step of n. The second stores every result it computes, so the work drops from exponential to linear, paid for with a table of 31 stored results.

Two conditions come with it. It is only correct for pure functions, whose output depends on nothing but their arguments. And the standard library's plain cache is unbounded: on a long-running service, called with ever-new arguments, it grows until the process dies. Its sibling, the least-recently-used cache, keeps 128 entries by default and evicts the rest. Chapter 9 takes the same idea further, to dynamic programming.

Buying Space With Time

The opposite trade spends time to save memory, and it is the right one whenever memory is the ceiling. Streaming a 50-gigabyte log file one line at a time needs a few kilobytes. Reading it into a list needs more memory than the machine has. Recomputing a value instead of storing it, compressing data held in memory, and keeping an approximate summary instead of the full set of values all trade processor time for memory.

When More Memory Is Slower

The trade has an optimum, and past it more space buys less time. A lookup table that fits in the processor's cache answers in about a nanosecond. The same table grown larger than the cache turns each "one read" into a trip to main memory costing about a hundred times more, which Chapter 4 measures. A cache grown larger than the server's RAM pushes the process into swapping, where memory is slower still.

So bigger is not automatically better. Past the size of the processor's caches, a bigger table buys less; past the size of RAM, it buys a slowdown; and past the machine's limit, it buys an out-of-memory kill.