Repository navigation
Speculative Bounded Tests
Speculative. A proposal, not adopted.
The test suites evaluate mathematical expressions through compute-engine, and one bad evaluation can run for minutes or take gigabytes: a reference example once exhausted a build box's memory, and oracle scans once ran out of it. The oracle scans and the reference examples test are capped; the other suites have only vitest's per-test timeout, which cannot interrupt a synchronous evaluation and says nothing about memory. This page proposes that every evaluation a test makes runs under a stated time and memory budget, and that a breach is a failure that names the test (and where it can, the expression) instead of a hung runner or an out-of-memory kill.
"Measured" below means read or counted from the tree at origin/main (bfa63e225), with path:line; counts name the pattern grepped, and a pattern count is an upper or lower bound, not a census. "Measured (draft)" means taken from a lane's startup measurement, lane gxstartup, not in the tree, one session's timings on a build box, not in the tree. "Assumed" means reasoned from how Node, vitest or compute-engine behave and not run here: there is no node_modules, so no behaviour was run.
Bound the test run in three layers, smallest first, and do not build a new evaluator.
-
A heap cap and a watchdog thread on every test fork (option C, with a thread inside the fork). A shared setup file starts a
worker_threadswatchdog that is not blocked by the test's synchronous loop. It watches a heartbeat the test runner updates at each test boundary and the process's memory. Past the per-test budget or the heap ceiling it prints the current test name and file, then kills the process. Time and memory are both bounded for all ~780 test files at one wiring point, with no change to how tests are written. It names the test, not the expression. -
Keep option B where it already runs (
runCases, reference's entries, backlog and resolver tests), and make its failure say time or memory, which today it cannot: both come backAborted(node.ts:223-227). -
Optionally add option A for expression attribution: wrap
evaluateince.withTimeLimit({ ms, label })so a cooperative breach names the expression. Pilot it; it catches only where the engine checks and bounds no memory.
Pilot on @notatio/analytic (94 test files, bignum and series numerics, a DEEP_TESTS user, its own nightly step). Measure first on a build box: whether a fork killed by the watchdog is reported by vitest with its file, whether the watchdog thread runs while the main thread is in a tight loop, and the suite's wall time before and after.
What would change this: if vitest cannot be made to report a killed fork usefully, run each file through runBounded (packages/utils/src/bounded.ts:54) instead (variant C-outer). If most real breaches turn out to be single expressions in otherwise fast files, B and A matter more than C.
| Mechanism | What it stops | Cost | Where used |
|---|---|---|---|
vitest testTimeout
|
An async test that outlives the limit. By JS semantics it cannot fire during a synchronous loop (assumed). No memory bound. | none | Per package: 60 s in ten packages, 300 s in combinatorics and statistics, 20 s in evaluation (packages/reference/vite.config.ts:14, packages/symbols/combinatorics/combinatorics/vite.config.ts:25, packages/symbols/combinatorics/statistics/vite.config.ts:15, packages/symbols/evaluation/evaluation/vite.config.ts:12). A third argument or timeout: in 32 test files (pattern timeout: [0-9_]+ or }, NN_NNN)). |
CI job timeout-minutes
|
The whole job, with no name for the test. | none |
ci.yml:211 (30 min per shard), nightly.yml:104 (60) and the 120-minute deep jobs, perf.yml:30 (45). |
ce.withTimeLimit({ ms, label }) |
A cooperative deadline: the engine polls it between steps and throws CancellationError with cause: 'timeout' and the label as attribution. A synchronous evaluate() honours it where the engine checks. It cannot stop one blocking host call such as a single RegExp.exec(), and fn must be synchronous. There is no ambient default; it is armed per span. |
A clock read per check; none at rest. | compute-engine clone docs/TIMEOUT-MODEL.md:9-10, src/compute-engine/index.ts:1802-1810, src/compute-engine/library/regexp.ts:20-27. Ours: cooperative-evaluate.ts:60; one test (packages/ce-patches/tests/algebraic-numbers.test.ts:173). |
ce.iterationLimit (default 1024 per collection walk), ce.recursionLimit (256) |
A count-based cap, deterministic; throws CancellationError. Not a time bound. |
none | Clone engine-runtime-state.ts:10-31; our collection reader declines past it (packages/engine/src/index.ts:35). |
ce.withStepBudget({ steps }) |
A deterministic work budget: the same on every machine, an opaque unit not comparable across engine versions. | none | Clone src/compute-engine/index.ts:1825-1860. Not used in this repo (grep). Whether 0.187.1 ships it is not checked. |
withDeadline / checkpoint()
|
Our own cooperative deadline for bigint kernels that never reach the engine's checks. Sync only. | none |
packages/engine/src/deadline.ts; deadlineTick in packages/ce-patches/src/compute-engine/library/algebraic-numbers.ts:99; evaluateCooperatively arms both (cooperative-evaluate.ts:60). |
evaluateIsolated / createEvaluatorPool / runCases
|
One evaluation in a pooled worker_threads worker: resourceLimits.maxOldGenerationSizeMb caps its heap (node.ts:150), terminate() is the hard time kill 200 ms after the cooperative deadline (node.ts:26, :207-210), a 10 s guard covers a worker that never starts (node.ts:37). A worker killed or crashed is replaced (node.ts:223-227). Results come back in order and one case cannot hurt another (run-cases.ts:55-58). |
A worker start plus a declared engine per worker (see below); workers are keyed by heap limit (node.ts:123-126). |
Three test files: packages/reference/tests/entries.test.ts:156,170, backlog.test.ts:40, resolver.test.ts:96-118; scripts adopt-wolfram-examples.ts:97, oracle-plausible.ts:329. |
worker_threads + resourceLimits, hand-rolled |
Same, per script, reporting ERR_WORKER_OUT_OF_MEMORY by name. |
as above |
packages/symbols/combinatorics/combinatorics/collections/scripts/plausible.ts:44-63 (768 MB, 60 s per family, :24-25); packages/reference/scripts/oracle-verdict-capped.ts:10,29-33 (20 s, terminate on overrun). |
Child process with --max-old-space-size and a silence watchdog |
One process per sweep leg; SIGKILL after 20 s with no output; the sweep restarts after the rule that died. | A process start per restart. |
packages/reference/scripts/verify-fungrim.ts:4-6,14-24. |
runBounded |
A process group under a time limit and a resident-memory ceiling (polled every 500 ms with ps, default 4096 MB, ORACLE_MEMORY_MB); killed on breach, on exit and on SIGINT; returns killed: "memory" | "timeout" and peak MB. |
One ps per poll. |
packages/utils/src/bounded.ts:34-112; every oracle kernel (packages/oracle/src/run.ts:15,139). |
| Oracle batching | 40 items a batch (run.ts:20), a 1 GiB per-item cap (:27), a stall limit of twice the item time (:25); a lost batch is bisected until the poison item is found (:1888-1916); a lane's deadline declines batches not yet started (:1937). |
Re-runs on a loss. |
packages/oracle/src/run.ts. |
| Container and job caps |
docker --memory at ORACLE_MEMORY_MB (12000 in the nightly). |
none |
nightly.yml:526,604,659. |
Two things this table shows. The mechanisms for time and memory exist and are good; they are applied per script, not to the test run. And nightly.yml carries no heap flags of its own: the caps live in the scripts and ORACLE_MEMORY_MB (grep of .github/workflows for heap, max-old, NODE_OPTIONS).
The engine itself: the pin is 0.187.0 || 0.187.1 (pnpm-workspace.yaml:41). The source clone at ~/Playground/@enumeratio/compute-engine says 0.148.0 in package.json, heads its changelog Unreleased, and holds newer code than that number (it has withStepBudget), so it is a development tree and not the pinned version; what it shows about limits may not match 0.187.1. In it the engine enforces nothing by itself: no ambient deadline, deadlines are cooperative, and about 160 checkDeadline( call sites poll them, concentrated in special functions, number theory, limits, integration and series (grep count by file). A synchronous evaluate() inside a withTimeLimit span does stop at the next check; code that does not reach a check (one large bigint operation, one regexp) is not stopped.
- 782 test files (
.testor.specwith.ts,.tsxor.js; 748 are.test.tsunder atests/folder). Counted by grep overgit ls-files. - About 408 files build an engine and evaluate on it in the test process: they match one of
new ComputeEngine((203),declaredEngine,bareEngine,createEngine,createLatexEngineordeclare…(ce. About 314 files call.evaluate(or.N((1478 call sites). There is no shared evaluate helper: no test file defines a top-levelvalue,evorevaluate, and the engine factories are the shared part.@notatio/engine/testing(packages/engine/src/testing.ts:10-34:createEngine,bareEngine,createLatexEngine) is imported by 191 files;declaredEngine(packages/reference/scripts/engines.ts:107) by 9. - 9 files go through an isolated worker (pattern
evaluateIsolated|runCases|createEvaluatorPool|openSession): six are the evaluation package's own tests, three are reference's (entries,backlog,resolver). The reference examples test is the only broad suite under a cap: 10 s, 512 MiB, three at once (packages/reference/tests/entries.test.ts:103-107), its comment saying a runaway example "fails fast instead of hanging the suite or eating the machine's memory (this box OOM'd once already)" (:100-102), and a starved case is retried alone before it counts as a breach (:159-170). - 14 test files import
worker_threadsorchild_process. - Evidence for the slow or risky suites:
- Combinatorics:
testTimeout300 s; 23 files cost 25 s or more and are left out of PR and main runs (smoke-skip.json,vite.config.ts:26-29); the suite alone takes about 90 minutes (ce-main.yml:111) and is split across two runners on the nightly (tools/ci/affected.ts:28). 55 of the 73DEEP_TESTSfiles are in it (patternDEEP_TESTSin test files, counted by package folder). - Statistics:
testTimeout300 s; its deep sweep is one of the longest nightly jobs (nightly.yml:93-99, "none past about 85 minutes"). - Analytic (4 deep files), reference (3), ce-patches (3), residues (2), census (2), and one each in number-theory, frontend, cli: the other
DEEP_TESTSusers. - Frontend
forms.test.tscarries a 20 s per-head budget because one head's printing takes seconds on a runner (packages/frontend/tests/forms.test.ts:16-18). - Reference: 60 s timeout "several seconds cold on a CI runner" for loading every record (
packages/reference/vite.config.ts:11-14).
- Combinatorics:
- What
tools/perfrecords: per test and per file duration and a package wall time, from vitest's JSON reporter, one package at a time, appended nightly tohistory.jsonon theperf-databranch, last 60 runs, with a machine fingerprint (tools/perf/README.md:8-34,src/history.ts:4-25). It flags a test at 1.5 times its trailing median and at least 200 ms over, with five prior runs (README.md:38-52); the run is advisory and never a gate (:67).perf.ymlsets noSMOKE_TESTSorDEEP_TESTS(perf.yml:28-52), so it times the standard run in full. What it cannot see: memory at all; a test that never finishes (no row is written, and the job's 45-minute limit ends it); which expression inside a test was slow; and anything before the nightly. - No test or config sets a vitest pool,
execArgvor a heap flag (grep ofvite.config.tsfiles forpool,poolOptions,execArgv,maxWorkers,isolate,fileParallelism: none). The only mention of the pool is a comment that a profiling run uses--pool=forks --maxWorkers=1 --no-isolateunder "vitest 4" (tools/perf/src/cpu-prof.ts:6-7). The installed vitest version and its option names are therefore assumed (the Vite+ docs are atnode_modules/vite-plus/docs, not present here).
| Names the expression | Bounds memory | Wall-time effect | Deterministic | |
|---|---|---|---|---|
| A. Engine time limit on every test engine | Yes, via the span label | No | Almost none | Time-based: a loaded runner trips it; withStepBudget is the deterministic alternative |
B. evaluateWithin in a worker with resourceLimits
|
Yes | Yes, heap of the worker | A worker and engine start per worker; a full reference engine is seconds (measured, draft) | Time breach is wall-clock; a heap breach is |
| C. Fork per file with a heap cap and a watchdog | Test and file, not expression | Yes, the whole process heap | Config only; a watchdog thread per fork | Heap breach: yes. Time breach: wall-clock |
| D. Budget from the nightly perf history | No | No | None in the run | No: ratios against a history from other machines |
| E. Nothing in the standard run; bound only deep and nightly sweeps | n/a | n/a | None | n/a |
A. The engine's own time limit on every test engine. A vitest setup file (or createEngine, testing.ts:10) wraps evaluate, N and simplify in ce.withTimeLimit({ ms, label }), with the label the current test name plus the expression's text, so a CancellationError carries attribution naming both. There is a precedent for wrapping evaluate once on the function-node prototype (packages/engine/src/modular.ts:157-176), which reaches an engine however the test built it. It is cheap and it names the expression. It catches only where the engine checks: our bigint kernels need checkpoint() and deadlineTick (the patches that have them do), a single large operation or regexp is not stopped (clone regexp.ts:20-27), and it bounds no memory, which is the failure that hurt. A timeout is a clock read, so a loaded runner can breach a limit a quiet one does not; reference's entries test already retries a starved case alone (entries.test.ts:159-170). Nesting only shortens a deadline, so a test limit never extends a handler's own and a handler may fall back only from its own span's expiry (clone TIMEOUT-MODEL.md:20-30); a breach of the outer limit propagates as a failure. withStepBudget is deterministic but an opaque unit that moves between engine versions (clone index.ts:1825-1860), so it would need retuning at each bump.
B. A shared evaluateWithin(expr, { ms, mb }). This largely exists: createEvaluatorPool().evaluateDetailed(json, { timeMs, memoryBytes, setup, materialize }) returns Evaluated, Aborted or Error with a reason and the elapsed time (node.ts:96-121), and runCases batches it. The new part would be a thin test-facing wrapper and a decision about what a test's own engine is. That is the limit: a worker cannot be handed an engine or a boxed expression, only MathJSON and a setup module URL whose configure(ce) rebuilds the declarations (worker.ts:53-65). The worker keeps one declared engine per setup URL for its life and each call runs in its own scope with free-symbol types reset (worker.ts:9-14,67-79, isolate.ts:53), so the declaration cost is paid once per worker, not per call. A test that declares a library with closures, registers a custom head, or reads the result as a boxed expression cannot move over without being rewritten around a setup module; most of the roughly 400 engine-building files are of that kind (assumed from the patterns above, not sampled file by file). Cost, measured (draft): a cold worker with the full reference engine takes about 4.2 s (import of every library about 0.7 s, declareEvaluation about 1.6 s, library declarations about 0.8 s), three at once about 8 s; the pool caps live workers at availableParallelism() - 1 (node.ts:139). Under a 10 s guard that is thin on a runner several times slower (the draft's estimate, a straight multiply). Worker heap caps also do not count memory outside the V8 heap (assumed from Node's resourceLimits, which caps heap and stack sizes), and the OOM case is indistinguishable from a time kill at the call site (node.ts:223-227; plausible.ts:59 shows the code to read, ERR_WORKER_OUT_OF_MEMORY).
C. A forked process per file with a heap cap and a watchdog. Two variants.
-
C-inner (preferred). Vitest forks one process per test file by default (assumed for vitest 4; cpu-prof comment
cpu-prof.ts:6-7). Pass--max-old-space-sizeto the forks (test.execArgv, assumed name) so a runaway allocation aborts that fork with V8's heap-limit error instead of growing until the machine swaps. A setup file starts a watchdogworker_threadsthread: its event loop is separate, so it runs while the main thread is stuck in a synchronous loop (assumed). The test runner writes the current test name and a timestamp into aSharedArrayBufferat each test start and end (viabeforeEach/afterEachin the setup file); the watchdog reads it, and past the budget it printstest "<name>" in <file> exceeded <ms> msand ends the process. It also samplesprocess.memoryUsage().rssand does the same past a ceiling. It bounds all engine-building files at once, with no rewrites. It names the test and file but not the expression, and the kill reaches vitest as a crashed fork (how vitest reports that, and whether the file is named, is the first thing to measure). -
C-outer. Run
vp test run <file>per file underrunBounded(bounded.ts:54-112), which already kills a process group on a time or resident-memory breach and reports it. It needs no assumption about vitest's crash reporting, but it starts vitest per file (the full suite is 780 files) and forfeits vitest's own scheduling; it would be the fallback for the files that need it, such as the smoke-skipped combinatorics files.
D. A budget from the nightly perf history. A test fails when it exceeds k times its own median from perf-data. It adds no wall time to a run but it is time only, it needs history.json fetched into every run (a network dependency on a branch), the median comes from other machines (the history already divides out a slow runner's median slowdown, README.md:47-49), and a hang produces no row. It tells you a test got slower, not that one expression ran away. It stays what it is, an advisory drift report; it is not a limit.
E. Do nothing in the standard run; bound the deep and nightly sweeps. The deep sweeps are where the long, memory-hungry work already lives (nightly.yml:93-99) and a job limit already ends them. It leaves a runaway in a standard run to the 30-minute shard limit (ci.yml:211) and a local vp test to the developer's patience and swap. It is the baseline the other options are measured against.
-
One default for the repo, in
@notatio/config(packages/config/index.js, which the package configs already import forfmtandlint): a time per test and a memory ceiling per fork, applied by each package'svite.config.tsthrough one exportedtestfragment. The per-packagetestTimeoutlines (reference/vite.config.ts:14,combinatorics/vite.config.ts:25, …) already show that a package overrides by writing its own value; the fragment keeps that. -
An override per package in that package's config, as now. A package that raises it says why in a comment, as
referencedoes (vite.config.ts:11-13). -
An override per test through vitest's own third argument, which the watchdog reads from the test's own timeout so there is one number to set per test and not two. A deliberate long test says so by its timeout and by
DEEP_TESTS, the convention that exists: a sweep takes a small budget by default and its full one underDEEP_TESTS=1(AGENTS.md, Testing; wiki Contributing). A breach in the standard run is never answered by raising the number; the rule "Don't just raise a timeout" stays. -
For a worker call (B), the budget is the call's
timeMsandmemoryBytes;runCasesalready lets a case override the call's default (run-cases.ts:12-17). -
The failure message names the file, the test, the limit that fired and its value, and the peak seen:
packages/analytic/tests/x.test.ts › "name": exceeded 60 s (limit from packages/config); for memoryexceeded 1024 MB heap; for option A add the expression text. Reference's message today names the example and both caps (entries.test.ts:187-189, "exceeded the 10000ms/536870912-byte cap — tighten the example or raise the cap"); the new ones separate time from memory, and say "tighten the test", with no suggestion to raise the cap.
Smallest first step: @notatio/analytic, one package, no source changes outside its config and a shared setup file. It has 94 test files, numeric kernels with bignum loops and series that are the likeliest to run away, a 60 s testTimeout that a synchronous loop would not respect, four DEEP_TESTS files, and its own first step in the nightly deep job (nightly.yml:114). Reference is already capped by B; combinatorics is too large and slow for a first pass.
On a build box, before any change, measure and record:
- The suite's wall time and peak resident memory,
vp testinpackages/symbols/analysis/analytic, three runs (/usr/bin/time -v, orrunBounded'speakMb,bounded.ts:30). Usetools/perf's per-file durations for the slowest files. - Worker start cost and engine declaration cost per worker: re-run the draft's probe (
engine-startup-measurement.md: node boot, import,new ComputeEngine(),declareEvaluation, declarations) for analytic's setup, andrunCaseswall time for one trivial case at concurrency 1 and 3. - Whether a watchdog
worker_threadsthread fires while the main thread is inwhile(true), from inside a vitest fork; whetherprocess.kill(process.pid, "SIGKILL")from it (orprocess.abort()) is reported by vitest as a failure with the file named; and the exacttest.execArgvoption name and pool default for the installed vitest. - What a
--max-old-space-sizebreach prints in a fork: confirm it is a failure with a name, not a hang.
Then:
- Add
testBoundsto@notatio/config(time, heap MB, watchdog on/off) and awatchdog-setup.tsunder it; wire analytic'svite.config.tsonly. Seed the limits from measurement 1 (twice the slowest test's duration, rounded) and leave memory at a ceiling a quarter of the box's RAM. - Add one test that is meant to fail (a
while(true)and an allocation loop) behindPROBE_BOUNDS=1, run by hand, to prove the message and the kill, and keep it out of the standard run. - Run analytic's suite on a CI runner via the existing shard; read the wall time against measurement 1. Accept if the overhead is within noise and the probe fails as stated.
- Only then widen: ce-patches, then the evaluation package, then residues and number-theory, then the large suites. Combinatorics last, and with its smoke-skip list considered.
- Fix B's reporting in the same pass or a second one: surface
ERR_WORKER_OUT_OF_MEMORYas a distinct outcome from a time kill inevaluateDetailed(node.ts:223-227) soentries.test.ts:187-189can say which. - Option A is a separate, optional change after 1 to 4: prototype wrap in the setup file (the
modular.ts:157pattern), measured on analytic for false breaches on a loaded runner.
Do not add tests beyond the one probe without asking.
-
Limit by time or by steps? Recommend wall time, at a generous multiple (a runaway is minutes, a slow test seconds), with
withStepBudgetexamined only if false breaches appear. A step budget's unit changes between engine versions (cloneindex.ts:1825-1860), and thece-bumpflow would then have to retune it. - What default? Recommend a time per test of twice the slowest test in the package after measurement 1, floor 20 s; a memory ceiling of 2 GiB per fork on a CI runner and a quarter of RAM locally. The numbers come from the box, not from this page.
- Hard-kill or soft-fail on a time breach? Recommend kill: a soft failure from a thread that cannot interrupt the main thread does not stop the hang. The kill ends the file, so later tests in it do not run; the message must say that.
-
Does a breach fail the standard run or only report? Recommend fail, after one clean nightly of measurement mode (log only), since the perf history shows runners vary about 2x (
tools/perf/README.md:50-51) and the first limits will be guesses. - Do the 9 worker-based test files keep their own caps? Recommend yes: they declare 10 s and 512 MiB for a reason of their own and are bounded already; the new watchdog's budget for such a file should be larger than the sum its cases can take, or those files get the watchdog switched off.
-
Is the Mac a target? Recommend yes: the incident was the developer's machine.
ps-based RSS polling (bounded.ts:36-52) works on macOS and Linux; a heap cap throughexecArgvis the same on both. Memory outside the V8 heap (large typed arrays) needs the RSS watchdog, which is the case for a--max-old-space-sizecap not seeing. - Per-expression naming for the 400 engine-building files? Recommend not now: the test name is enough to find the expression in nearly every test, and option A can follow on one package if a breach in practice does not say which expression.
- Does the nightly keep its own job limits? Recommend yes, unchanged, as the outer guard; the new bounds are inside them.
Measured (read or counted in the tree): the mechanisms in the table and their line references; no vitest pool, execArgv or heap setting in any vite.config.ts; per-package testTimeout values; 782 test files, 9 using the isolated evaluator, 14 importing worker_threads or child_process, 73 reading DEEP_TESTS (55 in combinatorics), 23 smoke-skipped; the pattern counts for engine-building files (408), new ComputeEngine( (203) and @notatio/engine/testing (191); what tools/perf records and its drift rule; the oracle's caps and runBounded's behaviour; the engine pin and the clone's limit machinery (withTimeLimit, withStepBudget, iterationLimit, recursionLimit, and "no ambient deadline").
Measured (draft): cold worker and engine start times, and the three-at-once penalty (a lane's startup measurement, lane gxstartup, not in the tree, one build box, compute-engine 0.187.1, median of five).
Assumed, not run: that vitest 4's default pool is forks and what test.execArgv is called; that a watchdog thread runs while the main thread loops and can kill the process; that vitest reports a killed fork with its file; that a V8 heap-limit abort in a fork surfaces as a named failure; what resourceLimits does and does not cap; that a vitest timeout cannot fire during a synchronous loop; that most of the roughly 400 engine-building files hold engines or boxed values a worker cannot take; that withStepBudget ships in 0.187.1; the 4x-slower-runner scaling of the worker start time; how often a standard run today hits a limit (no data: the perf history does not record failures or memory).