liveBook · Manning

Interleaving

As explained in Grokking Simplicity

An ordering formed by combining steps from multiple timelines while preserving the order of steps within each timeline.

Interleaving is an ordering formed by combining steps from multiple timelines while preserving each timeline’s internal order. An action from one timeline may occur between two actions from another when the execution model permits it. section 15.11

Use timeline diagrams to make possible orderings visible:

  • Place actions that may run simultaneously or out of order on separate timelines. section 15.22
  • Use dotted lines for required ordering, such as an asynchronous callback following its request. section 15.22
  • Combine actions that cannot interleave into one box, and consolidate a timeline that starts another. section 15.22 section 15.20

Two clicks, different answers

Two click-handler timelines can produce ten possible orderings. Slow clicks may produce the correct result, while a fast interleaving can produce the wrong value because the actions occur in a different order. Tracing one problematic ordering exposes the bug, but longer timelines can create too many orderings to inspect manually. section 15.24 section 15.25

Image

Inspect the click-handler timeline to follow a concrete ordering and see how interleaving changes the resulting variable values. section 15.25

The execution model determines how much interleaving is possible. JavaScript’s synchronous actions do not interleave on its single main thread, but asynchronous callbacks run later at an unknown time and reintroduce separate timeline boxes. Multithreaded systems allow broader interleaving, while message-passing processes avoid shared memory. section 15.14 section 15.8

How Grokking Simplicity covers it

How deep it goes
Defines interleaving, diagrams its constraints, simplifies timelines, and traces concrete orderings without exhaustively solving every possibility.
Examples
Demonstrates interleaving with Java increment operations, JavaScript click handlers, and add-to-cart callback timelines.
What it assumes
Assumes basic sequential code and asynchronous operations, while defining timelines, actions, and interleaving through concrete diagrams.
What you can do after
Diagnose ordering bugs by drawing timelines, identifying possible interleavings, and applying execution-model constraints.
How it connects
Connects interleaving with timeline diagrams, asynchronous callbacks, threads, shared resources, message passing, and locks.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Grokking Simplicity. The section links point to the parts of the book it draws on.