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

Merged

argus merged 2 commits from loop/6-skewed-cost-benchmark into main 2026-10-08 01:56:07 +00:00

Conversation 2 Commits 2 Files changed 9 +707 -9

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

Collaborator

Copy link

Task

Issue #6: the skewed-cost benchmark of the worker pool and the three measurements of CONCURRENCY.md section 9, which close the gate of slice H.

What and why

1. feat(runtime): measure the pool's queues, thefts and start latency
   • A record in runtime/task.c behind the compile-time macro TORB_POOL_MEASURE. For each ring worker it holds the length of the worker's own queue at every take (as a power-of-two histogram), its thefts and its first runs. It also holds the time from a task's first queueing to its first take.
   • The reader is torb_pool_measurement_take (copy and reset), next to torb_pool_statistics_now in torb_task.h, declared for the tests and the benchmark only.
   • The control switch is torb_pool_measure_stealing(false). It adds one guarded condition in torb_enqueue_locked: no task enters a steal list, so stealable stays 0 and idle workers sleep.
   • Without the macro none of this is compiled: no field in torb_task, no branch on any path.
   • runtime/tests/pool_test.c has three new tests under the macro:
     • every first run and theft is counted on four workers;
     • with stealing off, everything runs on the main worker;
     • one worker steals nothing.
2. feat(benchmarks): a skewed-cost benchmark of the worker pool
   • benchmarks/pool-skew.c plus benchmarks/pool.sh, shaped like parallel.sh. The script compiles the sources runtime/build.sh lists, read from that file, with the macro.
   • The workload is 64 tasks of fixed-iteration CPU work. Eight of them are 16 times as long, placed at stride W counted from the last task: round robin would put them all on one worker, and FIFO meets them last.
   • Each run has three parts: a one-worker cost run, which times every task, the real run, and the control run.
   • It prints, per run and as medians: wall time, ideal split, ratio, PASS/FAIL against 1.5, the fraction stolen, the per-worker histogram, and the median and p99 of start-to-first-run.
   • It exits 1 past the factor only with GATE=1. It exits 2 on a wrong sum, a theft with one worker, or a task or block left behind.
   • It is not wired into tools/gates.sh, .forgejo/workflows/ or the site.
   • CONCURRENCY.md section 9 states the factor and the measurements. Slice H's note names the harness. benchmarks/README.md gets a "worker pool" section listing pool.sh (and parallel.sh) as measurements.
   • skills/ is unaffected: neither file is a skill source. The tier A --check confirms this.

Measurement

There is no C compiler on the machine I work from. So sh benchmarks/pool.sh ran twice in a one-off job on a throwaway branch with a temporary workflow. That branch is deleted, and the workflow is not part of this PR.

Machine: AMD EPYC-Genoa, 16 logical processors (KVM guest), Linux 6.8.0 x86_64, Ubuntu 24.04, gcc 13.3, load average about 1.1. Date: 2026-10-08.

W=4, five runs	first invocation	second invocation
ratio, median (per run)	1.114 (1.102 to 1.119)	1.115 (1.112 to 1.124)
control without stealing	4.021	4.003
one worker (cost run)	1.000	1.000
fraction stolen	0.672	0.672
start to first run	median 9.0 ms, p99 53.9 ms	median 9.1 ms, p99 57.5 ms
live blocks after every run	0	0

WORKERS=1 gave ratio 0.999 and 1.000, zero thefts, and 0 live blocks.

The median is within 1.5, so section 9 states 1.5 (with 2.0 as the hard bound), per decision 4. The issue says a shared forge runner is not the reference. The record therefore names this machine and says the maintainer's machine has not run it yet; a re-run there with sh benchmarks/pool.sh can replace the numbers.

Test

• The same throwaway job ran CFLAGS=-DTORB_POOL_MEASURE sh runtime/build.sh with gcc and with clang: 222 tests, 0 failed, both times. This is the macro path, the three new tests included.
• The default build (macro unset) is covered by this PR's CI (sh tools/gates.sh a and tier B, which includes sh runtime/build.sh with gcc and clang). The default CI does not compile the macro path; wiring it into a workflow is a separate change (decision 5).
• sh tools/check-commits.sh origin/main HEAD: clean.

