13. Dividing one job

Chapter 12 closed by naming a subject it had not covered. Everything concurrent in the three chapters behind us was concurrent because two different jobs were in flight — one reader totalling words while another looked for the busiest document. Cutting a single job into pieces is a different question, and it begins in the same place every time: the pieces have to add up somewhere.

The shelf’s word count is one job. Its loop runs on one core, and the obvious way to spread it is to give the loop to a reader:

struct Doc { title: str, words: int }

fn main() -> !int {
    let store = freeze region {
        var docs = List[Doc]()
        (mut docs).push(Doc { title: "regions", words: 900 })
        (mut docs).push(Doc { title: "moves", words: 640 })
        docs
    }
    var total = 0
    scope readers {
        readers.spawn(fn() { for d in store { total += d.words } })
    }
    print("{total} words")
    0
}

That program does not run, in either implementation, and the rest of this chapter is why.

13.2 The race that does not compile

Here is the compiler on it:

error[E1101]: this task writes to `total`, which it captures from the enclosing function
  --> ./s1.lu:15:47
   |
15 |         readers.spawn(fn() { for d in store { total += d.words } })
   |         ----------------------------------------------------------- the task's closure captures it at this spawn
   |                                               ^^^^^ tasks cannot mutate captured state
   |
   = note: task captures are copies, `imm` shares, or region moves (D14) — never mutable windows
     onto the parent's locals; two tasks writing one binding is the data race the memory
     model forbids. Three ways out: send results over a `channel` and let one owner mutate;
     guard truly shared state with a `Mutex` acquired in a `when` block; or, for loop-shaped
     work, use `par` with a reduction.

warning[W1101]: this write to `total` stays inside the task
  --> ./s1.lu:15:47
   |
15 |         readers.spawn(fn() { for d in store { total += d.words } })
   |                       -------------------------------------------- the closure captured it at spawn
   |                                               ^^^^^ lands on the task's own copy
   |
   = note: task captures copy (or move); the enclosing binding never sees this assignment. Send the
     result over a channel, or return it through the scope's join.

And here is the interpreter, which does not run it either:

$ lupin divide.lu
divide.lu: E1101: this task writes to `total`, which it captures from the enclosing function: unsynchronized mutable capture across tasks (D14 — copy, share `imm`, or `move`; a `sync` type mediates shared writes) [conc.task.spawn] at 347..352
$ echo $?
2

Two tools, one code, one span — 347..352 is the same five bytes the compiler underlines. This is the part of the book where the differential stops being an argument and becomes a boring fact: the specification says total may not be written from a task, and both readings of the specification say so before the program starts, in the same words about the same bytes. Chapter 3 set the pattern as two tools, one rule, and two enforcement moments — the compiler proving it before the program starts, the interpreter catching it in the act. Here the two moments collapse into one, which is what a rule looks like when both readings have finished arguing about it.

Now read where the error points, because it is not where you would put it. There is one task in that program. One task cannot race with anything — there is nothing to interleave with, and the sum it computes would be arithmetically correct. The compiler rejects it anyway, at the capture, and the phrase it uses is tasks cannot mutate captured state.

That is the rule chapter 10 stated positively and this chapter cashes. D14 gives a task body three ways to touch anything it did not create: it copies, it reads imm data, or it takes a region by move. A mutable window onto the parent’s local is not on the list, and the check does not wait to see how many tasks want one. Wolf is not detecting your race. It is declining to compile the shape a race is made of, and the shape has one instance in it.

The consequence is worth stating plainly, because it is the pitch. Add the second reader and you have written the classic lost-update bug — two tasks, one accumulator, an answer that depends on timing. You will never see it. The program that would have contained it does not build, and it did not build back when it was still a one-task program that worked. Exercise 13-3 is the two-task version, and part of what it asks is how much the two tools say about it.

W1101 is the same fact from the other side, and it is what makes the rejection teachable rather than merely correct. The closure captured total by value, so if the write were allowed to stand it would land on the task’s private copy and the parent’s total would print 0 — not a race at all, a silently wrong answer. The error says the shape is forbidden; the warning says what the shape would have done. Read them together and you know both that you may not write it and why you did not want to.

The two answers this program has

The note ends with three ways out. Here are the two that answer the program above, and you have already met both.

The first is a channel, which is the route §10.1 said existed and left to chapter 12 to build. Each reader computes its piece and sends it; one owner — main, after the join — does the adding:

struct Doc { title: str, words: int }

fn main() -> !int {
    let store = freeze region {
        var docs = List[Doc]()
        (mut docs).push(Doc { title: "regions", words: 900 })
        (mut docs).push(Doc { title: "moves", words: 640 })
        docs
    }
    let parts = channel[int](2)
    scope readers {
        readers.spawn(fn() { parts.send(store[0].words) })
        readers.spawn(fn() { parts.send(store[1].words) })
    }
    var total = 0
    for _ in 0..2 { total += parts.recv() else |_| { return 1 } }
    print("{total} words")
    0
}

$ lupin fanout.lu
1540 words

The accumulator did not disappear; it moved. total is still a plain var and it is still added to twice, but both additions now happen in one task, after the brace that guarantees the other two are finished. Nothing is guarded because nothing is shared: the readers own their partial sums, the channel carries copies, and main owns the total. This is the shape to reach for by default, and the reason is that it has no critical section to get wrong.

The explorer agrees, over every interleaving it can reach:

$ lupin conform-run fanout.lu --explore=16
fanout.lu: explored 2 schedule(s) in 2 execution(s) (DPOR; 0 slept, 0 pruned), frontier closed
  outcomes: 1 distinct — observably deterministic (every schedule agrees)
    exit(0) ×2 stdout=1540 words\n leaks=0 forest=ok — replay: --seed=0
  deadlocks: 0 · races: 0 · max depth: 3 decision(s)

