Understand CPython's Reference Counting

Topic Overview

Reference Counting in CPython

CPython reclaims most objects immediately when their refcount hits zero. Every \`PyObject\` header stores \`ob_refcnt\`; \`Py_INCREF\` and \`Py_DECREF\` adjust it under the GIL.

Cycles and PyGC

Simple refcounting cannot free reference cycles. CPython adds a generational cycle detector for container objects that opt into tracking.

Rules for extension authors:

• Borrowed references: caller still owns the object
• New references: you must \`Py_DECREF\` when done
• Stealing references: callee takes ownership

For example, \`x = [1, 2]; y = [x]; x.append(y)\` creates a cycle only the cyclic GC can break; refcount alone leaves both lists alive forever.

\`\`\`c Py_INCREF(obj); /* use obj */ Py_DECREF(obj); \`\`\`

Design Notes

Container cycles need the cyclic GC even when refcounting handles acyclic graphs. Tune `gc.set_threshold` only after you understand which objects participate in `gc.get_objects` tracking.

For This Exercise

This exercise asks you to explain refcount semantics and cyclic GC's role. You will document when objects free immediately versus when the cycle collector must run.

You will use the same mental model here when reading production interpreter source later in the track. Sketch one concrete input on paper, predict the outcome, then confirm with code. That discipline catches logic errors early and makes debugging far faster when you extend the implementation in follow-on tasks.

Your Task

Model CPython's memory management for lists and strings: reference counting, plus the cycle collector that cleans up what refcounting can't. Every statement is traced as the Py_INCREF/Py_DECREF calls it performs. When a count reaches zero, the object is deallocated immediately, and deallocating a list releases its items. Cycles survive until gc.collect() finds them.

Input

One statement per line (# starts a comment):

cCopy
Loading…

Rules

• Creation: [] and 'text' create a new object with refcnt 1. Ids count up from 1 across all objects.
• Assignment x = y: incref y's object. Rebinding a name stores the new reference first, then decrefs the old one.
• append: increfs the item. pop: removes the last item and decrefs it, since the result is discarded. del decrefs the name's object and unbinds the name.
• Deallocation: at refcnt 0, the object is freed. A list first releases its items from last to first, as list_dealloc does. clear() releases items in the same order.
• sys.getrefcount(x) prints refcnt + 1, because the argument itself holds a reference.
• gc.collect() runs the CPython algorithm over the live lists (strings are not GC-tracked):
  1. gc_refs = refcnt for each list.
  2. For each list, subtract 1 from the gc_refs of every list it contains.
  3. Lists with gc_refs > 0 are referenced from outside. They, and every list reachable from them, survive.
  4. The rest are unreachable. Print gc: N unreachable: list#a, list#b (or gc: 0 unreachable). Then, for each one in id order that is still alive: incref it, clear it, and decref it.

Output

Each refcount change is printed as it happens, indented by two spaces:

cCopy
Loading…

A freed line comes after the item releases it caused.

show prints each live object in id order: list#1 refcnt 1 [str#2, list#4] or str#2 'hi' refcnt 2, or no live objects. Then it prints names: a=list#1 s=str#2, in the order names were first bound, skipping deleted ones, or names: none.

Errors leave everything unchanged:

• NameError: name 'x' is not defined
• AttributeError: 'str' object has no attribute 'append'
• AttributeError: 'list' object has no attribute 'sort'
• IndexError: pop from empty list
• SyntaxError: invalid syntax

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Implement deallocation as a recursive decref. Freeing a list decrefs its items, which may free them in turn.
2. gc.collect must only use refcounts and container contents. It has no access to the names, just as CPython's collector doesn't know about stack frames.

Hidden tests cover a self-referencing list, a cycle kept alive by a name and then released, collection with nothing to collect, x = x, and every error.