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

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

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)

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:

  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:

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:

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:

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.

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:

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:

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

🧪 Try It Yourself

Exercise 1 – Start a Process

Press Run to see what your code prints.

Exercise 2 – Process Pool map()

Press Run to see what your code prints.

Exercise 3 – Multiprocessing Queue

Press Run to see what your code prints.