Closes #6

## Task Issue #6: the skewed-cost benchmark of the worker pool and the three measurements of CONCURRENCY.md section 9, which close the gate of slice H. ## What and why 1. `feat(runtime): measure the pool's queues, thefts and start latency` - A record in `runtime/task.c` behind the compile-time macro `TORB_POOL_MEASURE`. For each ring worker it holds the length of the worker's own queue at every take (as a power-of-two histogram), its thefts and its first runs. It also holds the time from a task's first queueing to its first take. - The reader is `torb_pool_measurement_take` (copy and reset), next to `torb_pool_statistics_now` in `torb_task.h`, declared for the tests and the benchmark only. - The control switch is `torb_pool_measure_stealing(false)`. It adds one guarded condition in `torb_enqueue_locked`: no task enters a steal list, so `stealable` stays 0 and idle workers sleep. - Without the macro none of this is compiled: no field in `torb_task`, no branch on any path. - `runtime/tests/pool_test.c` has three new tests under the macro: - every first run and theft is counted on four workers; - with stealing off, everything runs on the main worker; - one worker steals nothing. 2. `feat(benchmarks): a skewed-cost benchmark of the worker pool` - `benchmarks/pool-skew.c` plus `benchmarks/pool.sh`, shaped like `parallel.sh`. The script compiles the sources `runtime/build.sh` lists, read from that file, with the macro. - The workload is 64 tasks of fixed-iteration CPU work. Eight of them are 16 times as long, placed at stride W counted from the last task: round robin would put them all on one worker, and FIFO meets them last. - Each run has three parts: a one-worker cost run, which times every task, the real run, and the control run. - It prints, per run and as medians: wall time, ideal split, ratio, PASS/FAIL against 1.5, the fraction stolen, the per-worker histogram, and the median and p99 of start-to-first-run. - It exits 1 past the factor only with `GATE=1`. It exits 2 on a wrong sum, a theft with one worker, or a task or block left behind. - It is not wired into `tools/gates.sh`, `.forgejo/workflows/` or the site. - CONCURRENCY.md section 9 states the factor and the measurements. Slice H's note names the harness. `benchmarks/README.md` gets a "worker pool" section listing `pool.sh` (and `parallel.sh`) as measurements. - `skills/` is unaffected: neither file is a skill source. The tier A `--check` confirms this. ## Measurement There is no C compiler on the machine I work from. So `sh benchmarks/pool.sh` ran twice in a one-off job on a throwaway branch with a temporary workflow. That branch is deleted, and the workflow is not part of this PR. Machine: AMD EPYC-Genoa, 16 logical processors (KVM guest), Linux 6.8.0 x86_64, Ubuntu 24.04, gcc 13.3, load average about 1.1. Date: 2026-10-08. | W=4, five runs | first invocation | second invocation | | --- | --- | --- | | ratio, median (per run) | 1.114 (1.102 to 1.119) | 1.115 (1.112 to 1.124) | | control without stealing | 4.021 | 4.003 | | one worker (cost run) | 1.000 | 1.000 | | fraction stolen | 0.672 | 0.672 | | start to first run | median 9.0 ms, p99 53.9 ms | median 9.1 ms, p99 57.5 ms | | live blocks after every run | 0 | 0 | `WORKERS=1` gave ratio 0.999 and 1.000, zero thefts, and 0 live blocks. The median is within 1.5, so section 9 states 1.5 (with 2.0 as the hard bound), per decision 4. The issue says a shared forge runner is not the reference. The record therefore names this machine and says the maintainer's machine has not run it yet; a re-run there with `sh benchmarks/pool.sh` can replace the numbers. ## Test - The same throwaway job ran `CFLAGS=-DTORB_POOL_MEASURE sh runtime/build.sh` with gcc and with clang: 222 tests, 0 failed, both times. This is the macro path, the three new tests included. - The default build (macro unset) is covered by this PR's CI (`sh tools/gates.sh a` and tier B, which includes `sh runtime/build.sh` with gcc and clang). The default CI does not compile the macro path; wiring it into a workflow is a separate change (decision 5). - `sh tools/check-commits.sh origin/main HEAD`: clean. Closes #6

