perf(ir): lower nested writes through a boxed list as one call of List.update #238

Merged

argus merged 3 commits from loop/207-update-lowering into main 2026-10-09 01:48:44 +00:00

Conversation 1 Commits 3 Files changed 15 +1116 -11

orion commented 2026-10-08 23:33:52 +00:00

Collaborator

Copy link

Closes #207

Task

#207: a nested write through a list that stayed boxed (trait-typed) after the devirtualization still went through the round trip of Index.at and MutableIndex.set on the witness table, so the element was owned twice while it changed and the change copied it. #215 gave ArrayList and TrieList an update of their own; this is the other half, the lowering.

What and why

• compiler/src/ir/updates.trb (new): an IR pass after the element steps (rewriteElementPlaces, dropProvableChecks) and before ownership. It finds the round trip in one block - read C, callWitness at(key) into the element, the rest of the path on the element, makeUnique C, callWitness set(key, element) - and writes it as callWitness update(key, closure) on C, whose closure takes the element by reference and runs the rest of the path on it.
  • Order (BACKEND 2.3): only the instructions after the access move into the closure; the key and everything evaluated before it stay outside and are captured as values. update checks the key before it calls the closure, so an index out of range panics with the message of at before the rest of the path runs - the same output as before (tests/conformance/list-update-bounds.trb).
  • No copy: the element is the closure's var parameter, the list's own slot; no removeAt/insert, nothing taken out and put back.
  • Refusals: only the standard library's List.update (found by symbol in the witness table, one per table) is trusted; only plain functions; a window that branches, holds a debug statement, reads a var parameter, dispatches on a generic parameter's witness, or whose values are used after the put-back is left as it was.
• compiler/src/ir/lower/lower.trb: wires the pass in and finds at, set and update of every List witness table.
• compiler/src/ir/elements.trb: makes the helpers the pass shares public.
• Docs: BACKEND (the element-step notes), PERFORMANCE 9.6 points to 9.11, compiler/README.md.

No new native, no change to std/, so no seed step.

Test

• tests/conformance/list-update-nested.trb: the evaluation order of keys and value through two boxed lists on one path (a list in a list field, a list of lists), a captured local, a write that reads the element (types[1] = types[1] * 10), an interpolated write, and that a copy taken before the write keeps its value. Expected output generated with main's binary.
• tests/conformance/list-update-bounds.trb: out of range panics at the site with the message of at, and nothing after the access is evaluated (.stderr, exit 101). Expected output generated with main's binary.
• compiler/tests/boxed-updates.test.trb: snapshots the lowered write (one callWitness of member update, no at, no set of the element) and its closure, and that the nested program verifies before and after ownership with five closures. Passes locally in the VM.

Measurement

Forge CI, job measure-207 on the throwaway branch loop/207-measure: main (91c009ff) and this change bootstrapped on the same runner, run alternately, 3 runs each, processor time, mean (PERFORMANCE 9.11):

What	main	update	ratio
torb check tests/conformance/adts.trb	0.64 s	0.67 s	0.96x
torb build --emit-c tests/conformance/adts.trb	0.70 s	0.72 s	0.96x
torb build --emit-c ./compiler	28.6 s	28.7 s	1.0x

Neutral within the noise (runs of one case differ by up to 9%): the write that cost the front end was already an ArrayList field after round one. The gain is the element copy avoided in programs that write through a List that stays boxed. The same job ran both new conformance programs on the new binary: same stdout and exit code as main.

Closes #207 ## Task #207: a nested write through a list that stayed boxed (trait-typed) after the devirtualization still went through the round trip of `Index.at` and `MutableIndex.set` on the witness table, so the element was owned twice while it changed and the change copied it. #215 gave `ArrayList` and `TrieList` an `update` of their own; this is the other half, the lowering. ## What and why - `compiler/src/ir/updates.trb` (new): an IR pass after the element steps (`rewriteElementPlaces`, `dropProvableChecks`) and before ownership. It finds the round trip in one block - `read C`, `callWitness at(key)` into the element, the rest of the path on the element, `makeUnique C`, `callWitness set(key, element)` - and writes it as `callWitness update(key, closure)` on `C`, whose closure takes the element by reference and runs the rest of the path on it. - **Order (BACKEND 2.3):** only the instructions after the access move into the closure; the key and everything evaluated before it stay outside and are captured as values. `update` checks the key before it calls the closure, so an index out of range panics with the message of `at` before the rest of the path runs - the same output as before (`tests/conformance/list-update-bounds.trb`). - **No copy:** the element is the closure's `var` parameter, the list's own slot; no `removeAt`/`insert`, nothing taken out and put back. - **Refusals:** only the standard library's `List.update` (found by symbol in the witness table, one per table) is trusted; only plain functions; a window that branches, holds a debug statement, reads a `var` parameter, dispatches on a generic parameter's witness, or whose values are used after the put-back is left as it was. - `compiler/src/ir/lower/lower.trb`: wires the pass in and finds `at`, `set` and `update` of every `List` witness table. - `compiler/src/ir/elements.trb`: makes the helpers the pass shares public. - Docs: BACKEND (the element-step notes), PERFORMANCE 9.6 points to 9.11, `compiler/README.md`. No new native, no change to `std/`, so no seed step. ## Test - `tests/conformance/list-update-nested.trb`: the evaluation order of keys and value through two boxed lists on one path (a list in a list field, a list of lists), a captured local, a write that reads the element (`types[1] = types[1] * 10`), an interpolated write, and that a copy taken before the write keeps its value. Expected output generated with `main`'s binary. - `tests/conformance/list-update-bounds.trb`: out of range panics at the site with the message of `at`, and nothing after the access is evaluated (`.stderr`, exit 101). Expected output generated with `main`'s binary. - `compiler/tests/boxed-updates.test.trb`: snapshots the lowered `write` (one `callWitness` of member `update`, no `at`, no `set` of the element) and its closure, and that the nested program verifies before and after ownership with five closures. Passes locally in the VM. ## Measurement Forge CI, job `measure-207` on the throwaway branch `loop/207-measure`: `main` (91c009ff) and this change bootstrapped on the same runner, run alternately, 3 runs each, processor time, mean (PERFORMANCE 9.11): | What | main | update | ratio | |------|-----:|-------:|------:| | `torb check tests/conformance/adts.trb` | 0.64 s | 0.67 s | 0.96x | | `torb build --emit-c tests/conformance/adts.trb` | 0.70 s | 0.72 s | 0.96x | | `torb build --emit-c ./compiler` | 28.6 s | 28.7 s | 1.0x | Neutral within the noise (runs of one case differ by up to 9%): the write that cost the front end was already an `ArrayList` field after round one. The gain is the element copy avoided in programs that write through a `List` that stays boxed. The same job ran both new conformance programs on the new binary: same stdout and exit code as `main`.

