In 05-01 we spent memory without remorse: an auxiliary set here, an unbounded cache there — all in exchange for time. This lesson presents the bill. The case that will accompany us is the RutaBus nightly job: a process that in the small hours reads the day's tap record file — several million lines — and produces statistics per line and stop. It works perfectly on the developer's laptop; in production, inside a container with 512 MB, it dies with a terse Killed. We will learn why memory matters even when there is "plenty", how to actually measure it (which is not as obvious as timing), and a repertoire of concrete techniques — generators, batches, __slots__, compact representations — so that this job can process millions of tap records without ever holding them all in RAM at once.

1. Why memory matters even when there is "plenty"
2. Measuring memory (I): sys.getsizeof and its traps
3. Measuring memory (II): tracemalloc
4. Generators and iterators: processing without materializing
5. Batch processing (chunks)
6. Lightweight objects: __slots__, tuples, namedtuple, and dataclass
7. Homogeneous numeric data: array (and a mention of NumPy)
8. Interning and reference sharing
9. The graph representation according to density
10. The reverse trade-off: trading time for memory

"My machine has 32 GB, who cares about a list of a million elements?" Four reasons why you should:

• The processor's caches. RAM is slow compared with the CPU's L1/L2/L3 caches (tens versus hundreds of cycles per access). A compact dataset fits in cache and is traversed fast; a scattered, bulky one causes constant cache misses. Less memory usually means more speed, even with the same algorithm.
• The garbage collector (GC). In Python, every live object is work for the memory manager. Millions of small objects mean more collection cycles and longer pauses.
• Containers and cloud with limits. In production the process doesn't get "the whole machine": it gets what its container declares (512 MB, 1 GB...). Exceeding it doesn't produce an elegant error: the operating system kills the process (OOM kill — the Killed of our job). And in the cloud, more reserved memory is quite literally a bigger bill.
• Scale changes on its own. The job that processes 2 million tap records today will process 10 million within two years. A design that is O(n) in memory has an expiry date; an O(1) one does not.

And the warning symmetric to 05-01's: no guessing here either. Measure first.

sys.getsizeof(obj) returns the bytes taken up by that object... and that is where the traps begin:

Trap 1: the measure is shallow. Those 88 bytes are the list — that is, its header plus the 4 references — but not the referenced objects: the string "Main Square" (60 bytes), the "L1", the integer... are not included. For a container, getsizeof measures the wrapper, not the contents. (It is the copies-vs-references distinction from 02-02 applied to measurement.)

Trap 2: the references may be shared. If a million tap records reference the same "Main Square" string, that string takes 60 bytes in total, not 60 million. Summing getsizeof recursively can overestimate as much as the shallow measure underestimates.

Trap 3: containers over-allocate. A list grows with the geometric over-allocation we saw in 02-03 (the amortized analysis of append): after a million appends, the list has room reserved for more elements than it contains.

Conclusion: getsizeof is useful for comparing the unit weight of two representations (we will use it that way in section 6), but it does not answer "how much memory does my program use?". That is what the next tool is for.

tracemalloc is to memory what cProfile was to time in 05-01: it records which line of code made each allocation. Let's measure the first (naive) version of the tap record job:

How to read it:

• get_traced_memory() gives the current memory and the peak — the peak is what kills the container.
• The snapshot by lineno points at the culprits: line 7 (the list of split-up tap records: 2 million small lists with their strings) holds 622 MiB, and line 6 (readlines) another 154 MiB. Line 8, the one that does the useful work, spends 400 bytes.

The diagnosis is devastating: 99.9% of the memory goes into materializing data that is only traversed once. That is exactly the problem the next two techniques solve.

In 02-02 we saw that a generator takes O(1): it is a recipe that produces values one at a time, not the whole collection. Applying it to the job is immediate, because files in Python are already iterators over lines:

At any given instant there is one live tap record in memory: the one being processed. Measured with tracemalloc, the peak drops from 812 MB to under 1 MB — the job fits in any container, and will keep fitting when the tap records quintuple. Same result, same time complexity, memory from O(n) to O(1).

The typical aggregations fit this mold effortlessly: sum, max, min, a dictionary of counters... all of them consume the stream one item at a time. The limits are the ones we already noted in 02-02: a generator cannot be indexed, has no len, and is exhausted by traversing it — for two passes you must call it again (re-reading the file: time for memory, the trade-off once more).

Between "everything in memory" and "one at a time" there is a useful middle ground: processing in batches. It is the solution when the destination of the data prefers groups — inserting into a database 1,000 at a time, sending to an API in blocks — or when it pays to amortize a fixed per-operation cost:

