Third battery: optimization. Here we work out the whole of Module 5 — measure first (05-01), memory (05-02) and parallelization (05-03) — using the analysis from Module 2 as a diagnostic tool. The working material is RutaBus code that is slow but realistic: the kind of code that actually shows up in production, not lab examples.
How to work through this lesson: before looking at each solution, write your own diagnosis following the method distilled at the end of Module 5 — measure → algorithm → code → memory → parallelize — and only then compare. If you have Python at hand, actually measure before/after versions with timeit on synthetic data: checking that your estimated gain holds (or doesn't) is half the learning.
Contents
- Reading a profile: deciding where to attack first.
- The slow punctuality report: the full hierarchy applied.
- Memory: the nightly job that chokes.
- Do I parallelize or not?: classifying CPU/I-O and applying Amdahl with numbers.
- When NOT to optimize.
Exercise 1: Read the profile before touching anything
Difficulty: basic
RutaBus's daily_close() process takes 21.5 seconds. Before touching code, someone did the right thing (05-01): ran cProfile on it. Summarized output:
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.002 0.002 21.500 21.500 close.py:12(daily_close)
180000 17.800 0.000 17.800 0.000 close.py:31(find_fare)
1 2.100 2.100 2.400 2.400 close.py:55(sort_tap_records)
180000 0.900 0.000 0.900 0.000 close.py:44(round_amount)Questions: (a) which function do you attack first and why?; (b) is it the one called the most times?; (c) 180,000 calls with near-zero percall but a huge tottime: does that suggest an algorithm-level or a micro-level optimization in the 05-01 hierarchy?; (d) if you got find_fare down to negligible time, what would be the maximum speedup for the close?
Solution
(a) find_fare: it accumulates 17.8 of the 21.5 seconds (83%). The column in charge is tottime (the function's own time), as we saw in 05-01. Optimizing anything else first is working on the remaining 17%.
(b) Trap avoided: round_amount is called the same 180,000 times and accumulates only 0.9 s. The number of calls is not the criterion; the total time is.
(c) Algorithm level. Each individual call is cheap (percall ≈ 0.0001 s) but it is made 180,000 times with a cost that, judging by the total, grows with the data: the typical pattern is a repeated linear search (a fare looked up with in/a loop over a list for every tap record → O(n·m), as we analyzed in 02-01). The algorithm-level fix is changing the structure: a fare dict turns each lookup into O(1). Micro-optimizing the inside of find_fare (micro level) would leave the O(n·m) intact.
(d) Remaining time ≈ 21.5 − 17.8 = 3.7 s → maximum speedup ≈ 21.5 / 3.7 ≈ ×5.8. It is the same arithmetic as Amdahl's law (05-03) applied to sequential optimization: the part you don't touch caps the total gain.
Common mistake: opening the code and "optimizing what looks slow" without a profile. The profile here disproves two reasonable intuitions: neither the sort (2.1 s, in plain sight and with a suspicious name!) nor the most-called function was the problem.
Exercise 2: The slow punctuality report
Difficulty: medium
This report takes minutes at current volumes (n ≈ 200,000 arrivals, m ≈ 500 critical stops, and ~30% of arrivals happen at critical stops):
def punctuality_report(arrivals, critical_stops):
# arrivals: list of n tuples (stop, line, delay_min)
# critical_stops: LIST of m stop names
report = ""
for stop, line, delay in arrivals:
if stop in critical_stops: # (1)
worst = max(d for _, _, d in arrivals) # (2)
report += f"{stop};{line};{delay};{worst}\n" # (3)
return reportTasks: (a) derive the current complexity with the analysis from 02-01, identifying the cost of (1), (2) and (3); (b) apply the 05-01 hierarchy: what you change, in what order, and at what level each change sits; (c) rewrite the function; (d) estimate the gain with the given numbers.
Hint: one of the three problems is orders of magnitude worse than the other two. Find it first: it decides where to start.
Solution
(a) Diagnosis.
- (1)
stop in critical_stopson a list: O(m) per iteration → O(n·m) total = 200,000 × 500 = 10⁸ comparisons. - (2)
max(...)traverses the n arrivals inside the loop, and it is invariant: it computes the same thing on every pass. It runs on each hit (~0.3·n = 60,000 times) × O(n) → 1.2 × 10¹⁰ operations. This is the monster. - (3) String concatenation: each
+=copies the whole report (02-01). With k ≈ 60,000 lines, cost Θ(k²) in characters copied: ~10⁹–10¹⁰ depending on line length.
(b) Plan according to the hierarchy (05-01: highest yield first):
- Algorithm — hoist the invariant:
worstis computed once, outside the loop. Eliminates the 10¹⁰ term. - Algorithm/structure — list → set:
set(critical_stops)once (O(m)) and each lookup becomes O(1). Eliminates the 10⁸. - Code — accumulate and
join: build a list of lines and join them at the end, Θ(total length) instead of Θ(k²).
(c) Rewrite:
def punctuality_report(arrivals, critical_stops):
critical = set(critical_stops) # O(m), once
worst = max(d for _, _, d in arrivals) # O(n), once
lines = []
for stop, line, delay in arrivals: # O(n)
if stop in critical: # O(1)
lines.append(f"{stop};{line};{delay};{worst}\n")
return "".join(lines) # O(total)(d) Gain. Before: dominated by (2), ~10¹⁰ elementary operations — tens of seconds or minutes in CPython. After: Θ(n + m) ≈ 4 × 10⁵ operations — tens of milliseconds. Estimated gain: 3–4 orders of magnitude. And the mandatory final step of the method: confirm it by measuring with timeit on synthetic data of the same size (05-01) — estimates are checked, not declared.
Common mistakes: (1) starting with the join because "string concatenation is the famous one" — here it was the third problem in magnitude; the hierarchy exists to order the attacks; (2) not recognizing (2) as an invariant because "it's inside an if"; (3) converting to a set inside the loop (if stop in set(critical_stops)), which is O(m) per iteration again with extra construction cost — worse than the original list.
Exercise 3: The nightly job that chokes
Difficulty: medium
This job processes the day's tap-record file (several GB) and dies with a MemoryError on the 8 GB server:
def top_amounts(file_path):
with open(file_path) as f:
lines = f.readlines() # the whole file
tap_records = [parse(l) for l in lines] # another copy
valid = [x for x in tap_records if x.amount > 0] # yet another
sorted_items = sorted(valid, key=lambda x: x.amount)
return sorted_items[-10:] # top 10 amountsQuestions: (a) how many structures proportional to the file coexist in memory at the worst moment?; (b) rewrite it so that auxiliary memory is O(k) with k = 10, using what we saw in 05-02 and the top-k from 04-04; (c) with what tool would you confirm the improvement?; (d) in what situation would generators not be enough, requiring batch processing?
Solution
(a) At the moment of the sorted there coexist: lines (all the strings), tap_records (all the objects), valid (references to nearly all of them) and the new list sorted builds. Between 3 and 4 simultaneous O(n) structures — with a file of several GB, the MemoryError is guaranteed. Note from 02-02: valid holds references, not copies of the objects, but lines and tap_records are each new content.
(b) The file can be traversed lazily (an open file is already a line-by-line iterator) and the top-10 needs no sorting at all: it is a k largest problem, and for small k in streaming the tool is a heap (04-05 gave us heapq; 04-04 gave us the quickselect alternative, which is no use here because it requires the whole list in memory):
import heapq
def top_amounts(file_path):
with open(file_path) as f:
valid = (x for x in map(parse, f) if x.amount > 0) # generator
return heapq.nlargest(10, valid, key=lambda x: x.amount)Auxiliary memory: O(k) — the generator produces the tap records one at a time (05-02) and nlargest retains only the 10 best seen. Time: Θ(n log k) versus the Θ(n log n) of sorting everything; with k = 10, in practice linear.
(c) tracemalloc (05-02): measure the memory peak of both versions with a test file. The original version peaks in gigabytes; the new one, in kilobytes. (For time, timeit; to find out where it is spent, cProfile — each tool answers a different question.)
(d) When the computation needs to group state that also grows without bound — for example, "total amount per unique ticket" with hundreds of millions of distinct tickets: the accumulator dict would end up being the new problem. That is where the batches of 05-02 come in: process by chunks (by hour, by line), flush partial results and combine afterwards — which is exactly the external sorting we sketched in 04-03.
Common mistakes: (1) "fixing it" by changing readlines() to list(f) — the same materialization with different syntax; (2) building the generator and then calling sorted(valid, ...) on it: sorted materializes the whole iterable and the improvement silently evaporates; (3) turning the generator into a list "just for a moment, to debug" and forgetting it there.
Exercise 4: Do I parallelize or not?
Difficulty: high
Two RutaBus jobs are candidates for parallelization:
- Job A: queries the municipal traffic API for 60 zones; each call takes ~0.5 s, almost all network waiting, and the responses are processed in microseconds.
- Job B: recomputes Dijkstra from each of the network's 300 stops (pure CPU; the origins are independent of one another). Measured: 90% of the time is the Dijkstra runs; the remaining 10% (loading the graph and dumping results) is sequential.
Questions: (a) classify each job (CPU-bound / I-O-bound) and choose threads or processes, justifying with the GIL (05-03); (b) which concurrent.futures executor would you use in each case?; (c) for Job B, compute with Amdahl's law the speedup with 4 and with 8 processes, and the theoretical limit with infinitely many; (d) the machine has 8 cores: is it worth configuring 16 processes?
Solution
(a) Job A: I/O-bound — the time goes to waiting on the network, not computing. During an I/O wait the thread releases the GIL, so threads work perfectly (and are cheaper than processes). Job B: CPU-bound — the GIL prevents two threads from executing Python bytecode at once, so threads would contribute nothing; processes are needed, each with its own interpreter and its own GIL. And it is the ideal case: as we saw in 05-03, Dijkstra per origin is embarrassingly parallel — zero dependencies or communication between tasks.
(b) Job A → ThreadPoolExecutor (e.g. max_workers=20; since it is network waiting, more workers than cores is reasonable). Job B → ProcessPoolExecutor with max_workers ≈ number of cores:
from concurrent.futures import ProcessPoolExecutor
with ProcessPoolExecutor(max_workers=8) as pool:
results = dict(zip(STOPS, pool.map(dijkstra_from, STOPS)))(c) Amdahl (05-03) with parallelizable fraction p = 0.9: S(N) = 1 / ((1 − p) + p/N).
| N processes | Calculation | Speedup |
|---|---|---|
| 4 | 1 / (0.1 + 0.225) | ×3.08 |
| 8 | 1 / (0.1 + 0.1125) | ×4.71 |
| ∞ | 1 / 0.1 | ×10 (ceiling) |
With 8 processes you do not get ×8: you get ×4.7, because the 10% sequential part does not speed up and weighs proportionally more and more.
(d) No. Two reasons that stack: (i) Amdahl gives S(16) = 1/(0.1 + 0.05625) ≈ ×6.4 theoretical — going from 8 to 16 processes would add at most another ×1.36; (ii) that theoretical figure is not even reached: with 8 physical cores, 16 CPU-bound processes compete for the same cores and add context-switching and memory overhead (each process duplicates the graph). More workers than cores only makes sense when there is waiting (Job A), not when there is computation.
Common mistake: parallelizing as the first resort. The Module 5 hierarchy puts parallelizing last for a reason: if inside dijkstra_from there were a list where a heap belongs, fixing that would yield more than all 8 cores together — and the two improvements multiply if you do the cheap one first.
Exercise 5: When NOT to optimize
Difficulty: medium
Two real situations on the RutaBus team:
- Case 1:
monthly_report.pyruns once a month, takes 4 seconds and is 80 readable lines. A colleague proposes spending 2 days rewriting it withmultiprocessing,lru_cacheand__slots__to get it down to 0.5 s. - Case 2: the app's
find_connectionendpoint responds in 900 ms and receives 50,000 requests a day. Users complain about slowness. Nobody has profiled it.
Questions: (a) which of the two deserves optimization effort? Quantify; (b) what would you do first in the case that does deserve it?; (c) what concrete risks does optimizing Case 1 carry?
Solution
(a) Case 2, no contest. Let's quantify both:
- Case 1: saving of 3.5 s/month = 42 seconds a year, in exchange for 2 days of engineering. Even if the salary were free, you would not recover the investment in a century.
- Case 2: 50,000 × 0.9 s = 45,000 s = 12.5 hours a day of aggregated user waiting, on the critical path of the app experience. Every 100 ms you shave off is ~1.4 hours a day handed back to users.
(b) Measure it (05-01): cProfile on the endpoint with representative requests, before touching a line. "Nobody has profiled it" means nobody knows whether the 900 ms are the route query (a Dijkstra over a clumsy graph representation? a linear stop search?), the database or the serialization. Optimizing without a profile is gambling; with 12.5 hours/day at stake, you gamble little and measure a lot. Then, the hierarchy: algorithm → code → memory → parallelize.
(c) Risks of Case 1: (i) new bugs in a process that worked — every change carries a probability of error, and here with no benefit to offset it; (ii) maintainability: 80 readable lines become multiprocessing with shared state, which the next colleague will take hours to understand (and remember from 05-03 that sharing state between processes requires Lock and serialization: real complexity); (iii) opportunity cost: those 2 days are not spent on Case 2, which is actually bleeding. The Module 5 rule was exactly this: optimized code is paid for in readability and risk, so you optimize what is on the critical path and leave alone what is not.
A final nuance so the rule does not become dogma: if the monthly report started running every 5 minutes, or its input file grew a hundredfold, the analysis changes — optimization decisions expire with the data, which is why they rest on measured numbers and not on opinions.
Common mistake: optimizing for technical satisfaction ("I know how to make it faster") instead of impact. The professional question is not "can it go faster?" — almost everything can — but "how much is it worth for it to go faster, and how much does it cost to get there?".
Conclusion
You have applied the full Module 5 method to realistic code written by others: reading a profile and choosing the target by tottime and not by intuition; attacking a slow report in the right order (invariant out of the loop, list → set, join) while estimating gains of orders of magnitude; turning a memory-hungry job into an O(k) stream with generators and a heap; deciding threads versus processes with the GIL and putting numbers on the speedup with Amdahl; and — the most profitable skill of all — recognizing when the best optimization is not to optimize.
You now have the three muscles trained separately: analysis (06-01), design (06-02) and optimization (06-03). In the final lesson of the course we will use them all at once: three final projects that build, end to end, complete pieces of RutaBus.