Parallel programming
This guide goes past the tour chapter on parallelism. It explains how parallel: and parallel for actually run (fork-join on a work-stealing scheduler), exactly what the compiler's race checker allows and refuses and why, the patterns that cover most real programs, how to tell whether parallelism will pay off, and what happens on WebAssembly and when a task hits a runtime error.
The model: fork-join
Tern has two parallel statements, and both are fork-join: the program forks into tasks at the start of the block and joins them at the end. Nothing started inside a block outlives it, so when the next line after the block runs, every task has finished and every result is in place.
fn count_multiples(n: int, k: int) int:
c = 0
for i in 1..n + 1:
if i % k == 0:
c += 1
return c
fn main():
both = 0
parallel: # each line is one task
threes = count_multiples(1_000_000, 3)
fives = count_multiples(1_000_000, 5)
do: # `do:` makes several lines one task
fifteens = count_multiples(1_000_000, 15)
both = fifteens
print(threes, fives, both)
squares = [0] * 10
parallel for i in 0..len(squares): # iterations spread across cores
squares[i] = i * i
print(squares)333333 200000 66666
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]- In
parallel:, every line is a task, anddo:groups several lines into one task. A variable created by a one-line task (threes = ...) is visible after the block. Variables created inside ado:are local to it (fifteensis gone after the block), so create a variable before the block, likeboth, when ado:task should fill it. parallel for i in a..b:runs the body once peri, with iterations spread across all cores. It only works on a range: to process an array, loop over its indexes,parallel for i in 0..len(xs):.returnisn't allowed inside either one. Assign to a variable and return after the block.
There are no threads, locks, futures, or channels to manage. You write what can happen at the same time; the runtime decides where it runs.
How it runs: work stealing
The runtime starts one worker thread per core the first time a parallel block runs (set TERN_THREADS=4 in the environment to use a different number). Each worker has its own queue of tasks:
- Starting a block pushes its tasks onto the current worker's queue. The task records live on the stack, so starting a task doesn't allocate.
- A worker takes its own newest task first (it is likely still in the cache). A worker with nothing to do steals the oldest task from another worker's queue, which tends to be the biggest piece of remaining work.
- The thread waiting at the end of a block doesn't sleep: it runs queued tasks until its own block's tasks are done. So blocks can nest (a task can start its own
parallel:block, and recursive functions can useparallel:) without running out of threads. parallel fordoesn't make one task per iteration. It cuts the range into up to eight chunks per worker (at most 256), and each chunk runs its iterations in an ordinary loop. A loop of ten million cheap iterations is a few hundred tasks, not ten million.
Values make this simple. A task reads the variables it uses directly: nothing is copied to start it, even a large array, because nothing else can change that array while the block runs. The race checker below is what guarantees that.
What the race checker allows
The rule for parallel: is: a variable that one task writes can't be read or written by any other task in the same block. Reading a variable from any number of tasks is fine.
The rule for parallel for is: iteration i may write only element i of an array (out[i] = ..., out[i].field = ..., fill(&out[i])), and if it writes out[i], it may read only out[i] from that array. Variables created inside the loop body belong to one iteration, so they are free to use.
These are allowed:
struct Stats:
total: int
biggest: int
fn stats_of(xs: [int]) Stats:
s = Stats(0, 0)
for x in xs:
s.total += x
s.biggest = max(s.biggest, x)
return s
fn normalize(row: mut [float]):
t = 0.0
for x in row:
t += x
for i in 0..len(row):
row[i] = row[i] / t
fn main():
data = [4, 8, 15, 16, 23, 42]
parallel: # both tasks read `data`: fine
s = stats_of(data)
doubled = data.map(fn(x) x * 2)
print(s, doubled)
rows = [[1.0, 3.0], [2.0, 2.0], [5.0, 15.0]]
parallel for i in 0..len(rows):
normalize(&rows[i]) # `&rows[i]`: writes only element i
print(rows)
prices = [10, 20, 30]
with_tax = [0] * len(prices)
parallel for i in 0..len(prices):
tax = prices[i] / 10 # a local variable of this iteration
with_tax[i] = prices[i] + tax # reads any of `prices`, writes with_tax[i]
print(with_tax)Stats{total: 108, biggest: 42} [8, 16, 30, 32, 46, 84]
[[0.25, 0.75], [0.5, 0.5], [0.25, 0.75]]
[11, 22, 33]What it refuses, and why
Each of these would be a data race: two threads touching the same memory at the same time, with at least one of them writing. In most languages that compiles and fails sometimes, at random, under load. Tern refuses it.
Two tasks writing one variable:
fn main():
hits = 0
parallel:
hits += 1
hits += 1
print(hits)5: error: data race on `hits`: the task on line 4 writes it while the task on line 5 writes it at the same time. Give each task its own variable and combine them after the blockOne task writing what another reads. bump(&count) counts as a write, since & marks an argument the function may change:
fn bump(n: mut int):
n += 1
fn main():
count = 0
parallel:
bump(&count)
print(count)8: error: data race on `count`: the task on line 7 writes it while the task on line 8 reads it at the same time. Give each task its own variable and combine them after the blockEvery iteration writing one shared variable. This is the most common mistake, and the message says how to fix it:
fn main():
total = 0
parallel for i in 0..100:
total += i
print(total)4: error: iterations of `parallel for` run at the same time, so writing `total` from every iteration would race; store per-iteration results in an array indexed by `i`, or combine results after the loopWriting any element other than out[i], including pushing onto a shared array:
fn main():
evens = [0] * 10
parallel for i in 0..5:
evens[i * 2] = i
found: [int] = []
parallel for i in 0..5:
found.push(i)
print(evens, found)4: error: iterations of `parallel for` run at the same time, so writing `evens` from every iteration would race; write only `evens[i]`, or combine results after the loop
7: error: iterations of `parallel for` run at the same time, so writing `found` from every iteration would race; write only `found[i]`, or combine results after the loopi * 2 never collides with another iteration's index, but the checker doesn't do arithmetic: it accepts exactly the loop variable as the index. Compute into out[i] and rearrange afterwards, or loop over the indexes you want to write.
Reading a neighbor while writing your own element:
fn main():
xs = [1, 2, 3, 4, 5]
parallel for i in 0..4:
xs[i] = xs[i + 1] - xs[i]
print(xs)4: error: each iteration writes `xs[i]`, so reading any other part of `xs` inside the loop would raceIteration 1 reads xs[2] while iteration 2 may be overwriting it, so the result would depend on timing. Read from one array and write another: diffs[i] = xs[i + 1] - xs[i].
Maps can't be written from parallel for at all, since two keys can land in the same internal table:
fn main():
squares: {int: int} = {}
parallel for i in 0..10:
squares[i] = i * i
print(squares)3: error: `squares` is not an arrayFill an array in parallel, then build the map from it afterwards.
Why the checker can be this simple
The checker works because of how the rest of Tern is built. There are no references or pointers, so two variables never share memory: checking by name is checking by memory. Parameters are read-only unless declared mut, and a mut argument is marked with & at the call site, so the checker sees every write a task can make by reading the task itself, without following calls into other functions. Closures capture copies, so a closure can't be a hidden way to write a variable either.
The checker is conservative: it refuses some programs that would be fine, like evens[i * 2] above. It never accepts a program that races on a Tern value.
What it does not check is the outside world. Two tasks can both print, append to the same file, or write to the same database; each of those operations is safe on its own, but their order is not defined. print lines from different tasks can appear in any order.
Pattern: per-task results, combined after
Give each task its own result variable, then combine them after the block. This is the fix the error messages suggest, and it is usually the fastest way too, since tasks never wait for each other.
struct Range:
lo, hi: int
fn sum_squares(r: Range) int:
t = 0
for i in r.lo..r.hi:
t += i * i
return t
fn main():
n = 3_000_000
third = n / 3
parallel:
a = sum_squares(Range(0, third))
b = sum_squares(Range(third, 2 * third))
c = sum_squares(Range(2 * third, n))
print(a + b + c)8999995500000500000Pattern: parallel for writing out[i]
When every element can be computed on its own, allocate the output first and have iteration i fill out[i]. Then do anything that needs the whole array (a sum, a max, a sort) in an ordinary loop afterwards.
fn collatz_steps(n: int) int:
steps = 0
x = n
while x != 1:
if x % 2 == 0:
x = x / 2
else:
x = 3 * x + 1
steps += 1
return steps
fn main():
n = 100_000
steps = [0] * n
parallel for i in 0..n:
steps[i] = collatz_steps(i + 1)
best = 0
for i in 0..n:
if steps[i] > steps[best]:
best = i
print("longest chain below", n + 1, "starts at", best + 1, "with", steps[best], "steps")longest chain below 100001 starts at 77031 with 350 stepsPattern: chunking
parallel for already chunks its range, so a loop over elements is fine as it is. Chunk by hand when each task needs its own running state: a partial sum, a map, a buffer. Loop over chunk numbers, and give each chunk one slot of the output.
fn main():
readings: [int] = []
for i in 0..1_000_000:
readings.push((i * 7919) % 1000)
chunks = 16
size = (len(readings) + chunks - 1) / chunks
over = [0] * chunks # one partial count per chunk
parallel for c in 0..chunks:
lo = c * size
hi = min(lo + size, len(readings))
n = 0
for i in lo..hi:
if readings[i] > 990:
n += 1
over[c] = n
total = 0
for n in over:
total += n
print(total, "readings over 990")9000 readings over 990A few times more chunks than cores (16 to 64 on a typical machine) gives the scheduler room to balance uneven chunks without adding much overhead.
Pattern: parallel map-reduce
Map each chunk to a partial result (here, a word-count map), then reduce the partial results into one. The partial results live in an array with one slot per chunk, so the map step passes the race checker; the reduce step is an ordinary loop.
fn count_words(lines: [str], lo: int, hi: int) {str: int}:
counts: {str: int} = {}
for i in lo..hi:
for w in lines[i].split(" "):
if w != "":
counts[w] = counts.get(w, 0) + 1
return counts
fn main():
lines: [str] = []
for i in 0..10_000:
lines.push("the quick brown fox")
lines.push("jumps over the lazy dog")
chunks = 8
size = (len(lines) + chunks - 1) / chunks
partial: [{str: int}] = [{}] * chunks
parallel for c in 0..chunks: # map
partial[c] = count_words(lines, c * size, min((c + 1) * size, len(lines)))
total: {str: int} = {}
for p in partial: # reduce
for w, n in p:
total[w] = total.get(w, 0) + n
print(total){"the": 20000, "quick": 10000, "brown": 10000, "fox": 10000, "jumps": 10000, "over": 10000, "lazy": 10000, "dog": 10000}Pattern: recursive divide and conquer
A recursive function can split its work with parallel: at each level. Below a cutoff size it runs sequentially, so the program doesn't create millions of tiny tasks.
fn sum_range(xs: [int], lo: int, hi: int) int:
if hi - lo <= 10_000: # small enough: just loop
t = 0
for i in lo..hi:
t += xs[i]
return t
mid = (lo + hi) / 2
parallel:
left = sum_range(xs, lo, mid)
right = sum_range(xs, mid, hi)
return left + right
fn main():
xs: [int] = []
for i in 0..1_000_000:
xs.push(i)
print(sum_range(xs, 0, len(xs)))499999500000Performance: when it pays off
Parallelism has a fixed cost per block: tasks must be queued, idle workers woken, and everyone joined at the end. On a 14-core laptop that cost is a few microseconds for a small parallel: block and can reach a few hundred microseconds for a parallel for when many sleeping workers have to be woken. Some measurements from that machine:
| Work | Sequential | parallel for |
|---|---|---|
| 2,000,000 Collatz chains (about 100ns each) | 220ms | 23ms |
10,000,000 × out[i] = i * 2 | 6ms | 2ms |
a parallel for over 64 elements, repeated 100,000 times | 1ms | over 9s |
The rules of thumb that follow:
- Give each block real work. Aim for at least a millisecond of total work per
parallelblock, and ideally much more. Put the parallel loop outside your hot loop, never inside it: oneparallel forover a million items beats a million small blocks. - Cheap per-element work is limited by memory, not cores. Copying or adding arrays speeds up only a little, because every core waits on the same memory.
- Uneven work is fine. If some iterations take much longer than others, idle workers steal the remaining chunks. For very uneven work, make more chunks by hand.
- Don't parallelize what is already parallel. A web server already handles requests on every core; under load, a
parallelblock inside a handler only adds overhead. It still helps a single slow request when the server is idle. - Measure.
time.now_ms()before and after, withTERN_THREADS=1for a sequential baseline of the very same binary:
tern build crunch.tn -o crunch
TERN_THREADS=1 ./crunch # everything on one core
./crunch # all coresOn WebAssembly
The wasm target has one thread, so parallel: and parallel for run their tasks one after another, in order, on that thread. The program means the same thing, since the race checker guarantees that tasks can't observe each other; it just doesn't run faster. The race checks still apply, so code that compiles for wasm also compiles, and is race-free, natively.
You can see the sequential behavior on a native build with TERN_THREADS=1.
Runtime errors inside tasks
A runtime error inside a task (an index out of range, a missing map key, division by zero) behaves like one anywhere else:
- In a program, it prints
runtime error in f (prog.tn:N): ...and ends the program with exit status 2. The block never completes, and no code after it runs. - In a web request, the block first waits for all of its tasks to finish, then the error is raised in the request, which answers
500while the server keeps running. See Building web apps.
fn main():
out = [0] * 1000
parallel for i in 0..1000:
out[i] = 100 / (500 - i) # iteration 500 divides by zero
print("never printed", out[0])$ tern run divide.tn
runtime error in main (divide.tn:4): division by zero
$ echo $?
2There is no way to catch the error inside the task. When a task can fail in an expected way (bad input, say), return a status in its result instead, and check it after the block:
struct Parsed:
ok: bool
value: int
fn parse_all(lines: [str]) [Parsed]:
out = [Parsed(false, 0)] * len(lines)
parallel for i in 0..len(lines):
n = lines[i].trim().to_int(-1)
if n >= 0:
out[i] = Parsed(true, n)
return out
fn main():
results = parse_all(["12", "7", "oops", "30"])
total = 0
for i, r in results:
if r.ok:
total += r.value
else:
print("line", i + 1, "is not a number")
print("total", total)line 3 is not a number
total 49Long-running tasks
parallel is for work that starts and finishes together. For tasks that outlive a block, channels between tasks, or shared state behind a lock, there is the task module, which is documented separately.