nish/threads

Data parallelism, a scope for heterogeneous tasks, and a lock that owns its data (docs/wp29-thread-surface.md §4.1, §4.2 and §4.3).

import {
  AtomicI32,
  AtomicI32Array,
  AtomicI64,
  AtomicI64Array,
  Channel,
  Mutex,
  MutexGuard,
  ThreadScope,
  parallelFrom,
  parallelMap,
  parallelMapInto,
  parallelReduce,
  scope,
  scopeWithStack,
} from "nish/threads";
import { parallelFrom, parallelMap, parallelMapInto, parallelReduce, scope, scopeWithStack } from "nish/threads";

const sumOf = (xs: i32[]): i32 => {
  let total: i32 = 0;
  for (const x of xs) {
    total = total + x;
  }
  return total;
};

export const main = (): i32 => {
  const src: i32[] = [1, 2, 3, 4];
  const k: i32 = 10;
  const dst: i32[] = [0, 0, 0, 0];
  parallelMapInto(src, dst, (x) => x * 3);               // dst is [3, 6, 9, 12]
  const ys = parallelMap(src, (x) => x * k);             // [10, 20, 30, 40]: `k` is read by the body
  const sq = parallelFrom(4, (i) => i * i);              // [0, 1, 4, 9]
  const total = parallelReduce(src, (a, b) => a + b, 0); // 10
  const out: i32[] = [0, 0];
  {
    using s = scope();
    s.spawn(sumOf, ys, out, 0);
    s.spawn(sumOf, sq, out, 1);
  } // both tasks have run, and `out` is [100, 14]
  {
    using s = scopeWithStack(64 * 1024 * 1024); // each task's thread has a 64 MiB stack
    s.spawn(sumOf, src, out, 0);
  }
  return total;
};
What is written here is the meaning, not the implementation

Each body below is the sequential program, and it is what runs under Node, what npm run check type-checks, and what the compiler checks the call against.

The compiler then recognises the exported templates by module and name and lowers an instance of parallelMapInto, parallelFrom or parallelReduce onto nish_parallel_range (runtime/runtime-parallel.c): it replaces the one call that walks the whole range — mapRange for a map, fromRange for a parallelFrom, reduceBlocks for a reduce — with a region that hands each thread a contiguous piece of it, and emits the rest of the body as written. parallelMap is parallelMapInto into an array it allocates first. So the length check, its message and the order a reduce combines in are this file's, whichever way the program is compiled.

What makes the region safe is checked at the call, not trusted

What makes the region safe is checked at the call, not trusted (docs/LANGUAGE.md, "Data parallelism"): the function passed as f may write nothing its caller could observe, may allocate only temporaries it drops before it returns — they are given back after every element — dst may not be reachable from an element of src, and the result type is a number, a boolean or an enum — or, for a map, a string or an array of those scalars, which the join copies out of the worker's arena.

An arrow written at the call may read the const locals and the parameters of the function it is written in: each one is handed to the body as a parameter of its own, which no body may write through. Importing this module compiles the program with --threads, because every worker needs an arena of its own.

A reduce is deterministic

src is split into min(64, ceil(n / BLOCK)) blocks, each block is folded from identity, and the block results are combined left to right — here, on one thread, and by the compiled program on any number of them — so an f64 sum is the same bits on one core or sixty four. That needs f to be associative and identity to be its identity, which the checker enforces for an arrow whose body is one operator on its two parameters and cannot see through a named function.

Functions

parallelFrom

A new array of n elements, f(i) at index i, computed on as many threads as the machine has and the length is worth: Array.from({ length: n }, (_, i) => f(i)), with the array allocated before any element is.

const parallelFrom: <U>(n: i32, f: (i: i32) => U) => U[]
ni32required

how many elements the array has.

f(i: i32) => Urequired

computes the element at an index from the index alone, under the rules parallelMapInto gives its f.

returnsU[]

a new array of n elements, which the caller owns.

parallelMap

A new array of f(src[i]) for every index of src: parallelMapInto into an array this call allocates, before any element is computed, so nothing but the map itself can hold it while the region runs.

const parallelMap: <T, U>(src: T[], f: (x: T) => U) => U[]
srcT[]required

the elements to map, read and not written.

f(x: T) => Urequired

computes one element from one element of src, under the rules parallelMapInto gives its f.

returnsU[]

