concurrency: the skewed-cost benchmark and the measurements of section 9 #6

New issue

Closed

opened 2026-10-05 21:07:09 +00:00 by orion · 5 comments

orion commented 2026-10-05 21:07:09 +00:00

Collaborator

Copy link

Goal

Close the gate of CONCURRENCY.md slice H: a skewed-cost benchmark of the worker pool, and the three measurements of section 9, taken and written into the design record. The inbox and the stealing of unstarted tasks are built; nothing yet shows that they balance a skewed load.

Source

Pinned at a022d2a8af1d27cb5a07f2a79be68a2ee5f7d12b (main):

• CONCURRENCY.md section 9, "What to measure": queue-length histogram per worker, fraction of tasks that ran on another worker than the one that spawned them, time from spawn to first run (median and 99th percentile), and the skewed-cost gate.
• CONCURRENCY.md slice H: "the skewed-cost benchmark within its stated factor, and the fraction of stolen tasks reported"; the status note says the benchmark and the measurements are "not written yet".
• CONCURRENCY.md, "The pool, as built (7.7)": the inbox is the worker's run queue, the thief takes the oldest unstarted movable task from the victim's steal list.
• Precedent for a ratio with a wide band on one known machine, kept out of tools/gates.sh: PERFORMANCE.md section 6, "A benchmark ratio budget" and benchmarks/README.md.

No ROADMAP milestone is sliced here beyond the record's own slice H, and CONCEPT "Open Questions" has nothing on scheduling or stealing.

What exists, what does not

• torb_pool_statistics_now() (runtime/include/torb_task.h) counts resumed and stolen, summed over workers. It is C-only: no .trb program can read it, and this issue does not change that.
• runtime/tests/pool_test.c already starts N hand-written state-machine tasks of a given cost from the main thread (run_works) and asserts stolen grows. Use it as the model for the harness.
• Not present: the per-worker queue-length samples and the spawn-to-first-run timestamps. Those are the new runtime instrumentation.
• benchmarks/parallel.sh measures parallel() speed-up; it does not look at tasks of uneven cost.

Decisions made here (so the implementer does not have to ask)

1. The harness is C, against the runtime, with no public surface. The statistics are not exposed to TorbScript, and no env var, driver flag or std name is added. The benchmark is a C program built and run by a script in benchmarks/ (for example benchmarks/pool-skew.c and benchmarks/pool.sh, shaped like parallel.sh), linking the sources runtime/build.sh lists.
2. Instrumentation is compiled out by default. The queue-length samples and the timestamps live behind a compile-time macro (for example TORB_POOL_MEASURE) that only the harness sets, so the default build, the emitted programs and the seed's copy of the runtime pay nothing. The macro adds one record in task.c plus a reader function next to torb_pool_statistics_now; it is declared as test/benchmark-only like torb_pool_set_workers.
3. Cost is CPU work, not sleeping, in tasks of fixed iteration counts, so the result does not depend on the timer. Skew: N tasks (default 64) where about one in eight costs about 16 times the rest, spawned in a loop from the main thread in the worst order (the long ones clustered so that round robin alone would put them on the same worker).
4. Ideal split = max(total cost / W, cost of the longest task), with W the worker count; cost is measured by running the same tasks on one worker. Stated factor: 1.5 of the ideal split, hard bound 2.0. If the median of five runs on a machine with at least four cores is within 1.5, state 1.5 in section 9. If it lands between 1.5 and 2.0, state the measured factor rounded up and say why. Above 2.0 the implementer does not loosen the gate or change the stealing silently: the PR (or a comment on this issue) reports the numbers and the item waits for an owner decision.
5. Not a CI gate. Like run.sh it is a measurement on a machine the record names (processor, logical cores, OS), exits non-zero past the factor only when asked (for example GATE=1), is not wired into tools/gates.sh, .forgejo/workflows/ or the website's benchmark report, and a forge runner shared with other jobs is not the reference. Wiring it into a workflow is a separate, later change.
6. Fraction stolen = stolen / N; a started task never moves, so a steal before first run is exactly "ran on a worker other than the one that spawned it" for the spawn loop.

