# Race freedom > The compile-time rule that makes every par body free of data races, why it is enough, every error it reports (E0501, E0502, E0503, E0505), and how to restructure code that breaks it. Source: https://docs.brinelang.org/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 [Section titled “The rule”](#the-rule) Inside the body of `par for`, `par [...]`, a `par` reduction or `par(a, b)`: 1. **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`. 2. **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] = ...`). 3. **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. 4. **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. 5. **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. ```brine 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) ``` Output ```text [14, 24, 34, 44] ``` ## Why this is enough [Section titled “Why this is enough”](#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 [Section titled “Assigning an outer variable”](#assigning-an-outer-variable) race.br ```brine fn main(): let xs = [1, 2, 3, 4] var total = 0 par for i in 0..len(xs): total += xs[i] print(total) ``` ```text 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: ```brine fn main(): let xs = [1, 2, 3, 4] let total = par sum(x for x in xs) print(total) ``` Output ```text 10 ``` A reduction is both race-free and [deterministic](/parallelism/deterministic-reductions/), 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 [Section titled “Writing another element”](#writing-another-element) `out[i]` must use exactly the loop variable. Any other index could be the one another iteration writes: stride.br ```brine fn main(): let n = 5 var out = [0] * (2 * n) par for i in 0..n: out[2 * i] = i * i print(out) ``` ```text 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: ```brine 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) ``` Output ```text [0, 0, 1, 0, 4, 0, 9, 0, 16, 0] ``` ## Reading the array you write [Section titled “Reading the array you write”](#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: smooth.br ```brine 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) ``` ```text 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: ```brine 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) ``` Output ```text [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 [Section titled “Changing an outer array”](#changing-an-outer-array) `push`, `pop`, `insert`, `sort` and the other changing methods count as writes: collect.br ```brine 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) ``` ```text 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: ```brine 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) ``` Output ```text [7, 21, 35, 49, 63, 77, 91] 7 ``` ## Passing an outer variable as ref [Section titled “Passing an outer variable as ref”](#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: log.br ```brine 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) ``` ```text 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: ```brine fn main(): let log = par [f"step {i}" for i in 0..4] print(log) ``` Output ```text ["step 0", "step 1", "step 2", "step 3"] ``` ## Changing a map [Section titled “Changing a map”](#changing-a-map) Maps can be read in a `par` body but not changed, not even at the loop index: squares.br ```brine fn main(): var squares: {int: int} = {} par for i in 0..5: squares[i] = i * i print(squares) ``` ```text 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 ``` ```brine 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) ``` Output ```text {0: 0, 1: 1, 2: 4, 3: 9, 4: 16} ``` ## Effects that depend on order [Section titled “Effects that depend on order”](#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](/reference/errors/#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`): files.br ```brine fn main(): par for i in 0..4: let r = write_file(f"part{i}.txt", f"part {i}\n") ``` ```text 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: ```brine 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") ``` Output ```text 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 [Section titled “Leaving the loop early”](#leaving-the-loop-early) first.br ```brine fn main(): let xs = [3, 8, 1, 9] par for i in 0..len(xs): if xs[i] > 5: break ``` ```text 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](/reference/errors/#e0342). To find the first match, ask with a reduction: ```brine 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) ``` Output ```text 1 ``` ## Restructuring patterns [Section titled “Restructuring patterns”](#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 [Section titled “Rules”](#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](/reference/errors/#e0501)). * An array written at `out[i]` can’t be used any other way in that loop ([E0502](/reference/errors/#e0502)). * No `write_file`, `run`, `exit`, changing `os` calls or `world` in `par` ([E0503](/reference/errors/#e0503)); `print` and reads are allowed. * No `break` or `return` ([E0505](/reference/errors/#e0505)); `continue` is fine. * `par for` has no invariants ([E0507](/reference/errors/#e0507)) and `par [...]` has no `if` filter ([E0508](/reference/errors/#e0508)). See also: [parallelism overview](/parallelism/overview/), [deterministic reductions](/parallelism/deterministic-reductions/), [references](/language/functions/).