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.

13.1 par

Chapter 6 ended on a promise, in a box, on a page that has been in your hands since Part 1: the word counter’s for word in text.words() loop “becomes parallel by changing one call”, and this section was named as the place that diff gets checked. Since wolf 0.2.15 there is a par to do it with. Here is the diff, here is what it costs, and here is the part of the box that was not right.

xs.par(f) maps f over a list, in parallel, and answers a list. It is [conc.task.par], and it is defined by desugaring to a scope full of spawns — it adds no semantics to this chapter, only shape. Which means it needs a list to map over, and chapter 6’s count takes one str and answers one tally. One string is not a list of anything. So before a single call can change, the text has to arrive in pieces and the tallies have to be added back together.

Here is that program, still running on one core:

fn count(text: str) -> Map[str, int] {
    var tally = Map[str, int]()
    for word in text.words() {
        let w = word.lower()
        tally[w] = (tally[w] else 0) + 1
    }
    tally
}

fn main() -> !int {
    let pieces = [
        "The wolf runs and the moon watches over the wolf",
        "The pack answers and the moon does not",
        "A wolf is a wolf and the moon is the moon",
    ]
    var parts = List[Map[str, int]]()
    for p in pieces { (mut parts).push(take count(p)) }
    var total = Map[str, int]()
    for part in parts {
        for (w, n) in part.pairs() { total[w] = (total[w] else 0) + n }
    }
    print("the {total["the"]} wolf {total["wolf"]} moon {total["moon"]}")
    0
}

$ wolf run wordcount.lu
the 7 wolf 4 moon 4

Two things in it are worth naming before the parallel version arrives, because both are already here and neither is the price of parallelism. The first is the split: pieces is the text having been cut up. The second is the merge, the loop over parts that adds each piece’s tally into total. A divided job’s pieces have to add up somewhere, and that somewhere is the same loop whether the pieces were counted one after another or all at once. The merge is what splitting costs, not what par costs. The take on the push is chapter 5’s rule doing its job: handing a value to a container copies it, and count(p) is a temporary nobody else holds, so take says hand it over for good and the copy does not happen.

And now the diff:

fn count(text: str) -> Map[str, int] {
    var tally = Map[str, int]()
    for word in text.words() {
        let w = word.lower()
        tally[w] = (tally[w] else 0) + 1
    }
    tally
}

fn main() -> !int {
    let pieces = [
        "The wolf runs and the moon watches over the wolf",
        "The pack answers and the moon does not",
        "A wolf is a wolf and the moon is the moon",
    ]
    let parts = pieces.par(count)
    var total = Map[str, int]()
    for part in parts {
        for (w, n) in part.pairs() { total[w] = (total[w] else 0) + n }
    }
    print("the {total["the"]} wolf {total["wolf"]} moon {total["moon"]}")
    0
}

$ wolf run wordcount.lu
the 7 wolf 4 moon 4

One call. count is untouched and so is its signature; the merge loop is untouched; pieces is untouched; the two programs print the same bytes. The two lines that pushed each tally in turn are pieces.par(count).

Now the correction chapter 6 is owed. Its box said “signature, types, top, and main all stand”. The signature stands, the types stand, top stands — main does not. It has to hand par a list, so the split and the merge live there, and in §6.5’s program they do not exist yet. Against a counter that already works on pieces, par is one call and the box is exactly true. Against §6.5’s counter, which takes one string, main is restructured first and then one call changes. The promise is kept in the first sense and overstated in the second, and the distance between them is one paragraph of main — not a rewrite, which is what the box said to hold us to.

Three guarantees make that diff safe to make, and all three are load-bearing above. Results come back in input order, whatever the schedule: out[i] is f(xs[i]) for every i, so the merge sees the same maps in the same order as the serial version and no reordering can change what the program prints ([conc.task.par.order]). The tasks join inside the call — par is a scope that opens and closes between the parentheses — so by the time the next line runs, every piece is counted. And f is checked as a spawned closure’s body, so a write to captured enclosing state is E1101 at the write, with the par named as the spawn site ([conc.task.par.capture]). That last one is §13.2’s whole subject, from the other end.

par also does not spawn a task per element, and is not allowed to: the runtime cuts 0..n into k = min(n, W) contiguous chunks, where W is its worker count, and a task per element is not a conforming desugar ([conc.task.par.chunk]). Three pieces above means at most three tasks. No clause lets a program ask what k was.

Now the number, which a chapter about parallelism is usually coy about.

