Garbage Collection

In the previous lesson the program itself made the release decision: b and d were released and their space reclaimed. That decision has two ways of going wrong. A block that is never released stays unusable until the program ends. An address used after release reads or writes memory that has since been handed to another request. Neither shows up in the source text; both surface only at runtime.

This lesson models the arrangement that takes the decision away from the program and hands it to the runtime. The handoff requires a criterion — not which object is still needed, but which one is reachable. Mark and sweep itself, along with the reachability criterion, was already established earlier in this catalog, in the Garbage Collection lesson of the Memory and Performance topic in the Asynchronous JavaScript and the Runtime course, and is not repeated here. What this lesson adds is measurement alone: how many steps does the handoff cost, and what does that step count depend on.

Baseline, Setup, and the Name of the Cost

The baseline without an abstraction is manual release. There is no collector, no scan, no pause; a block’s lifetime is written into the program text. Its cost is paid not at runtime but in correctness.

The setup is a tracing garbage collector. Starting from the root set, references are followed, every object reached is marked; unmarked objects have their space reclaimed. The name of the cost is pause, and in this lesson a pause is not a duration but a step count: how many objects were scanned.

• BD13 — The object graph is the common definition’s model: 40 objects, seed 20260218, root set the first three objects. Links come from the generator and are the same on every run.
• BD14 — Scanning one object is one step; an object’s size and the number of links it carries do not change the step count.
• BD15 — Collection runs in one pass with the program fully stopped. There is no incremental or concurrent collection in this model.
• BD16 — Sweeping walks the entire object list once to reclaim unmarked objects’ space; this too is one step per object.

"""M01/K05 common definition (excerpt): object graph , reachability and mark-and-sweep."""
SEED = 20260218


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def object_graph(seed=SEED, n=40, roots=3):
    r = generator(seed)
    links = {i: [] for i in range(n)}
    for i in range(n):
        for _ in range(r(3)):
            h = r(n)
            if h != i and h not in links[i]:
                links[i].append(h)
    return links, list(range(roots))


def mark_and_sweep(links, roots):
    seen, stack, scan = set(), list(roots), 0
    while stack:
        d = stack.pop()
        if d in seen:
            continue
        seen.add(d)
        scan += 1
        for h in links[d]:
            stack.append(h)
    return {"reachable": len(seen), "collected": len(links) - len(seen),
            "scan": scan}


G, K = object_graph()
print("objects:", len(G), "| links:", sum(len(v) for v in G.values()), "| roots:", len(K))
print("baseline measurement:", mark_and_sweep(G, K))
print()
print("roots  reachable  collected  marking  sweeping  total work  per collected")
for roots in (1, 2, 3, 4, 6, 8, 12):
    g, k = object_graph(roots=roots)
    r = mark_and_sweep(g, k)
    total = r["scan"] + len(g)
    print(f"{roots:5d}  {r['reachable']:9d}  {r['collected']:9d}  {r['scan']:7d}"
          f"  {len(g):8d}  {total:10d}  {total / r['collected']:13.2f}")

objects: 40 | links: 44 | roots: 3
baseline measurement: {'reachable': 17, 'collected': 23, 'scan': 17}

roots  reachable  collected  marking  sweeping  total work  per collected
    1          3         37        3        40          43           1.16
    2          7         33        7        40          47           1.42
    3         17         23       17        40          57           2.48
    4         19         21       19        40          59           2.81
    6         21         19       21        40          61           3.21
    8         23         17       23        40          63           3.71
   12         25         15       25        40          65           4.33

Three numbers sit side by side. Baseline: manual release, 0 scan steps, 0 pause. Setup: a tracing collector with three roots, 17 of 40 objects reachable, 23 collected. Cost: a 17-step pause followed by a 40-step sweep pass, 57 steps total.

Notice that reachability is a traversal: starting from the root set, following links, walking without revisiting what it has already seen. The graph traversal from the Data Structures course is not redefined here, it is invoked directly; the only novelty is that the visit count is counted as a cost.

What the root set is also reads from the arrangement this course built. In the address space from the Memory Layout lesson, the places the collector counts as “starting points” are settled: the local variables sitting on each thread’s own stack, the global variables in the initialized and uninitialized data segments, and the references currently held in registers. These three are not a list the process’s own code hands over by name; they are read from the address space’s structure. In the model, this same set is the roots parameter, and its size is directly a cost item — the traversal deepens as the root count grows. Nothing outside the roots is ever a starting point; so a cluster of objects that reference each other but are cut off from the roots gets collected regardless of how many links it carries.

What the Pause Is Proportional To