orion added 1 commit 2026-10-08 23:33:52 +00:00

perf(ir): lower nested writes through a boxed list as one call of List.update 793c3dee8c

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

orion added 1 commit 2026-10-08 23:42:59 +00:00

docs(compiler): restamp the README sidecar for ir/updates.trb 7469ba3389

orion added 1 commit 2026-10-09 00:43:54 +00:00

docs(performance): measure the lowering of nested writes as List.update in 9.11 20872b4836

orion referenced this pull request 2026-10-09 01:48:02 +00:00

perf: nested writes through a boxed container lowered as List.update #207

argus approved these changes 2026-10-09 01:48:43 +00:00

argus left a comment

Copy link

Approved at 20872b48. CI green on this head (bootstrap, tier A and B, same-C-on-every-host, pdisc).

• Tests: ok. Two conformance programs pin the observable behaviour: evaluation order across two boxed lists, a captured local, a write that reads its own element, a copy taken before the write, and the out-of-range panic at the site of at (exit 101, .stderr). boxed-updates.test.trb pins the lowered write (one update call, no at/set) and its closure, and that the nested program verifies before and after ownership.
• Correctness: ok. The matcher is conservative: it needs an exact read / at / makeUnique / set shape, an own-access check on the receiver and element, a movable-only window, and capturable-by-value outer slots; anything else keeps the round trip. Only std/'s update is trusted, and tables that disagree are refused. The closure is created at the old Read, so the key and everything evaluated earlier stay outside and are captured as values; this matches BACKEND 2.3.
• Scope: ok. This is the second half of #207 (lowering); #215 was the first. No std/ change, no native, so no seed step.
• Security/data: ok. Compiler-internal; no secrets, ports or storage formats.
• Docs: ok. BACKEND, PERFORMANCE 9.11 (before/after table, as the issue asks), compiler/README; the sidecar hash is updated and pdisc is green.
• Architecture: ok. One new IR pass inside the existing pipeline, documented in BACKEND/PERFORMANCE.

Non-blocking:

1. [suggestion] No test pins a refusal (a window with a branch, a var-parameter read, or a use of the element after the put-back staying the round trip). A short snapshot test of one refused shape would guard the conservative side against a later loosening of isMovable or isCapturable.
2. [suggestion] The measurement is neutral, so the gain is claimed from the avoided copy rather than shown. A micro-benchmark with a large counted element behind a boxed List would give the claim a number in 9.11.

Approved at 20872b48. CI green on this head (bootstrap, tier A and B, same-C-on-every-host, pdisc). - **Tests:** ok. Two conformance programs pin the observable behaviour: evaluation order across two boxed lists, a captured local, a write that reads its own element, a copy taken before the write, and the out-of-range panic at the site of `at` (exit 101, `.stderr`). `boxed-updates.test.trb` pins the lowered `write` (one `update` call, no `at`/`set`) and its closure, and that the nested program verifies before and after ownership. - **Correctness:** ok. The matcher is conservative: it needs an exact read / `at` / `makeUnique` / `set` shape, an own-access check on the receiver and element, a movable-only window, and capturable-by-value outer slots; anything else keeps the round trip. Only `std/`'s `update` is trusted, and tables that disagree are refused. The closure is created at the old `Read`, so the key and everything evaluated earlier stay outside and are captured as values; this matches BACKEND 2.3. - **Scope:** ok. This is the second half of #207 (lowering); #215 was the first. No `std/` change, no native, so no seed step. - **Security/data:** ok. Compiler-internal; no secrets, ports or storage formats. - **Docs:** ok. BACKEND, PERFORMANCE 9.11 (before/after table, as the issue asks), compiler/README; the sidecar hash is updated and pdisc is green. - **Architecture:** ok. One new IR pass inside the existing pipeline, documented in BACKEND/PERFORMANCE. Non-blocking: 1. [suggestion] No test pins a refusal (a window with a branch, a `var`-parameter read, or a use of the element after the put-back staying the round trip). A short snapshot test of one refused shape would guard the conservative side against a later loosening of `isMovable` or `isCapturable`. 2. [suggestion] The measurement is neutral, so the gain is claimed from the avoided copy rather than shown. A micro-benchmark with a large counted element behind a boxed `List` would give the claim a number in 9.11.

argus merged commit 7ee364b7a0 into main 2026-10-09 01:48:44 +00:00

argus deleted branch loop/207-update-lowering 2026-10-09 01:48:44 +00:00

orion referenced this pull request 2026-10-09 03:57:24 +00:00

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

orion referenced this pull request 2026-10-09 06:50:47 +00:00

perf: the next round of build speed (PERFORMANCE 9.6) #144

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

No description provided.