Acceptance criteria

• The harness runs N skewed-cost tasks on W workers (TORB_WORKERS / the torb_pool_set_workers path of pool_test.c) and prints: wall time, the ideal split, their ratio, and PASS/FAIL against the factor.
• The run also prints the fraction of stolen tasks, the per-worker queue-length histogram, and the median and 99th percentile of spawn-to-first-run time.
• With the instrumentation macro unset, runtime/ compiles to the same behaviour: sh runtime/build.sh is green, no new field or branch on a default hot path beyond what the macro guards, and the live-block counter is zero after every harness run.
• With one worker the harness reports ratio 1.0 and zero thefts (the pool starts no thread, pool_test.c one_worker_runs_everything_on_the_main_thread).
• A control run with stealing switched off (a switch that exists only under the instrumentation macro) shows the skew the stealing removes; its ratio is reported next to the real one. If the switch needs more than a few lines in task.c, drop the control and say so in the PR.
• Section 9 of CONCURRENCY.md states the factor and the three measurements with the machine and the date; slice H's status note drops "not written yet" and names the harness; docs/PERFORMANCE.md or benchmarks/README.md gets a row/paragraph for the new script, saying it is a measurement.
• sh tools/gates.sh ab green in the worktree (the change touches runtime/, so tier B applies), or the forge CI of the PR green and stated so.
• tools/check-commits.sh clean; docs changes regenerate skills/ as CLAUDE.md asks.

Seed

Does not touch the seed: no syntax change, no new native, no driver flag, no std name the compiler looks up by string. seed/ is not touched.

Size and commits

One PR, two Conventional Commits:

1. feat(runtime): measure the pool's queues, thefts and start latency (the macro-guarded instrumentation and its unit test in runtime/tests/pool_test.c).
2. feat(benchmarks): a skewed-cost benchmark of the worker pool (the harness, the script, the numbers in CONCURRENCY.md section 9 and slice H, the README/PERFORMANCE row, regenerated skills/).

Suggested implementer: opus/high (runtime/task.c locking order and a hot path are involved).

Dependencies and collisions

• Depends on nothing open. Slice H's inbox and stealing are on main.
• #155 / PR 160 and #156 / PR 161 (slice F) edit docs/design/CONCURRENCY.md too (slice F's status note and gaps 4/5), in other regions than section 9, slice H and "The pool, as built"; expect at most a trivial rebase in the file. They touch no runtime file.
• #4 (slice F, gap 6, Window) is checker/std work and does not touch the pool.

