torbscript/language
Watch
1
0
Fork
You've already forked language
 0
Code Issues 139 Pull requests 2 Projects Releases 18 Packages 3 Wiki Activity Actions

perf: P10 - do not emit a witness member nothing calls #57

New issue
Closed
opened 2026-10-05 21:07:15 +00:00 by orion · 6 comments
orion commented 2026-10-05 21:07:15 +00:00
Collaborator
Copy link

Context

F12: a whole-program dead-member scan, a code-size fix. Waits until there are two back ends to answer to.

Source

Acceptance criteria

  • The round as PERFORMANCE.md section 5 specifies it
  • The named benchmark or snapshot recorded before and after

Dependencies

None known.

Moved from the planning lists of the docs; the design record stays the specification.

## Context F12: a whole-program dead-member scan, a code-size fix. Waits until there are two back ends to answer to. ## Source - [PERFORMANCE.md round P10](https://git.torb.dev/torbscript/language/src/commit/393ef2608e4a60b8ff76d8b6b408951b822d887d/docs/PERFORMANCE.md#L1220) ## Acceptance criteria - [ ] The round as PERFORMANCE.md section 5 specifies it - [ ] The named benchmark or snapshot recorded before and after ## Dependencies None known. _Moved from the planning lists of the docs; the design record stays the specification._
orion added this to the Kernel of natives milestone 2026-10-05 21:07:15 +00:00
orion commented 2026-10-09 05:16:18 +00:00
Author
Collaborator
Copy link

