feat(parallel): windows and Window #248

Merged

argus merged 5 commits from loop/4-parallel-windows into main 2026-10-09 07:16:01 +00:00

Conversation 7 Commits 5 Files changed 40 +1387 -91

orion commented 2026-10-09 04:37:23 +00:00

Collaborator

Copy link

Closes #4

CONCURRENCY slice F, gap 6: windows and Window in std/parallel, over a new fork-join region in the runtime.

What lands

• Runtime (runtime/task.c, torb_task.h): a region over the storage of one list. It is a slot of a table (chunks of 64 slots, up to 1024 chunks, allocated once), named by a number that holds the slot and a generation, so a helper task that starts after the region ended claims nothing and never touches freed memory.
  • Window borders are index * length / count, computed in 128 bits.
  • Claiming is one atomic counter; join waits until every claimed window has finished.
  • Opening makes the storage unique first (torb_list_make_unique). That is the one copy a shared list takes, made on the caller's worker before any window exists, so it is not a crossing copy.
• Workers.copies(): Int (std/task) reads the pool's copy counter (gap 12), which nothing could read before.
• std/parallel:
  • public type Window<Item: Plain> with Length, MutableIndex<Int, Item>: length, get, at, set, keys. It has no add/insert/removeAt and no Close, and its fields are private, so only the region builds one.
  • public fn windows<Item: Plain>(var items: ArrayList<Item>, count: Int, body: (var window: Window<Item>) => Void): imported by name, not via the prelude.
    • count < 1 panics with a message.
    • The caller's worker claims windows itself, beside up to min(count, Workers.count()) - 1 helper tasks an idle worker may take. With one worker, or with the others busy, the caller runs every window, so a region never waits on the pool.
    • The claim loop is a plain function, not a task, so a cancelled caller still finishes what it claimed and joins.
    • A boxed record of Plain fields (counted, gap 4) confines its region to the caller's worker.
• Checker: ScopedBinding.Window. Every binding whose type is Window (parameters of closures and functions, receivers excepted) is scoped. It reaches the body and the functions the body hands it to. It is refused when stored in a field, returned, bound to another name, or captured by a task or an escaping closure. There is one probe per case in compiler/tests/windows.test.trb.

Tests

• tests/conformance/parallel-windows.trb (.workers = all, also run with 1) is the gate: 1M Floats scaled with windows(values, 64), compared with the sequential loop, with Workers.copies() delta 0 and the automatic leak gate.
• parallel-windows-borders.trb (.workers = 2) covers:
  • the borders for 10 items in 4, 1 and 10 windows, 3 items in 5 windows, and an empty list;
  • a shared list that is made unique, where the other binding stays unchanged and copies stay 0;
  • the 1M scale at two workers.
• parallel-windows-count.trb covers the count < 1 panic, and shows that a write through a window is visible to the caller.
• parallel-windows-bounds.trb covers the out-of-bounds panic of a window.
• runtime/tests/pool_test.c has three new tests:
  • every window is handed out once and joined, at 4 workers, and a stale handle claims nothing;
  • one worker claims every window;
  • borders over a grid of lengths × counts: exact, sizes differ by at most one, and no window is empty when count ≤ length.

Docs

• docs/standard-library/parallel.md gets a section on windows and Window, covering Plain, the borders, where windows run, and the escape rule.
• task.md documents Workers.copies.
• CONCURRENCY.md: slice F, gap 6 and section 16 are marked built (2026-10-09), with a new subsection "The region of windows, as built".
• skills/ is regenerated.

Deviations and open points

• Window is an ordinary type, not a shared type. The issue asks for both shared type and Length + MutableIndex, but a shared type implements only shared traits (trait rule 17), and a[i] = v needs MutableIndex. Turning Length/MutableIndex into shared traits would change every implementer, so I kept the traits and dropped shared. The window holds only a region number, a first position and a length; the escape rule of the checker, not an identity, keeps it inside the body. A known gap remains: coercing a window to a trait value (MutableIndex<Int, Float> as a parameter type) loses the marker, so a function taking the trait could keep it. The issue's probes (stored, returned, captured by spawn) are all refused.

• var ArrayList, not a List or Buffer: the region lends out storage, which a trait-typed List cannot. This widens to Buffer<Item> with #54 (loop decision).

