The Project | About Us | Contribute | Donations | License

HOME

With the code tuned (05-01) and memory under control (05-02), one resource remains that we have ignored so far: a modern processor has 4, 8, or 16 cores, and everything we have written in this course uses exactly one. This lesson teaches how to distribute the work — when to do it, how to do it in Python and, above all, when not to do it. Because parallelizing is not free: it requires classifying the task (does it wait or does it compute?), getting around a famous Python quirk called the GIL, paying hidden startup and communication costs, and accepting a mathematical ceiling — Amdahl's law — that no number of cores can lift. On RutaBus we will see the two canonical scenarios: querying 50 district traffic APIs (waiting) and recomputing the time matrix of the whole network (computing), each with its correct tool. This lesson also closes the module: at the end we will recap the complete method of the optimization craft.

Concurrency and parallelism: not the same thing
Classify before you distribute: CPU-bound versus I/O-bound
Python's GIL, explained with no varnish
Threads for I/O-bound: ThreadPoolExecutor
Processes for CPU-bound: ProcessPoolExecutor
What parallelizes well: embarrassingly parallel problems
Amdahl's law: the ceiling on the gain
Hidden costs and when NOT to parallelize
Race conditions and Lock
Module closing: the complete method

Concurrency and parallelism: not the same thing

Two words that are constantly confused and name different things:

Concurrency: managing several tasks at once, even if they don't advance simultaneously. A lone cook tending three pots — while one boils, they stir another — is concurrent: progress is interleaved.
Parallelism: executing several tasks at literally the same time. Three cooks, three pots, three burners: progress is simultaneous.

	Concurrency	Parallelism
Idea	Structuring tasks that overlap	Executing computations at once
Requires multiple cores	No (one is enough)	Yes
Gains time when...	tasks wait (network, disk)	tasks compute
In Python	`threading`, `asyncio`	`multiprocessing`