[loop:torbscript] intake: in scope (author orion, label loop), source PERFORMANCE.md round P10, not a duplicate. Same precondition as P9 (two back ends), checked in refine; code-size result measured in forge CI. next: refine, waiting (ready buffer full: #4, #163, #164, #223 are ready) until 2026-10-10T04:00:00Z

[loop:torbscript] intake: in scope (author orion, label loop), source PERFORMANCE.md round P10, not a duplicate. Same precondition as P9 (two back ends), checked in refine; code-size result measured in forge CI. next: refine, waiting (ready buffer full: #4, #163, #164, #223 are ready) until 2026-10-10T04:00:00Z
orion commented 2026-10-09 20:30:29 +00:00
Author
Collaborator
Copy link

[loop:torbscript] claim refine by session:loop-torbscript-20261009 until 2026-10-10T00:30Z

[loop:torbscript] claim refine by session:loop-torbscript-20261009 until 2026-10-10T00:30Z
orion commented 2026-10-09 20:33:16 +00:00
Author
Collaborator
Copy link

[loop:torbscript] refine: ready.

Goal. A witness table slot that no CallWitness of the whole program can reach is left empty: the C back end writes NULL and emits neither the thunk nor (unless a direct Call still names it) the member's instance, and the bytecode back end gets the same -1 it already writes for a missing chunk. Output of every program stays byte-for-byte the same at run time; only code size and build time move.

Implements. PERFORMANCE.md finding F12 and round P10 (section 5, first ledger only). The second ledger of F12 (P6 copies that gained nothing) is split off, see below.

Precondition "two back ends": met. ROADMAP milestone 7: the bytecode VM interprets the same IR as the C back end, and the conformance suite holds both to one behaviour (torb run/torb test run in the VM by default, --native and torb build in C). So the pass answers to both: the bytecode emitter (backend/bytecode/emit.trb, emitTables) already maps a member without a chunk to -1, and vm/embed.trb / vm/interpret.trb copy the member list as numbers. This also corrects the round table's "only the C back end pays": the VM is covered by the same IR convention.

Seed. Does not touch the seed: no syntax change, no new native, no new driver flag, no std name looked up by string. One PR, a plain compiler change, so the two-commit rule does not apply.

Size. One PR, two Conventional Commits:

  1. perf(ir): leave a witness member nothing calls out of its table
  2. docs(performance): record round P10 and its measurement

Design (decided by the loop, no owner question).

  • Key of a slot: (table.applied trait, member index). Tables of one trait share their slot layout, and CallWitness.member is a static index, so a scan over all CallWitness instructions of all functions, resolving each witness source to the tables it can name, is complete. Reuse reachableTables/membersAt from ir/kept.trb (move to a shared place if needed) rather than a second resolver. A source that cannot be named (reachableTables returns None) makes every slot of its trait live: sound by construction, nothing proved is nothing removed.
  • Narrowing: a supertrait is reached through nested, whose tables are tables of the supertrait with their own slots, so a CallWitness on the narrowed value marks the supertrait's slot; the scan follows nested steps the same way reachableTables does.
  • Representation: WitnessTable.members keeps its length (indices are positions); a dead slot holds FunctionId(-1). Chosen over a separate set because the three consumers that tolerate "no member" already test hasFunction/bounds (ir/kept.trb isKeptByAny/membersAt, cli/partial.trb, backend/c/body.trb keep set via keepReached), and bytecode emit already writes -1.
  • Place in the pipeline (ir/lower/lower.trb, finishLowering): after dropListBoundsChecks (the last step that can add or remove CallWitness; lowerBoxedUpdates adds some) and before trackCallerSites (which reads table members to make caller-site copies, so no copy is made for a dead slot). Runs for lowerLibrary too, since both go through finishLowering.
  • Fixpoint: the scan runs over functions that are kept, then repeats while it kills a slot whose now-unkept member held the last CallWitness of another slot (a dead member's body is not emitted, so its calls no longer count). Iterate to the fixed point over the keep set; stop when no slot changes. The result is a pure function of the program (no ordering dependence), so --emit-c twice stays byte identical.
  • Verifier (ir/verify.trb): assert that every -1 slot is unreachable, not merely unreached: no CallWitness in a function the program keeps resolves to a table whose slot at its member is -1; and printWitnessTable prints a dead slot as - instead of calling functionAt. This is the "IR verifier asserts every NULL entry is unreachable" the design record asks for.

Acceptance criteria (testable).

  1. After the pass, for the three-line list program of F2 (add, length), the C contains one thunk for each (trait, index, target) that some CallWitness can reach and no thunk for any other; the count is pinned in the test (design record: 24 thunks, 25 102 bytes before).
  2. The C of that program stays under a pinned byte budget equal to the measured size after the change plus 2%, and strictly below 25 102 bytes (recorded before/after in the PR description).
  3. compiler/tests/lower-generics.test.trb / a new compiler/tests/witness-dead.test.trb: (a) a slot called only through a supertrait-narrowed value stays live; (b) a slot reached only by a member that is itself dead dies in the same run (fixpoint); (c) a witness source that cannot be named keeps all slots of the trait; (d) a table of a trait whose value is only ever devirtualized has all slots dead and the table still emits as a valid (empty-array, NULL) table.
  4. A negative verifier test: a hand-built IR with a CallWitness onto a -1 slot is rejected by ir/verify.trb.
  5. sh tools/gates.sh ab green (tier B: the conformance suite in both back ends with the leak gate on, same output/exit codes/panics/leak counts), --emit-c twice byte identical, bootstrap fixpoint holds.
  6. The compiler's own program.c is smaller than before by a recorded number of bytes and thunks; the number goes into the PR description and into PERFORMANCE.md (round P10 row marked done, F12 "what was measured").

Exact files. compiler/src/ir/witness.trb (the scan; the round table names it) and/or compiler/src/ir/instances.trb only if the instance set needs the same notion, compiler/src/ir/kept.trb (share reachableTables/membersAt), compiler/src/ir/lower/lower.trb (one call in finishLowering), compiler/src/ir/ir.trb (doc of WitnessTable.members: -1 is a dead slot), compiler/src/ir/verify.trb, compiler/src/ir/print.trb, compiler/src/backend/c/emit.trb (emitWitnessTables, emitWitnessTable, thunkNamesOf, emitThunk loops skip -1, write NULL), compiler/src/backend/c/body.trb and compiler/src/backend/c/crossing.trb (the loops over table.members at the keep set and the split-unit crossing check), compiler/src/backend/bytecode/emit.trb (confirm -1 path), compiler/src/cli/partial.trb (confirm). Tests: new compiler/tests/witness-dead.test.trb, a pinned size in compiler/tests/emit-c.test.trb. Docs: docs/PERFORMANCE.md (P10 row, F12 measured), docs/BACKEND.md if it states the table layout. No std/, no runtime/ change (the runtime never reads a table slot by index; checked by grep).

Measurement plan (forge CI, decided here).

  • Before (main) and after (branch), in the PR's tier A/B jobs and recorded in the PR description: (i) wc -c of torb build --emit-c for the three-line list program; (ii) the count of witness thunk definitions in it; (iii) wc -c and the thunk count of the compiler's own program.c from the bootstrap; (iv) wall time of the compiler's C compile step (87 s today) and of sh tools/bootstrap.sh; (v) the VM: bytecode size of the same program (torb build --embed-vm or the disassembler) if the bytecode emitter's function set shrinks.
  • No run-time regression: the nightly benchmarks.yml table (benchmarks/*, game.sh) of the first nightly after merge is compared with the previous one; the pass changes no executed instruction, so the expected delta is noise. A slowdown over noise reopens the issue.
  • If the compiler's own program.c shrinks by less than the 13% the thunk and instance shares suggest, record the number and why in PERFORMANCE.md; that is a result, not a blocker.

Out of scope (split). F12's second ledger, dropping the P6 copies that gained nothing (334 of 1 021 in the compiler's program, 0.5 MB of C), is a different mechanism (a remap of the contiguous tail of FunctionIds in ir/devirtualize.trb) and gets its own issue (#281), so this PR stays one reviewable change.

Implementer. opus, effort high (compiler/src IR pass with a soundness argument and a verifier invariant; a wrong dead slot is a null function pointer at run time).

next: implement

[loop:torbscript] refine: ready. **Goal.** A witness table slot that no `CallWitness` of the whole program can reach is left empty: the C back end writes `NULL` and emits neither the thunk nor (unless a direct `Call` still names it) the member's instance, and the bytecode back end gets the same `-1` it already writes for a missing chunk. Output of every program stays byte-for-byte the same at run time; only code size and build time move. **Implements.** [PERFORMANCE.md](https://git.torb.dev/torbscript/language/src/branch/main/docs/PERFORMANCE.md) finding F12 and round P10 (section 5, first ledger only). The second ledger of F12 (P6 copies that gained nothing) is split off, see below. **Precondition "two back ends": met.** ROADMAP milestone 7: the bytecode VM interprets the same IR as the C back end, and the conformance suite holds both to one behaviour (`torb run`/`torb test` run in the VM by default, `--native` and `torb build` in C). So the pass answers to both: the bytecode emitter (`backend/bytecode/emit.trb`, `emitTables`) already maps a member without a chunk to `-1`, and `vm/embed.trb` / `vm/interpret.trb` copy the member list as numbers. This also corrects the round table's "only the C back end pays": the VM is covered by the same IR convention. **Seed.** Does not touch the seed: no syntax change, no new native, no new driver flag, no std name looked up by string. One PR, a plain compiler change, so the two-commit rule does not apply. **Size.** One PR, two Conventional Commits: 1. `perf(ir): leave a witness member nothing calls out of its table` 2. `docs(performance): record round P10 and its measurement` **Design (decided by the loop, no owner question).** - Key of a slot: `(table.applied trait, member index)`. Tables of one trait share their slot layout, and `CallWitness.member` is a static index, so a scan over all `CallWitness` instructions of all functions, resolving each witness source to the tables it can name, is complete. Reuse `reachableTables`/`membersAt` from `ir/kept.trb` (move to a shared place if needed) rather than a second resolver. A source that cannot be named (`reachableTables` returns `None`) makes every slot of its trait live: sound by construction, nothing proved is nothing removed. - Narrowing: a supertrait is reached through `nested`, whose tables are tables of the supertrait with their own slots, so a `CallWitness` on the narrowed value marks the supertrait's slot; the scan follows `nested` steps the same way `reachableTables` does. - Representation: `WitnessTable.members` keeps its length (indices are positions); a dead slot holds `FunctionId(-1)`. Chosen over a separate set because the three consumers that tolerate "no member" already test `hasFunction`/bounds (`ir/kept.trb` `isKeptByAny`/`membersAt`, `cli/partial.trb`, `backend/c/body.trb` keep set via `keepReached`), and bytecode emit already writes `-1`. - Place in the pipeline (`ir/lower/lower.trb`, `finishLowering`): after `dropListBoundsChecks` (the last step that can add or remove `CallWitness`; `lowerBoxedUpdates` adds some) and before `trackCallerSites` (which reads table members to make caller-site copies, so no copy is made for a dead slot). Runs for `lowerLibrary` too, since both go through `finishLowering`. - Fixpoint: the scan runs over functions that are kept, then repeats while it kills a slot whose now-unkept member held the last `CallWitness` of another slot (a dead member's body is not emitted, so its calls no longer count). Iterate to the fixed point over the keep set; stop when no slot changes. The result is a pure function of the program (no ordering dependence), so `--emit-c` twice stays byte identical. - Verifier (`ir/verify.trb`): assert that every `-1` slot is unreachable, not merely unreached: no `CallWitness` in a function the program keeps resolves to a table whose slot at its member is `-1`; and `printWitnessTable` prints a dead slot as `-` instead of calling `functionAt`. This is the "IR verifier asserts every NULL entry is unreachable" the design record asks for. **Acceptance criteria (testable).** 1. After the pass, for the three-line list program of F2 (`add`, `length`), the C contains one thunk for each `(trait, index, target)` that some `CallWitness` can reach and no thunk for any other; the count is pinned in the test (design record: 24 thunks, 25 102 bytes before). 2. The C of that program stays under a pinned byte budget equal to the measured size after the change plus 2%, and strictly below 25 102 bytes (recorded before/after in the PR description). 3. `compiler/tests/lower-generics.test.trb` / a new `compiler/tests/witness-dead.test.trb`: (a) a slot called only through a supertrait-narrowed value stays live; (b) a slot reached only by a member that is itself dead dies in the same run (fixpoint); (c) a witness source that cannot be named keeps all slots of the trait; (d) a table of a trait whose value is only ever devirtualized has all slots dead and the table still emits as a valid (empty-array, `NULL`) table. 4. A negative verifier test: a hand-built IR with a `CallWitness` onto a `-1` slot is rejected by `ir/verify.trb`. 5. `sh tools/gates.sh ab` green (tier B: the conformance suite in both back ends with the leak gate on, same output/exit codes/panics/leak counts), `--emit-c` twice byte identical, bootstrap fixpoint holds. 6. The compiler's own `program.c` is smaller than before by a recorded number of bytes and thunks; the number goes into the PR description and into PERFORMANCE.md (round P10 row marked done, F12 "what was measured"). **Exact files.** `compiler/src/ir/witness.trb` (the scan; the round table names it) and/or `compiler/src/ir/instances.trb` only if the instance set needs the same notion, `compiler/src/ir/kept.trb` (share `reachableTables`/`membersAt`), `compiler/src/ir/lower/lower.trb` (one call in `finishLowering`), `compiler/src/ir/ir.trb` (doc of `WitnessTable.members`: `-1` is a dead slot), `compiler/src/ir/verify.trb`, `compiler/src/ir/print.trb`, `compiler/src/backend/c/emit.trb` (`emitWitnessTables`, `emitWitnessTable`, `thunkNamesOf`, `emitThunk` loops skip `-1`, write `NULL`), `compiler/src/backend/c/body.trb` and `compiler/src/backend/c/crossing.trb` (the loops over `table.members` at the keep set and the split-unit crossing check), `compiler/src/backend/bytecode/emit.trb` (confirm `-1` path), `compiler/src/cli/partial.trb` (confirm). Tests: new `compiler/tests/witness-dead.test.trb`, a pinned size in `compiler/tests/emit-c.test.trb`. Docs: `docs/PERFORMANCE.md` (P10 row, F12 measured), `docs/BACKEND.md` if it states the table layout. No `std/`, no `runtime/` change (the runtime never reads a table slot by index; checked by grep). **Measurement plan (forge CI, decided here).** - Before (main) and after (branch), in the PR's tier A/B jobs and recorded in the PR description: (i) `wc -c` of `torb build --emit-c` for the three-line list program; (ii) the count of witness thunk definitions in it; (iii) `wc -c` and the thunk count of the compiler's own `program.c` from the bootstrap; (iv) wall time of the compiler's C compile step (87 s today) and of `sh tools/bootstrap.sh`; (v) the VM: bytecode size of the same program (`torb build --embed-vm` or the disassembler) if the bytecode emitter's function set shrinks. - No run-time regression: the nightly `benchmarks.yml` table (`benchmarks/*`, `game.sh`) of the first nightly after merge is compared with the previous one; the pass changes no executed instruction, so the expected delta is noise. A slowdown over noise reopens the issue. - If the compiler's own `program.c` shrinks by less than the 13% the thunk and instance shares suggest, record the number and why in PERFORMANCE.md; that is a result, not a blocker. **Out of scope (split).** F12's second ledger, dropping the P6 copies that gained nothing (334 of 1 021 in the compiler's program, 0.5 MB of C), is a different mechanism (a remap of the contiguous tail of `FunctionId`s in `ir/devirtualize.trb`) and gets its own issue (#281), so this PR stays one reviewable change. **Implementer.** opus, effort high (compiler/src IR pass with a soundness argument and a verifier invariant; a wrong dead slot is a null function pointer at run time). next: implement
orion commented 2026-10-09 20:34:12 +00:00
Author
Collaborator
Copy link

[loop:torbscript] claim implement by session:loop-torbscript-20261009 until 2026-10-10T04:40Z

[loop:torbscript] claim implement by session:loop-torbscript-20261009 until 2026-10-10T04:40Z
orion commented 2026-10-10 00:07:00 +00:00
Author
Collaborator
Copy link

[loop:torbscript] implement: PR #284 open, CI green (617f8b16).
Token usage: roughly 1.5M tokens over two contexts; the CI measurement waits took most of it.
next: waiting (merge gate review of PR #284)

[loop:torbscript] implement: PR #284 open, CI green (617f8b16). Token usage: roughly 1.5M tokens over two contexts; the CI measurement waits took most of it. next: waiting (merge gate review of PR #284)
argus closed this issue 2026-10-10 00:49:38 +00:00
orion commented 2026-10-10 00:49:56 +00:00
Author
Collaborator
Copy link

[loop:torbscript] PR #284 merged by argus (fced7f58). Issue closed by the merge; no release or deploy step in the PR. Open: the compiler-size rows of the PR table were measured on the pre-rebase base; main CI for fced7f58 is still running. If its artifacts differ, correct the table in docs/PERFORMANCE.md via a follow-up PR.
next: none (done)

[loop:torbscript] PR #284 merged by argus (fced7f58). Issue closed by the merge; no release or deploy step in the PR. Open: the compiler-size rows of the PR table were measured on the pre-rebase base; main CI for fced7f58 is still running. If its artifacts differ, correct the table in docs/PERFORMANCE.md via a follow-up PR. next: none (done)
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
Kernel of natives
Projects
Clear projects
No items
No project
Assignees
Clear assignees
No assignees
1 participant
Notifications
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#57
No description provided.