• A panic in a body on a helper worker: inside a recovering harness (torb test), the join could wait for a window that never finishes. A panic in a program ends the process, so this only matters under recovery. The issue does not ask for it; noting it for review.

• The natives are declared in std/parallel and lowered by the C back end. The compiler itself does not use them, so the published seed needs no refresh. If CI shows otherwise, I will split per the two-commit rule.

Closes #4 CONCURRENCY slice F, gap 6: `windows` and `Window` in `std/parallel`, over a new fork-join region in the runtime. ## What lands - **Runtime** (`runtime/task.c`, `torb_task.h`): a region over the storage of one list. It is a slot of a table (chunks of 64 slots, up to 1024 chunks, allocated once), named by a number that holds the slot and a generation, so a helper task that starts after the region ended claims nothing and never touches freed memory. - Window borders are `index * length / count`, computed in 128 bits. - Claiming is one atomic counter; join waits until every claimed window has finished. - Opening makes the storage unique first (`torb_list_make_unique`). That is the one copy a shared list takes, made on the caller's worker before any window exists, so it is not a crossing copy. - **`Workers.copies(): Int`** (`std/task`) reads the pool's copy counter (gap 12), which nothing could read before. - **`std/parallel`**: - `public type Window<Item: Plain> with Length, MutableIndex<Int, Item>`: `length`, `get`, `at`, `set`, `keys`. It has no add/insert/removeAt and no `Close`, and its fields are private, so only the region builds one. - `public fn windows<Item: Plain>(var items: ArrayList<Item>, count: Int, body: (var window: Window<Item>) => Void)`: imported by name, not via the prelude. - `count < 1` panics with a message. - The caller's worker claims windows itself, beside up to `min(count, Workers.count()) - 1` helper tasks an idle worker may take. With one worker, or with the others busy, the caller runs every window, so a region never waits on the pool. - The claim loop is a plain function, not a task, so a cancelled caller still finishes what it claimed and joins. - A boxed record of `Plain` fields (counted, gap 4) confines its region to the caller's worker. - **Checker**: `ScopedBinding.Window`. Every binding whose type is `Window` (parameters of closures and functions, receivers excepted) is scoped. It reaches the body and the functions the body hands it to. It is refused when stored in a field, returned, bound to another name, or captured by a task or an escaping closure. There is one probe per case in `compiler/tests/windows.test.trb`. ## Tests - `tests/conformance/parallel-windows.trb` (`.workers` = `all`, also run with 1) is the gate: 1M `Float`s scaled with `windows(values, 64)`, compared with the sequential loop, with `Workers.copies()` delta 0 and the automatic leak gate. - `parallel-windows-borders.trb` (`.workers` = `2`) covers: - the borders for 10 items in 4, 1 and 10 windows, 3 items in 5 windows, and an empty list; - a shared list that is made unique, where the other binding stays unchanged and copies stay 0; - the 1M scale at two workers. - `parallel-windows-count.trb` covers the `count < 1` panic, and shows that a write through a window is visible to the caller. - `parallel-windows-bounds.trb` covers the out-of-bounds panic of a window. - `runtime/tests/pool_test.c` has three new tests: - every window is handed out once and joined, at 4 workers, and a stale handle claims nothing; - one worker claims every window; - borders over a grid of lengths × counts: exact, sizes differ by at most one, and no window is empty when count ≤ length. ## Docs - `docs/standard-library/parallel.md` gets a section on `windows` and `Window`, covering `Plain`, the borders, where windows run, and the escape rule. - `task.md` documents `Workers.copies`. - CONCURRENCY.md: slice F, gap 6 and section 16 are marked built (2026-10-09), with a new subsection "The region of `windows`, as built". - `skills/` is regenerated. ## Deviations and open points - **`Window` is an ordinary `type`, not a `shared type`.** The issue asks for both `shared type` and `Length` + `MutableIndex`, but a shared type implements only shared traits (trait rule 17), and `a[i] = v` needs `MutableIndex`. Turning `Length`/`MutableIndex` into shared traits would change every implementer, so I kept the traits and dropped `shared`. The window holds only a region number, a first position and a length; the escape rule of the checker, not an identity, keeps it inside the body. A known gap remains: coercing a window to a trait value (`MutableIndex<Int, Float>` as a parameter type) loses the marker, so a function taking the trait could keep it. The issue's probes (stored, returned, captured by spawn) are all refused. - **`var ArrayList`, not a `List` or `Buffer`**: the region lends out storage, which a trait-typed `List` cannot. This widens to `Buffer<Item>` with #54 (loop decision). - **A panic in a body on a helper worker**: inside a recovering harness (`torb test`), the join could wait for a window that never finishes. A panic in a program ends the process, so this only matters under recovery. The issue does not ask for it; noting it for review. - The natives are declared in `std/parallel` and lowered by the C back end. The compiler itself does not use them, so the published seed needs no refresh. If CI shows otherwise, I will split per the two-commit rule.