Memory goes from O(1) to O(batch size) — controlled and constant, chosen by us, independent of the total. The size parameter is a dial between memory and per-operation overhead: it gets tuned by measuring, like everything in this module.

Even when the stream is lazy, sometimes you must retain a portion: the 200,000 tap records of line L1 for a later analysis, for example. Then the unit weight of each object gets multiplied by 200,000, and the representation matters. Let's compare the options for a 4-field TapRecord (shallow bytes per instance, CPython 3.12, 64-bit):

* Measured with getsizeof (shallow: the values are extra, but they are the same in every case — what changes is the wrapper).

The key is in the second row: a plain class stores its attributes in an internal dictionary (__dict__), flexible but expensive. __slots__ declares the attributes up front and eliminates that dictionary:

For 200,000 instances: ~69 MB with a plain class, ~14 MB with __slots__ — about 5 times less, with the same usage syntax. The price: you cannot add undeclared attributes (r.extra = 1 → AttributeError), which in a record-like object is more virtue than limitation. Quick criteria:

• Internal, positional, short-lived data → tuple.
• Immutable record with names → namedtuple.
• Mutable record with names and millions of instances → __slots__ or @dataclass(slots=True) (the latter adds __init__, repr, and comparison for free).
• dict as the default for massive data, no: it is the heaviest option in the table.

When what is retained is numbers of the same type — the minute of each tap record, for example — there is one more leap. A Python list stores references to integer objects (28+ bytes each, scattered across RAM); the standard library's array module stores the values raw and contiguous:

The same idea, on steroids, is NumPy: compact n-dimensional arrays with vectorized operations in C (minutes.mean(), matrix @ vector). For serious numeric work — the Floyd-Warshall matrix D at large scale, massive statistics — it is the ecosystem's standard tool; here it is enough to know it exists, why it wins (same reason as array: raw, contiguous data), and that its vectorized side will pop up again in 05-03.

One last turn of the screw on the job: each tap record carries the name of its stop as a string. Two million tap records, but only ~3,000 distinct stops: reading the file, Python creates two million string objects, almost all of them repeated copies of the same 3,000 values. The solution is to share references: make every Main Square tap record point to the same string. sys.intern maintains that table of unique instances:

With that, the two million stop fields weigh what 3,000 strings weigh, not what 2,000,000 do (tens of MB recovered), and as a bonus stop == other comparisons between interned strings resolve by comparing references. The same effect can be achieved with a homemade cache (seen.setdefault(stop, stop)). Two honest nuances: Python already interns some small strings and identifiers on its own (which is why the problem sometimes "isn't noticeable"), and this is the deep reason behind trap 2 of getsizeof — with shared references, summing unit sizes overestimates.

We already applied this criterion of "representation according to the data" to the RutaBus graph in 04-06, back then with an eye on time. Let's revisit the same table from the memory angle:

The matrix pays one cell per possible pair, whether or not the segment exists; the dictionary pays only for the real segments. In a sparse graph (E ≪ V², like every transit network: each stop connects to 2–4 neighbors, not to all 20,000) the matrix wastes almost all its cells on INF. In a dense one, the matrix pays off: no per-entry cost of dicts and O(1) access to any pair — and if the desired output is all-pairs (Floyd-Warshall), the O(V²) is irreducible because it is the size of the answer, as we already noted in 04-06. The moral generalizes section 6: the right representation depends on the shape of the data — density here, homogeneity in array, repetition in interning.

In 02-02, build_index spent memory to gain time, and in 05-01 lru_cache did the same. This lesson has walked the opposite direction of the same axis, and it is worth saying explicitly: sometimes the right move is to pay time to free memory.

• Recompute instead of caching. If distances_from (05-01, exercise 2) caches the distances from 20,000 origins, that is 20,000 dictionaries of 20,000 entries: gigabytes. If each origin is queried only a few times, better to recompute: Dijkstra takes milliseconds and the unbounded cache was an OOM on layaway. The middle ground is to bound it: lru_cache(maxsize=500) retains the 500 most queried origins and recomputes the rest.
• Re-read instead of retaining. The generator that gets exhausted and forces a second read of the file is this trade-off: two 30-second passes versus 800 MB retained.
• The criterion is the usual one: measure both quantities and look at which resource is scarce in your environment. In the 512 MB container, memory is scarce; in the report that must be out in 5 minutes and has RAM to spare, time is scarce. The mistake is not choosing one or the other: it is choosing without having measured either.

