Tern

11. Parallelism

Modern computers have many cores, and Tern makes using them a matter of one keyword. This chapter covers parallel: blocks (run a few different things at once), do: groups, and parallel for (spread a loop across all cores). Because Tern has no shared references, the compiler can check every parallel block for data races, and this chapter shows the errors it gives and how to fix each one.

parallel: blocks

Inside a parallel: block, every statement is a separate task, and all of them run at the same time. The block ends when every task has finished:

fn count_primes(lo: int, hi: int) int:
    n = 0
    for x in lo..hi:
        if x < 2:
            continue
        prime = true
        d = 2
        while d * d <= x:
            if x % d == 0:
                prime = false
                break
            d += 1
        if prime:
            n += 1
    return n

fn main():
    parallel:
        low = count_primes(0, 100_000)
        high = count_primes(100_000, 200_000)
    print(low, high, low + high)
Output
9592 8392 17984

The two calls run on two cores. A variable created by a one-line task, like low and high, can be used after the block. There are no threads to create, no locks, and nothing to join: the block itself waits.

do: groups

When one task needs several statements, group them with do:. The statements inside a do: run in order, as one task, alongside the other tasks of the block:

fn sum(xs: [int]) int:
    t = 0
    for x in xs:
        t += x
    return t

fn main():
    data = [4, 8, 15, 16, 23, 42]
    evens = 0
    largest = 0
    parallel:
        total = sum(data)
        do:
            ev = data.filter(fn(x) x % 2 == 0)
            evens = len(ev)
        do:
            for x in data:
                largest = max(largest, x)
    print(total, evens, largest)
Output
108 4 42

Variables created inside a do: group are local to it, like ev here. To use a value computed in a do: group after the block, create the variable before the block (as with evens and largest) and assign it inside. Every task can read data, because nobody writes it.

The race checker

A data race happens when two tasks use the same variable at the same time and at least one of them writes it. The result then depends on timing, and the bug may show up once in a thousand runs. In Tern, a race is a compile error:

Does not compile
fn main():
    hits = 0
    parallel:
        hits += 1
        hits += 1
    config = [1, 2, 3]
    parallel:
        config.push(4)
        print(len(config))
    print(hits, config)
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
9: error: data race on `config`: the task on line 8 writes it while the task on line 9 reads it at the same time. Give each task its own variable and combine them after the block

The checker can be exact because Tern has no references. A task can only reach a variable by naming it (or passing it with & to a mut parameter), so the compiler sees every read and write. In a language with pointers, two innocent-looking names might refer to the same data.

The fix is what the message says: give each task its own variable, and combine after the block, when the tasks are done:

fn main():
    parallel:
        a = 1
        b = 1
    hits = a + b
    config = [1, 2, 3]
    bigger = config
    parallel:
        bigger.push(4)
        n = len(config)
    print(hits, bigger, n)
Output
2 [1, 2, 3, 4] 3

bigger = config is a copy, so the first task changes its own array while the second task reads the original. Thanks to copy-on-write, the copy is made only when push runs.

parallel for

parallel for i in a..b: runs the iterations of a loop at the same time, spread across all cores. It is the tool for "do the same work to every element":

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 1..n:
        steps[i] = collatz_steps(i)
    best = 1
    for i in 1..n:
        if steps[i] > steps[best]:
            best = i
    print(best, "takes", steps[best], "steps")
Output
77031 takes 350 steps

The rule is simple: iteration i may write only element i of an array (steps[i], or fields of it, like ps[i].x). It may read anything that no iteration writes.

parallel for races and their fixes

The two classic mistakes are accumulating into one variable, and reading a neighbor that another iteration is writing:

Does not compile
fn main():
    xs = [3, 1, 4, 1, 5, 9, 2, 6]
    total = 0
    parallel for i in 0..len(xs):
        total += xs[i]
    smooth = [0] * len(xs)
    parallel for i in 1..len(xs):
        smooth[i] = smooth[i - 1] + xs[i]
    print(total, smooth)
Compiler output
5: 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
8: error: each iteration writes `smooth[i]`, so reading any other part of `smooth` inside the loop would race

For a total, let each iteration write its own slot, then combine after the loop. When each iteration does very little (like one addition), give each iteration a whole chunk of the array instead, so the per-task overhead is spread over real work:

fn main():
    xs = [0] * 1_000_000
    for i in 0..len(xs):
        xs[i] = i % 7
    chunks = 8
    size = (len(xs) + chunks - 1) / chunks
    partial = [0] * chunks
    parallel for c in 0..chunks:
        lo = c * size
        hi = min(lo + size, len(xs))
        t = 0
        for i in lo..hi:
            t += xs[i]
        partial[c] = t
    total = 0
    for p in partial:
        total += p
    print(total)
Output
2999997

The running-sum loop (smooth[i] = smooth[i - 1] + ...) is different: each step depends on the previous one, so it is not parallel work at all. Write it as an ordinary for loop. The compiler's error is telling you something true about the algorithm.

When to use it

  • Use parallel: for a few independent, sizable pieces of work: two searches, loading and parsing different files, computing several statistics of one data set.
  • Use parallel for when every element needs the same, reasonably expensive work.
  • Don't parallelize tiny loops. Starting tasks costs a little; if each iteration is a single addition, the plain loop is faster. Measure.
  • Output from print inside parallel tasks can appear in any order. Compute in parallel, then print after the block.
  • On WebAssembly, parallel blocks run their tasks one after another, so programs still work there, just without the speedup.

For longer-lived concurrency (work that outlives a block, or tasks that talk to each other), see the parallel programming guide.

Try it

You have the scores of 8 students on 5 tests each, as an array of arrays. With a parallel for, compute every student's average into an array of floats. Then, in a parallel: block, compute the best average and the worst average at the same time (two do: groups), and print both.

Solution

fn main():
    scores = [
        [70, 80, 90, 85, 75], [55, 60, 65, 70, 50], [95, 90, 100, 85, 90], [80, 80, 80, 80, 80],
        [60, 75, 70, 65, 80], [88, 92, 79, 85, 91], [45, 50, 60, 55, 40], [77, 83, 90, 70, 80],
    ]
    avg = [0.0] * len(scores)
    parallel for i in 0..len(scores):
        t = 0
        for s in scores[i]:
            t += s
        avg[i] = float(t) / float(len(scores[i]))
    best = avg[0]
    worst = avg[0]
    parallel:
        do:
            for a in avg:
                best = max(best, a)
        do:
            for a in avg:
                worst = min(worst, a)
    print(avg)
    print("best", best, "worst", worst)
Output
[80.0, 60.0, 92.0, 80.0, 70.0, 87.0, 50.0, 80.0]
best 92.0 worst 50.0

Next: 12. Modules and packages. Reference: §15 Parallelism. Guide: Parallel programming.

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