Concurrency and parallelism

// A thread shares its process's memory.
// A new process gets its own copy of it.
const memory = { count: 0, name: "game state" };
​
const threadView = memory;                    // same object
const processView = structuredClone(memory);  // a full copy
​
threadView.count += 1;
processView.count += 100;
​
console.log("original:", memory.count);       // the thread's change shows
console.log("process copy:", processView.count);
console.log("same object?", threadView === memory, processView === memory);

// Three tasks, one worker: a scheduler that takes turns.
// Each task is a generator; "yield" means "I can pause here".
function* task(name, steps) {
  for (let i = 1; i <= steps; i++) {
    console.log(name + i);
    yield;
  }
}
​
const ready = [task("A", 3), task("B", 3), task("C", 3)];
let tick = 0;
​
while (ready.length > 0) {
  const t = ready.shift();      // take the task at the front
  const { done } = t.next();    // run it until it yields
  tick++;
  if (!done) ready.push(t);     // not finished: back of the queue
}
console.log("finished after", tick, "turns on one core");

let count = 0;
const pause = () => new Promise((r) => setTimeout(r, 0));
​
async function increment(name) {
  const seen = count;        // 1. READ the shared value
  await pause();             // ...the other thread runs here...
  count = seen + 1;          // 2. WRITE back what this thread computed
  console.log(name, "wrote", count);
}
​
await Promise.all([increment("T1"), increment("T2")]);
console.log("two increments, count =", count);

// Two "threads" each add 1 to count 1000 times.
// A scheduler may switch between them after any step,
// like a real OS can. Each increment is THREE steps.
function* incrementer(state, regs, id, times) {
  for (let i = 0; i < times; i++) {
    regs[id] = state.count;    // READ  into this thread's register
    yield;
    regs[id] = regs[id] + 1;   // ADD   in the register
    yield;
    state.count = regs[id];    // WRITE back to shared memory
    yield;
  }
}
​
function run(seed) {
  let rnd = seed;                       // a tiny seeded random generator
  const random = () => (rnd = (rnd * 16807) % 2147483647) / 2147483647;
  const state = { count: 0 }, regs = [0, 0];
  const threads = [incrementer(state, regs, 0, 1000), incrementer(state, regs, 1, 1000)];
  while (threads.length) {
    const i = random() < 0.5 ? 0 : threads.length - 1;   // who runs next?
    if (threads[i].next().done) threads.splice(i, 1);
  }
  return state.count;
}
​
for (const seed of [1, 2, 3, 4, 5]) {
  console.log("run", seed, "→ count =", run(seed), "(expected 2000)");
}

class Mutex {
  locked = false;
  waiting = [];             // who is queued for the lock
  async lock() {
    if (!this.locked) { this.locked = true; return; }
    await new Promise((wake) => this.waiting.push(wake));
  }                         // when we wake, the lock was handed to us
  unlock() {
    const next = this.waiting.shift();
    if (next) next();       // hand it straight to the next in line
    else this.locked = false;
  }
}
​
let count = 0;
const m = new Mutex();
const pause = () => new Promise((r) => setTimeout(r, 0));
​
async function increment() {
  await m.lock();
  try {
    const seen = count;     // the critical section:
    await pause();          // nobody else can get in here now
    count = seen + 1;
  } finally {
    m.unlock();             // finally: unlock even if something throws
  }
}
​
const jobs = [];
for (let i = 0; i < 100; i++) jobs.push(increment());
await Promise.all(jobs);
console.log("100 increments, count =", count);

class Mutex {
  locked = false; waiting = [];
  async lock() {
    if (!this.locked) { this.locked = true; return; }
    await new Promise((wake) => this.waiting.push(wake));
  }
  unlock() { const n = this.waiting.shift(); n ? n() : (this.locked = false); }
}
const pause = () => new Promise((r) => setTimeout(r, 10));
const accountA = new Mutex(), accountB = new Mutex();
const done = [];
​
async function transfer(name, first, second) {
  await first.lock();
  console.log(name, "holds its first lock");
  await pause();                       // ...long enough for the other to start
  console.log(name, "waits for its second lock");
  await second.lock();                 // waits forever
  done.push(name);
  second.unlock(); first.unlock();
}
​
transfer("T1: A → B", accountA, accountB);
transfer("T2: B → A", accountB, accountA);   // opposite order!
​
void setTimeout(() => {
  console.log("after 0.5 s, finished:", done.length, "of 2");
  if (done.length === 0) console.log("Deadlock: each holds what the other needs.");
}, 500);

// Five philosophers round a table, five forks. Philosopher p
// needs forks p and p+1 (mod 5), so each fork is shared by two.
const N = 5;
const forks = Array(N).fill(null);          // who holds each fork
​
function attempt(order) {
  forks.fill(null);
  const held = Array.from({ length: N }, () => []);
  const wants = (p) => order(p).filter((f) => !held[p].includes(f))[0];
  let moved = true, ate = [];
  while (moved) {
    moved = false;
    for (let p = 0; p < N; p++) {
      if (ate.includes(p)) continue;
      const f = wants(p);
      if (f === undefined) {               // has both forks: eat, then put them down
        ate.push(p);
        for (const g of held[p]) forks[g] = null;
        held[p] = [];
        moved = true;
      } else if (forks[f] === null) {      // the fork it wants next is free
        forks[f] = p; held[p].push(f); moved = true;
      }
    }
  }
  return ate;
}
​
const leftFirst = (p) => [p, (p + 1) % N];
const lowerFirst = (p) => [p, (p + 1) % N].sort((a, b) => a - b);
​
console.log("everyone takes the left fork first, ate:", attempt(leftFirst));
console.log("everyone takes the lower-numbered fork first, ate:", attempt(lowerFirst));