Reading the table’s first two columns together produces an unexpected pattern. At a root count of 1, 37 objects are collected and the pause is 3 steps. At a root count of 12, only 15 objects are collected and the pause is 25 steps. As the garbage collected shrinks, the pause grows.

This inverse relation is not a coincidence, it follows from the method’s own definition: marking visits only reachable objects. A dead object is never visited — it was already unreachable. The construction below isolates the same relation independently of the common definition’s graph: the surviving object count is held fixed while the dead object count is multiplied by thirty.

"""What the pause is proportional to: surviving objects fixed , garbage variable."""


def mark_and_sweep(links, roots):
    seen, stack, scan = set(), list(roots), 0
    while stack:
        d = stack.pop()
        if d in seen:
            continue
        seen.add(d)
        scan += 1
        for h in links[d]:
            stack.append(h)
    return {"reachable": len(seen), "collected": len(links) - len(seen),
            "scan": scan}


def construct(alive, dead):
    """Survivors are reached by a chain from the root , dead objects are linked among themselves."""
    links = {i: [] for i in range(alive + dead)}
    for i in range(alive - 1):
        links[i].append(i + 1)
    for j in range(alive, alive + dead):
        links[j].append(alive + (j - alive + 1) % dead)
    return links, [0]


print("alive  dead  total  marking  sweeping  collected")
for alive, dead in ((8, 32), (8, 152), (8, 992), (32, 8), (200, 8)):
    g, k = construct(alive, dead)
    r = mark_and_sweep(g, k)
    print(f"  {alive:5d}  {dead:4d}  {len(g):5d}  {r['scan']:7d}"
          f"  {len(g):8d}  {r['collected']:9d}")

alive  dead  total  marking  sweeping  collected
      8    32     40        8        40         32
      8   152    160        8       160        152
      8   992   1000        8      1000        992
     32     8     40       32        40          8
    200     8    208      200       208          8

In the first three rows, the surviving count is fixed at 8 and the dead count climbs from 32 to 992; the marking step stays at 8. In the last two rows, the dead count is fixed at 8 and the surviving count climbs from 32 to 200; the marking step climbs from 32 to 200. That is the lesson’s sentence: the length of the pause is proportional not to the garbage collected, but to the objects that survive.

The practical consequence is direct. A program that produces many short-lived objects does not cost the collector much; those objects are never visited at all. What is expensive is a large, long-lived object structure — it gets rescanned from end to end on every collection and is never collected.

Sweeping’s Share

If marking is proportional to survivors, sweeping is proportional to the total: reclaiming unmarked objects’ space requires walking the entire list once. In the table, the sweeping column is 40 in every row, because the object count never changes.

Total work is the sum of the two, and the last column reduces it to a per-collected-object figure. At a root count of 1, 1.16 steps are spent per collected object; at a root count of 12, 4.33 steps. The gap is 3.7-fold, and all of it comes from the rise in the surviving object count. The collector’s efficiency depends on how much garbage sits in the heap — the more garbage, the cheaper the collection.

Sweeping’s share in this model is also worth noting: in the three-root run, 40 of the total work is sweeping, 17 is marking. So the larger part of the pause comes not from scanning but from walking the list. A collector that copies objects next to the survivors while reclaiming space removes this pass entirely, paying only the 17 steps; in exchange it must move every surviving object and update every reference that points to it. This trade-off is the same one as compaction in the previous lesson.

Sweeping also has an end that stays out of view. The bytes of the 23 reclaimed objects go back to the heap, that is, they are handed over to the previous lesson’s allocator; from there the rules of external fragmentation take over. The collector decides which object dies; the order of death decides where and at what size the next gap opens. So garbage collection does not replace an allocator, it is built on one, and it inherits the remainder problem measured in the previous lesson. This is also why a copying collector is willing to pay for moving: by laying the objects it moves end to end, it reduces allocation back down to sliding a single boundary.

Splitting the Pause

A pause that takes 17 steps in one piece can be shrunk by splitting marking into chunks and giving the program turns in between. It is not free: because the program runs between two chunks, the object graph can change, so the changed region has to be rescanned.

• BD17 — After every interruption, 2 objects need rescanning. This number is the model’s parameter; in a real implementation it would depend on how many references the program changes during the interruption.

"""Incremental collection: the cost of splitting the pause. Survivors 17 , total 40."""
ALIVE = 17          # reachable object count measured by block 01
TOTAL = 40
RESCAN = 2          # objects needing rescan after each interruption

