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;
};
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.
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.
parallelMapInto
dst[i] = f(src[i]) for every index of src, on as many threads as the machine has and the length is worth.
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.
scope
A new scope, for a using declaration: using s = scope().
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).
AtomicI32
An i32 that a scope's tasks and a parallel body may update together (docs/LANGUAGE.md, "Atomics").
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").
AtomicI64
An i64 that a scope's tasks and a parallel body may update together (docs/LANGUAGE.md, "Atomics").
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").
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.
Mutex
A lock that owns its data (docs/wp29-thread-surface.md §4.3).
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").
ThreadScope
A scope of tasks, joined when the block that declares it ends (docs/wp29-thread-surface.md §4.2).
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[]
ni32requiredhow 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[]requiredthe 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[]requiredthe 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[]requiredthe elements to fold, read and not written.
f(acc: T, x: T) => Trequiredcombines 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
returnsThreadScopea 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
bytesi32requiredthe 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.
returnsThreadScopea 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. |

