Parallelism

Race freedom

A data race in Brine is a compile error. Inside a par body, variables from outside are read-only, with one exception: par for i in ... may write an outer array at exactly [i], and then may not touch that array any other way. Because Brine values never alias, that rule is all it takes.

The rule

Inside the body of par for, par [...], a par reduction or par(a, b):

Outer variables are read-only. You can’t assign them, call a method that changes them (push, pop, sort, insert, …), change a map, or pass them as ref.
The exception: out[i]. In par for i in lo..hi, an array declared outside the loop may be written at out[i], where the index is exactly the loop variable. The element may be a struct or an array itself (out[i].x = ..., grid[i][j] = ...).
An array written at out[i] isn’t accessed any other way in that loop. No out[i - 1], no len(out), no passing out to a function.
No effects that depend on order. write_file, run, exit, the os calls that change things outside the program, and world communication aren’t allowed. print is.
Every iteration runs to its end. No break, no return, no ?. continue is fine.

Variables declared inside the body are local to one iteration, and you can do anything with them.

fn fill(ref xs: [int]):
    for k in 0..len(xs):
        xs[k] = k

fn main():
    let base = [10, 20, 30, 40]
    var out = [0] * 4
    par for i in 0..4:
        var local = [0] * 3  # local to this iteration
        fill(ref local)  # `ref` to a local is fine
        local.push(base[i])  # reading outer values is fine
        out[i] = len(local) + local[3]
    print(out)

[14, 24, 34, 44]

Why this is enough

A data race needs two threads touching the same memory at the same time, one of them writing. In most languages the compiler can’t rule that out, because two names can point at the same memory. In Brine they can’t:

Values, not shared objects. let b = a copies, and arguments are passed by value. Arrays and strings share memory only until one copy is changed (copy-on-write), and the reference counts are atomic. Nothing you can write reaches another variable’s memory.
References are second-class. A ref can’t be stored in a struct or an array, or returned, so the compiler always knows which variable a ref names. let r = ref out inside a par body counts as out.
Functions can only change what they are given as ref. A function called from a par body gets copies of outer values, and rule 1 stops it from getting a ref to one.

So the only memory several iterations can reach is the outer variables. Rule 1 makes them read-only. Rule 2 lets iteration i write element i, which no other iteration writes, and rule 3 makes sure no other iteration reads it while it changes. With no writes in common and no reads of another iteration’s writes, there is no race, and the result can’t depend on timing.

The rules are checked on the body as written, not by analysis of what the indexes might be, so the errors are predictable: the same code is accepted or rejected on every machine.

Assigning an outer variable

fn main():
    let xs = [1, 2, 3, 4]
    var total = 0
    par for i in 0..len(xs):
        total += xs[i]
    print(total)

error[E0501]: cannot assign to `total` inside a `par` body
 --> race.br:5:9
  |
5 |         total += xs[i]
  |         ^^^^^ would be a data race
  |
  = note: `total` is shared by all parallel iterations
  = help: a `par for` may only write `total[i]` (its own element); to combine values use `par sum(...)`, `par [...]`, or a sequential loop
  = run `brine explain E0501` for more about this error
error: could not compile due to 1 error

Combining values from every iteration is what reductions are for:

fn main():
    let xs = [1, 2, 3, 4]
    let total = par sum(x for x in xs)
    print(total)

A reduction is both race-free and deterministic, and with a filter it also covers counting (par sum(1 for x in xs if x > 0)), finding the largest (par max), and testing (par any, par all).

Writing another element

out[i] must use exactly the loop variable. Any other index could be the one another iteration writes:

fn main():
    let n = 5
    var out = [0] * (2 * n)
    par for i in 0..n:
        out[2 * i] = i * i
    print(out)

error[E0501]: cannot assign to `out` inside a `par` body
 --> stride.br:5:9
  |
5 |         out[2 * i] = i * i
  |         ^^^^^^^^^^ would be a data race
  |
  = note: `out` is shared by all parallel iterations
  = help: a `par for` may only write `out[i]` (its own element); to combine values use `par sum(...)`, `par [...]`, or a sequential loop
  = run `brine explain E0501` for more about this error