Measured on this book’s own machine: an Apple M5 Pro, 18 logical cores (12 performance and 6 efficiency), wolf 0.2.15, each program built with wolf build and the binary timed, so no compile time is counted. The input is 72 pieces of about 380,000 characters each — the same three sentences above, repeated, so that every piece holds real work and there are four pieces per core.

Read the first row again. The word counter, parallelized by changing one call, on a machine with eighteen cores, is more than twice as slow as the version that used one. Nothing is wrong with the program; both versions print the same bytes, and both are conforming.

What is wrong is the body. word.lower() allocates a fresh str for every word in the text — about fourteen million of them across the seventy-two pieces — and a task’s allocations land where a task’s allocations land: tasks run with the process root as their ambient region, and the native root arena serializes allocation behind one lock ([conc.task.par.cost]). Eighteen workers that all allocate spend their time queueing at that lock instead of counting. The tell is not in the wall clock but beside it: the serial run spends 0.02 s inside the kernel and the parallel run spends 28.75 s there, spread across its workers. That is not work. That is waiting.

The second row is the same program with the one allocation taken out — counting the word view words() already handed us instead of a lowercased copy of it — run on the same input with the same one-call diff. It is 11.4x faster on 18 cores. The third row is a loop that only computes, and it gets 16.6x. Nothing about par changed between the three rows. What changed is what f does between spawns.

The specification says this in one sentence, and it is the sentence to carry out of this section:

Speedup is not promised: a list shorter than W, or an f cheaper than a spawn, can make xs.par(f) slower than xs.map(f), and both are conforming.

So chapter 6’s promise, stated honestly, is this: the diff is one call, and what the call buys is a property of f, not a property of par. The compiler will not tell you which row of that table your program is in. Measuring it is the job, and it is a smaller job than the rewrite you were promised you would not have to do.

Two notes on the machines, both of which this section ran on. lupin executes xs.par(f) sequentially and prints the same bytes, which is conforming rather than a shortfall — input order is the guarantee, not concurrency — so the timings above are the compiler’s alone. And the serial twin above is spelled as a loop, not as pieces.map(count), although map is par’s exact serial partner and the diff between those two is a single word. map is a std.list function that has to reach its home module ([type.method.resolve]), and this book pins no std for the tools to find (wolf-book#39), so pieces.map(count) is E0301 under wolf and unsupported under lupin on the machines that check these pages. pieces.par(count) runs on both without one: par is the language’s own builtin ([type.comb.builtin]), not a library function. The loop printed above is what map would have written.

par is what the language hands you when the job already divides into a list. The rest of this chapter is what happens when you divide one by hand instead, and the obvious way to spread a loop is to give it 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 §13.2 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 give each task
     its own copy and combine the results after the scope joins.

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 12:47
$ echo $?
2

Both tools reject it with the same code, and both point at the same five characters: the total inside the closure. 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 declines to compile the shape a race is made of, and the shape has one instance in it.

The consequence 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, not 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 capture check enforces a rule about what may exist in two places at once; a closure is one boundary that rule crosses, 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), a `sync` type, or a struct, enum or tuple whose every field is one of those
    ([conc.chan.type], [conc.chan.payload]) — 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 4:25
$ echo $?
2

Both tools refuse the declaration in the same clause vocabulary. 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, not 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. E1101 and E1102 enforce one rule at two boundaries, with 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 wrong, not fast.

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. The two shapes available to write it in are both shapes the machine can check, which is what made that uneventful. 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. Wolf’s claim is narrower than Rust’s, 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?

Exercise 13-9 (extension · lupin). The caesar shift, sequential on purpose: shift(s, k) moves each lowercase letter k places with wraparound (chars, casts, % 26) and passes everything else through. Encode a line with k = 3, decode with the same function, and make main exit nonzero if the round trip misses. Two questions: what number decodes for k = 3, and — the extension — if the shift instead came from the letters of a key word repeating along the message, what would decode have to do that it does not do now?

Exercise 13-10 (comprehension + extension · lupin). 13-5’s byte scan found lines; this one counts hits. Write count(hay, needle, overlapping) — the same hay[i..i + needle.len] == needle probe — where the flag decides whether a hit advances i by one byte or by the needle’s length. Predict both answers for "aaaa" / "aa" before running. Which convention does a text editor’s find-and-replace need, and what goes wrong under the other one?

Exercise 13-11 (extension · lupin). 13-5 searched a str with str slices. Do it a layer down, over bytes, and lend the haystack rather than handing it over: find(hay, needle) -> int takes two List[int] byte views and answers the first index where the needle starts, or -1. The window comparison belongs in its own function, so the slice happens inside a callee working on a view it does not own. Two questions: what does the caller still hold after the call, and how many bytes does one window cost?