Reference counts
Reference counts
Counting references
Problem. The shop closes a cart, and no name refers to its price list any more. How could CPython know that it can reuse the memory of that list?
New words
- reference count: the number of references to an object
- deallocate: return an object's memory for reuse
CPython stores a reference count in the ob_refcnt field of every object. The interpreter raises the count with Py_INCREF and lowers it with Py_DECREF. When the count reaches 0, CPython deallocates the object at once.
These count as references:
- a name bound to the object
- an item in a list, tuple, dict or set
- an argument in an active function call
- a temporary hold while Python uses the object
In CPython: the function sys.getrefcount reads the count. It reads one higher than the number of names, because its own argument is a temporary reference. The output below comes from CPython 3.12 at the top level of a script. Other versions, and code inside a function, can print other numbers.
import sys
prices = []
print(sys.getrefcount(prices))
backup = prices
print(sys.getrefcount(prices))
del backup
print(sys.getrefcount(prices))
2
3
2
The statement del x removes the name x. It lowers the object's count by one. It never frees the object directly.
The method __del__ runs when an object's count reaches 0. To see when, give a class a __del__ that prints.
class Probe:
def __del__(self):
print("freed")
first = Probe()
second = first
del first
print("after del first")
del second
print("after del second")
after del first
freed
after del second
So del first removed one name, and the object stayed. del second removed the last reference, and freed printed before the next line.
NOTE: CPython frees most objects the moment the last reference goes. The language does not promise it. Close files explicitly, and never rely on immediate cleanup.
A dead object returns its memory to the allocator, and a new object may reuse the spot. In CPython, the code below usually prints True. Nothing promises it.
old = []
old_id = id(old)
del old
new = []
print(old_id == id(new))
True
So two objects with separate lifetimes can share an id(). Never keep an old id as a permanent label.
Recall. For d = {} and items = [d, d], what does sys.getrefcount(d) print? List every reference.
Counting in the toy heap
Problem. How could the toy heap from the previous note free an object when its last reference goes?
- Add a
"refcount"field to each record. It starts at 0. - Raise an item's count when a list takes it.
- Raise the count when
bindlinks a name. Lower the old object's count whenbindreplaces a link, after the raise. decreflowers a count. When the count reaches 0,decrefcallsfree.freeremoves the object from the heap and lowers the count of each item it held.
Step 3 raises the new count before it lowers the old one. If a name is rebound to the object it already links to, this order stops decref from freeing that object too early.
import itertools
heap = {}
namespace = {}
addresses = itertools.count(1000)
def allocate(type_name, value):
address = next(addresses)
heap[address] = {
"type": type_name,
"value": value,
"refcount": 0,
}
if type_name == "list":
for item in value:
incref(item)
return address
def incref(address):
heap[address]["refcount"] += 1
def decref(address):
record = heap[address]
record["refcount"] -= 1
if record["refcount"] == 0:
free(address)
def free(address):
record = heap.pop(address)
print("freed", address)
if record["type"] == "list":
for item in record["value"]:
decref(item)
def bind(name, address):
incref(address)
if name in namespace:
decref(namespace[name])
namespace[name] = address
def unbind(name):
decref(namespace.pop(name))
def make_list(*items):
stored = []
for item in items:
stored.append(allocate("int", item))
return allocate("list", stored)
The function unbind plays the role of the del statement. It removes a name from the namespace. The function free plays the role of deallocation. It removes an object from the heap.
A list holds a reference to each item, so freeing one list can free many objects.
bind("a", make_list(1, 2))
bind("b", namespace["a"])
unbind("a")
unbind("b")
freed 1002
freed 1000
freed 1001
The following trace table shows the code above, one row per line. The list sits at address 1002.
namespace |
heap[1002]["refcount"] |
len(heap) |
output |
|---|---|---|---|
| {'a': 1002} | 1 | 3 | |
| {'a': 1002, 'b': 1002} | 2 | 3 | |
| {'b': 1002} | 1 | 3 | |
| {} | 0 | freed 1002, freed 1000, freed 1001 |
The list is freed first. Then free lowers the count of its two integers, and each reaches 0.
Recall. After bind("c", make_list(7)) and then bind("c", make_list(8)), which addresses does the toy print as freed, and why?
Sources
- The Python Language Reference, Data model, Basic customization (
__del__): https://docs.python.org/3.12/reference/datamodel.html - The Python Language Reference, The del statement: https://docs.python.org/3.12/reference/simple_stmts.html
- The Python Standard Library, sys (getrefcount): https://docs.python.org/3.12/library/sys.html
- Python glossary (reference count): https://docs.python.org/3.12/glossary.html
- CPython source,
Include/object.h, 3.12 branch: https://github.com/python/cpython/blob/3.12/Include/object.h
Cards
What does CPython do when an object's reference count reaches 0?
Reveal
It deallocates the object at once and returns its memory for reuse.
In CPython 3.12, what does this script print, and why?
import sys
s = []
t = s
u = [s]
print(sys.getrefcount(s))
Reveal
4. The references are the name s, the name t, the slot in the list u, and the temporary argument of getrefcount. Other versions can print another number.
Name four kinds of reference that raise an object's count in CPython.
Reveal
A name bound to the object, an item in a list, tuple, dict or set, an argument in an active function call, and a temporary hold while Python uses the object.
What does the statement del x do to the object that x links to?
Reveal
It removes the name x and lowers the object's count by one. It never frees the object directly.
Does freed print right after del keep here?
class Probe:
def __del__(self):
print("freed")
keep = Probe()
alias = keep
del keep
Reveal
No. The name alias still holds a reference, so the count stays above 0. freed prints after del alias.
Does the Python language promise that an object is freed the moment its last reference goes?
Reveal
No. CPython does it for most objects, but the language gives no promise. Close files explicitly.
Can two Python objects with separate lifetimes share one id()?
Reveal
Yes. A dead object returns its memory, and a new object may reuse the same spot. Never keep an old id as a permanent label.
In a toy heap with reference counts, what does bind(name, address) do when the name already has a link, and in what order?
Reveal
It calls incref on the new address first. Then it calls decref on the old address and stores the new address under the name. Raising first keeps a self-rebind from freeing the object.
In a toy heap with reference counts, addresses count up from 1000, and make_list allocates each integer before the list. On a fresh heap, what are the list's count and len(heap) after these lines?
bind("m", make_list(1, 2, 3))
bind("n", namespace["m"])
unbind("m")
Reveal
The list's count is 1, and len(heap) is 4. The name n still holds the list, so nothing is freed. The heap has three integers and one list.