Capstone: Fix Five Performance Problems in an Order Pipeline

Fix five performance problems in an order-processing module. Some of them waste time and some hold on to memory, and every fix must keep the results the same.

orders = [make_order(index, customers=3, high_from=100) for index in range(6)]
print(join_totals(orders, active=[0, 2]))
# {0: Decimal('3.10'), 2: Decimal('7.10')}
print(top_high_value(10, customers=3, threshold=Decimal(500), limit=2))
# [8, 9]

Customer 0 has orders 0 and 3, and customer 2 has orders 2 and 5. In the scan, make_order gives the last limit orders an amount of 1000. The rest stay under 100, so orders 8 and 9 are the matches.

The starter already returns these results. Your job is to keep them and change how the code gets them.

What to write

Fix join_totals, dump, CustomerDirectory, Accumulator and top_high_value. Keep their names and parameters. A defect comment in the starter marks each one.

• Add type annotations to make_order, so the file passes mypy --strict. Keep what it does.
• You can assume that counts and limits are zero or more, customers is at least 1, and memory_budget is positive.

1. Build the set of active customers once

The starter checks order.customer_id in active for every order. When active is a list, each check compares against every item. So N orders and A active IDs cost up to N × A comparisons. The exercise on choosing containers for membership checks covers the fix.

• join_totals(orders, active) returns a dictionary that maps each active customer who has orders to the sum of their order amounts.
• Read orders only once. The driver passes a generator.
• Before the loop, build a set or frozenset from active, and check membership in that. A set lookup takes about the same time however many IDs the set holds.
• Never use in on active itself. The driver counts those checks and expects zero.

2. Return the order's own values from dump

The starter calls dataclasses.asdict, which rebuilds every nested value. Each OrderLine in lines becomes a new dictionary inside a new tuple. The exercise on converting dataclasses to JSON-ready values shows what asdict copies.

• dump(order) returns a new dictionary with exactly the keys id, customer_id, amount and lines.
• Put the order's own Decimal in amount and its own tuple in lines, so dump(order)["lines"] is order.lines.
• The result is a dictionary for other Python code to read, not JSON.

Sharing lines is safe here because the tuple and every OrderLine in it are frozen. Don't share a nested value that someone can change.

3. Let the customer cache release customers

The starter puts @lru_cache(maxsize=None) on lookup. That cache belongs to the class, and it keeps every argument and every result. Since self is an argument, it keeps every directory and every customer alive for as long as the class exists. The exercise on caching method results without keeping objects alive covers this.

A weak reference points to an object without keeping it alive. Once no ordinary reference to the object remains, Python frees it.

• CustomerDirectory.lookup(id) returns Customer(id=id, name=f"customer-{id}").
• While other code still holds a customer, lookup returns that same object.
• Once nothing else holds the customer, the cache must let Python free it. A later lookup can then create a new, equal customer.
• Give each directory its own cache. A weakref.WeakValueDictionary created in __init__ holds its values by weak reference.
• Add weakref_slot=True to the @dataclass on Customer. Because the class uses slots=True, Python cannot make a weak reference to a customer without it.

4. Join the bytes only when asked

The starter adds each chunk with self.buffer += chunk. A bytes object cannot change, so each += copies everything so far into a new object. The total copying grows with the square of the number of chunks. The exercise on building text without repeated copying covers this.

• Accumulator.add(chunk) stores the chunks in order.
• value() returns every chunk added so far as one bytes object.
• A value that value() returned earlier must not change when more chunks arrive. So return bytes, never a bytearray that you keep adding to.
• Keep the chunks in a list, and join them with b"".join(...) when someone calls value(). A bytearray inside the class works too, if value() returns a bytes copy of it.
• One test adds 20,000 chunks of 2,000 bytes. It must finish inside the test's 5-second time limit.

5. Scan lazily and stop at the limit

The starter builds all n orders in a list, then a second list of matches, and only then takes the first limit. For 120,000 orders, its memory peaks at about 43 MB. The tracemalloc exercise shows how to measure this.

• top_high_value(n, customers, threshold, limit) looks at make_order(index, customers, n - limit) for each index from 0 to n - 1, in that order.
• It returns the IDs of the first limit orders whose amount is greater than threshold, in scan order. These are the first matches, not the largest amounts.
• Make the orders one at a time with a generator, and stop as soon as you have limit matches.
• The driver measures the scan's peak memory. It must stay under memory_budget, which is 1,000,000 bytes by default.

In the tests the matching orders come last, so the scan still looks at almost every order. The fix saves memory, not time.

What the driver checks

Keep solve and _CountingIds as they are. _CountingIds is a collection that counts each in check on it, and the driver passes one as active.

• totals_size is the number of customers in the join result. total_0 and total_7 are the totals for customers 0 and 7, as strings, or "0" when a customer has none.
• membership_calls counts the in checks on active. It must be 0.
• high_value is the list that top_high_value returns for a threshold of 500 and a limit of 12.
• peak_ok is True when the scan's peak memory is under memory_budget. The driver measures it with tracemalloc, above what was already in use.
• alive_after_gc counts the customers still alive after the driver drops its references and runs gc.collect(). It must be 0.
• buffer_len is the length of the final value(). alias_stable is True when a value returned earlier kept its length after another add.
• lines_by_reference is True when dump returned the order's own lines tuple. amount is the dumped amount as a string.

Going further

In your own code, measure before you fix. Each question needs its own tool:

• peak_ok measures only top_high_value. tracemalloc traces every Python allocation in the process, so other work running at the same time can push the peak up. Run this check on its own.
• Calling value() after every small add would still copy the whole buffer each time. The driver adds all its chunks first.
• A weak cache can rebuild a customer that a strong cache would have kept. You save memory at the cost of that extra work.
• The Python documentation covers tracemalloc, lru_cache and weak references.