outcomes: 1 distinct is §17.2’s verdict arriving early: two schedules exist, both were run, and the program has one answer. Addition commutes, so the order the two pieces arrive in cannot be observed — which is a property of the operation you combined them with, not of the language, and is the first thing to check when a divided job starts giving two answers.

The second way out is for state that is genuinely shared, where no amount of rearranging makes one owner enough. Two numbers that must agree with each other are the honest case, and §12.4 built the instrument:

fn main() -> !int {
    let words = Mutex(0)
    let docs = Mutex(0)
    scope readers {
        readers.spawn(fn() { when (words, docs) { words += 900; docs += 1 } })
        readers.spawn(fn() { when (docs, words) { words += 640; docs += 1 } })
    }
    when (words, docs) { print("{words} words in {docs} documents") }
    0
}

$ lupin guarded.lu
1540 words in 2 documents

Two things about that program are the point. The two when lines name their operands in opposite orders and it does not matter, for the reason §12.4 gave: the set is acquired whole, in a canonical order the program never writes. And when needs a set — two operands, minimum, which is why this example guards two counters rather than one. That is not a limitation to work around. A single number under a lock is a job for the program above: one owner and a channel, with no lock at all.

The same law, one boundary over

The rule the capture check enforces is not really about closures. It is about what may exist in two places at once, and a channel is the other place a value can go:

struct Doc { title: str, words: int }

fn main() -> !int {
    let inbox = channel[List[Doc]](1)
    0
}

error[E1102]: `List[Doc]` cannot be sent through a channel
 --> ./s4.lu:7:25
  |
7 |     let inbox = channel[List[Doc]](1)
  |                         ^^^^^^^^^ not a sendable payload type
  |
  = note: channel payloads must be `Copy` data, `imm` data, a region value (the send is its affine
    move), or a `sync` type ([conc.chan.type]) — sending anything else would give two tasks
    one mutable value. D14's verbs are the ways out: `move` the data into a region and send
    the region, `freeze` it into shareable `imm` data, or guard it with a `Mutex`.

$ lupin inbox.lu
inbox.lu: E1102: `List[Doc]` cannot be sent through a channel: a payload must be `Copy`, `imm`, a moved region, or a `sync` type — a bare region-interior `List` is none of those. Send the region instead [conc.chan.type] at 83..92
$ echo $?
2

Same two tools, same agreement, same clause vocabulary — and notice that no send appears in the program. The channel’s type is the claim, so the declaration is where the claim is checked, which means a sendability mistake is found at the line where you designed the queue rather than at the line where you finally used it.

Read the four admitted classes back slowly. Copy data, imm data, a region that moves, and a sync type: that is D14’s list again, the one §10.1 gave for what a task body may touch and §12.1 taught three of by showing them work. Two error codes, two boundaries, one rule — and the same note under both, offering the same three ways out. A language that had written this twice would have left you a way to smuggle a mutable value across one boundary by declaring it at the other.

Exercise 13-2 (fingers · lupin) — Nine numbers, squared and summed, on one core: build the list, square each into a second list, add them up, print the total. Run it and keep the program. The number it prints is the number every divided version of this job has to agree with, and a divided job that does not reproduce its sequential answer is not faster — it is wrong.

Exercise 13-3 (comprehension · wolf + lupin) — Two tasks increment a captured var:

fn main() -> !int {
    var hits = 0
    scope s {
        s.spawn(fn() { hits += 1 })
        s.spawn(fn() { hits += 1 })
    }
    hits
}

Before running it, predict the three fixes the note offers and which two apply here. Then run it under both tools and account for the difference in what they print — the codes and the spans agree, and the amount of output does not. Which tool tells you about the second spawn, and what does the extra warning on it say that W1101 did not?

Exercise 13-4 (spelunking · lupin) — Two programs differ in one print. Explore both and read the verdicts: ex13-4a.lu prints the arrival order and the sum, ex13-4b.lu prints only the sum, and one of them is SCHEDULE-DEPENDENT. Same tasks, same channel, same schedules. Why do the verdicts differ, and what does that mean for how you design a divided job’s output?

Where this leaves the shelf

The count is divided and the answer is still 1540. What made that uneventful was not care; it was that the two shapes available to write it in are both shapes the machine can check. A task that touches only what it copies, reads only what is frozen, and sends its answer home needs no reasoning about ordering at all, and the explorer will say so in one line. A task that must share needs the whole lock set at once, and there is no spelling for taking them one at a time.

What you cannot do is the third thing: reach out of the closure and add to the parent’s variable. C and Go both let you write that and find out later — Go’s race detector will tell you about it in a run that happens to hit it, which is a different offer from being unable to write it. Rust refuses it too, and refuses it earlier than its reputation suggests: Send and the borrow checker close the same hole with different machinery, and wolf’s claim here is not that it caught something Rust misses. The claim is narrower and it is about the diagnostic. The accumulator in the closure is not a bug this book teaches you to avoid. It is a program that does not build, in both implementations, with a note that names the three shapes you meant instead.

Exercise 13-5 (extension · lupin) — grep, wolfished: write grep(text, pattern) -> List[str] ! {EmptyPattern} returning the matching lines. Substring search is yours to write with byte slices. Why is the empty pattern an error here, when POSIX grep happily matches it everywhere?

Exercise 13-7 (comprehension · lupin) — One Euler step for two bodies on a line, gravity only, equal masses. Before running: what is v1 + v2 after the step, and is your answer exact or approximate for f64 arithmetic?