Latticework — Master the skills engineers actually use

Explanation

Reference counting is one of the simplest real garbage collection strategies: every object tracks how many live references point to it. Creating a new reference increments the count; dropping one decrements it; the moment the count hits zero, nothing in the program can reach that object anymore, so it's safe to free immediately.

def simulate_refcounts(operations):
    refcounts = {}
    freed = []
    for kind, obj_id in operations:
        if kind == "alloc":
            refcounts[obj_id] = 1
        elif kind == "ref":
            refcounts[obj_id] += 1
        elif kind == "unref":
            refcounts[obj_id] -= 1
            if refcounts[obj_id] == 0:
                freed.append(obj_id)
                del refcounts[obj_id]
    return freed

Try it

This is EXACTLY why CPython (which uses reference counting as its primary GC) also needs a SEPARATE cycle-detecting collector running periodically -- pure refcounting like this simulate_refcounts function would never free two objects that reference each other, since neither one's count ever reaches zero on its own.

Loading editor…

Exercise

Write `simulate_refcounts(operations)`: `operations` is a list of `('alloc', obj_id)`, `('ref', obj_id)`, or `('unref', obj_id)`. `'alloc'` sets the object's count to 1; `'ref'` increments it; `'unref'` decrements it, and if it reaches 0, the object is freed (record its ID, in order, in the returned list; don't track it further). Return the list of freed object IDs.

Quiz

Reference counting is one real garbage collection strategy (used by CPython, among others). What's its most well-known failure case?

Checkpoint

You can simulate reference-counting garbage collection, and understand its classic blind spot: reference cycles that never reach a count of zero.

Garbage Collection