## Goal Close the gate of CONCURRENCY.md slice H: a skewed-cost benchmark of the worker pool, and the three measurements of section 9, taken and written into the design record. The inbox and the stealing of unstarted tasks are built; nothing yet shows that they balance a skewed load. ## Source Pinned at `a022d2a8af1d27cb5a07f2a79be68a2ee5f7d12b` (`main`): - [CONCURRENCY.md section 9, "What to measure"](https://git.torb.dev/torbscript/language/src/commit/a022d2a8af1d27cb5a07f2a79be68a2ee5f7d12b/docs/design/CONCURRENCY.md#L853): queue-length histogram per worker, fraction of tasks that ran on another worker than the one that spawned them, time from `spawn` to first run (median and 99th percentile), and the skewed-cost gate. - [CONCURRENCY.md slice H](https://git.torb.dev/torbscript/language/src/commit/a022d2a8af1d27cb5a07f2a79be68a2ee5f7d12b/docs/design/CONCURRENCY.md#L1280): "the skewed-cost benchmark within its stated factor, and the fraction of stolen tasks reported"; the status note says the benchmark and the measurements are "not written yet". - [CONCURRENCY.md, "The pool, as built (7.7)"](https://git.torb.dev/torbscript/language/src/commit/a022d2a8af1d27cb5a07f2a79be68a2ee5f7d12b/docs/design/CONCURRENCY.md#L1558): the inbox is the worker's run queue, the thief takes the oldest unstarted movable task from the victim's steal list. - Precedent for a ratio with a wide band on one known machine, kept out of `tools/gates.sh`: [PERFORMANCE.md section 6, "A benchmark ratio budget"](https://git.torb.dev/torbscript/language/src/commit/a022d2a8af1d27cb5a07f2a79be68a2ee5f7d12b/docs/PERFORMANCE.md#L1275) and [benchmarks/README.md](https://git.torb.dev/torbscript/language/src/commit/a022d2a8af1d27cb5a07f2a79be68a2ee5f7d12b/benchmarks/README.md#L7). No ROADMAP milestone is sliced here beyond the record's own slice H, and CONCEPT "Open Questions" has nothing on scheduling or stealing. ## What exists, what does not - `torb_pool_statistics_now()` (`runtime/include/torb_task.h`) counts `resumed` and `stolen`, summed over workers. It is C-only: no `.trb` program can read it, and this issue does not change that. - `runtime/tests/pool_test.c` already starts N hand-written state-machine tasks of a given cost from the main thread (`run_works`) and asserts `stolen` grows. Use it as the model for the harness. - Not present: the per-worker queue-length samples and the spawn-to-first-run timestamps. Those are the new runtime instrumentation. - `benchmarks/parallel.sh` measures `parallel()` speed-up; it does not look at tasks of uneven cost. ## Decisions made here (so the implementer does not have to ask) 1. **The harness is C, against the runtime, with no public surface.** The statistics are not exposed to TorbScript, and no env var, driver flag or std name is added. The benchmark is a C program built and run by a script in `benchmarks/` (for example `benchmarks/pool-skew.c` and `benchmarks/pool.sh`, shaped like `parallel.sh`), linking the sources `runtime/build.sh` lists. 2. **Instrumentation is compiled out by default.** The queue-length samples and the timestamps live behind a compile-time macro (for example `TORB_POOL_MEASURE`) that only the harness sets, so the default build, the emitted programs and the seed's copy of the runtime pay nothing. The macro adds one record in `task.c` plus a reader function next to `torb_pool_statistics_now`; it is declared as test/benchmark-only like `torb_pool_set_workers`. 3. **Cost is CPU work, not sleeping**, in tasks of fixed iteration counts, so the result does not depend on the timer. Skew: N tasks (default 64) where about one in eight costs about 16 times the rest, spawned in a loop from the main thread in the worst order (the long ones clustered so that round robin alone would put them on the same worker). 4. **Ideal split** = `max(total cost / W, cost of the longest task)`, with `W` the worker count; cost is measured by running the same tasks on one worker. **Stated factor: 1.5 of the ideal split, hard bound 2.0.** If the median of five runs on a machine with at least four cores is within 1.5, state 1.5 in section 9. If it lands between 1.5 and 2.0, state the measured factor rounded up and say why. Above 2.0 the implementer does not loosen the gate or change the stealing silently: the PR (or a comment on this issue) reports the numbers and the item waits for an owner decision. 5. **Not a CI gate.** Like `run.sh` it is a measurement on a machine the record names (processor, logical cores, OS), exits non-zero past the factor only when asked (for example `GATE=1`), is not wired into `tools/gates.sh`, `.forgejo/workflows/` or the website's benchmark report, and a forge runner shared with other jobs is not the reference. Wiring it into a workflow is a separate, later change. 6. **Fraction stolen** = `stolen / N`; a started task never moves, so a steal before first run is exactly "ran on a worker other than the one that spawned it" for the spawn loop. ## Acceptance criteria - [ ] The harness runs N skewed-cost tasks on W workers (`TORB_WORKERS` / the `torb_pool_set_workers` path of `pool_test.c`) and prints: wall time, the ideal split, their ratio, and PASS/FAIL against the factor. - [ ] The run also prints the fraction of stolen tasks, the per-worker queue-length histogram, and the median and 99th percentile of spawn-to-first-run time. - [ ] With the instrumentation macro unset, `runtime/` compiles to the same behaviour: `sh runtime/build.sh` is green, no new field or branch on a default hot path beyond what the macro guards, and the live-block counter is zero after every harness run. - [ ] With one worker the harness reports ratio 1.0 and zero thefts (the pool starts no thread, `pool_test.c` `one_worker_runs_everything_on_the_main_thread`). - [ ] A control run with stealing switched off (a switch that exists only under the instrumentation macro) shows the skew the stealing removes; its ratio is reported next to the real one. If the switch needs more than a few lines in `task.c`, drop the control and say so in the PR. - [ ] Section 9 of CONCURRENCY.md states the factor and the three measurements with the machine and the date; slice H's status note drops "not written yet" and names the harness; `docs/PERFORMANCE.md` or `benchmarks/README.md` gets a row/paragraph for the new script, saying it is a measurement. - [ ] `sh tools/gates.sh ab` green in the worktree (the change touches `runtime/`, so tier B applies), or the forge CI of the PR green and stated so. - [ ] `tools/check-commits.sh` clean; docs changes regenerate `skills/` as `CLAUDE.md` asks. ## Seed Does not touch the seed: no syntax change, no new native, no driver flag, no std name the compiler looks up by string. `seed/` is not touched. ## Size and commits One PR, two Conventional Commits: 1. `feat(runtime): measure the pool's queues, thefts and start latency` (the macro-guarded instrumentation and its unit test in `runtime/tests/pool_test.c`). 2. `feat(benchmarks): a skewed-cost benchmark of the worker pool` (the harness, the script, the numbers in CONCURRENCY.md section 9 and slice H, the README/PERFORMANCE row, regenerated `skills/`). Suggested implementer: opus/high (`runtime/task.c` locking order and a hot path are involved). ## Dependencies and collisions - Depends on nothing open. Slice H's inbox and stealing are on `main`. - #155 / PR 160 and #156 / PR 161 (slice F) edit `docs/design/CONCURRENCY.md` too (slice F's status note and gaps 4/5), in other regions than section 9, slice H and "The pool, as built"; expect at most a trivial rebase in the file. They touch no runtime file. - #4 (slice F, gap 6, `Window`) is checker/std work and does not touch the pool.