print("chunks  pause count  longest pause  marking work  total work")
for chunks in (17, 8, 4, 2, 1):
    count = -(-ALIVE // chunks)
    marking = ALIVE + (count - 1) * RESCAN
    print(f"{chunks:6d}  {count:12d}  {min(chunks, ALIVE):13d}"
          f"  {marking:13d}  {marking + TOTAL:11d}")

chunks  pause count  longest pause  marking work  total work
    17             1             17             17           57
     8             3              8             21           61
     4             5              4             25           65
     2             9              2             33           73
     1            17              1             49           89

The longest pause drops from 17 steps to 1, total work climbs from 57 steps to 89. What is gained is not total cost but the distribution of cost: instead of stopping for 17 steps at once, the program stops 17 times for one step each, advancing in between. A metric that looks at response time calls this an improvement; a metric that looks at total work calls it a 1.56 times worsening. Both are correct, and which one matters depends on the metric — this is where the course’s second claim gets paid in this lesson.

How Often to Collect

When the collector runs is also a decision, and it pits two costs against each other. Collecting early keeps the heap small but runs the collector often; collecting late runs the collector rarely but raises the heap’s peak.

• BD18 — The program produces 200 objects, and each object becomes unreachable 30 steps after it is produced. Lifetime is fixed; a real program would have a distribution.

"""Collection frequency: the trade-off between memory peak and collector work."""
OBJECTS = 200         # how many objects are produced
LIFETIME = 30         # steps after which an object becomes unreachable

print("every N allocations  collections  marking work  sweeping work  peak resident")
for n in (10, 25, 50, 100, 200):
    resident, peak, collections, marking, sweeping = [], 0, 0, 0, 0
    for t in range(OBJECTS):
        resident.append(t)
        peak = max(peak, len(resident))
        if (t + 1) % n == 0:
            alive = [i for i in resident if t < i + LIFETIME]
            collections += 1
            marking += len(alive)
            sweeping += len(resident)
            resident = alive
    print(f"{n:20d}  {collections:11d}  {marking:13d}  {sweeping:14d}  {peak:13d}")

every N allocations  collections  marking work  sweeping work  peak resident
                  10           20            570             740             40
                  25            8            235             405             55
                  50            4            120             290             80
                 100            2             60             230            130
                 200            1             30             200            200

A setup that collects every ten allocations keeps the heap at 40 objects at most and costs the collector 1310 steps. A setup that collects only at the end pays 230 steps but the heap grows to 200 objects. A five-times-lower memory peak is bought in exchange for 5.7 times more collector work. Every point between these two extremes is a valid choice, and what decides the choice is whether memory or the processor is scarce on the machine.

What Is Reachable Is Not Collected

The criterion is not “is it needed” but “can it be reached,” and this distinction names the problem the collector does not solve. When the root count climbs from 3 to 12, the collected object count drops from 23 to 15; nothing changed in the graph, only the region reachable from the roots grew. In a program, this corresponds to holding an object that is no longer used in a list or a map: the object is unnecessary, it is reachable, and it is not collected.

That is why garbage collection does not eliminate memory leaks, it changes the leak’s form. Under manual release, a leak is a forgotten release call; under tracing collection, a leak is a reference that is never cut from the roots. In both cases the leak is a program defect, and its diagnosis is sought in the program.

Summary

• The tracing collector reaches 17 of 40 objects from three roots and collects 23; the pause is 17 scan steps, sweeping is 40 steps, total work is 57 steps.
• With the surviving object count fixed, raising the dead object count from 32 to 992 leaves the marking step at 8; with the dead count fixed, raising the surviving count from 32 to 200 raises the step from 32 to 200.
• The pause is proportional to surviving objects, not to garbage collected; the cost per collected object climbs from 1.16 to 4.33 steps while the only thing that changes is the surviving object count.
• The sweep pass is proportional to the total object count and is the larger share of total work in this model; a copying collector removes this pass, paying for moving and reference updates in exchange.
• Splitting marking into chunks drops the longest pause from 17 steps to 1 but raises total work from 57 to 89 steps; raising collection frequency drops the memory peak from 200 to 40 objects while raising collector work from 230 steps to 1310.
• The criterion is reachability, not necessity; an unneeded object that has not been cut off from a root is never collected, which is why a collector does not remove leaks.

Next Step

These three lessons measured three separate questions about memory, and in all three the data vanished once the run ended. Most of the data a process produces, though, has to outlive the run, and that requires a second abstraction — one where bytes are named, placed in directories, and split into fixed-size blocks. The next lesson models the file system: the 4741 bytes of six files are placed into 512-byte blocks, the bytes going to waste are counted, and sweeping the block size measures the trade-off between internal fragmentation and the block list the inode has to carry.