// Atomics: read-modify-write as ONE indivisible step.
const cell = new Int32Array(1);          // one 32-bit integer
​
Atomics.add(cell, 0, 1);                 // count += 1, atomically
Atomics.add(cell, 0, 1);
console.log("after two Atomics.add:", Atomics.load(cell, 0));
​
// compare-and-swap: "if it is still 2, make it 10"
const old1 = Atomics.compareExchange(cell, 0, 2, 10);
console.log("CAS expecting 2: saw", old1, "→ now", cell[0]);
​
// "if it is still 2, make it 99": it isn't, so nothing changes
const old2 = Atomics.compareExchange(cell, 0, 2, 99);
console.log("CAS expecting 2: saw", old2, "→ still", cell[0]);
​
console.log("SharedArrayBuffer here?", typeof SharedArrayBuffer);

// Build any atomic update from compare-and-swap:
// read, compute, and only write if nobody changed it meanwhile.
function atomicDouble(arr, i) {
  let tries = 0;
  while (true) {
    tries++;
    const seen = Atomics.load(arr, i);
    const want = seen * 2;
    if (Atomics.compareExchange(arr, i, seen, want) === seen) return tries;
    // someone else got in first: go round again with the new value
  }
}
​
const cell = new Int32Array([21]);
const tries = atomicDouble(cell, 0);
console.log(cell[0], "after", tries, "try");

// An actor: private state, a mailbox, and one message at a time.
function makeActor(init, receive) {
  const mailbox = [];
  let state = init;
  let busy = false;
  async function drain() {
    busy = true;
    while (mailbox.length) {
      const msg = mailbox.shift();          // one at a time, in order
      state = await receive(state, msg);
    }
    busy = false;
  }
  return {
    send(msg) { mailbox.push(msg); if (!busy) drain(); },
  };
}
​
const counter = makeActor(0, async (count, msg) => {
  await null;                               // pausing mid-message is safe:
  if (msg.type === "inc") return count + 1; // nobody else can touch count
  if (msg.type === "get") msg.reply(count); // answers are messages too
  return count;
});
​
// two senders, 500 messages each, and not a lock anywhere
for (let i = 0; i < 500; i++) {
  counter.send({ type: "inc" });
  counter.send({ type: "inc" });
}
counter.send({ type: "get", reply: (n) => console.log("count =", n) });

// postMessage COPIES what you send (a "structured clone"),
// or MOVES it if you list it as a transfer.
const ch = new MessageChannel();          // two connected ports
const arrived = new Promise((resolve) => {
  ch.port2.onmessage = (e) => resolve(e.data);
});
​
const sent = { score: 1, tags: ["a"] };
ch.port1.postMessage(sent);
sent.score = 999;                         // too late: a copy is on its way
sent.tags.push("changed");
​
const got = await arrived;
console.log("receiver got:", got.score, got.tags);
ch.port1.close();
​
// a transfer hands the memory over instead of copying it
const buf = new ArrayBuffer(1_000_000);
const moved = structuredClone(buf, { transfer: [buf] });
console.log("after the transfer I have", buf.byteLength, "bytes;",
            "the receiver has", moved.byteLength);

// Amdahl's law: p = the share of the work that can run in parallel,
// n = the number of cores. The rest (1 - p) runs on one core.
const speedup = (p, n) => 1 / ((1 - p) + p / n);
​
for (const p of [0.5, 0.9, 0.95, 0.99]) {
  const row = [1, 4, 16, 64, 1024].map((n) => speedup(p, n).toFixed(1).padStart(6));
  console.log("p =", String(p).padEnd(4), row.join(" "),
              "  limit ×" + (1 / (1 - p)).toFixed(0));
}
console.log("cores:      1      4     16     64   1024");

// Gustafson's view: with more cores we usually grow the problem.
// s = serial share of the time on the parallel machine.
const scaled = (s, n) => s + (1 - s) * n;
​
for (const n of [4, 16, 64, 1024]) {
  console.log(n, "cores: Amdahl", (1 / (0.05 + 0.95 / n)).toFixed(1),
              "· Gustafson", scaled(0.05, n).toFixed(1));
}

// A GPU runs the SAME small function (a "kernel") for every index.
// Here a loop stands in for thousands of cores doing it at once.
function add(i, a, b, out) {
  out[i] = a[i] + b[i];
}
​
const n = 8;
const a = Float32Array.from({ length: n }, (_, i) => i);
const b = Float32Array.from({ length: n }, (_, i) => 10 * i);
const out = new Float32Array(n);
​
for (let i = 0; i < n; i++) add(i, a, b, out);   // a GPU: all at once
console.log(Array.from(out));

// GPU threads run in lockstep groups ("warps" of 32 on NVIDIA).
// If threads in a warp take different branches, the warp runs
// BOTH branches one after the other, with half its lanes switched off.
function passes(warp, branch) {
  const goesIf = warp.some((x) => branch(x));
  const goesElse = warp.some((x) => !branch(x));
  return (goesIf ? 1 : 0) + (goesElse ? 1 : 0);
}
​
const warp = Array.from({ length: 32 }, (_, i) => i);
console.log("if (x < 100):   ", passes(warp, (x) => x < 100), "pass");
console.log("if (x % 2 == 0):", passes(warp, (x) => x % 2 === 0), "passes");