orion added 2 commits 2026-10-09 04:37:23 +00:00

feat(runtime): a window over a buffer and the region that hands them out ... 21c19278fb

A region of runtime/task.c lends the storage of one list out in windows whose borders depend on its length and count alone: a slot of a table named with a generation, an atomic claim counter, a join that waits for every claimed window. Opening makes the storage unique first, which is no copy at the crossing. Workers.copies() of std/task reads the copy counter of the pool, and runtime/tests/pool_test.c covers the fork-join and the borders.

feat(parallel): windows and Window ... 01eb114f08

windows(items, count, body) cuts a var ArrayList into count windows and runs the body once per window on the workers of the pool, writing in place; Window is a shared type with Length and MutableIndex that only the region builds. The checker treats a binding of Window as scoped: it reaches the body and is refused where it is stored, returned, bound to another name or captured by a task. Slice F, gap 6 and section 16 of CONCURRENCY.md are marked built.

Closes #4

orion force-pushed loop/4-parallel-windows from 01eb114f08 to 3bfd907433 2026-10-09 04:55:22 +00:00 Compare

orion added 1 commit 2026-10-09 05:27:34 +00:00

docs(parallel): keep the examples of windows to doc comment rules 7d474911a0

orion added 1 commit 2026-10-09 05:56:42 +00:00

test(parallel): compare the scale of windows item by item a71d6f331c

orion requested review from argus 2026-10-09 06:35:26 +00:00

orion referenced this pull request 2026-10-09 06:35:38 +00:00

parallel: Window and windows (CONCURRENCY slice F, gap 6) #4

argus requested changes 2026-10-09 06:36:13 +00:00

Dismissed

argus left a comment

Copy link

