7.5. Know How to Recognize When Concurrency Is Necessary¶
Inevitably, as the scope of a program grows, it also becomes more complicated. Dealing with expanding requirements in a way that maintains clarity, testability, and efficiency is one of the most difficult parts of programming. Perhaps the hardest type of change to handle is moving from a single-threaded program to one that needs multiple concurrent lines of execution.
Let me demonstrate how you might encounter this problem with an example. Say that I want to implement Conway’s Game of Life, a classic illustration of finite state automata. The rules of the game are simple: You have a two-dimensional grid of an arbitrary size. Each cell in the grid can either be alive or empty:
>>> ALIVE = '*'
>>> EMPTY = '-'
The game progresses one tick of the clock at a time. Every tick, each cell counts how many of its neighboring eight cells are still alive. Based on its neighbor count, a cell decides if it will keep living, die, or regenerate. (I’ll explain the specific rules further below.) Here’s an example of a 5 × 5 Game of Life grid after four generations with time going to the right:
0 | 1 | 2 | 3 | 4
----- | ----- | ----- | ----- | ----- ---- | ---- | --- | --*-- | ----- --- | --- | -*--- | -*--- | --- ---- | --*- | --**- | --*-- | ----- ----- | ----- | ----- | ----- | -----
I can represent the state of each cell with a simple container class. The class must have methods that allow me to get and set the value of any coordinate. Coordinates that are out of bounds should wrap around, making the grid act like an infinite looping space:
>>> class Grid:
>>> def __init__(self, height, width):
>>> self.height = height
>>> self.width = width
>>> self.rows = []
>>> for _ in range(self.height):
>>> self.rows.append([EMPTY] * self.width)
>>>
>>> def get(self, y, x):
>>> return self.rows[y % self.height][x % self.width]
>>>
>>> def set(self, y, x, state):
>>> self.rows[y % self.height][x % self.width] = state
>>>
>>> def __str__(self):
>>> output = ''
>>> for row in self.rows:
>>> for cell in row:
>>> output += cell
>>> output += '\n'
>>> return output.strip()
To see this class in action, I can create a Grid instance and set its initial state to a classic shape called a glider:
>>> grid = Grid(5, 9)
>>> grid.set(0, 3, ALIVE)
>>> grid.set(1, 4, ALIVE)
>>> grid.set(2, 2, ALIVE)
>>> grid.set(2, 3, ALIVE)
>>> grid.set(2, 4, ALIVE)
>>> print(grid)
-------- -------- --***---- --------- ---------
Now, I need a way to retrieve the status of neighboring cells. I can do this with a helper function that queries the grid and returns the count of living neighbors. I use a simple function for the get parameter instead of passing in a whole Grid instance in order to reduce coupling (see Item 38: “Accept Functions Instead of Classes for Simple Interfaces” for more about this approach):
>>> def count_neighbors(y, x, get):
>>> n_ = get(y - 1, x + 0) # North
>>> ne = get(y - 1, x + 1) # Northeast
>>> e_ = get(y + 0, x + 1) # East
>>> se = get(y + 1, x + 1) # Southeast
>>> s_ = get(y + 1, x + 0) # South
>>> sw = get(y + 1, x - 1) # Southwest
>>> w_ = get(y + 0, x - 1) # West
>>> nw = get(y - 1, x - 1) # Northwest
>>> neighbor_states = [n_, ne, e_, se, s_, sw, w_, nw]
>>> count = 0
>>> for state in neighbor_states:
>>> if state == ALIVE:
>>> count += 1
>>> return count
Now, I define the simple logic for Conway’s Game of Life, based on the game’s three rules: Die if a cell has fewer than two neighbors, die if a cell has more than three neighbors, or become alive if an empty cell has exactly three neighbors:
>>> def game_logic(state, neighbors):
>>> if state == ALIVE:
>>> if neighbors < 2:
>>> return EMPTY # Die: Too few
>>> elif neighbors > 3:
>>> return EMPTY # Die: Too many
>>> else:
>>> if neighbors == 3:
>>> return ALIVE # Regenerate
>>> return state
I can connect count_neighbors and game_logic together in another function that transitions the state of a cell. This function will be called each generation to figure out a cell’s current state, inspect the neighboring cells around it, determine what its next state should be, and update the resulting grid accordingly. Again, I use a function interface for set instead of passing in the Grid instance to make this code more decoupled:
>>> def step_cell(y, x, get, set):
>>> state = get(y, x)
>>> neighbors = count_neighbors(y, x, get)
>>> next_state = game_logic(state, neighbors)
>>> set(y, x, next_state)
Finally, I can define a function that progresses the whole grid of cells forward by a single step and then returns a new grid containing the state for the next generation. The important detail here is that I need all dependent functions to call the get method on the previous generation’s Grid instance, and to call the set method on the next generation’s Grid instance. This is how I ensure that all of the cells move in lockstep, which is an essential part of how the game works. This is easy to achieve because I used function interfaces for get and set instead of passing Grid instances:
>>> def simulate(grid):
>>> next_grid = Grid(grid.height, grid.width)
>>> for y in range(grid.height):
>>> for x in range(grid.width):
>>> step_cell(y, x, grid.get, next_grid.set)
>>> return next_grid
Now, I can progress the grid forward one generation at a time. You can see how the glider moves down and to the right on the grid based on the simple rules from the game_logic function:
- class ColumnPrinter:
...
columns = ColumnPrinter() for i in range(5):
columns.append(str(grid)) grid = simulate(grid)
print(columns)
>>>
0 | 1 | 2 | 3 | 4
---*----- | --------- | --------- | --------- | ---------
----*---- | --*-*---- | ----*---- | ---*----- | ----*----
--***---- | ---**---- | --*-*---- | ----**--- | -----*---
--------- | ---*----- | ---**---- | ---**---- | ---***---
--------- | --------- | --------- | --------- | ---------
This works great for a program that can run in one thread on a single machine. But imagine that the program’s requirements have changed—as I alluded to above—and now I need to do some I/O (e.g., with a socket) from within the game_logic function. For example, this might be required if I’m trying to build a massively multiplayer online game where the state transitions are determined by a combination of the grid state and communication with other players over the Internet.
How can I extend this implementation to support such functionality? The simplest thing to do is to add blocking I/O directly into the game_logic function:
Click here to view code image
- def game_logic(state, neighbors):
... # Do some blocking input/output in here: data = my_socket.recv(100) ...
The problem with this approach is that it’s going to slow down the whole program. If the latency of the I/O required is 100 milliseconds (i.e., a reasonably good cross-country, round-trip latency on the Internet), and there are 45 cells in the grid, then each generation will take a minimum of 4.5 seconds to evaluate because each cell is processed serially in the simulate function. That’s far too slow and will make the game unplayable. It also scales poorly: If I later wanted to expand the grid to 10,000 cells, I would need over 15 minutes to evaluate each generation.
The solution is to do the I/O in parallel so each generation takes roughly 100 milliseconds, regardless of how big the grid is. The process of spawning a concurrent line of execution for each unit of work—a cell in this case—is called fan-out. Waiting for all of those concurrent units of work to finish before moving on to the next phase in a coordinated process—a generation in this case—is called fan-in.
Python provides many built-in tools for achieving fan-out and fan-in with various trade-offs. You should understand the pros and cons of each approach and choose the best tool for the job, depending on the situation. See the items that follow for details based on this Game of Life example program (Item 57: “Avoid Creating New Thread Instances for On-demand Fan-out,” Item 58: “Understand How Using Queue for Concurrency Requires Refactoring,” Item 59: “Consider ThreadPoolExecutor When Threads Are Necessary for Concurrency,” and Item 60: “Achieve Highly Concurrent I/O with Coroutines”).
7.5.1. Things to Remember¶
A program often grows to require multiple concurrent lines of execution as its scope and complexity increases.
The most common types of concurrency coordination are fan-out (generating new units of concurrency) and fan-in (waiting for existing units of concurrency to complete).
Python has many different ways of achieving fan-out and fan-in.