You can chop carrots while a pot of broth cooks, but you cannot finish the soup before its ingredients are ready. Programming tasks have similar relationships. Tasks are independent when they can run in any order, on different processing resources, and still produce the same result. One task does not need another task’s intermediate result. section 7.1 section 2.8
To find independent work, break a problem into tasks and ask what each task must wait for. A task dependency graph makes this visible: nodes are tasks, and edges show dependencies. Tasks with no dependency between them, such as making broth and chopping vegetables, can proceed concurrently. A dependent step must wait. section 7.1
Independence makes parallel execution possible, but it is not enough by itself: the computer also needs processing resources that can run tasks simultaneously. If tasks depend on previous results, synchronization makes them wait and can limit the benefit. Tasks needing little or no synchronization are called embarrassingly parallel. section 2.7 section 2.8
Check password candidates separately
Each candidate password can be checked against a hash without first checking the other candidates. Split the candidates into ranges, assign ranges to processing resources, and check them in parallel. The checks have no dependency on one another; the goal is to find the matching password. section 2.10
Count votes, then combine
Give each worker a separate pile of ballots to count. The workers can produce their summaries independently, but the final total depends on those summaries. This is the fork/join pattern: fork independent work, then join its results at a synchronization point. Independence may apply to one stage of a problem without applying to the whole problem. section 7.7
# Chapter 7/count_votes/count_votes_concurrent.py
import typing as T
import random
from multiprocessing.pool import ThreadPool
Summary = T.Mapping[int, int]
def process_votes(pile: T.List[int], worker_count: int = 4) -> Summary:
vote_count = len(pile) #1
vpw = vote_count // worker_count #1
#1
vote_piles = [ #1
pile[i * vpw:(i + 1) * vpw] #1
for i in range(worker_count) #1
] #1
#1
with ThreadPool(worker_count) as pool: #1
worker_summaries = pool.map(process_pile, vote_piles) #1
total_summary = {} #2
for worker_summary in worker_summaries: #2
print(f"Votes from staff member: {worker_summary}") #2
for candidate, count in worker_summary.items(): #2
if candidate in total_summary: #2
total_summary[candidate] += count #2
else: #2
total_summary[candidate] = count #2
return total_summary
def process_pile(pile: T.List[int]) -> Summary:
summary = {}
for vote in pile:
if vote in summary:
summary[vote] += 1
else:
summary[vote] = 1
return summary
if __name__ == "__main__":
num_candidates = 3
num_voters = 100000
pile = [random.randint(1, num_candidates) for _ in range(num_voters)]
counts = process_votes(pile)
print(f"Total number of votes: {counts}")
The Python vote-counting example divides a pile into worker piles and uses a ThreadPool to process them, making the independent stage concrete. section 7.7
Independence can also separate different kinds of work: searching emails and displaying them can be distinct tasks, as can sending and receiving emails. Look for genuine independence rather than merely adding workers. If workers must wait for the same resource or for one another’s results, the extra coordination may slow the work instead of helping. section 7.2 section 2.8
