Concurrency line
Parallelism deep-dive
Two cashiers pack at the same moment, but one person still counts the cart first and checks it at the end.
Stops explain each step. The film plays the whole ride.
- Handing out a half
- Waiting on a copy
- Bringing a half back
- Slower, or stuck on one
One person counts the cart
One person counts the whole cart before anyone can pack. The extra cashiers wait.
Next stop: Only one cashier starts
All stops
The everyday version
Two cashiers, one cart. Farah counts it before the split and checks it after. Hiring another packer does not shrink that counting.
- The countis the Serial stretch
The stretch one person must do, before the split and after the halves meet.
- Cashier 1is the Core 1
Packs the left half at the same moment as the other cashier.
- Cashier 2is the Core 2
Packs the right half. Idle during the count and the check.
- The checkis the Join
Where the halves meet. One person finishes, and the slower half sets the wait.
- One cashieris the concurrency page
Many carts in progress, and only one basket open. That is not this page.
Interview questions
Say the short answer first. Go deeper only if they ask.
What does Amdahl’s law say?
Speedup is capped by the fraction you cannot split.
For a fixed job, speedup with n cores is 1 / ((1 - p) + p / n), where p is the fraction that parallelises. At p of 0.95, even infinite cores top out at 20 times. At p of 0.5, the ceiling is 2 times. Quote a ceiling, not a vague diminishing return.
“Twice the cores, twice as fast.”
When is Amdahl the wrong picture?
When the job grows with the machine, or when copying costs more than the split.
Gustafson–Barsis 1988 grows the problem as the machine grows. Scaled speedup is about n - s(n - 1). Split and merge overhead is the other miss: neither law includes it, and it can make two cores slower than one.
“Amdahl says parallel programming is pointless.”
How do you get real multicore speedup in CPython?
Not with pure Python threads on the default build.
A default build runs one thread’s bytecode at a time. Both cores need processes, a C extension that releases the GIL, a free-threaded build, or 3.14 InterpreterPoolExecutor, where each worker has its own interpreter and its own GIL. Threads still win for waiting, because waiting releases the core.
“Threads always use all the cores.”
What is the wall-clock time of a split job?
The serial parts, plus the slower half, plus the cost of the split.
You wait for the longer parallel part, not the average of the two. A lopsided split leaves one core idle at the join. The formulas still omit the time spent copying the work out and merging the answers.
“Add the two halves and divide by two.”
Does the speedup formula include the cost of splitting?
No. Copying and merging can erase the speedup.
Say the overhead before the ceiling. Amdahl and Gustafson both assume the split is free. If copying the work out and merging the answers dominates, two cores finish later than one.
“The formula already includes the copy.”
Cheat-sheet
Commands you will actually type.
def amdahl(p, n):
return 1 / ((1 - p) + p / n)Fixed-size speedup. p is the fraction that splits, n is the core count.
amdahl(0.95, 1_000_000_000) # about 20A job that is 95 percent parallel tops out near 20 times, even with a huge n.
def gustafson(n, s):
return n - s * (n - 1)Scaled speedup when the job grows. s is the serial share of the parallel run.
from concurrent.futures import ProcessPoolExecutorSeparate processes, so Python bytecode can run on more than one core.
from concurrent.futures import InterpreterPoolExecutor # 3.14Each worker has its own interpreter and its own lock, so bytecode can use two cores.