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_item now calls incref on 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_list passes a new Python list to allocate. The copy then holds the same item addresses in its own list, and allocate raises 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.