Memory Usage

The previous lesson opened a run’s call breakdown and found the hot path by call count. There was one thing the breakdown did not say: advance was called 80 times under both loads, but how many objects did the structure that those 80 calls worked on hold in memory?

The question is not idle. Eight tasks’ ten steps can be held as a list of lists, as a class that makes every step an object, or as a single byte string. All three carry the same 80 steps and make the scheduler give the same answer. The number of objects they hold, though, is not the same — and this lesson measures that number.

Why Objects, Not Bytes

Asking how much space a structure takes in memory, in bytes, seems natural, but that number is not this course’s measure. The reason is in the measure itself: an object’s byte equivalent depends on how the interpreter lays the object out, and it changes from environment to environment. A changing number cannot compare two shapes.

Object count, by contrast, comes from the structure itself. How many items a list has, how many items point to the same object, whether an instance also carries a dictionary — all of this can be counted by walking the structure, and it comes out the same on every run.

The count has to have a limit. Starting from one object and walking everything reachable from it reaches its type, the module the type is defined in, and from there the whole program; a number like that measures the environment, not the structure. So the walk tracks containers — list, tuple, dict, instance dictionary, and slot — and stops at type objects, functions, and modules. What is counted is the structure the data holds, not the whole program that uses that data.

The number has meaning too. Every object has its own identity, its own type, and its own lifetime; carrying these brings a fixed overhead per object, and this overhead is not proportional to the data inside the object. Spreading a ten-step list across eighty separate objects means paying the overhead eighty times without growing the data. This is why the memory claim is built on object count.

Creating Versus Holding

The Data Structures and Functional Tools course counted the created object: with a class that counts its own instantiation, it measured how many objects a shape produces over the course of a run, and showed that the lazy shape does not reduce production, only holding. This measurement is not repeated here, it is used by reference.

The question here is the other half. Once the run has ended, how many objects are standing at the same time inside the structure that is kept? Creating is a flow measure, holding is a state measure. Two shapes can create the same number of objects and hold wildly different numbers; two shapes can hold the same number of objects and have created wildly different numbers.

Six Shapes

The measured structures are derived from the same eight tasks the shared definition produces, and all of them carry the same 80 steps.

List, shared string is the shared definition’s own shape: steps point to two immutable strings, and all 80 slots bind to one of those two objects. List, separate string is the same structure, the only difference being that each step’s string is rebuilt at run time — the values are equal, the objects are separate. Dict, shared string turns the outer list into a dict keyed by task number.

Object, dict-backed wraps every step in a class instance; the instance holds its attributes in a dictionary. Object, slotted builds the same class with a __slots__ declaration; because attribute names are fixed in advance, the instance does not carry a dictionary too. Single bytes object gathers the 80 steps into one immutable bytes object; task boundaries are recovered with arithmetic.

The measurement’s assumptions:

• PE7 — All six shapes are derived from the shared definition’s tasks output and carry the same 80 steps; none of them changes the data.
• PE8 — The count walks the structure and counts distinct objects: a shared object gets counted once no matter how many places point to it. The distinction is made by identity, but no identity number is printed.
• PE9 — The walk tracks lists, tuples, dicts, instance dictionaries, and slots. Type objects, functions, and modules are not counted; what is counted is the structure itself, not the whole run.
• PE10 — What is measured is the object held. Intermediate objects created while the structure is being built do not enter the count; those belong to the Data Structures course’s measure.
• PE11 — The measured byte count is not written. A structure’s byte equivalent depends on the environment; object count does not, and it is object count that compares the two shapes.
• PE12 — Each shape is resolved to the common form before it is handed to the scheduler, and the table shows whether the resolved list is the same as the shared definition’s; if it is not, the comparison is invalid.

Measurement

"""Memory: same 80 steps in six shapes; bytes are not counted, objects held are."""

SEED = 20260817
CPU, IO = "cpu", "io"


def make_rng(seed):
    state = seed % 2147483646 + 1

    def draw(n):
        nonlocal state
        state = (state * 48271) % 2147483647
        return state % n
    return draw


def tasks(count=8, steps=10, io_share=7, seed=SEED):
    draw, result = make_rng(seed), []
    for i in range(count):
        result.append([IO if draw(10) < io_share else CPU for _ in range(steps)])
    return result


