Performance: Solutions

# exercise_1.py
import random
import timeit
from benchmark import report

n = 100_000
as_list = list(range(n))
as_set = set(as_list)
random.seed(1)
targets = [random.randrange(n) for _ in range(200)]

def list_lookups() -> None:
    for t in targets:
        t in as_list

def set_lookups() -> None:
    for t in targets:
        t in as_set

t_list = timeit.timeit(list_lookups, number=20)
t_set = timeit.timeit(set_lookups, number=20)
report(list=t_list, set=t_set)
print(f"set faster on average-case targets too: "
      f"{t_set < t_list}")
#: set faster on average-case targets too: True

The conclusion does not change. target = n - 1 in the original measures the single worst case for a list scan: the element the scan reaches only after walking past every other one. Random targets cover every position instead, including targets near the front that a list finds quickly. The set’s O(1) hash lookup still beats the list’s O(n) scan by a wide margin (thousands of times faster in this run), because the scan for an average target still walks about half the list, far more work than one hash lookup. The worst case and the average case tell the same story here. They diverge when most real lookups cluster near the front of the list.

# exercise_3.py
import tracemalloc
from collections.abc import Callable
from itertools import islice

n = 1_000_000

def two_lists() -> list[int]:  # The original
    squares = [x * x for x in range(n)]
    evens = [s for s in squares if s % 2 == 0]
    return evens[:5]

def one_list() -> list[int]:
    return [x * x for x in range(n) if (x * x) % 2 == 0][:5]

def lazy() -> list[int]:  # The chapter's lazy version
    squares = (x * x for x in range(n))
    evens = (s for s in squares if s % 2 == 0)
    return list(islice(evens, 5))

def peak_of(func: Callable[[], list[int]]) -> int:
    tracemalloc.start()
    func()
    _, peak = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    return peak

result = one_list()
print(result, result == two_lists() == lazy())
#: [0, 4, 16, 36, 64] True
two, one = peak_of(two_lists), peak_of(one_list)
print("peak ratio, one list to two:", round(one / two, 1))
#: peak ratio, one list to two: 0.5
print(f"lazy peak under 1% of one list: "
      f"{peak_of(lazy) * 100 < one}")
#: lazy peak under 1% of one list: True

Skip the intermediate list. one_list() filters x * x directly instead of first building a squares list and then an evens list from it, so the million-element squares list disappears. Peak memory drops to about half of the two-list version’s. That is as close as an eager version gets.

Measure the remaining gap. The last line shows how far away the eager version still is: the lazy peak is under one percent of the one-list peak. The comprehension must build and hold the whole list of half a million even squares before [:5] discards nearly all of them. Restructuring the eager version cannot close that gap, because an eager version computes every value up front. The lazy generator pipeline stops when islice() has its five values, so it builds no large collection.

# exercise_4.py
from functools import cache

@cache
def noisy(n: int) -> int:
    print(f"computing noisy({n})")
    return n * n

print(noisy(3))
#: computing noisy(3)
#: 9
print(noisy(3))
#: 9
print(noisy(3))
#: 9

The "computing noisy(3)" message prints once, on the first call. Every later call with the same argument returns the cached result directly, without running the function body again, so the print() call (and any other side effect) does not run a second time. Skipping the body is the reason to cache only pure functions. A cache assumes that calling the function again is unnecessary, because the answer cannot have changed and the call does nothing observable besides computing that answer. An impure function breaks that assumption. The function performs any side effect, such as printing, writing a file, or incrementing a counter, on the first call with a given argument, and the cache silently skips it on every repeat.

# exercise_6.py
class Point:
    __slots__ = ("x", "y")
    def __init__(self, x: int, y: int) -> None:
        self.x = x
        self.y = y

class Point3D(Point):  # Declares no __slots__ of its own
    pass

p = Point3D(1, 2)
p.z = 3  # type: ignore
print(vars(p))
#: {'z': 3}
print(hasattr(Point(1, 2), "__dict__"))
#: False
print(Point3D.__slots__)
#: ('x', 'y')

Locate the new attribute’s storage. Point refuses p.z = 3 with an AttributeError, but Point3D accepts it, and vars(p) shows where the value went: an instance __dict__ that the base class does not have. Declaring __slots__ does not disable the instance dictionary for a whole hierarchy. It omits the __dict__ from the declaring class alone. Any subclass that does not declare its own __slots__ gets the default behavior, a __dict__, and inherits the parent’s slots alongside it.

Expose the inherited __slots__. The last line shows the trap: Point3D.__slots__ reads ('x', 'y'), inherited from Point, so reading that attribute makes the subclass look slotted while it still carries a __dict__.

Point3D quietly loses the memory saving. Every instance pays for both the two slots and a dictionary. A subclass of a slotted class must declare __slots__, using an empty tuple when it adds no fields of its own.

# exercise_7.py
import sys
from collections import Counter
from types import CodeType
from typing import Final

monitoring = sys.monitoring
TOOL: Final[int] = monitoring.PROFILER_ID
PY_START: Final[int] = monitoring.events.PY_START
NO_EVENTS: Final[int] = monitoring.events.NO_EVENTS
counts: Counter[str] = Counter()

def on_start(code: CodeType, offset: int) -> None:
    counts[code.co_name] += 1

