Skip to content
Tutorials Center
My learning

Topics

Lesson 48 of 61 ยท Code Generation and Runtimes

Memory Management and Garbage Collection

Learn how languages manage heap memory: manual freeing, reference counting, mark-and-sweep and copying collectors, with runnable Python simulations of each.

Every program that creates objects at run time needs a place to put them and a way to give the space back. Local variables live on the stack and disappear when a function returns, as you saw in runtime environments. Objects that must outlive the call that created them live on the heap, and nothing frees them automatically. Somebody has to decide when a heap object is no longer needed. That decision is the job of memory management.

Languages answer in three ways: the programmer decides, the compiler decides, or a runtime component called a garbage collector decides. In this lesson you will compare the main designs and run a tiny simulation of each: reference counting, mark-and-sweep and a copying collector. The simulations use plain Python dictionaries and lists as a pretend heap, so you can watch every step.

Manual, compiler-assisted and automatic

In C, you call malloc to get memory and free to return it. This gives full control and zero runtime overhead, but the bugs are famous:

  • Memory leak. You forget to call free, and the program slowly eats memory.
  • Use after free. You free an object and keep using the pointer. The memory may now belong to something else.
  • Double free. You free the same block twice and corrupt the allocator.

Some languages keep manual control but help you with rules the compiler checks. C++ destructors and smart pointers free an object when its owner goes out of scope. Rust goes further: its compiler tracks ownership and inserts the drop calls itself, rejecting programs that could use freed memory. There is no collector at run time, which is why this approach suits systems code.

Languages such as Java, Go, JavaScript, C# and Python use automatic memory management. You create objects freely, and the runtime finds and frees the unused ones. This removes a whole class of bugs, at the price of extra work at run time and, for some collectors, short pauses.

What counts as garbage?

A collector cannot read your mind, so it uses a safe, mechanical definition. Start from the roots: the places the running program can reach directly, such as local variables on the stack, CPU registers and global variables. An object is live if you can reach it from a root by following pointers. Everything else is garbage, because the program has no way to name it any more.

flowchart LR
    R1["root: variable t"] --> T["tree"]
    T --> L1["leaf1"]
    T --> L2["leaf2"]
    P["p"] --> Q["q"]
    Q --> P
    O["orphan"]
    classDef live fill:#d7f5dd,stroke:#2e7d32,color:#111
    classDef dead fill:#f9d6d5,stroke:#c62828,color:#111
    class T,L1,L2 live
    class P,Q,O dead

Objects reachable from a root are live (green). The pair p and q point at each other but nothing reaches them, so they are garbage like the orphan.

Notice the cycle p <-> q. Each object is pointed to by another object, yet the pair is unreachable from the program. A good collector must free it. This detail separates the two big families of algorithms.

Reference counting

The simplest idea: store a count in every object saying how many references point to it. When a reference is created, add one. When a reference disappears, subtract one. When the count reaches zero, nobody can reach the object, so free it immediately. Freeing an object also drops the references it holds, which may free more objects in a cascade.

Python Reference counting, including a leaked cycle

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The chain is freed completely: when the variable lets go of a, its count hits zero, a frees itself, which releases b, which releases c. The cycle is a different story. After the variable is dropped, x still has count 1 (from y) and y has count 1 (from x). Neither reaches zero, so both leak even though the program can no longer see them.

Reference counting has real strengths: memory is returned immediately, there are no long pauses, and the cost is spread evenly through the program. It also has costs: every pointer assignment updates a counter (and in threaded programs those updates must be atomic), and cycles need extra help. Swift and Objective-C use counting and ask you to mark some references as weak to break cycles. CPython counts references and adds a separate cycle detector, which you will meet at the end of this lesson.

Mark-and-sweep

A tracing collector does not count anything while the program runs. Instead, when memory runs low, it pauses the program and works out what is reachable. The classic algorithm, mark-and-sweep, has two phases:

  1. Mark. Start at the roots and follow every pointer, setting a mark bit on each object you visit. Use a work list so you never visit an object twice, which also makes cycles harmless.
  2. Sweep. Walk the entire heap. Every object without a mark is garbage and its space is freed. Clear the marks on the survivors for the next round.
Python Mark-and-sweep collector

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The heap fills up with six objects, so the next alloc triggers a collection. Marking starts at variable t and reaches only tree, leaf1 and leaf2. The sweep then frees p, q and orphan, including the unreachable cycle, and the new object fits.

Mark-and-sweep is simple and handles cycles, but it has weak spots. The program usually stops while the collector runs (a stop-the-world pause), the sweep must visit dead objects too, and freed objects leave holes of different sizes behind. This fragmentation can make it hard to find room for a big object even when plenty of total memory is free. Modern collectors reduce the pause with tri-color marking, where objects are white (not yet seen), gray (seen, children not yet scanned) or black (fully scanned), which allows marking to run concurrently with the program.