orion added this to the Milestone 7: the VM, tasks and the sandbox milestone 2026-10-05 21:07:09 +00:00

orion added the

loop

label 2026-10-05 21:07:09 +00:00

orion commented 2026-10-06 15:46:12 +00:00

Author

Collaborator

Copy link

[loop:torbscript] intake: in scope (author orion, label loop). Completes CONCURRENCY.md slice H (gate: skewed-cost benchmark plus the section 9 measurements); no collision with CONCEPT "Open Questions", no seed impact expected. Measurements need a stable runner, to settle in refine. Release freeze for 0.1.0 (2026-10-06) holds new PRs, next: refine (queued, buffer >= 2 ready)

[loop:torbscript] intake: in scope (author orion, label loop). Completes CONCURRENCY.md slice H (gate: skewed-cost benchmark plus the section 9 measurements); no collision with CONCEPT "Open Questions", no seed impact expected. Measurements need a stable runner, to settle in refine. Release freeze for 0.1.0 (2026-10-06) holds new PRs, next: refine (queued, buffer >= 2 ready)

orion commented 2026-10-07 22:11:50 +00:00

Author

Collaborator

Copy link

[loop:torbscript] claim refine by session:loop-torbscript-20261008 until 2026-10-08T00:11:50Z

[loop:torbscript] claim refine by session:loop-torbscript-20261008 until 2026-10-08T00:11:50Z

orion added the

ready

label 2026-10-07 22:14:47 +00:00

orion commented 2026-10-07 22:14:47 +00:00

Author

Collaborator

Copy link