def fib(n: int) -> int:
    return n if n < 2 else fib(n - 1) + fib(n - 2)

def square(n: int) -> int:
    return n * n

monitoring.use_tool_id(TOOL, "call counter")
monitoring.register_callback(TOOL, PY_START, on_start)
for target in (fib, square):
    monitoring.set_local_events(TOOL, target.__code__,
                                PY_START)
print(fib(10), square(4))
#: 55 16
for target in (fib, square):
    monitoring.set_local_events(TOOL, target.__code__,
                                NO_EVENTS)
monitoring.free_tool_id(TOOL)
print(counts)
#: Counter({'fib': 177, 'square': 1})

With set_events() in place of the local attachment, the new entry is 'square': 1. Nothing else appears, because PY_START fires when a Python code object starts running, and the module’s own frame starts before the tool attaches. CPython implements print() in C, so it starts no Python frame, and a program this small has no other candidates.

The two local attachments above produce the identical Counter, and that agreement is an artifact of the example’s size. In a real program set_events() reports every Python function the process runs, including library code you did not write and did not want counted, and it pays the callback cost on every one of those functions. Local attachment names the code objects you care about and leaves the rest running at full speed. Global monitoring answers “what ran.” Local monitoring answers “how often did this run,” which is the question you had when you opened sys.monitoring instead of a profiler.

Any script works. This one makes the two columns disagree on purpose:

# exercise_8.py
def inner() -> int:
    return sum(i * i for i in range(100_000))

def outer() -> int:
    return inner() + inner()

print(outer() > 0)
#: True

Run uv run python -m cProfile -s cumulative exercise_8.py. The largest cumtime belongs to exec, then <module>, then outer. The largest tottime belongs to {built-in method builtins.sum}, with the generator expression inside inner() second: the largest of the script’s own Python frames, where the arithmetic runs.

The two columns pick different functions because they measure different things. cumtime is the time from entering a function to leaving it, including everything it called, so a caller’s cumtime always covers the work beneath it. Every caller on the path accumulates the same time. tottime excludes the callees, so it attributes time to the frame that is executing.

A function high on cumtime and near zero on tottime is a pass-through: it is slow only because of what it calls, and rewriting it changes nothing. The two columns coincide only for a leaf function, one that calls nothing else, which is why the two rankings can name the same function only at the bottom of a call chain.

# exercise_9.py
import timeit
from array import array
from collections.abc import Callable
from benchmark import report

n = 200_000
as_list = [float(i) for i in range(n)]
as_array = array("d", as_list)

def best(f: Callable[[], float]) -> float:
    return min(timeit.repeat(f, number=20, repeat=5))

t_list = best(lambda: sum(as_list))
t_array = best(lambda: sum(as_array))
report(list=t_list, array=t_array)
print(f"array is slower to iterate: {t_array > t_list}")
#: array is slower to iterate: True

Not faster: on one machine the array took about 1.4 times as long as the list. The memory saving is real (the chapter measures 325,176 bytes against 80,080). The speed saving does not exist.

A list of floats stores pointers to float objects that already exist, so reading an element hands back a reference. An array stores raw eight-byte doubles instead of objects, so reading an element builds a fresh float object to hand to Python. That allocation, on every single element, eats the advantage of the tighter layout.

That cost is the chapter’s NumPy lesson arriving early: a compact layout pays off when the loop over it leaves Python. sum() over an array stays in Python and boxes every element. A NumPy sum over the same bytes creates no Python object per element, which is why vectorizing wins where array alone does not.

# ch18_join_vs_concat.py
import timeit
from benchmark import report

def build_join(parts: list[str]) -> str:
    return "".join(parts)

def build_concat(parts: list[str]) -> str:
    out = ""
    for p in parts:
        out += p
    return out

many = ["ab"] * 10_000
few = ["ab"] * 100
assert build_join(many) == build_concat(many)

j_many = timeit.timeit(lambda: build_join(many), number=200)
c_many = timeit.timeit(lambda: build_concat(many),
                       number=200)
report(join=j_many, concat=c_many)
print(f"join wins at 10,000 parts: {j_many < c_many}")
#: join wins at 10,000 parts: True

j_few = timeit.timeit(lambda: build_join(few), number=200)
c_few = timeit.timeit(lambda: build_concat(few), number=200)
print(f"join still wins at 100 parts: {j_few < c_few}")
#: join still wins at 100 parts: True
print(f"both under 50 microseconds per call at 100 parts: "
      f"{max(j_few, c_few) / 200 < 50e-6}")
#: both under 50 microseconds per call at 100 parts: True

The ratio does not go away. One machine measured join about 19 times faster at 10,000 parts and about 7 times faster at 100. What goes away is the amount at stake: at 100 short strings both versions finish in a couple of microseconds, so the loop must run thousands of times before the choice shows up in a profile.

The answer to “at which size does it stop mattering” is therefore not a size where the two versions become equally fast, but a size where both are fast enough that the difference is below anything you would measure.

Still, write join(). It is one line instead of three, it says what the result is rather than how it accumulates, and it is the version that keeps working when the 100 parts turn into 100,000. CPython does special-case out += p when out has a single reference, resizing in place instead of copying, which is why the loop is merely slower rather than quadratic. That optimization is an implementation detail, and it disappears the moment a second name refers to the string the loop is building.