← board

parallel for scheduling policy + reduction (load-aware, work-stealing)

Motivation

Today parallel for fans to a fixed worker count (CPU affinity) with a static contiguous split and a join barrier. Two gaps:

  1. No work distribution choice. Contiguous split is pathological for uneven workloads (Mandelbrot: in-set rows cluster in one worker → ~2x on 8 cores until you hand-interleave, see examples/mandelbrot/mandelbrot_parallel.pas). OpenMP solves this with schedule(static|dynamic|guided); we have only static.
  2. No system-load awareness. On a shared/busy box you want to consume only the FREE headroom (e.g. cap at ~90% total CPU, take half the free capacity per poll and re-check) instead of pinning every core. Useful mainly for LONG regions (sampling overhead is real) — an opt-in, experimental knob.

Plus a recurring safety gap: concurrent accumulation into a shared captured var (total := total + f(i)) is a data race — parallel-for captures BY-REF, see [[project_parallel_for_byref_capture_shared_write_race]] and WriteCap's 1-worker guard. A first-class reduction makes the common case safe + ergonomic.

Two ORTHOGONAL axes (design correction 2026-07-17)

An earlier draft mashed distribution and worker-count into one enum. They are independent — OpenMP splits them into schedule() and num_threads() for the same reason:

You compose them freely: "however many cores are free (load-aware) AND hand work out on demand (dynamic) so those workers stay balanced."

Axis 1 — distribution (the OpenMP schedule kinds)

canonical (proposed) OpenMP meaning overhead / balance
pdChunked static P contiguous blocks decided UP FRONT; zero runtime coordination. Bad on uneven loads (Mandelbrot). static,chunk variant = round-robin fixed chunks (interleave) cheapest / worst
pdGuided guided on-demand, chunk size starts big and SHRINKS (∝ remaining/P): few grabs early (cheap), fine tail balance middle / good
pdOnDemand dynamic persistent pool; a free worker grabs the next minChunk iters via an atomic next-index counter. Balances at runtime as workers free up priciest / best

