The toy heap and the object header

The toy heap and the object header

A toy heap

Problem. How could we model names and objects in a few lines of Python, so that an alias becomes visible?

We use two dicts. The heap maps an address to an object. The namespace maps a name to an address. The later notes in this journey extend this toy.

  1. Count addresses upward from 1000.
  2. allocate stores an object in the heap and returns its address.
  3. bind stores an address under a name.
  4. make_list allocates one integer object per item, then allocates a list that holds those addresses.
  5. value_of reads an object back as a plain Python value.
  6. append_item allocates an integer and adds its address to a list.
import itertools

heap = {}
namespace = {}
addresses = itertools.count(1000)


def allocate(type_name, value):
    address = next(addresses)
    heap[address] = {
        "type": type_name,
        "value": value,
    }
    return address


def bind(name, address):
    namespace[name] = address


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)

A list object holds the addresses of its items. So a container holds references.

bind("prices", make_list(5, 8))
bind("alias", namespace["prices"])
append_item("alias", 3)

The following trace table shows the code above, one row per line.

namespace value_of(namespace["prices"]) namespace["prices"] == namespace["alias"]
{'prices': 1002} [5, 8]
{'prices': 1002, 'alias': 1002} [5, 8] True
{'prices': 1002, 'alias': 1002} [5, 8, 3] True

The second bind stored an existing address, so the heap gained no object. Both names reach the new item.

NOTE: The toy explains the model. CPython's real memory layout is more complex.

Recall. Start a fresh toy heap. After bind("first", make_list(5, 8)) and bind("second", make_list(5, 8)), are namespace["first"] and namespace["second"] equal, and are value_of(namespace["first"]) and value_of(namespace["second"]) equal?

The object header

Problem. id() and is work on lists, strings, functions and None alike. How could one operator treat such different objects in the same way?

In CPython: every object starts with the same two fields, the header. The first field is a reference count, ob_refcnt. The second is a pointer to the object's type, ob_type. The next note covers the count. The function type(x) reads the pointer.

On a standard 64-bit CPython 3.12 build, each field takes 8 bytes. So a bare object takes 16 bytes. Another build can print another size.

import sys

print(sys.getsizeof(object()))
print(type([5, 8]), type(type([5, 8])))
16
<class 'list'> <class 'type'>

A type is an object too, and the type of list is type. Functions and None are objects as well.

In CPython: the ctypes module can read the pointer directly. It sits 8 bytes after the object's address, because the count comes first.

import ctypes

prices = [5, 8]
pointer = ctypes.c_void_p.from_address(id(prices) + 8)
print(pointer.value == id(list))
True

NOTE: This reads raw memory. A wrong address crashes Python. Read only the address of an object you hold.

Objects live on a private heap that the interpreter manages. Python code cannot allocate on it directly. In CPython: objects of 512 bytes or fewer come from a small-object allocator named pymalloc. It takes memory in 1 MiB arenas on a 64-bit build.

The function sys.getsizeof reports the memory of one object. The objects that it refers to stay out of the total.

import sys

size = sys.getsizeof
big = [[1] * 1000]
small = [[]]
print(size(big) == size(small))
True

Both outer lists hold one pointer. The inner list's size does not count.

Recall. For rows = [[1], [2]], does sys.getsizeof(rows) change after rows[0].append(9)?

Try it. Write copy_list(address) for the toy heap. It returns the address of a new list object that holds the same item addresses. Bind a name to the copy and append to the copy. Predict what value_of(namespace["prices"]) shows before you run it. The last note of this journey builds copy_list in full.

Sources

  • The Python Language Reference, Data model, Objects, values and types: https://docs.python.org/3.12/reference/datamodel.html
  • The Python Standard Library, sys (getsizeof): https://docs.python.org/3.12/library/sys.html
  • The Python Standard Library, ctypes: https://docs.python.org/3.12/library/ctypes.html
  • Python/C API, Memory Management: https://docs.python.org/3.12/c-api/memory.html
  • CPython source, Include/object.h, 3.12 branch: https://github.com/python/cpython/blob/3.12/Include/object.h

Cards

A toy model of Python memory uses two dicts, heap and namespace. What does each map?

Reveal

heap maps an address to an object record. namespace maps a name to an address.

In a toy heap where addresses count up from 1000 and make_list allocates each integer before the list, what do namespace and len(heap) show after this line on a fresh heap?

bind("cart", make_list(9))
Reveal

{'cart': 1001} and 2. The integer 9 took address 1000. The list took address 1001.

In a toy heap, bind(name, address) stores an address under a name, and append_item(name, item) adds a new integer to the named list. What does value_of(namespace["t"]) show after these lines?

bind("t", make_list(2, 4))
bind("u", namespace["t"])
append_item("u", 6)
Reveal

[2, 4, 6]. The names t and u link to one list address, so the new item shows under both.

Which two fields start the header of every CPython object?

Reveal

ob_refcnt, the reference count, and ob_type, the pointer to the object's type.

On a standard 64-bit CPython 3.12 build, how many bytes does sys.getsizeof(object()) report, and why?

Reveal

16 bytes. The header holds two 8-byte fields, the reference count and the type pointer. Another build can report another size.

On a standard 64-bit CPython build, how many bytes after id(x) does the ob_type pointer sit?

Reveal

8 bytes. The reference count comes first and takes 8 bytes.

What is type(type([]))?

Reveal

<class 'type'>. A type is an object too, and the type of list is type.

Does sys.getsizeof([[1] * 50]) == sys.getsizeof([[]]) give True or False, and why?

Reveal

True. The function getsizeof reports one object and leaves out the objects it refers to. Both outer lists hold one pointer.

Which allocator serves objects of 512 bytes or fewer in CPython, and how large is one of its arenas on a 64-bit build?

Reveal

The small-object allocator pymalloc. An arena is 1 MiB on a 64-bit build.