a new array of src.length elements, which the caller owns.

parallelMapInto

dst[i] = f(src[i]) for every index of src, on as many threads as the machine has and the length is worth. dst must be at least as long as src, which is checked once, before any element is written.

const parallelMapInto: <T, U>(
  src: T[],
  dst: U[],
  f: (x: T) => U,
) => void
srcT[]required

the elements to map, read and not written.

dstU[]required

where f(src[i]) is written, at the same index. If it is shorter than src the program stops before any element is written; any elements past src.length are left as they were.

f(x: T) => Urequired

computes one element from one element of src. It is called once per element, natively on any thread and in no set order, so it may write nothing its caller could observe (see the module header).

parallelReduce

f folded over src, blockwise from identity and then left to right over the blocks, so the answer does not depend on how many threads computed it. An empty src answers identity.

const parallelReduce: <T>(
  src: T[],
  f: (acc: T, x: T) => T,
  identity: T,
) => T
srcT[]required

the elements to fold, read and not written.

f(acc: T, x: T) => Trequired

combines an accumulator with an element, and the blocks' results with each other, so it must be associative for the answer to mean the fold it reads as.

identityTrequired

what each block's fold starts from, which must be f's identity, such as 0 for +.

returnsT

the fold of every element of src, the same however many threads computed it.

scope

A new scope, for a using declaration: using s = scope().

const scope: () => ThreadScope
returnsThreadScope

a new scope of its own, whose tasks run on threads of the platform's default stack size and are joined when the block ends.

scopeWithStack

A new scope whose tasks each run on a thread with a stack of at least bytes bytes, for a using declaration: using s = scopeWithStack(n). The tasks run on new threads, never on the one that joins. The runtime rounds bytes up to the page size and adds a guard page below it, so a task that overflows it faults instead of writing past it. Under Node, and on a target without threads, the size is checked and has no other effect.

const scopeWithStack: (bytes: i32) => ThreadScope
bytesi32required

the least stack each task's thread gets, in bytes. Below 131,072 (128 KiB) is a compile error when it is a constant (NL2584) and stops the program when it is computed.

returnsThreadScope

a new scope of its own, joined when the block ends.

Classes

AtomicI32

An i32 that a scope's tasks and a parallel body may update together (docs/LANGUAGE.md, "Atomics"). Each method is one indivisible operation: natively the compiler emits each body itself, as a sequentially consistent load atomic, store atomic, atomicrmw or cmpxchg on value (docs/IR_COOKBOOK.md, "Atomics"), and what is written below is the meaning, which is what runs under Node. add and sub wrap at 32 bits, as the native instruction does; add, sub, min, max and exchange answer the value before the update, and compareExchange the value it saw.

It reaches a task by the routes a Mutex does, and a parallel body through a capture; its value is named only through these methods. Results that do not depend on the order the updates land in need the updates to commute, which the checker does not prove.

class AtomicI32
Member
new AtomicI32(value: i32) An atomic holding value.
add(delta: i32): i32 Adds delta, wrapping, and answers the value before.
compareExchange(expected: i32, desired: i32): i32 Sets the value to desired if it is expected, and answers the value it saw.
exchange(value: i32): i32 Sets the value to value and answers the value before.
load(): i32 The value.
max(value: i32): i32 Keeps the larger of the value and value, and answers the value before.
min(value: i32): i32 Keeps the smaller of the value and value, and answers the value before.
store(value: i32): void Sets the value to value.
sub(delta: i32): i32 Subtracts delta, wrapping, and answers the value before.

AtomicI32Array

length i32 counters in one contiguous buffer, each of which a scope's tasks and a parallel body may update together (docs/LANGUAGE.md, "Atomic arrays"). It is AtomicI32 with the element's index first: each method checks i as an array index is checked, so an index out of range stops the program, and is then one indivisible operation on that element. Natively the compiler emits each body itself, as a sequentially consistent load atomic, store atomic, atomicrmw or cmpxchg on the element (docs/IR_COOKBOOK.md, "Atomics"), and what is written below is the meaning, which is what runs under Node. add and sub wrap at 32 bits, as the native instruction does.

Choose it over an AtomicI32[] when the counters are many or hot: an AtomicI32[] is one object per counter, each its own allocation, so neighbouring counters land on several cache lines; here they are adjacent i32s, as Rust's [AtomicI32; N] is. It reaches a task and a parallel body by the routes AtomicI32 does, and is refused where it is.

