Threads
Nish runs code on several threads without letting two threads race on the same memory. It does that by offering a few shapes of parallel work, each with rules the compiler checks, instead of raw threads and shared variables. Pick the shape by what the work is:
| You need | Reach for |
|---|---|
| the same work on every element of an array | parallelMap / parallelMapInto |
| a fold: a sum, a count, a maximum | parallelReduce |
| a few unlike jobs at once | scope + spawn |
| a shared counter, minimum, maximum or flag | AtomicI32 / AtomicI64 |
| many shared counters: a histogram, a count per route | AtomicI32Array / AtomicI64Array |
| a shared structure that tasks update | Mutex<T> |
| a pipeline: tasks that produce values for one that consumes them | Channel<T> |
All of them come from nish/threads. Importing it is the only switch: the
program is built for threads, and there is no thread count to choose. A
program that breaks one of the rules below is refused at compile time, with a
message that names the line and the reason; the rules are what keep threads
from racing on memory or deadlocking on a lock or a channel.
The same program also runs under Node, one task at a time, and prints the same answer (RUN_UNDER_NODE.md says how).
Threads share one process. To share memory between processes, such as prefork workers, see Shared memory between processes.
One function over an array: parallelMapInto and parallelReduce
parallelMapInto(src, dst, f) writes f(src[i]) into dst[i] for every
index. parallelReduce(src, f, identity) folds the array with f. Each
splits the array across as many threads as the machine has and the length is
worth. f is a top-level function named at the call, or an arrow written
there.
import { parallelMapInto, parallelReduce } from "nish/threads";
const square = (x: f64): f64 => x * x;
export const main = (): i32 => {
const n: i32 = 3000000;
const src = new Array<f64>(n);
for (let i: i32 = 0; i < src.length; i++) {
src[i] = toF64(i % 10);
}
const dst = new Array<f64>(n);
parallelMapInto(src, dst, square);
const total = parallelReduce(dst, (a, b) => a + b, 0.0);
console.log(`${total}`); // 85500000
return 0;
};
-
A short array is just a loop. The work is split only when every thread's share is big enough to pay for handing it to another thread, judged from what
fcosts, so there is no reason to guard a call by size. -
A slow thread does not hold the others up. A long array is cut into up to eight pieces per thread, and a thread that finishes one takes the next, so a core shared with another program, or elements that cost more than their neighbours, end up spread over the threads that have time.
-
The speedup is capped by what runs outside the map. Only the call is divided; the loop that fills
srcand the loop that reads the answers run on one thread. In the repository'sbench/par-heavy.tsthose two loops, an order-sensitive checksum among them, are about an eighth of the one-thread time, which caps four cores near 2.9x; the program measures about 2.7x. With a checksum the compiler vectorises, or four times the work per element, the same map is above 3x. The figures are in BENCHMARKS.md. -
dstmust be at least as long assrc, or the call panics before it writes anything.srcanddstmay be the same array. -
fwrites nothing its caller can see — no store through its argument, and no output: notconsole.log,console.error,write,writeErrororprocess.exit— and answers a number, aboolean, an enum, astring, or an array of numbers, booleans or enums (a reduce'sfonly the first three; see below). It may look keys up in aMaporSetits element reaches (get,has,size), but not change or iterate one, and it maypanic: if several elements panic at once, only the first prints its message, and the program exits 1.It may build strings and arrays on the way to its answer; they are freed after each element, and the compiler warns that each element pays for that. An array it makes itself, keeps in a
constand hands to nothing that keeps it is its own: it may fill it,pushonto it, or pass it to a helper that writes it. -
A string or an array is copied out once, then handed over. Each thread copies the answers it built into a block of its own before the next element reuses its arena. Once every thread has finished, the caller takes those blocks into its own arena whole when they hold 64 KB or more, and copies the answers in when they hold less, so the array you get back holds strings you own.
They are freed like anything else your function allocates: a function that runs a map and returns only a number gives the result and its strings back when it returns, even when it passes the strings to a helper that only reads them, and a map may run inside
using a = arena()unless its body answers arrays. An array of strings, an array of arrays, an object, aMapor aSetis refused: copying one would mean following every element. -
A reduce folds numbers, booleans or enums. Its
fanswers the same type it takes, on many threads at once, so a string there is refused; map the strings to numbers first,parallelReduce(parallelMap(words, (w) => w.length), (a, b) => a + b, 0). -
A reduce is deterministic. The array is folded in fixed blocks and the blocks are combined in order, so an
f64sum is the same bits on one core or sixty-four. For that to be the fold you meant,fmust be associative andidentityits identity:(a, b) => a - b, or+with an identity of1, is refused.
An element may carry a Map or a Set for f to look keys up in. f may
not reach an array dst could be, but a table's own arrays are private to it:
a Map<string, i32> beside an i32[] dst is fine, and a
Map<string, i32[]> is refused, because one of its values could be dst.
import { parallelMapInto } from "nish/threads";
class Doc {
index: Map<string, i32>;
constructor() {
this.index = new Map<string, i32>();
}
}
const score = (d: Doc): i32 => (d.index.get("a") ?? 0) + d.index.size;
export const main = (): i32 => {
const docs: Doc[] = [new Doc(), new Doc()];
docs[0].index.set("a", 10);
const out: i32[] = [0, 0];
parallelMapInto(docs, out, score);
console.log(`${out[0]} ${out[1]}`); // 11 0
return 0;
};
A string | null field shared through a Mutex takes a string or null.
The Mutex keeps its own copy of a stored string, and storing null frees it;
read the field back through ?.:
import { Mutex, scope } from "nish/threads";
class Last {
name: string | null = null;
}
const record = (last: Mutex<Last>, i: i32): void => {
using g = last.lock();
if (i % 2 === 0) {
g.value.name = `task ${i}`;
} else {
g.value.name = null; // the copy the slot held is freed
}
};
export const main = (): i32 => {
const last = new Mutex<Last>(new Last());
{
using s = scope();
s.spawn(() => record(last, 2));
}
using g = last.lock();
console.log(`${g.value.name?.length ?? -1}`); // 6
g.value.name = null;
console.log(`${g.value.name?.length ?? -1}`); // -1
return 0;
};
What is refused, and why. An f that prints, stores through its
argument or writes anything else its caller can see is refused at the call
(NL2345 for output), because every thread would make that write at once and
the order would be the scheduler's. So is a reduce whose arrow is plainly not
associative, because the blocks are combined in a fixed order. The rules are
in the reference, Data parallelism.
import { parallelMapInto } from "nish/threads";
const noisy = (x: i32): i32 => {
console.log(`${x}`); // a write every thread would make at once
return x * 2;
};
export const main = (): i32 => {
const src: i32[] = [1, 2, 3];
const dst: i32[] = [0, 0, 0];
parallelMapInto(src, dst, noisy);
return dst[0];
};
A new array: parallelMap and parallelFrom
parallelMap(src, f) answers a new array of f(src[i]), and
parallelFrom(n, f) a new array of n elements with f(i) at index i, the
way Array.from({ length: n }, (_, i) => f(i)) builds one. Each allocates the
array before it starts and then runs exactly the map above, under the same
rules for f. There is no dst to get wrong.
import { parallelFrom, parallelMap } from "nish/threads";
export const main = (): i32 => {
const squares = parallelFrom(5, (i) => i * i); // 0 1 4 9 16
const shifted = parallelMap(squares, (x) => x + 1); // 1 2 5 10 17
console.log(`${squares[4]} ${shifted[4]}`); // 16 17
return 0;
};
The answer may be a string or an array of numbers, too; each one is copied out of the thread that built it, so it lives as long as the array you get back:
import { parallelFrom, parallelMap } from "nish/threads";
export const main = (): i32 => {
const names = parallelFrom(3, (i) => `worker-${i}`); // worker-0 worker-1 worker-2
const lengths = parallelMap(names, (s) => s.length); // 8 8 8
const tags = parallelMap(names, (s) => s.substring(7)); // 0 1 2
console.log(`${names[2]} ${lengths[0]} ${tags[1]}`); // worker-2 8 1
return 0;
};
Each thread moves the strings its elements answer into blocks of its own, and
the caller takes the blocks whole at the join rather than copying each string
again, so the copy runs on every thread at once. A map of a million
`s${x % 100000}` strings took a median of 24 ms on 4 threads (22 to 32 ms
over nine runs), against 40 ms for the sequential loop.
On one thread the same
map takes as long as the loop, so a program that runs with
NISH_NUM_THREADS=1, or on a single core, loses nothing by using it. Still,
measure your own case: the threads pay off when each element does some work,
or when there is more than one core to run it.
What is refused, and why. The rules for f above, and an answer that is
an array of strings, an array of arrays, an object, a Map or a Set
(NL2348): each thread's memory is reused for its next element, and copying
such an answer out of it would mean following every element. Answer a string
or a number per element, and build the structure from them after the call.
import { parallelFrom } from "nish/threads";
export const main = (): i32 => {
const rows = parallelFrom(3, (i) => [`row-${i}`]); // a string[] per element
return rows.length;
};
Reading the function's constants
An arrow passed to one of these four forms may read the const locals and the
parameters of the function it is written in, which is how a scale, an offset
or a lookup table reaches the body:
import { parallelMap } from "nish/threads";
const affine = (xs: i32[], k: i32): i32[] => {
const b: i32 = 1;
const table: i32[] = [0, 100, 200];
return parallelMap(xs, (x) => x * k + b + table[x % 3]);
};
export const main = (): i32 => {
const ys = affine([1, 2, 3], 10);
console.log(`${ys[0]} ${ys[1]} ${ys[2]}`); // 111 221 31
return 0;
};
-
What the body reads, it only reads. Every thread sees the same values, so the body may not assign to one, store into an array or an object it reads this way, or hand one to a function that does. Each of those is refused at the call.
-
Only a
constor a parameter. Aletcould change while the threads read it: bind its value to aconstfirst.thisis not read by that name either; bind it, or the field you need, to aconst(const self = this,const k = this.k). -
Only the arrow written at the call. An arrow inside that arrow reads nothing from outside itself. An arrow given to
spawnreads them too, as the next section shows, and so does an arrow given to an ordinary function parameter (Functions), which runs on this thread and so may also write through what it reads. -
Not
dst. InparallelMapInto, a body may not read an array that could be the one being written. Aconsttable bound to its own array is fine beside adstthat is aconstbound to its own array, as inconst table = [1, 2]andconst dst = new Array<i32>(n). Any capture is fine beside adstthat is aconstbound to its own array and that nothing was given before the call: not stored in a field or a list, not passed to a function, not bound to a second name, not built into an object and not written by an earlierparallelMapInto.Indexing it, reading its
length, calling its methods and walking it withfor...ofgive it to no one. After the call you may handdston, except inside a loop around the call thatdstwas declared outside of, where the next pass's call comes after it; a loop that declares its owndsteach pass is fine.
import { parallelMap, parallelMapInto } from "nish/threads";
export const main = (): i32 => {
const src: i32[] = [3, 14, 15, 92];
const weights = parallelMap(src, (x) => x % 13);
const dst = new Array<i32>(src.length);
parallelMapInto(src, dst, (x) => weights[x % 4] + 1); // nothing had `dst` yet
const kept = dst; // after the call: fine
return kept[0];
};
Each of these is refused because every thread reads the same value at once:
a write to it, or a let that changes under the threads, would make the
answer depend on which thread ran first.
import { parallelMap } from "nish/threads";
export const main = (): i32 => {
const sum: i32 = 0;
const ys = parallelMap([1, 2, 3], (x): i32 => {
sum = sum + x; // every thread would write it at once
return x;
});
return ys[0];
};
Answer the value from the body instead, and fold the answers with
parallelReduce after the call. Here the body answers x itself, so the
fold reads the array the call was given:
import { parallelReduce } from "nish/threads";
export const main = (): i32 => {
const sumTotal = parallelReduce([1, 2, 3], (a, b) => a + b, 0);
return sumTotal;
};
Different tasks at once: using s = scope()
A scope runs different functions side by side, each on a thread. Open it with
using, hand it tasks with s.spawn(entry, arg, dst, at), and when the block
ends every task has run and entry(arg) is stored in dst[at]:
import { scope } from "nish/threads";
const sumOf = (xs: f64[]): f64 => {
let total: f64 = 0.0;
for (const x of xs) {
total = total + x;
}
return total;
};
const countPrimes = (limit: i32): i32 => {
let count = 0;
for (let n: i32 = 2; n < limit; n++) {
let prime = true;
for (let d: i32 = 2; d * d <= n; d++) {
if (n % d === 0) {
prime = false;
break;
}
}
if (prime) {
count++;
}
}
return count;
};
export const main = (): i32 => {
const xs: f64[] = [1.5, 2.5, 3.0];
const sums: f64[] = [0.0];
const primes: i32[] = [0];
{
using s = scope();
s.spawn(sumOf, xs, sums, 0); // sums[0] = sumOf(xs)
s.spawn(countPrimes, 1000, primes, 0); // primes[0] = countPrimes(1000)
} // both tasks have run here
console.log(`${sums[0]} ${primes[0]}`); // 7 168
return 0;
};
-
The tasks run when the block ends, all together, and their answers are stored after the last one finishes. That happens at every way out of the block — its end, a
return, abreak— so no task is ever left running. -
Read the answers after the block. A destination is a
constbound to a fresh array ([0],new Array<i32>(n)) that you only index; never pass it on. Inside the block, don't read a destination, and don't write memory a task could read — through a constructor either:new Bump(counter)whose constructor writescounteris refused like a call that does.Don't call a
MaporSetmethod that changes or walks the table either, even on one no task can reach or one you made in the block: the compiler judges the call, not which tables the tasks hold. Do it before the firstspawn, after the block, or in a helper that makes and fills its own table. An object you make in the block is yours to write, until anything a task reads may have got into it: stored in a field or an element, pushed, added to aMapor aSet, put in a literal, or handed to a function that keeps it.A field or an element of it counts as much as the object itself. So a
Map, aSetor an array you make there is yours to fill and walk, and what you read back out of it is yours to write when you put it there fresh. -
A task follows the rules of a parallel
fabove: it writes nothing another thread can see (except through aMutexor aChannel, below) and prints nothing (console.log,console.error,write,writeErrorandprocess.exitare all refused), answers a number, aboolean, an enum, astringor an array of numbers, booleans or enums when it has a destination — a string or an array is copied into the parent's memory when the scope joins — and opens no scope of its own.Looking a key up in a shared
MaporSet(get,has,size) is a read, so tasks may share a table that way; changing it, or walking it withfor...of, is a write. Handing a helper a string from a shared array (check(hashes[k])) is a read too: a string has nothing to write into. A task maypanic: if several threads panic at once, only the first prints its message, and the program exits 1. -
A task may
wipewhat it made. An array the task, or a function it calls, allocates itself (const buf = new Array<u8>(n)) is its own, sowipe(buf)before it returns is not a write another thread can see. Wiping anything else is: its argument, a local it captured, a field, or an array another call answered.A key shared with the tasks stays the parent's — make the
Secretbefore the block, let each taskexposeit, andwipeit after the block. A task may make aSecretof its own and wipe it, when the value is allocated right in the call:const k = secret(new Array<u8>(n)), filled insideexposeWith, thenwipe(k). ASecretmade from a local moved in (secret(buf)) or from another call's answer is refused, so allocate inside thesecret(...). -
A scope never leaves its block. It is only ever the receiver of
spawn: passing, storing or returning it is refused, and so is a scope bound withoutusing. -
Spawning costs no memory. Every task has run before the function, the loop pass or the
using a = arena()block around the scope gives back what it made, so an array you build and hand to a task is freed with the rest, unless the task answers it or you keep it.Inside an arena block, declare the scope after the arena —
using a = arena(), s = scope(), or ausing s = scope()of its own further in — so it joins before the release; a scope declared before the arena, or before a secondarena()of the same statement, joins after a release and may not be handed what the block made.
Tasks without a destination, and arrow tasks
A task that only updates something shared has no answer to store, so it needs
no destination: s.spawn(entry, arg) runs entry(arg), and
s.spawn(() => work(a, b)) runs an arrow that reads the const locals and
the parameters of the function it is written in. Either one answers void.
import { Mutex, scope } from "nish/threads";
class Tally {
total: i32 = 0;
}
const addAll = (tally: Mutex<Tally>, xs: i32[]): void => {
let t: i32 = 0;
for (const x of xs) {
t = t + x;
}
using g = tally.lock();
g.value.total = g.value.total + t;
};
export const main = (): i32 => {
const tally = new Mutex<Tally>(new Tally());
const low: i32[] = [1, 2, 3];
const high: i32[] = [40, 50];
{
using s = scope();
s.spawn(() => addAll(tally, low));
s.spawn(() => addAll(tally, high));
}
using g = tally.lock();
console.log(`${g.value.total}`); // 96
return 0;
};
-
What the arrow reads is the task's argument. It is handed to the task
when you spawn it, and the task reads it when the block ends, so every rule
above holds of it: inside the block, don't write
lowor anything it reaches, by any name, through any function or constructor. Aletis not read this way, since it could change before the task runs, and neither isthis: bind them to aconstfirst. -
A lock, yes; a guard or a channel, no. An arrow task may read a
Mutexand lock it, asaddAlldoes. Hand a channel to a task as its argument,s.spawn(produce, new Pipe(ch, 10)), so the scope can count its senders. -
No destination, no answer. An entry that answers a value with no
destination to store it in is refused; give it one with the four-argument
form, or make it answer
void. The arrow's thread is named after the function it is written in, so a debugger still shows where it came from.
What is refused, and why. Every refusal in a scope keeps one promise:
nothing a task reads changes while the task may be running. So a scope bound
without using is refused, since its tasks might never be joined (NL2388).
Reading a destination inside the block is refused, since its answer is not
there yet, and so is writing memory a task reads, since the task would see
whichever value was there when its thread got to it.
Reading a let from an
arrow task is refused for the same reason (NL2506): the let could change
before the task runs. nish --fix repairs the
missing using and the captured let; a destination read early or a write a
task would see is yours to move after the block.
import { scope } from "nish/threads";
export const main = (): i32 => {
let k: i32 = 3; // a `let` could change before the task runs
const out: i32[] = [0];
{
using s = scope();
s.spawn((n: i32): i32 => n + k, 1, out, 0);
}
return out[0];
};
Where the work runs
The first task runs on the thread that opened the scope, which would otherwise wait, and the others go to a pool of worker threads, one per core besides the calling thread's (at most 63), started the first time a program divides work and parked between uses. A Node addon starts threads for each call instead, and on WASI everything runs on the one thread. A scope with more tasks than cores queues the rest, and a thread that finishes one takes the next.
The core count follows what the process may actually use (its affinity
mask, a container's CPU quota), and NISH_NUM_THREADS=2 lowers it to two,
which is handy on a shared machine; NISH_NUM_THREADS=1 runs everything on
the calling thread. It never raises the count. A map's or a reduce's answer
is the same at any count; what a scope's tasks do under a lock can come out
in a different order, as the lock section below says.
A task that recurses deeply: scopeWithStack
A thread starts with a fixed stack, 8 MiB on Linux, and a task that recurses
deeper than that faults. A type checker walking a deep tree is the usual
case. scopeWithStack(bytes) is a scope whose tasks each run on a thread with
at least bytes of stack:
import { scopeWithStack } from "nish/threads";
const depth = (n: i32): i32 => (n === 0 ? 0 : depth(n - 1) + 1);
export const main = (): i32 => {
const out: i32[] = [0];
{
using s = scopeWithStack(64 * 1024 * 1024); // 64 MiB for each task
s.spawn(depth, 1000, out, 0);
}
console.log(`${out[0]}`); // 1000
return 0;
};
Everything else about it is a scope's. Its tasks all run on new threads, none on the thread that opened the scope. The size is rounded up to the page, and a guard page sits below it, so a task that still overflows faults instead of writing past the stack.
If the system cannot start one, out of threads or of
memory for the stack, the program ends with exit 1 and
nish: cannot start a thread for scopeWithStack: out of threads or of memory for its stack.
The smallest size is 131072 bytes (128 KiB). Below it,
a number written at the call is refused (below)
and a computed one panics with
scopeWithStack: a stack of 65536 bytes is below the minimum of 131072.
The size is for a scope's tasks only. parallelMap, parallelFrom and the
other data-parallel calls run on the pool's workers, which keep the
platform's default stack.
Under Node, on WASI and in a build without --threads, the size is checked
and then ignored. Every task runs on the one thread there, so a program that
recurses that deep also needs a large stack from Node: run it with
node --stack-size=…, under a raised ulimit -s.
Sharing a value: Mutex<T>
When tasks must update one value, put it in a Mutex. The value lives inside
the lock, and the only way to it is the guard that using g = m.lock()
binds, which holds the lock until its block ends:
import { Mutex, scope } from "nish/threads";
class Counter {
n: i32 = 0;
}
const addMany = (total: Mutex<Counter>): i32 => {
for (let k: i32 = 0; k < 100000; k++) {
using g = total.lock(); // waits for the lock, and holds it to the end of the block
g.value.n = g.value.n + 1;
} // released here, on every pass
return 0;
};
export const main = (): i32 => {
const total = new Mutex<Counter>(new Counter());
const done: i32[] = [0, 0, 0, 0];
{
using s = scope();
for (let t: i32 = 0; t < 4; t++) {
s.spawn(addMany, total, done, t);
}
}
using g = total.lock();
console.log(`${g.value.n}`); // 400000
return 0;
};
-
The value is fresh all the way down:
new Mutex<Counter>(new Counter()), never a value you still hold another reference to, which would be a way round the lock. -
Use the guard only as
g.value, and only to read or store a number, aboolean, an enum or astringthrough it. A string you store is copied into memory theMutexowns, and one you read is copied out to you, so neither side keeps a pointer the other can free.You may hand
gto a function of your own, called by name —bump(g)withconst bump = (g: MutexGuard<Counter>): void => { … }— which uses it the same way. Don't bindgorg.valueto another name, store or return either, or keep an array they reach: anything that outlives the block would outlive the lock (NL2466 for the guard, NL2467 for what it reaches). -
One lock at a time, and no waiting while you hold it. Inside a guard's block — directly or through any call — there is no second
lock(), noscope()and no parallel map. That is why a program that compiles cannot deadlock. -
Make the updates commute, as a count or an integer sum does. Natively the tasks take the lock in whatever order the scheduler picks, and under Node they take it in spawn order; only an order-independent update prints the same both ways.
-
A lock nobody holds is cheap; keep the block short. Taking a free lock is one atomic instruction. A task that finds the lock held checks again 64 times in a tight loop and then keeps checking, giving its core up to another thread before each check, so a long block makes every waiter spend processor time waiting for it.
A helper that takes the guard does the block's work under the block's lock, so the work can be split into functions without taking the lock twice:
import { Mutex, MutexGuard, scope } from "nish/threads";
class Stats {
count: i32 = 0;
total: i32 = 0;
}
const note = (g: MutexGuard<Stats>, x: i32): void => {
g.value.count = g.value.count + 1; // the helper uses `g` as the block would
g.value.total = g.value.total + x;
};
const addAll = (stats: Mutex<Stats>, xs: i32[]): void => {
for (const x of xs) {
using g = stats.lock();
note(g, x);
}
};
export const main = (): i32 => {
const stats = new Mutex<Stats>(new Stats());
const low: i32[] = [1, 2, 3];
const high: i32[] = [40, 50];
{
using s = scope();
s.spawn(() => addAll(stats, low));
s.spawn(() => addAll(stats, high));
}
using g = stats.lock();
console.log(`${g.value.count} ${g.value.total}`); // 5 96
return 0;
};
What is refused, and why. The guard is the lock, so anything that could
keep the guard past its block is refused. A helper is a plain function called
by name. Binding, storing, returning or walking the guard itself is refused
(NL2466), and handing g to a method, a constructor or a generic function is
refused too (NL2536), since this or a type parameter is a way for the guard
to be kept, and so is handing it twice in one call.
Binding, storing, returning or walking an object read through the guard, const c = g.value, is refused (NL2467); storing anything but a number, a boolean,
an enum or a string into it is refused (NL2468). null is stored only into a
string | null slot; into a slot that holds an object, next: Link | null, it
is refused (NL2537), since a guard stores no object. A guard bound with const
would never be released (NL2465). A second lock inside a guard's block is
refused because two tasks each holding one lock and waiting for the other would
wait forever.
import { Mutex, MutexGuard } from "nish/threads";
class Stats {
count: i32 = 0;
}
class Log {
last: i32 = 0;
note(g: MutexGuard<Stats>): void { // a method: `this` is a second way out
this.last = g.value.count;
}
}
export const main = (): i32 => {
const stats = new Mutex<Stats>(new Stats());
const log = new Log();
using g = stats.lock();
log.note(g);
return log.last;
};
import { Mutex } from "nish/threads";
class Counter {
n: i32 = 0;
}
export const main = (): i32 => {
const m = new Mutex<Counter>(new Counter());
const g = m.lock(); // a guard not bound by `using` would never be released
return g.value.n;
};
Counting without a lock: AtomicI32 and AtomicI64
When what tasks share is a counter, or one per bin of a histogram, an atomic is cheaper than a lock. Each method is one indivisible step, so no update is lost when two threads make one at the same moment. The fast pattern is the one below: each task counts into its own local array, then adds each count to the shared atomic once, at its end:
import { AtomicI32, parallelMapInto, scope } from "nish/threads";
class Shard {
xs: i32[];
bins: AtomicI32[];
constructor(xs: i32[], bins: AtomicI32[]) {
this.xs = xs;
this.bins = bins;
}
}
const binShard = (s: Shard): i32 => {
const local: i32[] = [0, 0, 0, 0]; // this task's own counts
for (const x of s.xs) {
const bin: i32 = x & 3;
if (bin < local.length) {
local[bin] += 1;
}
}
for (let b = 0; b < local.length; b++) {
s.bins[b].add(local[b]); // one indivisible add per bin, no lock
}
return 0;
};
export const main = (): i32 => {
const bins: AtomicI32[] = [new AtomicI32(0), new AtomicI32(0), new AtomicI32(0), new AtomicI32(0)];
const done: i32[] = [0, 0];
{
using s = scope();
s.spawn(binShard, new Shard([1, 2, 3, 4, 5], bins), done, 0);
s.spawn(binShard, new Shard([6, 7, 8], bins), done, 1);
}
const big = new AtomicI32(0);
const xs: i32[] = [3, 9, 4];
const ys: i32[] = [0, 0, 0];
parallelMapInto(xs, ys, (x) => big.max(x)); // a parallel function may update an atomic
console.log(`${bins[0].load()} ${bins[1].load()} ${big.load()}`); // 2 2 9
return 0;
};
-
The methods:
load(),store(v),add(n),sub(n),min(v),max(v),exchange(v)andcompareExchange(expected, desired). Each update gives back the value the counter held just before it;compareExchangestoresdesiredonly when the counter holdsexpected, and gives back what it found either way. - Only call its methods. The number inside is not a field you can read or store.
-
Don't touch it in the scope's block once the first task is spawned. Read
it before the first
spawnor after the block, when every task has finished. -
Scopes opened by one
usingshare nothing. Inusing s = scope(), t = scope(),t's tasks finish befores's natively, and under Node each runs where it is spawned, so a task ofsand a task oftmay not use the same destination array, the same atomic or the same lock. Two counters each made withnewin aconstof their own are two counters, and their tasks are fine side by side; one counter reached through a second name or a field counts as any counter of its type. Open scopes that share something inusingstatements of their own. -
Make the updates commute.
add,sub,minandmaxgive the same total whatever order the threads made them in; astore, anexchange, or an answer that depends on a value another task is changing does not, and would print differently natively and under Node. -
An
AtomicI64holds ani64. Node holds it as anumber: it agrees with native while values stay within ±2^53, and wrapping at 2^63 is native-only, the same limit as everyi64. Pass iti64values, nottoI64of a number, which is a BigInt under Node. -
Update it once per batch, not once per value. An atomic is cheaper than
a lock, not free: four tasks incrementing the same few counters wait on each
other's cores. Binning 32 million values into 256 bins on four cores
(
examples/histogram-atomic.ts) takes 24 ms with a local tally and oneaddper bin, 77 ms on one thread, and 677 ms with oneaddper value.
What is refused, and why. An atomic is safe to update from any task, but
its value is only an answer once every task has finished. So reading it inside
the scope's block after the first spawn, while the tasks may still be adding
to it, is refused (NL2513): the number would depend on how far each thread had got. Two scopes
opened by one using may not share an atomic either (NL2516), since natively
one scope's tasks finish before the other's start and under Node they run as
they are spawned, so the two would print different answers.
import { AtomicI32, scope } from "nish/threads";
const bump = (a: AtomicI32): i32 => a.add(1);
export const main = (): i32 => {
const a = new AtomicI32(0);
const done: i32[] = [0];
let seen: i32 = 0;
{
using s = scope();
s.spawn(bump, a, done, 0);
seen = a.load(); // the task may not have run yet
}
return seen;
};
Read it once the block has closed, when every task has finished:
import { AtomicI32, scope } from "nish/threads";
const bump = (a: AtomicI32): i32 => a.add(1);
export const main = (): i32 => {
const a = new AtomicI32(0);
const done: i32[] = [0];
{
using s = scope();
s.spawn(bump, a, done, 0);
}
const seen = a.load(); // every task has finished
console.log(`${seen}`); // 1
return 0;
};
import { AtomicI32, scope } from "nish/threads";
const bump = (a: AtomicI32): i32 => a.add(1);
const peek = (a: AtomicI32): i32 => a.load();
export const main = (): i32 => {
const a = new AtomicI32(0);
const bumped: i32[] = [0];
const seen: i32[] = [0];
{
using s = scope(), t = scope(); // t's tasks finish first natively
s.spawn(bump, a, bumped, 0);
t.spawn(peek, a, seen, 0);
}
return seen[0];
};
Many counters in one buffer: AtomicI32Array and AtomicI64Array
When there are many counters, or they are hot, keep them in one atomic array:
new AtomicI32Array(n) is n atomic i32s side by side in one buffer, each
starting at 0. Every method of AtomicI32 has a twin that takes the
element's index first, so hits.add(r, 1) adds 1 to counter r in one
indivisible step. This counts requests and bytes per route from a parallel
function:
import { AtomicI32Array, AtomicI64Array, parallelFrom } from "nish/threads";
const ROUTES: i32 = 4; // 0 = /, 1 = /login, 2 = /api, 3 = anything else
export const main = (): i32 => {
const hits = new AtomicI32Array(ROUTES); // one counter per route, one buffer
const bytes = new AtomicI64Array(ROUTES); // bytes served per route
const routes: i32[] = [0, 2, 2, 1, 2, 3, 0, 2];
const sizes: i64[] = [512, 90, 120, 300, 80, 64, 512, 100];
const seen = parallelFrom(routes.length, (i): i32 => {
hits.add(routes[i], 1); // one indivisible add on element routes[i]
bytes.add(routes[i], sizes[i]);
return routes[i];
});
for (let r = 0; r < hits.length; r++) {
console.log(`route ${r}: ${hits.load(r)} hits, ${bytes.load(r)} bytes`);
}
return seen.length - routes.length; // 0
};
It prints:
route 0: 2 hits, 1024 bytes
route 1: 1 hits, 300 bytes
route 2: 4 hits, 390 bytes
route 3: 1 hits, 64 bytes
-
The methods:
load(i),store(i, v),add(i, n),sub(i, n),min(i, v),max(i, v),exchange(i, v)andcompareExchange(i, expected, desired), each doing to elementiwhatAtomicI32's does to its counter.lengthsays how many elements there are; it is fixed when the array is made. -
An index out of range stops the program, as it does for any array:
index out of range: 16 >= 16, exit status 1. -
The rules are the atomic's. Only call its methods; don't touch it in the
scope's block once the first task is spawned; scopes opened by one
usingdon't share one; make the updates commute. AnAtomicI64Arrayholdsi64s with the same ±2^53 limit under Node, so give iti64values, assizesis above.
When to choose it over AtomicI32[]. An AtomicI32[] is one object per
counter, each its own allocation, so sixteen counters end up spread over
several cache lines, and the cores that update them pass those lines back and
forth. An AtomicI32Array(16) is sixteen adjacent i32s in 64 contiguous
bytes, the layout Rust's [AtomicI32; 16] has. Binning 3.2 million values
into 16 bins on four cores (bench/par-histogram-atomic.ts) took 58 to 66 ms
on the array against 101 to 114 ms on sixteen AtomicI32s, about 1.7x
faster. Use an AtomicI32 for one
counter, or for counters that belong to different objects. And a tally no other
core touches is cheaper still: when you can, count into a task's own local
array and add it to the shared one once, at the task's end, as the example
above does.
Passing values: Channel<T>
A Channel carries numbers or strings from the tasks that produce them to one that
consumes them. Producers call send, which never waits; the consumer walks
the channel with for...of, which waits for values and ends once every task
that may send has returned. Nobody closes a channel, so nobody can close one
too early.
import { Channel, scope } from "nish/threads";
class Pipe {
ch: Channel<i32>;
n: i32;
constructor(ch: Channel<i32>, n: i32) {
this.ch = ch;
this.n = n;
}
}
const produce = (p: Pipe): i32 => {
for (let i: i32 = 1; i <= p.n; i++) {
p.ch.send(i);
}
return p.n;
};
const consume = (p: Pipe): i32 => {
let sum: i32 = 0;
for (const x of p.ch) {
sum = sum + x;
}
return sum;
};
export const main = (): i32 => {
const sent: i32[] = [0, 0];
const sums: i32[] = [0];
const ch = new Channel<i32>(); // a `const`, right before its scope
{
using s = scope();
s.spawn(produce, new Pipe(ch, 10), sent, 0); // every sender first
s.spawn(produce, new Pipe(ch, 20), sent, 1);
s.spawn(consume, new Pipe(ch, 0), sums, 0); // then the one receiver
}
console.log(`${sums[0]}`); // 265
return 0;
};
-
A channel carries a number, a
boolean, an enum or astring. A string is copied when it is sent and again when it is received, so the receiver owns what it gets. Never an array or an object. -
Declare it as a
constjust before its scope, and hand it to a task as the task's argument or as a field of the object you build for it in thespawn, asnew Pipe(ch, 10)does. Don't bind it to another name, store it anywhere else or return it.new Channel<i32>()takes no capacity: a channel is unbounded. -
In the constructor of a class that holds a channel, use
thisonly for its own fields: set them, update them, read the ones that are numbers, strings or arrays of those, and store into what a channel-free field holds. Never handthison, call a method on it, or keep it anywhere. - One scope and one receiver. Only one scope's tasks use a channel, and it has exactly one receiver: a single task, or the parent after the scope's block. The parent sends only before the block.
- Spawn every sender before the receiver, and never let one task both send and receive on the same channel. Channels cannot deadlock because of this order.
- Print what the interleaving cannot change. Values from two senders arrive in the scheduler's order natively and in spawn order under Node, so a sum or a count is the same both ways and a list of the values is not.
What is refused, and why. A program that compiles cannot wait forever on a channel, and gives the same answer natively and under Node. A receiver spawned before a sender is refused (NL2481): under Node, where tasks run one after another in spawn order, it would find the channel empty and end before the sender ran. So is a task that both sends and receives, a second receiver, and a channel kept past its scope, each of which could leave a receiver waiting for a value no task will send.
import { Channel, scope } from "nish/threads";
const one = (ch: Channel<i32>): i32 => {
ch.send(1);
return 1;
};
const drain = (ch: Channel<i32>): i32 => {
let sum: i32 = 0;
for (const x of ch) {
sum = sum + x;
}
return sum;
};
export const main = (): i32 => {
const out: i32[] = [0, 0];
const ch = new Channel<i32>();
{
using s = scope();
s.spawn(drain, ch, out, 0); // the receiver first: under Node it finds nothing
s.spawn(one, ch, out, 1);
}
return out[0];
};
What crosses between threads
Each task has memory of its own, freed when the scope joins, so a value that leaves a task is copied into the memory of whoever receives it:
import { Mutex, scope } from "nish/threads";
class Last {
name: string = "";
}
const label = (n: i32): string => `job-${n}`;
const record = (box: Mutex<Last>): void => {
using g = box.lock();
g.value.name = label(3); // copied into memory the Mutex owns
};
export const main = (): i32 => {
const names: string[] = ["", ""];
const last = new Mutex<Last>(new Last());
{
using s = scope();
s.spawn(label, 1, names, 0); // the answer is copied out at the join
s.spawn(label, 2, names, 1);
s.spawn(record, last);
}
using g = last.lock();
console.log(`${names[0]} ${names[1]} ${g.value.name}`); // job-1 job-2 job-3
return 0;
};
-
Crosses: a number, a
boolean, an enum, astring, and an array of numbers, booleans or enums. That covers a task's answer stored in its destination, each element of aparallelMaporparallelFromthat answers strings, a value sent on aChannel<string>, and a string stored through a guard. -
Doesn't cross: an object of a class, an array of arrays, a
string[], aMapor aSet. Each holds pointers into the task's memory, which is gone once the task is joined, so an entry or a map that answers one is refused. Answer the numbers or strings it is built from, or build it after the scope from what the tasks answered. -
The copy back runs on every thread. A
parallelMaporparallelFromelement that is a string or an array is moved into a block of its chunk's as it is answered, and the joining thread takes the blocks whole, so a map of a million short strings took a median of 24 ms on four threads, against 40 ms for the same loop on one. A scope's task answer is copied in by the joining thread when it is under 64 KB, and taken whole above that.
Letting nish --fix write it
Most refusals in a thread program have one usual repair, and
nish --fix writes it in your source and compiles again.
This task reads a let that changes before the scope:
import { scope } from "nish/threads";
export const main = (): i32 => {
let k: i32 = 3;
k = k + 1;
const out: i32[] = [0];
{
using s = scope();
s.spawn((n: i32): i32 => n * k, 5, out, 0); // NL2506: `k` could change first
}
console.log(`${out[0]}`);
return 0;
};
nish --fix main.ts snapshots it in a const just before the spawn, which
the task may read:
import { scope } from "nish/threads";
export const main = (): i32 => {
let k: i32 = 3;
k = k + 1;
const out: i32[] = [0];
{
using s = scope();
const kNow = k;
s.spawn((n: i32): i32 => n * kNow, 5, out, 0); // reads the snapshot
}
console.log(`${out[0]}`); // 20
return 0;
};
It writes these repairs: const becomes using for a scope or a guard
bound without it (NL2388, NL2465); a task that answers a number or a
boolean with nowhere to store it gets a destination,
const answer = new Array<i32>(1) for an i32 task, above the scope and , answer, 0 after its
arguments (NL2511); a let an arrow task or a parallelMap arrow reads gets
a const snapshot (NL2506, NL2500); and an arrow that uses a channel moves to
a top-level const, mainTask, which the spawn names (NL2484).
It writes a repair only where your source alone decides it, so it leaves alone
a spawn in a loop, where every task would write the one slot; a let another
argument of the call names, or one a for header declares; and a channel arrow
that captures a local or leaves a parameter's or its result's type out, which
would not check at the top level; those stay refused for you to fix by hand.
The reference lists each case: What nish --fix writes for a thread
program.
Refused, and what to write instead
Every refusal on this page ends with the code to write in its place, in your program's own names where the compiler has them. This table pairs each one with an example on this page that compiles.
| Code | Refused | Write instead |
|---|---|---|
| NL2345 | f of a parallel call writes what its caller can see, or prints |
f answers the value, const square = (x: f64): f64 => x * x, and the call writes it, parallelMapInto(src, dst, square): the first example |
| NL2348 | an element answer that is an array of strings or arrays, an object, a Map or a Set |
answer a string or a number per element, const squares = parallelFrom(5, (i) => i * i), and build the structure after the call: parallelFrom |
| NL2503 | a parallel arrow writes a local of its function | answer the value from the body instead, and fold the answers with parallelReduce, const sumTotal = parallelReduce([1, 2, 3], (a, b) => a + b, 0): below the rule |
| NL2500 | a parallel arrow reads a let |
a const snapshot before the call, const kNow = k: below |
| NL2388 | scope() bound without using |
using s = scope(): below |
| NL2584 | scopeWithStack given a number below 131072 |
at least the minimum, scopeWithStack(64 * 1024 * 1024): below |
| NL2506 | an arrow task reads a let |
a const snapshot before the spawn, const kNow = k: nish --fix |
| NL2511 | a task that answers a value has no destination | const answer = new Array<i32>(1) above the scope and s.spawn(twice, 21, answer, 0): below |
| NL2465 | m.lock() bound without using |
using g = total.lock(): Mutex<T> |
| NL2536 | a guard handed to a method, a constructor or a generic function | a top-level helper, const note = (g: MutexGuard<Stats>, x: i32): void => {, called as note(g, x): the helper |
| NL2513 | an atomic read inside the scope's block after a spawn |
read it after the block, const seen = a.load(): atomics |
| NL2516 | two scopes of one using share an atomic |
one using per scope, using s = scope() and using t = scope(): below |
| NL2481 | a channel's receiver spawned before a sender | spawn every sender first, s.spawn(produce, new Pipe(ch, 10), sent, 0) above s.spawn(consume, new Pipe(ch, 0), sums, 0): Channel<T> |
| NL2484 | an arrow that uses a channel | a module function the spawn names, const mainTask = (c: Channel<i32>): void => { and s.spawn(mainTask, ch): below |
A let read by a parallel arrow
import { parallelMap } from "nish/threads";
export const main = (): i32 => {
let k: i32 = 3;
k = k + 1;
const xs: i32[] = [1, 2, 3];
const ys = parallelMap(xs, (x: i32): i32 => x * k); // `k` is a `let`
return ys[0];
};
Snapshot it in a const before the call, as nish --fix does:
import { parallelMap } from "nish/threads";
export const main = (): i32 => {
let k: i32 = 3;
k = k + 1;
const xs: i32[] = [1, 2, 3];
const kNow = k;
const ys = parallelMap(xs, (x: i32): i32 => x * kNow);
console.log(`${ys[2]}`); // 12
return 0;
};
A scope bound without using
import { scope } from "nish/threads";
const twice = (n: i32): i32 => n * 2;
export const main = (): i32 => {
const out: i32[] = [0];
{
const s = scope(); // never joined: its task might never run
s.spawn(twice, 21, out, 0);
}
return out[0];
};
Declare it with using, so the block's end joins it, as nish --fix does:
using s = scope(), as in the first scope example.
A stack below the minimum
import { scopeWithStack } from "nish/threads";
const twice = (n: i32): i32 => n * 2;
export const main = (): i32 => {
const out: i32[] = [0];
{
using s = scopeWithStack(4096); // no thread starts on 4 KiB
s.spawn(twice, 21, out, 0);
}
return out[0];
};
Ask for at least 131072 bytes. A program that needs a larger stack asks for
megabytes: using s = scopeWithStack(64 * 1024 * 1024), as in
the deep-recursion example.
A task answer with nowhere to go
import { scope } from "nish/threads";
const twice = (n: i32): i32 => n * 2;
export const main = (): i32 => {
{
using s = scope();
s.spawn(twice, 21); // the answer has nowhere to go
}
return 0;
};
Give the answer a one-slot destination above the scope, as nish --fix does,
and read it after the block:
import { scope } from "nish/threads";
const twice = (n: i32): i32 => n * 2;
export const main = (): i32 => {
const answer = new Array<i32>(1);
{
using s = scope();
s.spawn(twice, 21, answer, 0);
}
console.log(`${answer[0]}`); // 42
return 0;
};
Two scopes that share an atomic
The NL2516 example opens two
scopes in one using. Give each scope its own block, so the first one's tasks
have finished before the second one's start, natively and under Node alike:
import { AtomicI32, scope } from "nish/threads";
const bump = (a: AtomicI32): i32 => a.add(1);
const peek = (a: AtomicI32): i32 => a.load();
export const main = (): i32 => {
const a = new AtomicI32(0);
const bumped: i32[] = [0];
const seen: i32[] = [0];
{
using s = scope();
s.spawn(bump, a, bumped, 0);
}
{
using t = scope();
t.spawn(peek, a, seen, 0);
}
console.log(`${seen[0]}`); // 1
return 0;
};
A channel in an arrow
import { Channel, scope } from "nish/threads";
export const main = (): i32 => {
const ch = new Channel<i32>();
{
using s = scope();
s.spawn((c: Channel<i32>): void => { c.send(1); }, ch); // an arrow with a channel
}
let total: i32 = 0;
for (const v of ch) {
total = total + v;
}
return total;
};
The refusal writes the arrow out as a module function, named for the function
it was in, mainTask; put it above main and name it in the spawn, as
nish --fix does:
import { Channel, scope } from "nish/threads";
const mainTask = (c: Channel<i32>): void => {
c.send(1);
};
export const main = (): i32 => {
const ch = new Channel<i32>();
{
using s = scope();
s.spawn(mainTask, ch);
}
let total: i32 = 0;
for (const v of ch) {
total = total + v;
}
console.log(`${total}`); // 1
return 0;
};
The full rules, and the code each one is refused with, are in the reference:
Data parallelism,
Scoped tasks,
Mutex<T>,
Atomics and
Channel<T>.