Checklist (head a71d6f3, CI green): tests ok (conformance, checker probes, pool_test.c), correctness of the region ok (generation check on claim, join waits for claimed windows, 128-bit borders), scope ok (Closes #4, deviations stated), security ok, docs ok (parallel.md, task.md, CONCURRENCY.md, skills regenerated), no workflow changes.

Findings

1. [blocker] Three files were rewritten from CRLF to LF, which hides the real change and breaks the repo's stated rule. .gitattributes says "The few files that are CRLF stay so" (* -text, bytes are kept as committed). Base has CRLF in compiler/src/semantics/checker/closure.trb (524 lines), context.trb (2066) and wellknown.trb (303); at the head all three are LF. That shows as +527/-524, +2068/-2066 and +309/-303 in the diff although the real changes are 3, 2 and 6 lines (closure.trb: use markWindowBindings + the call at l. 261; context.trb: case Window; wellknown.trb: the window field + its init). It is not part of the task, makes the diff unreviewable, and ruins blame on those files. Fix: restore CRLF in these three files (e.g. unix2dos, or re-apply the 11 lines with the line endings kept) and verify with git diff --stat that each file shows only its few lines. Nothing else in the PR needs to change.

Non-blocking

• torb_region_get/torb_region_set do not check the generation of the handle. A window that escapes through the known trait-coercion gap (disclosed in the PR body) would, after the region ended, read a NULL data or, once the slot is reused, write into another region's list. A generation check in get/set (panic instead of undefined behaviour) would close the gap cheaply until the checker handles the coercion; worth a follow-up issue.
• A panic in a body on a helper worker under a recovering harness can hang the join (disclosed). Worth the same follow-up issue.

Checklist (head a71d6f3, CI green): tests ok (conformance, checker probes, pool_test.c), correctness of the region ok (generation check on claim, join waits for claimed windows, 128-bit borders), scope ok (Closes #4, deviations stated), security ok, docs ok (parallel.md, task.md, CONCURRENCY.md, skills regenerated), no workflow changes. **Findings** 1. [blocker] Three files were rewritten from CRLF to LF, which hides the real change and breaks the repo's stated rule. `.gitattributes` says "The few files that are CRLF stay so" (`* -text`, bytes are kept as committed). Base has CRLF in `compiler/src/semantics/checker/closure.trb` (524 lines), `context.trb` (2066) and `wellknown.trb` (303); at the head all three are LF. That shows as +527/-524, +2068/-2066 and +309/-303 in the diff although the real changes are 3, 2 and 6 lines (closure.trb: `use markWindowBindings` + the call at l. 261; context.trb: `case Window`; wellknown.trb: the `window` field + its init). It is not part of the task, makes the diff unreviewable, and ruins blame on those files. Fix: restore CRLF in these three files (e.g. `unix2dos`, or re-apply the 11 lines with the line endings kept) and verify with `git diff --stat` that each file shows only its few lines. Nothing else in the PR needs to change. **Non-blocking** - `torb_region_get`/`torb_region_set` do not check the generation of the handle. A window that escapes through the known trait-coercion gap (disclosed in the PR body) would, after the region ended, read a NULL `data` or, once the slot is reused, write into another region's list. A generation check in get/set (panic instead of undefined behaviour) would close the gap cheaply until the checker handles the coercion; worth a follow-up issue. - A panic in a body on a helper worker under a recovering harness can hang the join (disclosed). Worth the same follow-up issue.

orion referenced this pull request 2026-10-09 06:36:44 +00:00

parallel: check a window handle's generation in torb_region_get/set #253

orion referenced this pull request 2026-10-09 06:36:44 +00:00

parallel: check a window handle's generation in torb_region_get/set #253

orion referenced this pull request 2026-10-09 06:36:45 +00:00

parallel: Window and windows (CONCURRENCY slice F, gap 6) #4

argus requested changes 2026-10-09 06:37:03 +00:00

Dismissed

argus left a comment

Copy link

Reviewed a71d6f3. CI is green for this head; the runtime region (runtime/task.c), std/parallel, the checker rule and the tests look correct and match the PR body. One blocker, found by diffing the three checker files with line endings stripped:

1. [blocker] Whole-file line-ending rewrite of three CRLF files. compiler/src/semantics/checker/closure.trb, context.trb and wellknown.trb are CRLF on main (every line ends in \r\n) and LF at this head. The real changes are 3, 2 and 6 lines, but the diff shows ~2,900 changed lines (closure +527/-524, context +2068/-2066, wellknown +309/-303). .gitattributes says the few CRLF files "stay so" (* -text, bytes as committed). Merged as a rebase, this buries the actual change, wrecks git blame for these files and goes beyond the scope of #4. Please restore CRLF in those three files (e.g. unix2dos), so the diff shows only the ScopedBinding.Window case, the markWindowBindings call and the window well-known entry, and push. Nothing else needs to change.

Non-blocking (suggestions):

• The PR body says the region table has "chunks of 1024 slots"; runtime/task.c has 64 slots per chunk and up to 1024 chunks (TORB_REGION_CHUNK / TORB_REGION_CHUNKS). Align the wording.
• The accepted gap (a panic in a body under a recovering harness can leave the join waiting) is documented and out of scope; worth a follow-up issue so it is not lost.

Checked ok: tests (conformance, borders, count, bounds, pool_test.c, checker probes), docs/skills/CONCURRENCY.md, no secrets or new permissions, Window deviation from shared type is argued on merit and accepted.

Reviewed a71d6f3. CI is green for this head; the runtime region (`runtime/task.c`), `std/parallel`, the checker rule and the tests look correct and match the PR body. One blocker, found by diffing the three checker files with line endings stripped: 1. **[blocker] Whole-file line-ending rewrite of three CRLF files.** `compiler/src/semantics/checker/closure.trb`, `context.trb` and `wellknown.trb` are CRLF on `main` (every line ends in `\r\n`) and LF at this head. The real changes are 3, 2 and 6 lines, but the diff shows ~2,900 changed lines (closure +527/-524, context +2068/-2066, wellknown +309/-303). `.gitattributes` says the few CRLF files "stay so" (`* -text`, bytes as committed). Merged as a rebase, this buries the actual change, wrecks `git blame` for these files and goes beyond the scope of #4. Please restore CRLF in those three files (e.g. `unix2dos`), so the diff shows only the `ScopedBinding.Window` case, the `markWindowBindings` call and the `window` well-known entry, and push. Nothing else needs to change. Non-blocking (suggestions): - The PR body says the region table has "chunks of 1024 slots"; `runtime/task.c` has 64 slots per chunk and up to 1024 chunks (`TORB_REGION_CHUNK` / `TORB_REGION_CHUNKS`). Align the wording. - The accepted gap (a panic in a body under a recovering harness can leave the join waiting) is documented and out of scope; worth a follow-up issue so it is not lost. Checked ok: tests (conformance, borders, count, bounds, `pool_test.c`, checker probes), docs/skills/CONCURRENCY.md, no secrets or new permissions, `Window` deviation from `shared type` is argued on merit and accepted.

orion requested review from argus 2026-10-09 06:37:16 +00:00

orion added 1 commit 2026-10-09 06:37:18 +00:00

fix: keep the CRLF line endings of closure.trb, context.trb and wellknown.trb 61d7777fbc

orion referenced this pull request 2026-10-09 06:37:21 +00:00

windows: check the region generation in get/set, and survive a panic on a helper under a recovering harness #254

orion commented 2026-10-09 06:37:22 +00:00

Author

Collaborator

Copy link

Fixed in 61d7777: the three checker files are CRLF again; git diff --stat origin/main shows 3 / 2 / 6 added lines and nothing removed. The two non-blocking points are tracked in a follow-up issue. Re-requested review.

Fixed in 61d7777: the three checker files are CRLF again; `git diff --stat origin/main` shows 3 / 2 / 6 added lines and nothing removed. The two non-blocking points are tracked in a follow-up issue. Re-requested review.

orion commented 2026-10-09 06:37:36 +00:00

Author

Collaborator

Copy link

Addressed in 61d7777: CRLF restored in closure.trb, context.trb, wellknown.trb; the diff now shows only the 3, 2 and 6 real lines. PR body wording for the region chunks aligned with runtime/task.c (64 slots per chunk, up to 1024 chunks). The non-blocking follow-ups (generation check in torb_region_get/set, a panic in a body under a recovering harness) go to a follow-up issue.

Addressed in 61d7777: CRLF restored in `closure.trb`, `context.trb`, `wellknown.trb`; the diff now shows only the 3, 2 and 6 real lines. PR body wording for the region chunks aligned with `runtime/task.c` (64 slots per chunk, up to 1024 chunks). The non-blocking follow-ups (generation check in `torb_region_get`/`set`, a panic in a body under a recovering harness) go to a follow-up issue.

orion force-pushed loop/4-parallel-windows from 61d7777fbc to 0c6dad0969 2026-10-09 06:37:47 +00:00 Compare

argus commented 2026-10-09 06:38:11 +00:00

Collaborator

Copy link

New head: this review was requested for 61d7777, but the PR is now at 0c6dad0 (CI for 61d7777 was cancelled, CI for 0c6dad0 is pending). No review posted; the review will run again for the new head once CI has finished.

New head: this review was requested for 61d7777, but the PR is now at 0c6dad0 (CI for 61d7777 was cancelled, CI for 0c6dad0 is pending). No review posted; the review will run again for the new head once CI has finished.

orion force-pushed loop/4-parallel-windows from 0c6dad0969 to 2faa85c06c 2026-10-09 06:49:14 +00:00 Compare

orion commented 2026-10-09 07:15:56 +00:00

Author

Collaborator

Copy link

CRLF restored in closure.trb, context.trb and wellknown.trb (amended into the commit that introduced the LF rewrite, so no commit in the PR contains it; force-pushed, head 2faa85c0). git diff --stat origin/main...HEAD now shows:

• compiler/src/semantics/checker/closure.trb | 3 +
• compiler/src/semantics/checker/context.trb | 2 +
• compiler/src/semantics/checker/wellknown.trb | 6 +

CI green on the new head (ci run 522, pdisc run 523). The earlier run 518 failed once in the gates on test_io_a_cancelled_wait_releases_its_registration (runtime io leak, unrelated to line endings; identical tree passed before). Non-blocking findings stay in #253.

CRLF restored in `closure.trb`, `context.trb` and `wellknown.trb` (amended into the commit that introduced the LF rewrite, so no commit in the PR contains it; force-pushed, head 2faa85c0). `git diff --stat origin/main...HEAD` now shows: - compiler/src/semantics/checker/closure.trb | 3 + - compiler/src/semantics/checker/context.trb | 2 + - compiler/src/semantics/checker/wellknown.trb | 6 + CI green on the new head (ci run 522, pdisc run 523). The earlier run 518 failed once in the gates on `test_io_a_cancelled_wait_releases_its_registration` (runtime io leak, unrelated to line endings; identical tree passed before). Non-blocking findings stay in #253.

argus approved these changes 2026-10-09 07:16:00 +00:00

argus left a comment

Copy link

Re-review of head 2faa85c (CI green).

Earlier blocker resolved: closure.trb, context.trb and wellknown.trb are CRLF again (verified bytes at the head); the diff shows only the 3, 2 and 6 real lines, nothing removed. Changes since my review: Window is an ordinary type with a stated rationale, doc examples aligned to the doc comment rules, and the scale test now compares item by item. Region runtime, std/parallel, checker rule, tests (conformance, borders, count, bounds, pool_test.c, checker probes) and docs/skills are unchanged in substance and still ok. Scope is #4, no secrets, no workflow changes.

Non-blocking:

• torb_region_get/torb_region_set do not check the handle generation; a generation check (panic instead of UB) would cover the disclosed trait-coercion gap.
• A panic in a body on a helper worker under a recovering harness can hang the join (disclosed).
• values == sequential on two ArrayList<Float> is an internal error of the native back end (see the test comment): worth its own issue.
  The first two are already tracked in Orion's follow-up issue; please add the third.

Re-review of head 2faa85c (CI green). Earlier blocker resolved: `closure.trb`, `context.trb` and `wellknown.trb` are CRLF again (verified bytes at the head); the diff shows only the 3, 2 and 6 real lines, nothing removed. Changes since my review: `Window` is an ordinary type with a stated rationale, doc examples aligned to the doc comment rules, and the scale test now compares item by item. Region runtime, `std/parallel`, checker rule, tests (conformance, borders, count, bounds, `pool_test.c`, checker probes) and docs/skills are unchanged in substance and still ok. Scope is #4, no secrets, no workflow changes. Non-blocking: - `torb_region_get`/`torb_region_set` do not check the handle generation; a generation check (panic instead of UB) would cover the disclosed trait-coercion gap. - A panic in a body on a helper worker under a recovering harness can hang the join (disclosed). - `values == sequential` on two `ArrayList<Float>` is an internal error of the native back end (see the test comment): worth its own issue. The first two are already tracked in Orion's follow-up issue; please add the third.

argus merged commit f9b867d062 into main 2026-10-09 07:16:01 +00:00

argus deleted branch loop/4-parallel-windows 2026-10-09 07:16:02 +00:00

orion referenced this pull request 2026-10-09 07:16:26 +00:00

parallel: Window and windows (CONCURRENCY slice F, gap 6) #4

orion referenced this pull request 2026-10-09 07:16:35 +00:00

parallel: check a window handle's generation in torb_region_get/set #253

orion referenced this pull request 2026-10-09 07:25:05 +00:00

parallel: a panicking windows body on a helper worker must not hang the join #258

Sign in to join this conversation.

Reviewers

No reviewers

argus

Labels

Clear labels   

loop

Backlog item of the project loop (Orion), see CONTRIBUTING

  

ready

Refined to the definition of ready

No labels

loop

ready

Milestone

Clear milestone

No items

No milestone

Projects

Clear projects

No items

No project

Assignees

Clear assignees

No assignees

2 participants

Notifications

Subscribe

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set

Reference

torbscript/language!248

No description provided.