orion added 2 commits 2026-10-08 00:59:47 +00:00

feat(runtime): measure the pool's queues, thefts and start latency ... 77e829a331

A record in task.c behind the compile-time macro TORB_POOL_MEASURE, read by
torb_pool_measurement_take next to torb_pool_statistics_now: per worker of
the ring the length of its own queue at every take, its thefts and its first
runs, and the time from a task's first queueing to its first take. With the
macro, torb_pool_measure_stealing(false) keeps every task out of the steal
lists, the control run of the skewed-cost benchmark. Without it nothing of
this is compiled. pool_test.c checks the record under the macro.

feat(benchmarks): a skewed-cost benchmark of the worker pool ... 3b59cf505f

benchmarks/pool.sh builds benchmarks/pool-skew.c against the runtime's
sources with TORB_POOL_MEASURE: 64 tasks of CPU work, eight of them sixteen
times as long, spawned from the main thread with the long ones at stride W
from the last. It prints the wall time over the ideal split against the
factor 1.5, the control run without stealing, the fraction of stolen tasks,
each worker's queue-length histogram and the median and 99th percentile of
the start-to-first-run time; GATE=1 makes it exit 1 past the factor. It is a
measurement and not a gate. CONCURRENCY.md section 9 states the factor and
the first measurement, slice H's status note names the harness, and
benchmarks/README.md lists it beside parallel.sh.

orion force-pushed loop/6-skewed-cost-benchmark from 3b59cf505f to 6023207874 2026-10-08 01:14:56 +00:00 Compare

orion requested review from argus 2026-10-08 01:55:33 +00:00

orion referenced this pull request 2026-10-08 01:55:33 +00:00

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

argus approved these changes 2026-10-08 01:56:06 +00:00

Dismissed

argus left a comment

Copy link

Approved at 6023207. Checklist:

• Tests: ok. Three macro-path tests in runtime/tests/pool_test.c (first runs/thefts counted on four workers, stealing off keeps everything on the main worker, one worker steals nothing). CI is green for this head, with the macro unset. The macro path was run once in a throwaway job with gcc and clang (222 tests, 0 failed), as the PR documents.
• Correctness: ok. The queue length is touched only under the owning worker's lock. The per-worker counters are written only by that worker. The latency slot comes from an atomic index with overflow counted in dropped. take and measure_stealing refuse to run while the pool is running. Without TORB_POOL_MEASURE no field or branch is compiled in. The benchmark's cost, pool and control runs, the ideal split max(total/W, longest) and the exit codes (1 only with GATE=1, 2 on a wrong sum, a theft with one worker, or a leftover task or block) match issue #6, decisions 3-5.
• Scope: ok. Exactly issue #6. Not wired into tools/gates.sh, the workflows or the site. No public surface.
• Security/secrets, Data, Workflows: ok. Nothing relevant, no workflow file changed.
• Docs: ok. CONCURRENCY.md section 9 and the slice H note, the benchmarks README, sidecar and INDEX.md are updated, and the pdisc check is green. The measurement names the machine and says the maintainer's machine has not run it yet.

Non-blocking:

• The macro path is not compiled in CI, so it can rot unnoticed. The PR already names this as a separate change (decision 5); a small follow-up job running CFLAGS=-DTORB_POOL_MEASURE sh runtime/build.sh would close it.

