# Parallelism overview > The four par constructs (par for, par [...], par reductions, par(a, b)), how many threads they use, what a par body may contain, nesting, and which construct to pick. Source: https://docs.brinelang.org/parallelism/overview/ Parallelism in Brine is syntax: put `par` in front of a loop, a comprehension, a reduction or a pair of expressions, and it runs on every core (and on the GPU, when that’s faster). The compiler rejects any `par` body that could race, and reductions give the same bits on any number of threads, so adding `par` never changes what a correct program prints. ## The four constructs [Section titled “The four constructs”](#the-four-constructs) | Construct | What it does | Result | | ----------------------------- | ---------------------------------------------------------------- | ------------------------------ | | `par for i in lo..hi:` | runs the body once per `i`, in parallel | nothing; writes go to `out[i]` | | `par [e for x in xs]` | parallel map: one result per element | an array, in order | | `par sum(e for x in xs if c)` | parallel reduction: `sum`, `product`, `min`, `max`, `any`, `all` | one value | | `par(f(a), g(b))` | fork-join: evaluates the expressions at the same time | a tuple | ## A complete example [Section titled “A complete example”](#a-complete-example) overview\.br ```brine fn collatz_len(n: int) -> int: var x = n var steps = 0 while x != 1: x = x / 2 if x % 2 == 0 else 3 * x + 1 steps += 1 return steps fn main(): let n = 1_000_000 # par [...]: one result per element, in order let lens = par [collatz_len(i) for i in 1..=n] # par reductions, with and without a filter let longest = par max(l for l in lens) let total = par sum(l for l in lens) let long_ones = par sum(1 for l in lens if l > 300) # par for: each iteration writes only its own element of `hist` var hist = [0] * 8 par for b in 0..8: hist[b] = sum(1 for l in lens if l / 100 == b) # par(a, b): independent expressions, run at the same time let (a, b) = par(collatz_len(27), collatz_len(97)) print(f"longest: {longest}, average: {float(total) / float(n):.2f}, over 300: {long_ones}") print(f"by hundreds: {hist}") print(f"27 takes {a} steps, 97 takes {b}") ``` ```sh brine run overview.br ``` Output ```text longest: 524, average: 131.43, over 300: 5617 by hundreds: [344030, 530366, 119920, 5574, 106, 4, 0, 0] 27 takes 111 steps, 97 takes 118 ``` The output is the same on every run and every machine, whatever the number of threads. ## par for [Section titled “par for”](#par-for) `par for` runs its body once for every value of the loop variable, spread over the thread pool. The iterations run in no particular order, so the body can’t change variables from outside the loop, with one exception: an outer array may be written at the loop index. ```brine fn main(): let n = 8 var out = [0.0] * n par for i in 0..n: out[i] = sqrt(float(i)) print(out) ``` Output ```text [0.0, 1.0, 1.4142135623730951, 1.7320508075688772, 2.0, 2.23606797749979, 2.449489742783178, 2.6457513110645907] ``` * The loop can be over a range (`lo..hi`, `lo..=hi`, `range(a, b, step)`), an array, a map, or `enumerate(xs)`. Only a loop over a range can write `out[i]`; the others can read outer values but not write them. * `out[i]` must be exactly the loop variable. `out[2 * i]` and `out[i + 1]` are errors, and once the body writes `out[i]` it may not read `out` any other way (`out[i - 1]`, `len(out)`). See [race freedom](/parallelism/race-freedom/). * `continue` ends the current iteration. `break` and `return` are errors ([E0505](/reference/errors/#e0505)): other iterations are already running. * A `par for` can’t have an `invariant` ([E0507](/reference/errors/#e0507)): there is no state between iterations. ## par \[…] [Section titled “par \[…\]”](#par-) A parallel map evaluates the expression for every element and returns the results as an array, in the order of the input. It is the usual way to compute one value per element. ```brine fn main(): let words = ["fig", "pear", "plum", "banana"] let lengths = par [len(w) for w in words] let squares = par [i * i for i in 0..6] print(lengths, squares) ``` Output ```text [3, 4, 4, 6] [0, 1, 4, 9, 16, 25] ``` `par [...]` can’t have an `if` filter ([E0508](/reference/errors/#e0508)), because each element’s place in the result has to be known before the elements are computed. Filter with a sequential comprehension afterwards, or count and combine with a filtered reduction. ## par reductions [Section titled “par reductions”](#par-reductions) `par sum`, `par product`, `par min`, `par max`, `par any` and `par all` combine one value per element into a single result. A reduction may filter with `if`. ```brine fn main(): let total = par sum(i for i in 0..10 if i % 2 == 0) let p = par product(i for i in 1..6) let lo = par min(i * 3 - 7 for i in 0..10) let hi = par max(i for i in 0..10 if i < 5) let a = par any(i == 7 for i in 0..10) let b = par all(i < 10 for i in 0..10) print(total, p, lo, hi, a, b) ``` Output ```text 20 120 -7 4 true true ``` * Over no elements, `sum` is `0`, `product` is `1`, `any` is `false` and `all` is `true`. `min` and `max` of nothing panic (`max() of an empty sequence`). * Integer `sum` and `product` stop the program on overflow, as every integer operation does. * The elements are combined in one fixed order that depends only on how many there are, so a float `par sum` gives the same bits on 1 thread, 32 threads or a GPU. That order isn’t left to right, so it can differ from a sequential `sum` in the last bits (usually by being closer to the exact result). See [deterministic reductions](/parallelism/deterministic-reductions/). ## par(a, b) [Section titled “par(a, b)”](#para-b) A fork-join evaluates two or more independent expressions at the same time and returns their values as a tuple. ```brine fn fib(n: int) -> int: if n < 2: return n return fib(n - 1) + fib(n - 2) fn main(): let (a, b, c) = par(fib(30), fib(31), fib(32)) print(a, b, c) ``` Output ```text 832040 1346269 2178309 ``` The expressions follow the same rules as any `par` body: they can read variables but not change them, so `par(xs.pop(), len(xs))` and `par(bump(ref n), 5)` are errors. `par(e)` with one expression is [E0113](/reference/errors/#e0113). ## Threads [Section titled “Threads”](#threads) `par` constructs share one thread pool per process. It has one thread per core by default; change it with `--threads` or `BRINE_THREADS`: ```sh brine run collatz.br --release --threads 8 BRINE_THREADS=8 brine run collatz.br --release # the same; also works for built binaries ``` collatz.br ```brine fn collatz_len(n: int) -> int: var x = n var steps = 0 while x != 1: x = x / 2 if x % 2 == 0 else 3 * x + 1 steps += 1 return steps fn main(): let n = 10_000_000 let t0 = clock() let longest = par max(collatz_len(i) for i in 1..=n) let t1 = clock() print(f"longest chain below {n}: {longest} steps ({(t1 - t0) * 1000.0:.0f} ms)") ``` With the GPU turned off (`BRINE_GPU=off`) on a Ryzen 9 9950X3D (16 cores, 32 threads), `--release`: | `BRINE_THREADS` | 1 | 2 | 4 | 8 | 16 | 32 | | --------------- | ---- | --- | --- | --- | --- | -- | | time (ms) | 1355 | 710 | 360 | 181 | 102 | 63 | Every run prints `longest chain below 10000000: 685 steps`. With the GPU left on `auto`, the same program on an RTX 4090 takes 4-5 ms per run once the device is ready; see [GPU offload](/parallelism/gpu/). With [`--ranks N`](/parallelism/world/), every rank is its own process with its own pool. On one machine, give each rank its share of the cores (`--ranks 4 --threads 8` on 32 threads). See also [environment variables](/tooling/environment-variables/). ## What a par body can contain [Section titled “What a par body can contain”](#what-a-par-body-can-contain) A `par` body is ordinary Brine with one restriction: it can’t change anything that other iterations can see. In practice: | Allowed | Not allowed | | ------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------- | | reading any outer variable, array or map | assigning an outer variable ([E0501](/reference/errors/#e0501)) | | `out[i] = ...` in `par for i in` a range | `out[j]` for any other index, or reading `out` elsewhere in that loop ([E0502](/reference/errors/#e0502)) | | local `let`/`var`, local arrays, `push` on them | `push`, `pop`, `sort` and other changing methods on outer arrays; changing maps ([E0501](/reference/errors/#e0501)) | | calling functions, `ref` arguments to *local* variables | `ref` arguments to outer variables ([E0501](/reference/errors/#e0501)) | | `print`, `eprint`, `clock`, `read_file`, `getenv` | `write_file`, `run`, `exit`, changing `os` calls, `world` ([E0503](/reference/errors/#e0503)) | | `continue`, `assert`, panics | `break`, `return` ([E0505](/reference/errors/#e0505)), `?` ([E0342](/reference/errors/#e0342)) | `print` is allowed, but the lines come out in whatever order the iterations finish (each `print` writes its whole line at once). The rules and the errors are on the [race freedom](/parallelism/race-freedom/) page. ## Nesting [Section titled “Nesting”](#nesting) A `par` construct inside another one is allowed. The inner one runs on the thread that runs the outer iteration, sequentially, so nesting never starts more threads than the pool has: ```brine fn main(): let rows = par [par sum(i * j for j in 0..4) for i in 0..4] print(rows) ``` Output ```text [0, 6, 12, 18] ``` Usually it’s best to put `par` on the outermost loop that has enough iterations to keep every core busy, and leave the inner ones sequential. Nested constructs don’t run on the GPU, and neither does a construct whose body contains one. ## Which one to use [Section titled “Which one to use”](#which-one-to-use) | You want | Use | | ---------------------------------------------------- | ---------------------------------------------------------------------- | | one new value per element | `par [f(x) for x in xs]` | | one number from many (a total, a count, a maximum) | `par sum(...)`, `par max(...)`, … with `if` to filter | | a filtered array | a sequential `[x for x in xs if p(x)]`, or `par [...]` of flags first | | to fill an existing array, or several arrays at once | `par for i in 0..n:` writing `a[i]`, `b[i]` | | two or three unrelated pieces of work | `par(f(), g())` | | work spread over processes or machines | the [`world` module](/parallelism/world/), with `par` inside each rank | `par` pays off when a construct does enough work to cover handing it to the pool. Loops over a few dozen cheap elements are fine to leave sequential. ## Related pages [Section titled “Related pages”](#related-pages) * [Race freedom](/parallelism/race-freedom/): the rule and every error it gives * [Deterministic reductions](/parallelism/deterministic-reductions/): the order of a `par sum` * [GPU offload](/parallelism/gpu/): which constructs run on a GPU, and when * [Multiple processes: world](/parallelism/world/) and [deadlock freedom](/parallelism/deadlock-freedom/)