def run(jobs, workers, cpu_slots):
    remaining = [list(j) for j in jobs]
    tick = overlap = cpu_steps = io_steps = 0
    while any(remaining):
        active = [i for i, j in enumerate(remaining) if j][:workers]
        if not active:
            break
        slots_left, advanced = cpu_slots, 0
        for i in active:
            step = remaining[i][0]
            if step == CPU:
                if slots_left <= 0:
                    continue
                slots_left -= 1
                cpu_steps += 1
            else:
                io_steps += 1
            remaining[i].pop(0)
            advanced += 1
        tick += 1
        overlap += max(0, advanced - 1)
    return tick, overlap, cpu_steps, io_steps


def children(n):
    if isinstance(n, (list, tuple)):
        return list(n)
    if isinstance(n, dict):
        return list(n.keys()) + list(n.values())
    if hasattr(n, "__dict__"):
        return [n.__dict__]
    if hasattr(type(n), "__slots__"):
        return [getattr(n, a) for a in type(n).__slots__]
    return []


def count_objects(root):
    """Walks the structure; a shared object is counted once. No identity is printed."""
    seen, held, stack, kinds = set(), [], [root], {}
    while stack:
        n = stack.pop()
        if id(n) in seen:
            continue
        seen.add(id(n))
        held.append(n)
        name = type(n).__name__
        kinds[name] = kinds.get(name, 0) + 1
        stack.extend(children(n))
    return len(seen), kinds


def separate_string(s):
    return "".join([s[:2], s[2:]])


class Step:
    def __init__(self, kind):
        self.kind = kind


class SlimStep:
    __slots__ = ("kind",)

    def __init__(self, kind):
        self.kind = kind


G = tasks()
SHAPES = {
    "list, shared string": ([list(g) for g in G], lambda y: [list(g) for g in y]),
    "list, separate string": ([[separate_string(a) for a in g] for g in G],
                               lambda y: [list(g) for g in y]),
    "dict, shared string": ({i: list(g) for i, g in enumerate(G)},
                             lambda y: [y[i] for i in sorted(y)]),
    "object, dict-backed": ([[Step(a) for a in g] for g in G],
                             lambda y: [[a.kind for a in g] for g in y]),
    "object, slotted": ([[SlimStep(a) for a in g] for g in G],
                         lambda y: [[a.kind for a in g] for g in y]),
    "single bytes object": (bytes(1 if a == CPU else 0 for g in G for a in g),
                             lambda y: [[CPU if b else IO for b in y[i * 10:i * 10 + 10]]
                                        for i in range(8)]),
}

print(f"{'shape':<26s} {'objects':>7s} {'resolved list same':>19s} {'tick / overlap':>14s}")
for name, (structure, resolve) in SHAPES.items():
    count, _ = count_objects(structure)
    d = resolve(structure)
    tick, overlap, _, _ = run(d, 8, 1)
    print(f"{name:<26s} {count:7d} {str(d == G):>19s} {f'{tick} / {overlap}':>14s}")

print()
for name in ("list, shared string", "object, dict-backed", "object, slotted"):
    print(f"{name:<26s} {count_objects(SHAPES[name][0])[1]}")

print()
p = SHAPES["list, shared string"][0]
a = SHAPES["list, separate string"][0]
print(f"in shared shape, first step same object as the setup's -> {p[0][0] is G[0][0]}")
print(f"in separate shape, same -> {a[0][0] is G[0][0]}, equal -> {a[0][0] == G[0][0]}")
b = SHAPES["single bytes object"][0]
print(f"two slices taken from the bytes object are the same object -> {b[0:10] is b[0:10]}, "
      f"equal -> {b[0:10] == b[0:10]}")
print(f"total steps {sum(len(g) for g in G)}, fewest-object shape "
      f"{min(count_objects(y)[0] for y, _ in SHAPES.values())}, most "
      f"{max(count_objects(y)[0] for y, _ in SHAPES.values())}")

shape                      objects  resolved list same tick / overlap
list, shared string             11                True        31 / 49
list, separate string           89                True        31 / 49
dict, shared string             19                True        31 / 49
object, dict-backed            172                True        31 / 49
object, slotted                 91                True        31 / 49
single bytes object              1                True        31 / 49

list, shared string        {'list': 9, 'str': 2}
object, dict-backed        {'list': 9, 'Step': 80, 'dict': 80, 'str': 3}
object, slotted            {'list': 9, 'SlimStep': 80, 'str': 2}

in shared shape, first step same object as the setup's -> True
in separate shape, same -> False, equal -> True
two slices taken from the bytes object are the same object -> False, equal -> True
total steps 80, fewest-object shape 1, most 172

The Result Did Not Change