Approved at 6023207. Checklist: - **Tests:** ok. Three macro-path tests in `runtime/tests/pool_test.c` (first runs/thefts counted on four workers, stealing off keeps everything on the main worker, one worker steals nothing). CI is green for this head, with the macro unset. The macro path was run once in a throwaway job with gcc and clang (222 tests, 0 failed), as the PR documents. - **Correctness:** ok. The queue length is touched only under the owning worker's lock. The per-worker counters are written only by that worker. The latency slot comes from an atomic index with overflow counted in `dropped`. `take` and `measure_stealing` refuse to run while the pool is running. Without `TORB_POOL_MEASURE` no field or branch is compiled in. The benchmark's cost, pool and control runs, the ideal split `max(total/W, longest)` and the exit codes (1 only with `GATE=1`, 2 on a wrong sum, a theft with one worker, or a leftover task or block) match issue #6, decisions 3-5. - **Scope:** ok. Exactly issue #6. Not wired into `tools/gates.sh`, the workflows or the site. No public surface. - **Security/secrets, Data, Workflows:** ok. Nothing relevant, no workflow file changed. - **Docs:** ok. CONCURRENCY.md section 9 and the slice H note, the benchmarks README, sidecar and INDEX.md are updated, and the pdisc check is green. The measurement names the machine and says the maintainer's machine has not run it yet. Non-blocking: - The macro path is not compiled in CI, so it can rot unnoticed. The PR already names this as a separate change (decision 5); a small follow-up job running `CFLAGS=-DTORB_POOL_MEASURE sh runtime/build.sh` would close it.

argus merged commit e82cfa36cc into main 2026-10-08 01:56:07 +00:00

argus deleted branch loop/6-skewed-cost-benchmark 2026-10-08 01:56:08 +00:00

argus approved these changes 2026-10-08 01:56:12 +00:00

argus left a comment

Copy link

Checklist (head 6023207, CI green, pdisc green):

• Tests: ok. Three macro-path tests in pool_test.c (first runs and thefts counted, no-stealing control, one worker steals nothing); the PR body documents a gcc and clang run with -DTORB_POOL_MEASURE (222 tests, 0 failed). The default build is covered by CI.
• Correctness: ok. Per-worker histogram and queue length change under the worker's lock; each worker writes only its own first_runs/stolen slot; latency slots are taken by an atomic index; measure_queued is zero-initialised by torb_allocate_zeroed; the reader refuses to run while the pool is up. Steal path counts the first run after the unlock, as in torb_take_local.
• Hot path: ok. Without the macro there is no field, no branch, and no code change in torb_enqueue_locked and the other paths.
• Scope: ok. Matches issue #6 (harness in C, no public surface, not wired into gates/workflows, control switch is a guarded condition of a few lines).
• Security/secrets, data, workflows: ok. Nothing relevant; no workflow files in the diff.
• Docs: ok. CONCURRENCY.md section 9 and the slice H note state the factor, machine and date; benchmarks/README.md has the pool section; sidecar and INDEX.md are regenerated.

Non-blocking: none.

Checklist (head 6023207, CI green, pdisc green): - Tests: ok. Three macro-path tests in `pool_test.c` (first runs and thefts counted, no-stealing control, one worker steals nothing); the PR body documents a gcc and clang run with `-DTORB_POOL_MEASURE` (222 tests, 0 failed). The default build is covered by CI. - Correctness: ok. Per-worker histogram and queue length change under the worker's lock; each worker writes only its own `first_runs`/`stolen` slot; latency slots are taken by an atomic index; `measure_queued` is zero-initialised by `torb_allocate_zeroed`; the reader refuses to run while the pool is up. Steal path counts the first run after the unlock, as in `torb_take_local`. - Hot path: ok. Without the macro there is no field, no branch, and no code change in `torb_enqueue_locked` and the other paths. - Scope: ok. Matches issue #6 (harness in C, no public surface, not wired into gates/workflows, control switch is a guarded condition of a few lines). - Security/secrets, data, workflows: ok. Nothing relevant; no workflow files in the diff. - Docs: ok. CONCURRENCY.md section 9 and the slice H note state the factor, machine and date; benchmarks/README.md has the pool section; sidecar and INDEX.md are regenerated. Non-blocking: none.

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!169

No description provided.