class AtomicI32Array
Member
new AtomicI32Array(length: i32) An array of length elements, each 0.
readonly length: i32 How many elements the array holds, fixed when it is made.
add(i: i32, delta: i32): i32 Adds delta to element i, wrapping at 32 bits, and answers the element before.
compareExchange(i: i32, expected: i32, desired: i32): i32 Sets element i to desired if it is expected, and answers the value it saw.
exchange(i: i32, value: i32): i32 Sets element i to value and answers the element before.
load(i: i32): i32 Element i.
max(i: i32, value: i32): i32 Keeps the larger of element i and value, and answers the element before.
min(i: i32, value: i32): i32 Keeps the smaller of element i and value, and answers the element before.
store(i: i32, value: i32): void Sets element i to value.
sub(i: i32, delta: i32): i32 Subtracts delta from element i, wrapping at 32 bits, and answers the element before.

AtomicI64

An i64 that a scope's tasks and a parallel body may update together (docs/LANGUAGE.md, "Atomics"). Each method is one indivisible operation: natively the compiler emits each body itself, as a sequentially consistent load atomic, store atomic, atomicrmw or cmpxchg on value (docs/IR_COOKBOOK.md, "Atomics"), and what is written below is the meaning, which is what runs under Node. Node holds it as a number, so add and sub are + and - there, and it agrees with native while values stay within ±2^53; wrapping at 2^63 is native-only, the same limit as every i64. add, sub, min, max and exchange answer the value before the update, and compareExchange the value it saw.

It reaches a task by the routes a Mutex does, and a parallel body through a capture; its value is named only through these methods. Results that do not depend on the order the updates land in need the updates to commute, which the checker does not prove.

class AtomicI64
Member
new AtomicI64(value: i64) An atomic holding value.
add(delta: i64): i64 Adds delta and answers the value before; natively the sum wraps at 64 bits.
compareExchange(expected: i64, desired: i64): i64 Sets the value to desired if it is expected, and answers the value it saw.
exchange(value: i64): i64 Sets the value to value and answers the value before.
load(): i64 The value.
max(value: i64): i64 Keeps the larger of the value and value, and answers the value before.
min(value: i64): i64 Keeps the smaller of the value and value, and answers the value before.
store(value: i64): void Sets the value to value.
sub(delta: i64): i64 Subtracts delta and answers the value before; natively the difference wraps at 64 bits.

AtomicI64Array

length i64 counters in one contiguous buffer, each of which a scope's tasks and a parallel body may update together (docs/LANGUAGE.md, "Atomic arrays"). It is AtomicI64 with the element's index first: each method checks i as an array index is checked, so an index out of range stops the program, and is then one indivisible operation on that element. Natively the compiler emits each body itself, as a sequentially consistent load atomic, store atomic, atomicrmw or cmpxchg on the element (docs/IR_COOKBOOK.md, "Atomics"), and what is written below is the meaning, which is what runs under Node. Node holds each element as a number, so add and sub are + and - there, and agree with native while values stay within ±2^53; wrapping at 2^63 is native-only, as it is for AtomicI64.

Choose it over an AtomicI64[] when the counters are many or hot: an AtomicI64[] is one object per counter, each its own allocation, so neighbouring counters land on several cache lines; here they are adjacent i64s, as Rust's [AtomicI64; N] is. It reaches a task and a parallel body by the routes AtomicI64 does, and is refused where it is.

class AtomicI64Array
Member
new AtomicI64Array(length: i32) An array of length elements, each 0.
readonly length: i32 How many elements the array holds, fixed when it is made.
add(i: i32, delta: i64): i64 Adds delta to element i and answers the element before; natively the sum wraps at 64 bits.
compareExchange(i: i32, expected: i64, desired: i64): i64 Sets element i to desired if it is expected, and answers the value it saw.
exchange(i: i32, value: i64): i64 Sets element i to value and answers the element before.
load(i: i32): i64 Element i.
max(i: i32, value: i64): i64 Keeps the larger of element i and value, and answers the element before.
min(i: i32, value: i64): i64 Keeps the smaller of element i and value, and answers the element before.
store(i: i32, value: i64): void Sets element i to value.
sub(i: i32, delta: i64): i64 Subtracts delta from element i and answers the element before; natively the difference wraps at 64 bits.