Copying collection

A copying collector solves fragmentation by moving objects. It splits memory into two halves. The program allocates in the active half (the from-space) by just bumping a pointer, which is extremely fast. When that half is full, the collector copies every reachable object into the other half (the to-space), packed tightly, then swaps the roles. Everything left behind is garbage, and nothing needs to be swept.

Cheney's algorithm does the copying without recursion. It uses two pointers in the to-space: objects between the scan pointer and the allocation pointer have been copied but their fields still point into the old space. The collector scans one object at a time, copies whatever its fields point to, and updates the fields. A forwarding address left in the old copy ensures that each object is copied exactly once, even in a cycle.

Python Cheney's copying collector

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the result. The five live cells now sit side by side at addresses 0 to 4, every pointer was rewritten to the new addresses (the root a moved from 1 to 0), the shared leaf was copied once, and the cycle between list, head and tail survived intact. The two junk cells were never even looked at, so the work is proportional to the live data, not to the heap size. The price is that half of the memory is always idle, and every object's address changes, which means the runtime must know exactly which words are pointers.

Generational collection

Studies of real programs keep finding the same pattern, called the generational hypothesis: most objects die young. A temporary string or a loop's helper object is dead within microseconds, while a few objects (caches, configuration, long lists) live for the whole run.

A generational collector exploits this by splitting the heap into a small young generation and a larger old generation. New objects go to the young generation, which is collected often and cheaply (usually by copying, since few objects survive). Objects that survive a few rounds are promoted to the old generation, which is collected rarely. The catch: an old object may point to a young one, so the compiler emits a write barrier with every pointer store to record such pointers. Otherwise a minor collection would wrongly free a young object that only an old object references.

What the compiler and runtime must provide

Garbage collection is a partnership between the language implementation's compiler and its runtime:

  • Type and layout information, so the collector knows which fields of an object are pointers. A collector that uses this information is precise. A conservative collector (such as the Boehm collector for C) treats any word that looks like an address as a possible pointer, which needs no help from the compiler but cannot move objects safely.
  • Stack maps, tables generated by the compiler that say which stack slots and registers hold pointers at each point where a collection can occur.
  • Safepoints, places in the generated code (often loop back-edges and calls) where the program can be paused safely.
  • Barriers, small code snippets the compiler inserts around pointer loads or stores for generational and concurrent collectors.
  • Fast allocation. With a copying young generation, allocating is just ptr += size plus a limit check, often faster than malloc.

Python uses two of these at once

CPython frees most objects the instant their count reaches zero, and it also runs a cycle collector for the leftovers. The next example shows both using weak references, which observe an object without keeping it alive.

Python CPython: reference counting plus a cycle collector

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The plain object disappears at del, which is reference counting at work. The cycle survives del and only vanishes when gc.collect() traces reachability, exactly the situation from the first simulation.

Comparing the strategies

Strategy Frees when Handles cycles Main cost
Manual (free) the programmer says so not applicable bugs: leaks, use after free
Ownership (Rust, C++ RAII) owner leaves scope by design, mostly stricter programming model
Reference counting count reaches zero no, needs extra help counter updates, cycles
Mark-and-sweep memory is low yes pauses, fragmentation
Copying memory is low yes half the memory idle, objects move
Generational young generation fills yes write barriers, tuning

Real systems mix these. The JVM and .NET use generational collectors with copying young spaces, Go uses a concurrent tri-color mark-and-sweep, and Python combines counting with a generational cycle collector.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. An object is garbage when...

    Collectors define garbage as unreachable: there is no path from any root (stack, registers, globals) to the object, so the program cannot use it again.
  2. 2. Which problem is a pure reference-counting scheme unable to solve on its own?

    In a cycle every object keeps a count of at least one because of the others, so no count ever reaches zero. That is why CPython adds a cycle collector.
  3. 3. What is the main advantage of a copying collector over mark-and-sweep?

    Copying packs survivors together, which removes fragmentation and makes allocation a pointer bump. The collector must know which fields are pointers, and it needs a spare half-space.
  4. 4. Why does a generational collector need a write barrier?

    A minor collection only scans the young generation plus the roots. Without the barrier's record of old-to-young pointers, a young object referenced only by an old object would look unreachable.

Summary

  • Heap memory can be managed manually, by compiler-checked ownership, or automatically by a garbage collector.
  • Live objects are those reachable from the roots; everything else is garbage.
  • Reference counting frees objects immediately but cannot free cycles without help.
  • Mark-and-sweep marks reachable objects, then frees the rest; copying collectors move survivors into a fresh space and need work only for live data.
  • Generational collectors exploit the fact that most objects die young and rely on write barriers.
  • The compiler cooperates by providing pointer maps, safepoints and barriers.

Next: Bytecode and Virtual Machines