The distinction is not academic: it is what decides which tool to use. Concurrency exploits the waits of some tasks to make progress on others (a single core suffices, because waiting doesn't occupy the CPU); parallelism spreads computation across cores. And to know which of the two your problem needs, you first have to classify it.

Classify before you distribute: CPU-bound versus I/O-bound

Every slow task is slow for one of two reasons:

CPU-bound (limited by computation): the processor works at 100% the whole time. More speed = more cores computing.
I/O-bound (limited by input/output): the processor spends almost all its time waiting — for the network, the disk, a database. More speed = overlapping the waits.

Let's classify real RutaBus tasks:

Task	Where does the time go?	Type	Strategy
Recompute the time matrix (Dijkstra from every stop)	Pure computation over the graph	CPU-bound	Processes
Query the 50 district traffic APIs	Waiting for HTTP responses (~1 s each)	I/O-bound	Threads
Read the 2 GB tap record file	Waiting for the disk	I/O-bound	(little to gain: a single disk)
Generate the day's PDF reports	Computation (layout)	CPU-bound	Processes
Notify 10,000 users by push	Waiting for the delivery gateway	I/O-bound	Threads

A diagnostic trick: watch the system monitor while the task runs. One core pinned at 100%? CPU-bound. CPU bored and the task just as slow? I/O-bound. (And yes: this too is measure before acting — the 05-01 method doesn't take vacations.)

Python's GIL, explained with no varnish

Here Python has a quirk that must be told honestly. CPython — the standard interpreter — has a GIL (Global Interpreter Lock): a global lock that guarantees that only one thread executes Python bytecode at a time. Even if you launch 8 threads on an 8-core machine, their Python instructions take turns on the lock: there are never two running simultaneously.

Practical consequences, with no varnish:

Threads do NOT speed up CPU-bound tasks in CPython. Eight threads computing Dijkstras funnel the same work through a single lock, plus the cost of taking turns: it usually comes out the same or slower than serial.
Threads DO speed up I/O-bound tasks. When a thread sits waiting for the network or the disk, it releases the GIL and another thread advances. Fifty threads waiting on fifty APIs overlap beautifully: waiting requires no lock.
The way out for CPU-bound is processes. Each process is an independent Python interpreter, with its own memory and its own GIL: eight processes really do use eight cores.
Nuances for the complete map: C libraries (NumPy, mentioned in 05-02) often release the GIL during their computations, so they partially sidestep the limitation; and since version 3.13 CPython has been working on an experimental GIL-free mode (free-threaded). But the rule you should memorize today is the perennial production rule: threads for waiting, processes for computing.

Threads for I/O-bound: `ThreadPoolExecutor`

The recommended interface for both worlds is concurrent.futures: same methods (map, submit), only the executor changes. Let's start with the 50 traffic APIs:

import time
from concurrent.futures import ThreadPoolExecutor

def fetch_traffic(district):
    """Queries a district's traffic status (~1 s of network wait)."""
    time.sleep(1.0)                       # simulates the HTTP call; for real: requests.get(...)
    return district, "clear"

districts = [f"District-{i:02d}" for i in range(50)]

# SERIAL: 50 calls × 1 s = ~50 s
start = time.perf_counter()
statuses = dict(fetch_traffic(d) for d in districts)
print(f"serial:  {time.perf_counter() - start:.1f} s")     # serial:  50.1 s

# WITH THREADS: the 50 waits overlap
start = time.perf_counter()
with ThreadPoolExecutor(max_workers=10) as pool:
    statuses = dict(pool.map(fetch_traffic, districts))
print(f"threads: {time.perf_counter() - start:.1f} s")     # threads: 5.1 s

What is going on, line by line:

ThreadPoolExecutor(max_workers=10) creates a pool of 10 reusable threads; the with guarantees that all are waited for and closed on exit.
pool.map(f, data) is the everyday map, distributed: each thread takes a district, launches the query and, while it waits for the response (GIL released), another thread launches its own. It returns the results in input order.
50 tasks across 10 threads = 5 rounds of ~1 s ≈ 5 s. Why not 50 threads and take 1 s? You can, but each thread consumes resources and real APIs cap simultaneous requests; max_workers is a dial you tune by measuring.

To process responses as they arrive (instead of waiting for the order), there is concurrent.futures.as_completed; you will find it in real code and it works the same with both executors.

Processes for CPU-bound: `ProcessPoolExecutor`

Now the computing task: recomputing the minimum times of the whole network, zone by zone. Swapping threads for processes is literally a one-word change:

from concurrent.futures import ProcessPoolExecutor

def recalc_zone(zone):
    """Pure CPU: Dijkstra from every stop in the zone (04-05)."""
    return zone["name"], {origin: dijkstra(zone["network"], origin)[0]
                          for origin in zone["network"]}

if __name__ == "__main__":                # MANDATORY with processes (see below)
    zones = load_zones()                  # e.g. 8 zones of the metropolitan network
    with ProcessPoolExecutor(max_workers=4) as pool:
        matrices = dict(pool.map(recalc_zone, zones))

Differences that matter compared with threads:

Each worker is an independent Python process: its own memory, its own GIL, a real core all to itself. Four processes on four cores ≈ 4x on pure computation (minus the toll of section 8).
The if __name__ == "__main__": guard is not decorative: on Windows and macOS the child processes re-import your module to start up, and without the guard each child would re-trigger the pool creation — processes spawning processes without end.
Arguments and results travel serialized with pickle between processes (they do not share memory). This has two consequences: functions and data must be picklable (a lambda is not, a module-level function is), and moving large data costs — we quantify it in section 8.

What parallelizes well: embarrassingly parallel problems

Not every problem lets itself be distributed. The ideal case has a name of its own: embarrassingly parallel — the work splits into pieces that need nothing from one another.

We already know the perfect example from 04-06: the all-pairs time matrix can be built by running Dijkstra from each origin separately. The Dijkstra from Main Square neither reads nor writes anything from the Dijkstra from the University: V independent tasks, distributable as-is across the cores:

from concurrent.futures import ProcessPoolExecutor
from functools import partial

def time_matrix(network):
    with ProcessPoolExecutor() as pool:                      # workers = number of cores
        distances = pool.map(partial(dijkstra_from, network), network.keys())
    return dict(zip(network.keys(), distances))

(partial pins the network argument so map only distributes the origins; dijkstra_from(network, origin) returns the dict of distances.) With 8 cores and 20,000 origins, close to 8x. The instructive contrast is Floyd-Warshall: its outer loop over k is a sequential dependency — iteration k needs the complete matrix left behind by k−1 (that was the essence of the algorithm in 04-06) — so it cannot simply be distributed. A general rule for recognizing each case:

Is each piece computed only from the shared input (the network) and its own data? → embarrassingly parallel: per-scenario simulations, per-zone reports, one Dijkstra per origin.
Does each step need the result of the previous one? → sequential chain: Floyd-Warshall iterations, an accumulator that depends on order, the backtracking stack from 03-04.

Most real problems sit in between: a distributable part and a sequential part (reading the data, merging results). How much that sequential part limits you has an exact formula.

Amdahl's law: the ceiling on the gain

If a fraction p of a program's time is parallelizable (and the fraction 1−p is unavoidably sequential), the maximum speedup with n cores is:

S(n) = 1 / ((1 − p) + p/n)

The intuition: the parallel part gets divided by n, but the sequential part is paid in full, no matter what. Numbers:

p (parallelizable fraction)	n = 2	n = 4	n = 8	n = 16	n → ∞ (ceiling)
50%	1.33x	1.60x	1.78x	1.88x	2x
90%	1.82x	3.08x	4.71x	6.40x	10x
95%	1.90x	3.48x	5.93x	9.14x	20x
99%	1.98x	3.88x	7.48x	13.9x	100x

Two readings that hurt and are worth internalizing:

With half the program sequential, infinite cores give you 2x. Not one bit more.
Even with 90% parallelizable, 8 cores don't give 8x: they give 4.71x. The processor's brochure sells cores; Amdahl deals out reality.

Applied to the RutaBus matrix job: if loading the network and writing the results (sequential) is 10% of the total time, the ceiling is 10x even if the cluster has 64 cores. The practical consequence ties the whole module together: shrinking the sequential part (by optimizing it with 05-01 and 05-02) raises the ceiling on p — it often pays more than adding cores.

Hidden costs and when NOT to parallelize

Amdahl is the theoretical ceiling; in practice you sit even lower, because parallelizing charges tolls:

Process startup: creating a Python process costs tens or hundreds of milliseconds (it imports modules, initializes the interpreter). For a task of 2 seconds total, the pool can cost more than the work.
Serialization (pickling): every argument and every result gets serialized, travels, and gets deserialized. Sending the complete metropolitan network (several MB, 05-02) to each of 20,000 jobs copies it 20,000 times. Mitigations: send cheap references (the zone, not the whole graph; have each worker load the network once), group jobs with chunksize in pool.map, and return aggregated results instead of raw data.
Synchronization: if the tasks share anything (section 9), coordinating access consumes time and, in the worst case, re-serializes what you wanted to parallelize.

Hence the list of when NOT to parallelize:

When the total work is small: the overhead exceeds the gain. You verify this by measuring, not estimating.
When you haven't optimized serially yet: parallelizing the version with the in on a list from 05-01 is multiplying useless work by 8 cores. The module's order is the method's order: algorithm → code → memory → and only then, parallelize.
When the sequential part dominates (Amdahl): with p = 50%, complicating the code for a ceiling of 2x rarely pays off.
When moving the data costs more than computing it: tiny tasks over huge data are pickle's worst customer.

Race conditions and `Lock`

The price parallelism charges in correctness is called a race condition: two threads touching the same data at once, with a result that depends on the luck of the interleaving. The minimal example — a global counter of processed tap records:

import threading

counter = 0

def process_batch(batch):
    global counter
    for _ in batch:
        counter += 1        # NOT atomic!: read, add, write (3 steps)

threads = [threading.Thread(target=process_batch, args=([0] * 100_000,)) for _ in range(4)]
for thread in threads: thread.start()
for thread in threads: thread.join()
print(counter)              # expected 400000; got e.g. 273481 — and different every time

counter += 1 is three operations (read the value, add 1 to it, write it back). If two threads read "1000" at the same time, both write "1001": one increment is lost. The GIL does not protect against this — it guarantees one thread per bytecode instruction, but it can switch threads between the three operations. The solution is a Lock that makes the sequence exclusive:

lock = threading.Lock()

def process_batch(batch):
    global counter
    for _ in batch:
        with lock:           # only one thread inside at a time
            counter += 1     # now it is 400000, every time

Two observations and we close, because distributed systems are beyond this course:

The Lock re-serializes the section it protects: if nearly all the work goes through the lock, goodbye parallelism (Amdahl, again). Better design: have each thread accumulate into its own local counter and sum them at the end.
The best race condition is the one that cannot exist: that is why this lesson's examples distribute work without shared state (each task receives its data, returns its result, and map merges). Processes, by not sharing memory, make that discipline the default.

Module closing: the complete method

With this lesson, the craft promised at the end of Module 4 is complete. The method, in order — and the order is the method:

Step	Question	Tools	Lesson
1. Measure	Where does the time/memory go?	`perf_counter`, `timeit`, `cProfile`, `tracemalloc`	05-01, 05-02
2. Algorithm	Are the strategy and structure right?	Modules 2–4 (analysis, design, classics)	M2–M4
3. Code	Does the implementation waste work?	hierarchy: hoisting, `lru_cache`, idioms	05-01
4. Memory	Does it materialize or retain too much?	generators, batches, `__slots__`, representation	05-02
5. Parallelize	Is there distributable computation left that justifies it?	`concurrent.futures`; Amdahl as the ceiling	05-03

Each step multiplies the ones that follow: parallelizing (step 5) the wrong algorithm (step 2) spreads the mistake across 8 cores; and optimizing the sequential part (steps 3–4) is what raises the Amdahl ceiling of step 5. And everything begins and ends with measuring: the initial measurement says where to act and the final one proves it worked.

Common Mistakes and Tips

Using threads to speed up computation in CPython. The classic GIL mistake: 8 threads computing perform like 1 (or worse). Threads for waiting, processes for computing.
Forgetting if __name__ == "__main__": with processes. On Windows it produces startup errors or a cascade of processes. It goes in always, no exceptions.
Passing huge or non-picklable data to workers. A lambda as the work function fails; a 100 MB graph as a per-task argument turns the CPU you gained into serialization you lost. Module-level functions and lightweight arguments.
Parallelizing before optimizing serially. Multiplying by 4 a piece of code that is 100 times slower than necessary leaves you 25 times below the well-written serial version. Steps 1–4 first.
Over-protecting or under-protecting. Without a Lock, corrupt and intermittent results (the hardest bugs to reproduce); with a Lock around everything, a sequential program disguised as parallel. The good way out is usually to redesign so no state is shared.
Tip: always time the three versions — serial, threads, processes — with realistic data, as we did with the traffic APIs. The three-number table decides by itself, and sometimes the winner is the serial version.

Exercises

Exercise 1. Classify these RutaBus tasks as CPU-bound or I/O-bound and assign each one the appropriate tool (ThreadPoolExecutor, ProcessPoolExecutor, or "serial, not worth it"), justifying in one line: (a) geocoding 2,000 addresses by calling an external web service; (b) compressing the year's 365 tap record files (compression = intensive computation); (c) validating 500 tap records against an in-memory set; (d) running the demand simulation with 12 independent parameter scenarios.

Exercise 2. RutaBus's nightly recomputation takes 200 s: 20 s of loading and writing (sequential) and 180 s of independent Dijkstras (parallelizable). (a) Compute p and the speedup with 4 and with 16 cores according to Amdahl, and the ceiling with infinite cores. (b) A colleague cuts the loading from 20 s to 5 s by applying 05-02 (generator-based reading). Recompute the ceiling. What does this teach about the method's order?

Exercise 3. This thread-parallel code records the overcrowded stops detected by 4 concurrent analyzers, and it sometimes loses alerts. Explain the exact race condition and give two different solutions: one with Lock and one without shared state (a redesign with ThreadPoolExecutor.map).

alerts = []
def analyze(zone):
    for stop in zone:
        if stop["occupancy"] > 0.9:
            alerts.append(f"Overcrowded: {stop['name']}")

Solutions

Solution 1. (a) I/O-bound → ThreadPoolExecutor: 2,000 network waits that overlap; the GIL is released during each call. (b) CPU-bound → ProcessPoolExecutor: compressing is pure computation and the 365 files are independent (embarrassingly parallel). (c) Serial: 500 O(1) lookups against a set are microseconds; any pool costs more than the work (overhead > gain). (d) CPU-bound → ProcessPoolExecutor: 12 independent simulations, ideal for map; with more than 12 cores, the limit becomes the number of scenarios.

Solution 2. (a) p = 180/200 = 0.90. S(4) = 1/(0.1 + 0.9/4) = 3.08x (65 s); S(16) = 1/(0.1 + 0.9/16) = 6.4x (31 s); ceiling S(∞) = 1/0.1 = 10x (20 s: the sequential part in full). (b) With 5 s sequential: p = 180/185 ≈ 0.973 → ceiling 1/(5/185) = 37x, and S(16) rises to ~11.6x. The moral: optimizing the sequential part with the techniques of 05-01/05-02 raised the ceiling from 10x to 37x — more than adding cores would ever give under the old ceiling. Steps 3–4 of the method come before step 5 by mathematics too, not just by prudence.

Solution 3. The race is in alerts.append(...) from 4 threads: although each individual append is atomic in CPython, the general pattern of accumulating into shared structures from several threads is fragile (switching to alerts += [...], or to a counter, is enough to lose updates: interleaved read-modify-write). Solution 1, a lock:

alerts, lock = [], threading.Lock()
def analyze(zone):
    for stop in zone:
        if stop["occupancy"] > 0.9:
            with lock:
                alerts.append(f"Overcrowded: {stop['name']}")

Solution 2, no shared state (preferable): each task returns its own alerts and the main thread merges them — there is nothing to protect because nothing is shared:

def analyze(zone):
    return [f"Overcrowded: {s['name']}" for s in zone if s["occupancy"] > 0.9]

with ThreadPoolExecutor(max_workers=4) as pool:
    alerts = [a for batch in pool.map(analyze, zones) for a in batch]

It is the pattern of the whole lesson: distribute input, return results, aggregate at the end.

Conclusion

This module has walked the complete craft of turning a good algorithm into a fast program: measure before touching anything (05-01), squeeze the code by levels of impact, tame memory when it is the scarce resource (05-02), and finally — only finally — spread the computation across cores, with threads for the waits, processes for the computation, Amdahl's law as the ceiling, and the serialization and synchronization costs as the fine print. The method distills into five steps worth reciting in order: measure → algorithm → code → memory → parallelize. With this, the course has completed its arsenal: we know how to analyze (M1–M2), design (M3), recognize the classics (M4), and optimize (M5). What is not complete yet is fluency, and that is not something you read: you train it. Module 6 is exactly that — batteries of complexity, design, and optimization exercises, plus final projects that bring every piece together on RutaBus — because the gap between knowing these tools and thinking with them closes through practice, and that is where we are headed now.

Algorithm Parallelization

Contents

Concurrency and parallelism: not the same thing

Classify before you distribute: CPU-bound versus I/O-bound

Python's GIL, explained with no varnish

Threads for I/O-bound: `ThreadPoolExecutor`

Processes for CPU-bound: `ProcessPoolExecutor`

What parallelizes well: embarrassingly parallel problems

Amdahl's law: the ceiling on the gain

Hidden costs and when NOT to parallelize

Race conditions and `Lock`

Module closing: the complete method

Common Mistakes and Tips

Exercises

Solutions

Conclusion

Algorithm Analysis and Design Course

Module 1: Introduction to Algorithms

Module 2: Algorithm Analysis

Module 3: Algorithm Design Strategies

Module 4: Classic Algorithms

Module 5: Algorithm Optimization

Module 6: Practice and Exercises

Algorithm Parallelization

Contents

Concurrency and parallelism: not the same thing

Classify before you distribute: CPU-bound versus I/O-bound

Python's GIL, explained with no varnish

Threads for I/O-bound: ThreadPoolExecutor

Processes for CPU-bound: ProcessPoolExecutor

What parallelizes well: embarrassingly parallel problems

Amdahl's law: the ceiling on the gain

Hidden costs and when NOT to parallelize

Race conditions and Lock

Module closing: the complete method

Common Mistakes and Tips

Exercises

Solutions

Conclusion

Algorithm Analysis and Design Course

Module 1: Introduction to Algorithms

Module 2: Algorithm Analysis

Module 3: Algorithm Design Strategies

Module 4: Classic Algorithms

Module 5: Algorithm Optimization

Module 6: Practice and Exercises

Threads for I/O-bound: `ThreadPoolExecutor`

Processes for CPU-bound: `ProcessPoolExecutor`

Race conditions and `Lock`