Channel

A channel of scalars or strings between a scope's tasks (docs/wp29-thread-surface.md §4.4); a string is copied out of the sender's arena at send and into the receiver's at the loop: send from the tasks that produce, for (const x of ch) in the one that consumes, or in the parent once the scope has joined.

const ch = new Channel<i32>()
{
  using s = scope()
  s.spawn(produce, new Pipe(ch, 100), done, 0) // every sender first
  s.spawn(consume, new Pipe(ch, 0), sums, 0)   // then the one receiver
}

Nobody closes a channel: it closes when its scope has started to join and every task that may send on it has returned (docs/LANGUAGE.md, "Channels").

What is written here is the meaning under Node, where a scope's tasks run one at a time at their spawns: send pushes onto queue, and a loop takes values off its front until it is empty. That is correct because every sender is spawned before the receiver, so every sender has run by the time the receiver's loop starts. Natively the compiler writes send and the loop itself (src/emit-parallel.ts), onto a buffer the runtime keeps outside every arena behind state, and the loop waits while the channel is empty and still open.

class Channel<T>
Member
new Channel<T>() An empty channel, open until its scope joins.
[Symbol.iterator](): ChannelWalk<T> What for (const x of ch) asks for under Node: a walk that takes each value as it reaches it, so a second loop over the channel finds it empty, as it does natively.
send(x: T): void Hand x to the receiver. It never waits: a channel holds as many values as are sent.

Mutex

A lock that owns its data (docs/wp29-thread-surface.md §4.3). The data is reachable only through the guard lock() answers, bound by using, so no path to it skips the lock: new Mutex<Hist>(new Hist()) takes a fresh value, and using g = m.lock() is the only way to read or write it.

Under Node a scope's tasks run one at a time, at their spawn, so lock() answers the guard and waits for nothing: that is one of the orders the native program can run its critical sections in, and a program whose guarded updates commute prints the same either way.

class Mutex<T>
Member
new Mutex<T>(init: T) A free lock that owns init.
lock(): MutexGuard<T> The guard over the data, for a using declaration: using g = m.lock(). Natively the call waits until the lock is free and takes it.

MutexGuard

What a Mutex hands out: its data, as value, for as long as the block of the using declaration that took the lock (docs/LANGUAGE.md, "A lock that owns its data"). A guard is only ever named as g.value, and g.value only as the base of a field or element access, so nothing read through it outlives the lock.

Each Mutex makes exactly one guard, when it is made, and every lock hands out that one: taking the lock allocates nothing.

class MutexGuard<T>
Member
new MutexGuard<T>(value: T) A guard over value, with the lock free. Mutex makes its one guard with this.
value: T The data the lock owns.
[Symbol.dispose](): void What using calls when the guard's block ends. Natively the compiler emits the release itself at every exit of the block, and under Node nothing was taken, so there is nothing to give back.

ThreadScope

A scope of tasks, joined when the block that declares it ends (docs/wp29-thread-surface.md §4.2). It is only ever made by scope() in a using declaration, and only ever used as the receiver of spawn (docs/LANGUAGE.md, "Scoped tasks"), so no task can outlive it.

class ThreadScope
Member
new ThreadScope()
[Symbol.dispose](): void What using calls when the block ends. Natively the compiler emits the join itself at every exit of the block, and under Node every task has already run by the time this is reached, so there is nothing left to do.
spawn<A, R>(entry: (arg: A) => R, arg: A, dst: R[], at: i32): void Run entry(arg) on a thread of its own and store its answer in dst[at] when the scope closes. at is checked here, before the task is taken, and again when its answer is stored.
spawnThunk<R>(entry: () => R): void s.spawn(() => work(xs)) as the compiler reads it: run the arrow, whose captured const locals are its arguments, on a thread of its own when the scope closes, and store nothing. Only the compiler names this method, and a program that names it is refused as spawnWith's is (NL2389).
spawnWith<A, R>(entry: (arg: A) => R, arg: A): void s.spawn(entry, arg) as the compiler reads it: run entry(arg) on a thread of its own when the scope closes, and store nothing. entry answers void. Only the compiler names this method (see slotWritten): a scope is only ever the receiver of a spawn statement, so s.spawnWith(...) written in a program is refused by that rule (NL2389), as passing the scope would be.