[loop:torbscript] refine: body rewritten to the definition of ready (goal, pinned sources in CONCURRENCY.md section 9 / slice H, C-level harness with macro-guarded instrumentation and no public surface, stated factor 1.5 with hard bound 2.0, not a CI gate, no seed impact, one PR in two commits, implementer opus/high; no collision with #4, #155, #156), label ready set, worker usage ~75k tokens, next: implement

[loop:torbscript] refine: body rewritten to the definition of ready (goal, pinned sources in CONCURRENCY.md section 9 / slice H, C-level harness with macro-guarded instrumentation and no public surface, stated factor 1.5 with hard bound 2.0, not a CI gate, no seed impact, one PR in two commits, implementer opus/high; no collision with #4, #155, #156), label ready set, worker usage ~75k tokens, next: implement

orion referenced this issue 2026-10-07 22:18:46 +00:00

sandbox: the network grant, with the VM's tasks (NETWORK slice 10) #7

orion commented 2026-10-08 00:31:59 +00:00

Author

Collaborator

Copy link

[loop:torbscript] claim implement by session:loop-torbscript-20261008 until 2026-10-08T06:31:58Z

[loop:torbscript] claim implement by session:loop-torbscript-20261008 until 2026-10-08T06:31:58Z

orion referenced this issue 2026-10-08 00:37:27 +00:00

vm: read a call's chunk metadata from one per-chunk record (fibonacci(30)) #8

orion referenced this issue 2026-10-08 00:37:33 +00:00

vm: read a call's chunk metadata from one per-chunk record (fibonacci(30)) #8

orion referenced this issue 2026-10-08 00:58:18 +00:00

lint: redundant-closure, a closure that only passes its parameters on #9

orion referenced this issue 2026-10-08 00:58:26 +00:00

lint: redundant-closure, a closure that only passes its parameters on #9

orion referenced this issue from a pull request that will close it, 2026-10-08 00:59:47 +00:00

feat: a skewed-cost benchmark of the worker pool #169

orion referenced this issue 2026-10-08 01:22:31 +00:00

language server: reuse the declaration sites and the implementation index across keystrokes #10

orion referenced this issue 2026-10-08 01:22:31 +00:00

language server: semantic tokens without the resolver over the whole file per request #170

orion referenced this issue 2026-10-08 01:22:32 +00:00

language server: the first check of a document in slices #171

orion referenced this issue 2026-10-08 01:22:32 +00:00

language server: a rename checks the files of its name once #172

orion referenced this issue 2026-10-08 01:22:41 +00:00

language server: reuse the declaration sites and the implementation index across keystrokes #10

orion commented 2026-10-08 01:55:33 +00:00

Author

Collaborator

Copy link

[loop:torbscript] implement: resumed after the previous worker was stopped by a restart; head 6023207874 unchanged (two Conventional Commits, tools/check-commits.sh clean, mergeable without rebase), review requested from argus, PR #169, CI green (tier A, tier B, gates, bootstrap linux-x64, every host emits the same C; platform jobs skipped by path filter), worker usage ~45k tokens, next: review

[loop:torbscript] implement: resumed after the previous worker was stopped by a restart; head 6023207874 unchanged (two Conventional Commits, `tools/check-commits.sh` clean, mergeable without rebase), review requested from argus, PR #169, CI green (tier A, tier B, gates, bootstrap linux-x64, every host emits the same C; platform jobs skipped by path filter), worker usage ~45k tokens, next: review

argus closed this issue 2026-10-08 01:56:08 +00:00

Sign in to join this conversation.

No Branch/Tag specified

Branches Tags

main

loop/705-default-shadow

loop/691-tensor-core

loop/705-fix-candidate

orion/456-tierb-probe

loop/164-measure2

loop/207-measure

loop/164-prototype

probe/207-count

loop/205-measure

loop/140-hide-staged

nightly-20261103

nightly-20261031

nightly-20261029

nightly-20261027

nightly-20261026

nightly-20261025

nightly-20261024

nightly-20261023

nightly-20261021

nightly-20261020

nightly-20261015

nightly-20261014

nightly-20261013

nightly-20261011

nightly-20261010

nightly-20261009

nightly-20261008

seeds

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

Milestone 7: the VM, tasks and the sandbox

Projects

Clear projects

No items

No project

Assignees

Clear assignees

No assignees

1 participant

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#6

No description provided.