error: could not compile due to 1 error

Loop over the elements you write instead, and work out the input from the output index:

fn main():
    let n = 5
    var out = [0] * (2 * n)
    par for j in 0..2 * n:
        if j % 2 == 0:
            out[j] = (j / 2) * (j / 2)
    print(out)

[0, 0, 1, 0, 4, 0, 9, 0, 16, 0]

Reading the array you write

Once a loop writes xs[i], every other use of xs in it is an error, reads included, because the neighbouring element may be changing at that moment:

fn main():
    var xs = [0.0, 3.0, 9.0, 3.0, 0.0, 6.0]
    par for i in 1..len(xs) - 1:
        xs[i] = (xs[i - 1] + xs[i] + xs[i + 1]) / 3.0
    print(xs)

error[E0502]: `xs` is written at `xs[i]` in this `par for`, so it can't be accessed any other way
 --> smooth.br:4:18
  |
4 |         xs[i] = (xs[i - 1] + xs[i] + xs[i + 1]) / 3.0
  |                  ^^^^^^^^^ accessed here
  |
  = note: other iterations may be writing to the other elements at the same time
  = help: only use `xs[i]` inside the loop, or copy the data you need before the loop
  = run `brine explain E0502` for more about this error
error: could not compile due to 1 error

Read from a copy made before the loop. The copy costs nothing until the loop writes to xs (copy-on-write), and the result no longer depends on which neighbour was updated first:

fn main():
    var xs = [0.0, 3.0, 9.0, 3.0, 0.0, 6.0]
    let old = xs
    par for i in 1..len(old) - 1:
        xs[i] = (old[i - 1] + old[i] + old[i + 1]) / 3.0
    print(xs)

[0.0, 4.0, 5.0, 4.0, 3.0, 6.0]

A computation where each element needs the new value of the one before it (a running total, for example) is sequential by nature. Write it as a sequential loop.

Changing an outer array

push, pop, insert, sort and the other changing methods count as writes:

fn is_special(i: int) -> bool:
    return i % 7 == 0 and i % 2 == 1

fn main():
    var found: [int] = []
    par for i in 0..100:
        if is_special(i):
            found.push(i)
    print(found)

error[E0501]: cannot push to `found` inside a `par` body
 --> collect.br:8:13
  |
8 |             found.push(i)
  |             ^^^^^ would be a data race
  |
  = note: `found` is shared by all parallel iterations
  = help: a `par for` may only write `found[i]` (its own element); to combine values use `par sum(...)`, `par [...]`, or a sequential loop
  = run `brine explain E0501` for more about this error
error: could not compile due to 1 error

Compute the expensive part in parallel, one result per element, then collect sequentially. This also keeps the results in order, which pushing from many threads wouldn’t:

fn is_special(i: int) -> bool:
    return i % 7 == 0 and i % 2 == 1

fn main():
    let n = 100
    let keep = par [is_special(i) for i in 0..n]
    let found = [i for i in 0..n if keep[i]]
    let count = par sum(1 for i in 0..n if keep[i])
    print(found, count)

[7, 21, 35, 49, 63, 77, 91] 7

Passing an outer variable as ref

A ref argument lets the function change the variable, so an outer variable can’t be passed as ref from a par body:

fn record(ref log: [str], msg: str):
    log.push(msg)

fn main():
    var log: [str] = []
    par for i in 0..4:
        record(ref log, f"step {i}")
    print(log)

error[E0501]: cannot pass as `ref` `log` inside a `par` body
 --> log.br:7:20
  |
7 |         record(ref log, f"step {i}")
  |                    ^^^ would be a data race
  |
  = note: `log` is shared by all parallel iterations
  = help: a `par for` may only write `log[i]` (its own element); to combine values use `par sum(...)`, `par [...]`, or a sequential loop
  = run `brine explain E0501` for more about this error
error: could not compile due to 1 error

Return the value instead and let par [...] collect it:

fn main():
    let log = par [f"step {i}" for i in 0..4]
    print(log)

["step 0", "step 1", "step 2", "step 3"]

Changing a map

Maps can be read in a par body but not changed, not even at the loop index:

fn main():
    var squares: {int: int} = {}
    par for i in 0..5:
        squares[i] = i * i
    print(squares)

error[E0501]: cannot assign to `squares` inside a `par` body
 --> squares.br:4:9
  |
4 |         squares[i] = i * i
  |         ^^^^^^^^^^ would be a data race
  |
  = note: `squares` is shared by all parallel iterations
  = help: maps can't be changed inside `par`; compute the values with `par [...]`, then fill the map in a sequential loop
  = run `brine explain E0501` for more about this error
error: could not compile due to 1 error

fn main():
    let vals = par [i * i for i in 0..5]
    var squares: {int: int} = {}
    for i in 0..5:
        squares[i] = vals[i]
    print(squares)

{0: 0, 1: 1, 2: 4, 3: 9, 4: 16}

Effects that depend on order

Writing files and starting processes change the world outside the program, and the order of those changes would depend on timing. They’re E0503, as are exit, world communication, and the os functions that change things (os.spawn, os.wait, os.poll, os.kill, os.make_dir, os.remove_file, os.rename, os.sleep, os.enable_ansi):

fn main():
    par for i in 0..4:
        let r = write_file(f"part{i}.txt", f"part {i}\n")

error[E0503]: `write_file` can't be called inside a `par` body
 --> files.br:3:17
  |
3 |         let r = write_file(f"part{i}.txt", f"part {i}\n")
  |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ not allowed here
  |
  = help: its effects would happen in an unpredictable order; do it before or after the `par`
  = run `brine explain E0503` for more about this error
error: could not compile due to 1 error

Build the contents in parallel, then write them in order:

fn main():
    let texts = par [f"part {i}\n" for i in 0..4]
    for i in 0..4:
        match write_file(f"part{i}.txt", texts[i]):
            case Ok(_):
                pass
            case Err(e):
                eprint(e)
    print("wrote", len(texts), "files")

wrote 4 files

Reading is allowed: read_file, file_exists, getenv and clock can be called in a par body. So can print and eprint. Each call writes its whole line at once, but the lines of different iterations come out in whatever order the iterations run, so don’t rely on that order.

Leaving the loop early

fn main():
    let xs = [3, 8, 1, 9]
    par for i in 0..len(xs):
        if xs[i] > 5:
            break

error[E0505]: `break` is not allowed inside a `par for`
 --> first.br:5:13
  |
5 |             break
  |             ^^^^^ parallel iterations can't stop each other
  |
  = help: use `continue` to skip an iteration, or a sequential `for` loop
  = run `brine explain E0505` for more about this error
error: could not compile due to 1 error

return is rejected the same way, and ? (which may return) is E0342. To find the first match, ask with a reduction:

fn main():
    let xs = [3, 8, 1, 9, 4]
    if par any(x > 5 for x in xs):
        let first = par min(i for i in 0..len(xs) if xs[i] > 5)
        print(first)

Restructuring patterns

Sequential habit	Race-free version
`total += f(x)` in a loop	`par sum(f(x) for x in xs)`
counting matches	`par sum(1 for x in xs if p(x))`
tracking the best so far	`par max(...)`, `par min(...)`; for the index, `par min(i for i in 0..n if xs[i] == best)`
`found.push(x)` when `p(x)`	`let keep = par [p(x) for x in xs]`, then `[xs[i] for i in 0..n if keep[i]]`
updating an array in place from its neighbours	copy first (`let old = xs`), read `old`, write `xs[i]`
filling a map	`par [...]` for the values, then a sequential loop for the map
a histogram	`par for b in 0..bins:` with `hist[b] = sum(1 for x in xs if bucket(x) == b)`, or one `par sum` per bin
writing results to files	`par [...]` for the contents, then write sequentially
`break` on the first match	`par any(...)`, then `par min(i ... if ...)`

Rules

In a par body, outer variables are read-only; par for i in a range may write out[i] with exactly the loop variable (E0501).
An array written at out[i] can’t be used any other way in that loop (E0502).
No write_file, run, exit, changing os calls or world in par (E0503); print and reads are allowed.
No break or return (E0505); continue is fine.
par for has no invariants (E0507) and par [...] has no if filter (E0508).