Overhead↔balance ladder: pdChunked → pdGuided → pdOnDemand (small chunk). pdChunked needs no pool (today's path); pdGuided/pdOnDemand need the Phase B work-stealing pool + shared counter.

Axis 2 — worker count (the num_threads / load axis)

canonical (proposed) meaning
pwAllCores fixed = affinity core count (today's default)
pwFixed explicit fixedN workers
pwLoadOnce sample free CPU at region ENTRY, pick P, run to completion (Phase A; cheap, no mid-region reaction)
pwLoadCont monitor thread re-samples every T ms, parks/wakes workers mid-region to hold the headroom target (Phase B; reacts to load changes, higher overhead)

Load-aware has two sub-modes (once vs continuous) — they ARE pwLoadOnce / pwLoadCont, and map directly onto build phases A / B.

Policy record + presets

type
  TParDist    = (pdChunked, pdGuided, pdOnDemand);
  TParWorkers = (pwAllCores, pwFixed, pwLoadOnce, pwLoadCont);
  TParFlag    = (pfPinThreads, pfNoStealFromMain, pfSpinWait);  { future modifiers }
  TParPolicy  = record
    dist:    TParDist;
    workers: TParWorkers;
    fixedN, capPct, minChunk: Integer;   { 0 = mode default }
    flags:   set of TParFlag;            { orthogonal boolean modifiers (later) }
  end;

Convenience presets keep simple calls short:

const
  ParAllCores: TParPolicy = (dist: pdChunked;  workers: pwAllCores);
  ParPolite:   TParPolicy = (dist: pdOnDemand; workers: pwLoadOnce; capPct: 90);

Language surface (decided)

Optional policy value on the keyword — OpenMP's schedule()/num_threads() promoted from a pragma to real syntax. Bare parallel for unchanged (default = all cores, chunked), so existing code is untouched.

Three ways to pass a policy, in ascending specificity — a preset, an inline record, or named args in the clause (the compiler folds the named args into a policy; preferred inline form, see rationale below):

{ (a) preset — covers ~95% of uses, stays short }
parallel(ParPolite) for i := 0 to N-1 do Work(i);

{ (b) inline const record (plain record, compile-time const, NO heap) }
const HeavyIO: TParPolicy =
  (dist: pdOnDemand; workers: pwLoadCont; capPct: 80; minChunk: 64);
parallel(HeavyIO) for i := 0 to N-1 do Work(i);

{ (c) named args in the clause — inline tuning WITHOUT a named const, still
      type-checked + folded to a policy by the compiler (Phase 2 grammar) }
parallel(pdOnDemand, cap 90, chunk 64) for i := 0 to N-1 do Work(i);
parallel(workers pwLoadOnce, cap 90)   for i := 0 to N-1 do Work(i);

{ reduction: RTL gives each worker a private partial, combines at the barrier }
parallel(ParPolite) for i := 0 to N-1
  reduction(+: total)
do
  total := total + f(i);

{ default — all cores, chunked split, as today }
parallel for i := 0 to N-1 do Work(i);

Named-arg keys map 1:1 to TParPolicy fields (dist, workers, cap→capPct, chunk→minChunk, n→fixedN); a bare TParDist/TParWorkers/preset as the first arg sets that and defaults the rest. The parser validates keys + rejects duplicate/contradictory axes — the safety a packed int can't give.

Precedence

loop clause > PXXSetParForPolicy(P) (process default) > built-in default (all cores, chunked).

Why a RECORD (+ presets / named args), NOT packed bit-flags

Considered and rejected: encoding the policy as OR-able int constants (mLoadAware or 90, mNumCores or 8). Reasons:

Where bit-flags DO belong (later): genuinely orthogonal boolean MODIFIERS (pfPinThreads, pfNoStealFromMain, pfSpinWait) → a flags: set of TParFlag field. Pascal's set of gives OR ergonomics ([pfPinThreads, pfSpinWait]) WITH type safety — never hand-OR'd ints. That is the modifier layer, not the axis layer.

Names — OPEN sub-decision

Clear canonical names above; OpenMP name kept as a documented alias (NOT static/dynamic as bare identifiers — both reserved dialect keywords). pd/pw prefixes shown but not required — final spelling confirmed at implementation. Passing a bare TParDist or TParWorkers = that axis set, the other defaulted.

Names — OPEN sub-decision

Clear canonical names above; OpenMP name kept as a documented alias (NOT static/dynamic as bare identifiers — both reserved dialect keywords). pd/pw prefixes shown but not required — final spelling confirmed at implementation. Passing a bare TParDist or TParWorkers = that axis set, the other defaulted.

Runtime design — build order (A then B, decided)

Phase A — region-entry load throttle (cheap, ~zero overhead)

pwLoadOnce at region entry only: compute nw from free CPU, run the existing pdChunked split. No pool, no monitor thread.

Phase B — dynamic work-stealing pool (pdOnDemand/pdGuided + pwLoadCont)

Two things land together (both need the persistent pool):

Costs: persistent pool, atomic contention, monitor thread, park/wake — worth it only for long regions. This is what "saves the programmer from thread management" (the MTProcs ProcThreadPool setup pain, but owned by the RTL). Note the axes are independent: pdOnDemand + pwAllCores (balance, no throttle) and pdChunked + pwLoadOnce (throttle, no rebalance) are both valid Phase-A/B mixes.

Reduction (v1, decided)

reduction(op: var[, var...]), ops + * min max and or xor. Lowering: each worker gets a private zero/identity-init partial of var's type; the barrier folds partials with op into the real var. Needs: parser grammar (reduction(...) after the header, before do), IR to carry the reduction list, per-worker private slot allocation, a combine step at join. Start with scalar ordinals/floats; managed types later.

Portability

Caveats to document

Precedent (for the implementer)

Acceptance

Log