Build a toy heap with reference counts
Build a toy heap with reference counts
This note puts the toy heap together in one program. It joins the two-dict model from the object header note with the counts from the reference counts note. It also adds copy_list. The finished toy creates objects, links names to them, counts references, and frees each object when its last reference goes.
The parts
| Part | Job |
|---|---|
heap |
maps an address to an object record |
namespace |
maps a name to an address |
addresses |
hands out new addresses, counting up from 1000 |
allocate |
stores a record with a count of 0 and raises each item's count |
incref |
raises a count by 1 |
decref |
lowers a count by 1 and calls free at 0 |
free |
removes a record and lowers the count of each item it held |
bind |
links a name to an address, raising the new count first |
unbind |
removes a name and lowers its object's count |
make_list |
allocates one integer per item, then a list of their addresses |
value_of |
reads an object back as a plain Python value |
append_item |
allocates an integer, adds it to a list, and raises its count |
copy_list |
allocates a new list that holds the same item addresses |
The full code
Save this code as toy_heap.py, or paste it into a Python prompt. Every example below runs after it, in order, in one session.
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)
def value_of(address):
record = heap[address]
if record["type"] != "list":
return record["value"]
stored = record["value"]
return [value_of(item) for item in stored]
def append_item(name, item):
record = heap[namespace[name]]
new_address = allocate("int", item)
record["value"].append(new_address)
incref(new_address)
def copy_list(address):
stored = list(heap[address]["value"])
return allocate("list", stored)
Two functions changed from the earlier notes.
append_itemnow callsincrefon the new integer. The list holds a reference to it, so its count must be 1. With a count of 0, freeing the list would lower it to -1, and the integer would never be freed.copy_listpasses a new Python list toallocate. The copy then holds the same item addresses in its own list, andallocateraises the count of each item.
Aliases and counts
Bind a list, add an alias, and append through the alias.
bind("prices", make_list(5, 8))
bind("alias", namespace["prices"])
append_item("alias", 3)
print(namespace)
print(value_of(namespace["prices"]))
print(heap[1002]["refcount"])
{'prices': 1002, 'alias': 1002}
[5, 8, 3]
2
The integers 5 and 8 took addresses 1000 and 1001. The list took 1002. Two names link to the list, so its count is 2. The new integer 3 took address 1003.
A shallow copy
Copy the list, then append to the copy.
bind("copy", copy_list(namespace["prices"]))
append_item("copy", 4)
print(value_of(namespace["prices"]))
print(value_of(namespace["copy"]))
print(heap[1000]["refcount"], heap[1003]["refcount"])
[5, 8, 3]
[5, 8, 3, 4]
2 2
The copy is a new list at address 1004, so the append left the original alone. The new integer 4 took address 1005. The copy shares its first three items with the original. So the integer at 1000 now has a count of 2, one from each list. The integer at 1003 also has a count of 2.
Freeing
Remove the names one at a time.
unbind("prices")
unbind("alias")
print("names left:", list(namespace))
unbind("copy")
print(len(heap))
freed 1002
names left: ['copy']
freed 1004
freed 1000
freed 1001
freed 1003
freed 1005
0
The original list went first, when its second name went. Its items stayed, because the copy still held them. When copy went, the copy list was freed, and each of its four items reached 0.
Rebinding a name
Bind a name, then bind the same name to a new list.
bind("c", make_list(7))
bind("c", make_list(8))
print(namespace)
freed 1007
freed 1006
{'c': 1009}
The second bind lowered the count of the old list at 1007 to 0. Freeing that list lowered the count of the integer 7 at 1006 to 0 as well.
Now bind the name to the object it already links to.
bind("c", namespace["c"])
print(value_of(namespace["c"]), heap[namespace["c"]]["refcount"])
unbind("c")
print(len(heap))
[8] 1
freed 1009
freed 1008
0
The list survived the self-rebind. bind raised its count to 2 before it lowered the count back to 1. With the opposite order, the count would reach 0 first, and free would remove a list that a name still needs.
Where counting stops
Build two lists that hold each other, then remove both names.
first = allocate("list", [])
second = allocate("list", [first])
heap[first]["value"].append(second)
incref(second)
bind("x", first)
bind("y", second)
unbind("x")
unbind("y")
print(len(heap), heap[first]["refcount"], heap[second]["refcount"])
2 1 1
No name reaches either list, and no freed line appears. Each list holds the other, so each count stays at 1. Reference counting alone leaks a cycle. The note on cycles and the garbage collector shows how a collector frees these lists.
Try it. Add set_item(name, index, item). It allocates an integer and puts its address at index in the named list. Raise the new integer's count before you lower the old item's count. Predict which addresses print as freed before you run it.
Cards
In a toy heap with reference counts, why must append_item call incref on the integer it adds to a list?
Reveal
The list now holds a reference to it, so its count must be 1. With a count of 0, freeing the list would lower it to -1, and the integer would never be freed.
In a toy heap with reference counts, what does copy_list(address) return, and how does it change the item counts?
Reveal
The address of a new list that holds the same item addresses. allocate raises each item's count by 1, so every shared item gains one reference.
In a toy heap, a name copy links to a copy_list copy of the list under prices. After append_item("copy", 4), does value_of(namespace["prices"]) change?
Reveal
No. The copy is a separate list record, so the new item goes into the copy only. The two lists still share their older items.
In a toy heap with reference counts, two names link to one list, and a copy of that list shares its items. What is freed when both names are unbound?
Reveal
Only the original list. Its items stay, because the copy still holds a reference to each of them.
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, which addresses print as freed, in order?
bind("c", make_list(7))
bind("c", make_list(8))
Reveal
freed 1001, then freed 1000. The second bind lowers the old list at 1001 to 0. Freeing that list lowers the integer 7 at 1000 to 0.
In a toy heap with reference counts, what would go wrong if bind called decref on the old address before incref on the new one?
Reveal
A rebind to the same object, such as bind("c", namespace["c"]), would drop the count to 0 first. free would remove a list that the name still needs.
In a toy heap with reference counts, two lists hold each other, and both names are unbound. What are the counts, and is anything freed?
Reveal
Each count stays at 1, and nothing is freed. Reference counting alone leaks a cycle. A cycle collector is needed to free them.