Mini Project (Parallel Number Processing)

Goal

Create a CPU-bound job and speed it up using a process pool.

Example job:

compute something expensive for many items

Step 1: Define an expensive function

expensive.py

def expensive(x: int) -> int:
    # intentionally slow operation
    total = 0
    for i in range(1, 200_000):
        total += (x * i) % 97
    return total

Step 2: Run sequential

sequential.py

import time
from expensive import expensive
 
items = list(range(20))
 
start = time.time()
results = [expensive(x) for x in items]
print("sequential seconds:", round(time.time() - start, 2))
print(results[:5])

Step 3: Run in parallel (Pool)

parallel.py

import time
from multiprocessing import Pool
from expensive import expensive
 
items = list(range(20))
 
if __name__ == "__main__":
    start = time.time()
 
    with Pool() as pool:
        results = pool.map(expensive, items)
 
    print("parallel seconds:", round(time.time() - start, 2))
    print(results[:5])

Deliverable

Compare sequential vs parallel time.
Try different pool sizes.
Explain when multiprocessing helps (CPU-bound) vs not (I/O-bound).

The shape of every parallel batch job

Split the input, hand each piece to a worker, combine what comes back. The interesting decisions are all in the first box:

diagram Diagram mermaid

  flowchart LR
  IN["range 2 .. 3,000,000"] --> SP["split into k pieces"]
  SP --> W0["worker 0"]
  SP --> W1["worker 1"]
  SP --> W2["worker 2"]
  SP --> W3["worker 3"]
  W0 --> C["combine: sum the counts"]
  W1 --> C
  W2 --> C
  W3 --> C
  C --> OUT["216,816 primes"]

The correctness check comes first and is exact — however the work is split, the answer must not move:

verify.py

with mp.Pool(4) as pool:
    parts = pool.map(count_primes, chunks(2, 3_000_000, 4))
assert sum(parts) == 216_816        # holds for every split tried below

Splitting badly is the whole difficulty

Two splits of the same range across four workers, counted rather than timed, so the figures do not depend on the machine:

split	primes found by each worker	spread
four contiguous blocks	60,238 / 53,917 / 51,926 / 50,735	1.2×
every 4th number (stride 4)	1 / 108,532 / 0 / 108,283	108,532×

The stride split looks fair and is a catastrophe. With a stride of 4, two workers receive only even numbers, and every even number above 2 is rejected immediately. Those workers finish almost instantly having done nothing, while the other two do the entire job.

Counting the trial divisions actually performed (for n below 60,000, so the numbers stay readable) shows the same thing as a cost rather than a count:

split	divisions per worker	spread
contiguous	106,939 / 164,962 / 200,344 / 226,698	2.1×
stride 4	15,000 / 333,980 / 14,999 / 334,949	22×

Note that even the “good” split is not level: the last block does 2.1× the work of the first, because testing a larger n requires trying divisors up to $\sqrt{n}$ . Equal width is not equal work whenever the cost per item depends on the item.

See it move

Switch between the splits and watch how the work piles up. The bar that matters is the tallest one.

sketch Equal width is not equal work p5.js

Contiguous blocks give a mild imbalance because larger numbers cost more to test. A stride of 4 gives two workers only even numbers, so they do almost nothing.

Let the pool balance it for you

Rather than hand-designing a fair split, cut the work into more pieces than workers and let Pool hand out the next piece whenever a worker goes idle:

dynamic.py

import multiprocessing as mp
 
if __name__ == "__main__":
    pieces = chunks(2, 3_000_000, 64)        # 64 pieces, 4 workers
    with mp.Pool(4) as pool:
        parts = pool.map(count_primes, pieces)
    print(sum(parts))                         # 216816

A worker that draws a cheap piece simply comes back for another. The finer the pieces, the better the balance — until the per-task overhead takes over. Measured on the smaller range, 64 pieces beat 4, and 2,000 pieces were slower than 4, because each task carries pickling and dispatch cost of its own.

The deliverable

A complete, correct version to compare yours against:

parallel_primes.py

import multiprocessing as mp
import math, time
 
def is_prime(n):
    if n < 2: return False
    if n % 2 == 0: return n == 2
    for i in range(3, math.isqrt(n) + 1, 2):
        if n % i == 0: return False
    return True
 
def count_primes(rng):
    lo, hi = rng
    return sum(1 for n in range(lo, hi) if is_prime(n))
 
def chunks(lo, hi, k):
    step = (hi - lo) // k
    return [(lo + i * step, lo + (i + 1) * step if i < k - 1 else hi)
            for i in range(k)]
 
if __name__ == "__main__":                     # required: spawn re-imports this file
    LO, HI = 2, 3_000_000
    t = time.perf_counter()
    with mp.Pool(4) as pool:
        parts = pool.map(count_primes, chunks(LO, HI, 64))
    print(f"{sum(parts):,} primes in {time.perf_counter() - t:.2f}s")
    assert sum(parts) == 216_816               # the answer must not depend on the split

Check yourself

pch.quizTag pch.quizDefaultTitle

Splitting 2..3,000,000 across four workers by stride of 4 gives prime counts of 1, 108532, 0 and 108283. Why?

pch.quizShowAnswer

B — two workers receive only even numbers, which are rejected immediately, so they do almost no work — With stride 4, workers take n where n % 4 is 0 or 2 — all even. Every even number above 2 fails the first test, so those two workers idle while the other two do the whole job.
Even the contiguous split does 2.1x more divisions in the last block than the first. What causes that?

pch.quizShowAnswer

B — testing a larger n needs trial divisors up to its square root, so cost grows with n — The last block actually holds the FEWEST primes (50,735 against 60,238). It is slower because each candidate is larger and requires more divisors to be tried. Equal width is not equal work.
For the smaller range where the sequential run took 0.42 s, every Pool configuration was slower. Why?

pch.quizShowAnswer

B — pool startup is roughly 0.5-1 s, which alone exceeds the whole sequential run — Creating worker processes and pickling arguments costs about a second here. Work measured in fractions of a second cannot repay that, so parallelism is a net loss below some threshold.
Why does cutting the range into 64 pieces for 4 workers usually beat cutting it into exactly 4?

pch.quizShowAnswer

B — a worker that finishes a cheap piece immediately takes another, so idle time is absorbed — More pieces than workers lets Pool balance dynamically. The limit is per-task overhead: 2,000 pieces measured slower than 4, because dispatch and pickling began to dominate.