• Trusting getsizeof for containers. It measures the wrapper, not the contents. For "how much does my program use and who is responsible?", tracemalloc; getsizeof, only for comparing unit weights.
• Materializing out of habit. readlines(), list(...), or a comprehension "to see it better" turn O(1) into O(n) needlessly. Ask yourself: will I traverse this more than once? Do I need to index it? If not, leave the generator alone.
• Traversing a generator twice. The second pass does not raise an error: it yields nothing, silently. If you need two passes, materialize knowingly or regenerate the stream.
• Optimizing memory that doesn't matter. The warning from 02-02 still stands: if the job processes 5,000 tap records, the 800 MB never happen and __slots__ is noise. These techniques are justified with a tracemalloc in hand, just as 05-01 demanded a profile.
• Forgetting the peak. tracemalloc gives current memory and peak; the container dies from the peak. A huge temporary copy inside a function (a sorted(...) of the whole stream, for example) may leave no trace in the final memory and still kill the process.
• Tip: in data jobs, decide the memory contract first ("this process uses O(1)/O(batch), never O(n)") and protect it: any list(...) over the full stream is a contract violation that should be flagged in code review.

Exercise 1. This job computes the average tap-in minute per line. Point out every place where it materializes data unnecessarily and rewrite it with O(L) memory, L being the number of bus lines (3), independent of the number of tap records:

Exercise 2. With getsizeof, estimate how much shallow memory 500,000 retained tap records would save if they went from a 4-key dict (184 B) to a @dataclass(slots=True) (72 B). Then explain why the real saving measured with tracemalloc would be even bigger if intern is also applied to the stop names. Can getsizeof detect that second saving?

Exercise 3. RutaBus wants to publish the all-pairs minimum-time matrix of the metropolitan network (V = 20,000, E ≈ 60,000, sparse). A colleague proposes: "Floyd-Warshall on a matrix, like in 04-06". Refute or support the proposal with memory numbers (matrix cells at 8 bytes each), and propose which representation and strategy you would use if only 1% of the pairs are actually queried. (This is the third time this dilemma appears in the course — 04-06 looked at it in time, now it's memory's turn.)

Solution 1. It materializes three times: readlines() (the whole file), the tap_records list (everything split up), and the minutes lists (one extra pass per bus line, re-reading the full list). Single-pass version with accumulators:

Memory: two 3-entry dictionaries plus the tap record in flight. It makes no difference whether the file has two thousand or two billion lines. (As a bonus, it is also faster: one pass instead of L+1.)

Solution 2. Shallow saving: 500,000 × (184 − 72) = 56,000,000 bytes = 56 MB, in wrappers alone. The additional saving from interning is in the values: without it there are up to 500,000 string objects for ~3,000 distinct stops (~60 B each ≈ 30 MB → ~0.2 MB with interning). getsizeof cannot detect it: it is a shallow measure that does not follow references, so it cannot tell whether two tap records share the string or hold copies (traps 1 and 2). Only a global measurement like tracemalloc sees the difference.

Solution 3. The matrix needs V² = 400,000,000 cells × 8 B = 3.2 GB — just the distance matrix; with the nxt reconstruction matrix from 04-06, double that. Unfeasible in a normal container, and 99% of the cells will never even be queried. An alternative consistent with the graph's density: adjacency dict (O(V+E) ≈ a few MB) + Dijkstra on demand from the queried origin, with a bounded cache of per-origin results (lru_cache(maxsize=...) on distances_from, exercise 2 of 05-01) for the popular origins. You trade an O(V²) precomputation in memory for O((V+E) log V) recomputation in time — exactly the reverse trade-off of section 10, chosen because here the scarce resource is memory and the queries are sparse.

The RutaBus nightly job has gone from dying at 812 MB to running in O(1) memory, and along the way it has left a method behind: measure (tracemalloc for the global picture and the peak, getsizeof only for comparing unit wrappers), don't materialize what is only traversed (generators, line by line, batches when it pays to amortize), compact what is actually retained (__slots__, namedtuple, array, interning), and choose the representation according to the shape of the data — the graph's density decided between dict and matrix just as homogeneity decided between list and array. And we have closed the circle opened in 02-02: time and memory are two pans of the same scale, and knowing which one to load requires having measured both. With the code tuned (05-01) and memory under control, one resource remains untapped: the processor's other cores, which throughout this module have been watching a single one do all the work. The next lesson — parallelization — spreads the work among them, and along the way dismantles Python's most persistent myth: why threads don't always speed anything up, and what to use when they don't.