The table’s right two columns are the measurement’s validity condition. All six shapes, when resolved, come out identical to the shared definition’s list, and all six make the scheduler give the same answer: 31 ticks / 49 overlapping steps.

This defines what the difference in the left column is. Object count ranges from 1 to 172 while the outcome of the work never changes. What is measured is the price of holding the same result, not the result itself. Without this distinction, the table would not be a comparison, it would be six separate measurements.

The column’s presence in the table is not a formality. The most common mistake in memory measurements is silently changing the data while changing the shape — dropping a field, shortening a string, building a task incompletely. In such a measurement, object count does genuinely drop, but the drop’s cause is not the shape, it is the missing data. The resolved list same column tests this on every row; a row that was not True would be removed from the table.

What Sharing Costs

The first two rows are separated by a single difference. The structure is the same — one outer list, eight inner lists, eighty slots. The values are the same too; the equal -> True in the block below says so. The only thing that differs is the objects: in the shared shape, 80 slots point to two string objects; in the separate shape, to eighty.

The count rises from 11 to 89: 78 objects extra, for zero information in return. The identity test in the block below shows why — in the first shape, the step is the very object the setup produced; in the second, an equal but separate object.

This is the most common memory pattern found in real programs. Fields read from a file or a message are equal to each other even if they are separate objects; each one gets rebuilt during reading. Rebuilding sharing in a column where the same value repeats — producing a small set of immutable values once and pointing to them everywhere — drops object count directly.

Who Pays the Per-Object Overhead

The fourth and fifth rows are two constructions of the same class. Each step is an instance; the only difference is where the attributes are held.

The dict-backed construction holds 172 objects, the slotted construction 91. Where the 81 in between comes from is shown by the type breakdown: in the dict-backed shape, the dict count is 80 — one dictionary per instance — and an extra string for the attribute name is also counted, which is why str is 3 instead of 2. In the slotted shape, there is no dict row at all.

When attribute names are declared in advance, the instance does not need to carry a dictionary too. The gain grows multiplied by the instance count: here eighty instances are freed from eighty dictionaries. The price is flexibility — an undeclared attribute cannot be added later.

The third row shows another face of the same overhead. Turning the outer container from a list to a dict raises object count from 11 to 19. The eight extra objects are the eight keys themselves: a list position is not an object, a dict key is. Access is the same, the result is the same, eight objects extra.

The Price of a Single Object

The last row holds 80 steps in a single object. This is the lowest number in the table, and the reason is clear: the 80 values inside the bytes object are not separate objects, they are the contents of a single object. Structure boundaries — which ten steps belong to which task — are recovered with arithmetic.

The price sits in the last identity test in the block below: taking the same slice twice produces two separate objects. Reading a piece out of an immutable bytes object means building a new object on every read. So a structure that stands as one object produces objects as it is read; the number held drops while the number created rises.

The two measures being separate is useful here. The question to ask when choosing a shape is not one: how much is held, and what does accessing what is held produce each time? The bytes object is the best choice for the first, the worst for the second; the shared-string list is above the middle on both and holds 80 steps directly accessible with 11 objects.

The six rows give not a ranking but an axis. At one end, all of the structure’s information sits in objects and access is free; at the other end, structure information has moved into code, the object count has dropped to one, and the price of access is spread across every read. The measurement does not say which end is right — it says what each end costs. What decides is how many times the same structure will be looked at.

Summary

• This course measures memory load not by measured bytes but by object count held; byte equivalents depend on the environment, object count comes from the structure itself and comes out the same on every run.
• The same 80 steps can be held in six shapes ranging from 1 to 172 objects, and all six make the scheduler give the same 31 ticks / 49 overlapping steps.
• Losing sharing, without changing the structure, raises 11 objects to 89: eighty equal but separate strings, for zero information, are 78 extra objects.
• Holding a dictionary per instance means 172, declaring attribute names in advance means 91 objects; the 81 in between are eighty instance dictionaries and one attribute name.
• Turning the outer container from a list to a dict adds eight key objects; a list position is not an object, a dict key is.
• A structure held in a single object drops what is held to 1 but produces a new object on every read; the holding measure and the producing measure can pull in different directions.

Next Step

Two numbers have been measured so far: how many times a function is called, and how many objects a structure holds. Both point the same direction — the hot path is where the is_cpu_step call runs 322 times. Can that path be brought down further? Moving a hot path out of the language, to a lower level, is a commonly used route, and its gain is usually told in terms of time. The next lesson measures this not in time but as steps in a model: when the hot path’s step count drops, what happens to the total tick count, and how much does crossing the boundary itself take back?