Tern

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)
Output
333333 200000 66666
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
  • In parallel:, every line is a task, and do: groups several lines into one task. A variable created by a one-line task (threes = ...) is visible after the block. Variables created inside a do: are local to it (fifteens is gone after the block), so create a variable before the block, like both, when a do: task should fill it.
  • parallel for i in a..b: runs the body once per i, 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):.
  • return isn'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 use parallel:) without running out of threads.
  • parallel for doesn'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)
Output
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:

Does not compile
fn main():
    hits = 0
    parallel:
        hits += 1
        hits += 1
    print(hits)
Compiler output
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 block

One task writing what another reads. bump(&count) counts as a write, since & marks an argument the function may change:

Does not compile
fn bump(n: mut int):
    n += 1

fn main():
    count = 0
    parallel:
        bump(&count)
        print(count)
Compiler output
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 block

Every iteration writing one shared variable. This is the most common mistake, and the message says how to fix it:

Does not compile
fn main():
    total = 0
    parallel for i in 0..100:
        total += i
    print(total)
Compiler output
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 loop

Writing any element other than out[i], including pushing onto a shared array:

Does not compile
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)
Compiler output
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 loop

i * 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:

Does not compile
fn main():
    xs = [1, 2, 3, 4, 5]
    parallel for i in 0..4:
        xs[i] = xs[i + 1] - xs[i]
    print(xs)
Compiler output
4: error: each iteration writes `xs[i]`, so reading any other part of `xs` inside the loop would race

Iteration 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:

Does not compile
fn main():
    squares: {int: int} = {}
    parallel for i in 0..10:
        squares[i] = i * i
    print(squares)
Compiler output
3: error: `squares` is not an array

Fill 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)
Output
8999995500000500000

Pattern: 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")
Output
longest chain below 100001 starts at 77031 with 350 steps

Pattern: 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")
Output
9000 readings over 990

A 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)
Output
{"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)))
Output
499999500000

Performance: 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:

WorkSequentialparallel for
2,000,000 Collatz chains (about 100ns each)220ms23ms
10,000,000 × out[i] = i * 26ms2ms
a parallel for over 64 elements, repeated 100,000 times1msover 9s

The rules of thumb that follow:

  • Give each block real work. Aim for at least a millisecond of total work per parallel block, and ideally much more. Put the parallel loop outside your hot loop, never inside it: one parallel for over 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 parallel block 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, with TERN_THREADS=1 for a sequential baseline of the very same binary:
tern build crunch.tn -o crunch
TERN_THREADS=1 ./crunch     # everything on one core
./crunch                    # all cores

On 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 500 while the server keeps running. See Building web apps.
Compiles (not run here)
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 $?
2

There 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)
Output
line 3 is not a number
total 49

Long-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.

Source: docs/guides/parallelism.md. Every example on this page is compiled and run by tern x test docs.