perf(bytecode): VM list-iterate with the counted for pass (#482) #520

Merged

argus merged 2 commits from loop/482-vm-list-iterate into main 2026-10-27 09:33:45 +00:00

Conversation 1 Commits 2 Files changed 3 +117 -12

orion commented 2026-10-26 23:38:46 +00:00

Collaborator

Copy link

Closes #482

The counted for loop over a list ran 3x slower in the VM than before #475 (issue #482). Commit 1 widens the guard of tools/collection-cost.sh to compiler/src/backend/bytecode and compiler/src/vm, so this PR's tier B measures the VM, and prints the bytecode of benchmarks/list-iterate.trb for base and head. Commit 2 is the fix.

Root cause. The bytecode of the new loop is minimal (less, branch, one load with the list-item step, three adds), so the emitter is not at fault. kernelCall (compiler/src/vm/interpret.trb) turned the KernelOperation into its number with kernelNumberOf (compiler/src/backend/bytecode/format.trb), a linear scan over allKernelOperations. ElementAddress (what list-index uses) sits near the front of the table, ListItemAddress (operation 68, added late) near the back, so every item read scanned ~68 entries before the kernel ran: ~500 ns per read, 80M reads, 62 s - 20 s.

Fix. kernelNumberOf is a match, generated from the table in the table's order, so the C TORB_OPERATION_* numbering and the table are unchanged. compiler/tests/bytecode.test.trb already pinned "every operation maps to its index"; it now also pins that the table's last operation stays below kernelNativeBase.

Test. Tier B (tools/collection-cost.sh), VM fastest of 3, criteria: list-iterate <= ~22 400 ms (pre-#475 baseline in the issue: 20 339-20 828 ms), list-index <= 1.10x, native <= 1.7x, allocations 22/22.

• Before (run 1987, head 8cd52b0f, merge base already carries #475): list-index 22 672 -> 23 177 ms, list-iterate 62 358 -> 61 511 ms (noise floor; native 1.48x / 1.58x; allocations 22/22).
• After (run 2004, head 00a63378, the same two commits before the rebase onto the current main; forge CI green, tier A/B and gates): list-index 23 217 -> 23 476 ms (1.011x), list-iterate 62 321 -> 12 143 ms (5.1x faster; the pre-#475 baseline was 20 339-20 828 ms, so the fix also beats it: the item read no longer scans the table at all, #475's smaller loop now pays off); native ratios unchanged (list-iterate 1.60x, list-index 6.19x -> 6.41x with the usual noise); allocations 22/22; hello-world native size 0 bytes; bytes-pass 0.860; round trip 0.971 of the one before.
• tools/collection-cost.sh compares to the merge base, which already carries #475, so its "base" row is the slow one; the pre-#475 numbers come from the issue.
• tools/check-commits.sh origin/main HEAD: clean.

Closes #482 The counted `for` loop over a list ran 3x slower in the VM than before #475 (issue #482). Commit 1 widens the guard of `tools/collection-cost.sh` to `compiler/src/backend/bytecode` and `compiler/src/vm`, so this PR's tier B measures the VM, and prints the bytecode of `benchmarks/list-iterate.trb` for base and head. Commit 2 is the fix. **Root cause.** The bytecode of the new loop is minimal (`less`, `branch`, one `load` with the list-item step, three adds), so the emitter is not at fault. `kernelCall` (`compiler/src/vm/interpret.trb`) turned the `KernelOperation` into its number with `kernelNumberOf` (`compiler/src/backend/bytecode/format.trb`), a linear scan over `allKernelOperations`. `ElementAddress` (what `list-index` uses) sits near the front of the table, `ListItemAddress` (operation 68, added late) near the back, so every item read scanned ~68 entries before the kernel ran: ~500 ns per read, 80M reads, 62 s - 20 s. **Fix.** `kernelNumberOf` is a `match`, generated from the table in the table's order, so the C `TORB_OPERATION_*` numbering and the table are unchanged. `compiler/tests/bytecode.test.trb` already pinned "every operation maps to its index"; it now also pins that the table's last operation stays below `kernelNativeBase`. **Test.** Tier B (`tools/collection-cost.sh`), VM fastest of 3, criteria: `list-iterate` <= ~22 400 ms (pre-#475 baseline in the issue: 20 339-20 828 ms), `list-index` <= 1.10x, native <= 1.7x, allocations 22/22. - Before (run 1987, head 8cd52b0f, merge base already carries #475): `list-index` 22 672 -> 23 177 ms, `list-iterate` 62 358 -> 61 511 ms (noise floor; native 1.48x / 1.58x; allocations 22/22). - After (run 2004, head 00a63378, the same two commits before the rebase onto the current `main`; forge CI green, tier A/B and gates): `list-index` 23 217 -> 23 476 ms (1.011x), **`list-iterate` 62 321 -> 12 143 ms** (5.1x faster; the pre-#475 baseline was 20 339-20 828 ms, so the fix also beats it: the item read no longer scans the table at all, #475's smaller loop now pays off); native ratios unchanged (`list-iterate` 1.60x, `list-index` 6.19x -> 6.41x with the usual noise); allocations 22/22; hello-world native size 0 bytes; bytes-pass 0.860; round trip 0.971 of the one before. - `tools/collection-cost.sh` compares to the merge base, which already carries #475, so its "base" row is the slow one; the pre-#475 numbers come from the issue. - `tools/check-commits.sh origin/main HEAD`: clean.

orion added 1 commit 2026-10-26 23:38:46 +00:00

chore(tools): measure the bytecode and the VM in collection-cost.sh ... 9030a853d8

The guard now also fires for a branch that touches compiler/src/backend/bytecode or compiler/src/vm, and the
script prints the bytecode of the chunks of benchmarks/list-iterate.trb for the merge base and this checkout
(#482).

orion force-pushed loop/482-vm-list-iterate from 9030a853d8 to f9acf31b5f 2026-10-27 00:36:37 +00:00 Compare

orion force-pushed loop/482-vm-list-iterate from f9acf31b5f to 8cd52b0f72 2026-10-27 01:02:43 +00:00 Compare

orion referenced this pull request 2026-10-27 01:04:18 +00:00

perf: torb run --vm of benchmarks/list-iterate is 3x slower with the counted for pass (follow-up of #470) #482

orion referenced this pull request 2026-10-27 03:12:53 +00:00

perf: torb run --vm of benchmarks/list-iterate is 3x slower with the counted for pass (follow-up of #470) #482

orion referenced this pull request 2026-10-27 03:17:09 +00:00

perf: torb run --vm of benchmarks/list-iterate is 3x slower with the counted for pass (follow-up of #470) #482

orion force-pushed loop/482-vm-list-iterate from 8cd52b0f72 to 00a63378d5 2026-10-27 03:23:45 +00:00 Compare

orion referenced this pull request 2026-10-27 04:15:05 +00:00

perf: torb run --vm of benchmarks/list-iterate is 3x slower with the counted for pass (follow-up of #470) #482

orion referenced this pull request 2026-10-27 06:31:06 +00:00

perf: torb run --vm of benchmarks/list-iterate is 3x slower with the counted for pass (follow-up of #470) #482

orion force-pushed loop/482-vm-list-iterate from 00a63378d5 to 24803ba850 2026-10-27 06:31:51 +00:00 Compare

orion changed title from WIP: perf(bytecode): VM list-iterate with the counted for pass (#482) to perf(bytecode): VM list-iterate with the counted for pass (#482) 2026-10-27 06:32:23 +00:00

orion requested review from argus 2026-10-27 06:32:24 +00:00

orion referenced this pull request 2026-10-27 06:32:35 +00:00

perf: torb run --vm of benchmarks/list-iterate is 3x slower with the counted for pass (follow-up of #470) #482

argus approved these changes 2026-10-27 09:33:44 +00:00

argus left a comment

Copy link

Approved.

• Tests: ok. bytecode.test.trb already pinned "every operation maps to its index"; the new test pins the last operation and last < kernelNativeBase. CI green on this head (tier A/B, gates, pdisc, commit messages).
• Correctness: ok. I checked the 91 match arms against allKernelOperations: same order, same numbers, and the set equals the KernelOperation cases, so the C TORB_OPERATION_* numbering is unchanged and the match is exhaustive.
• Scope: ok. Issue #482 only: the fix plus the measurement guard in tools/collection-cost.sh (measurement only, exits 0).
• Security/data/docs/architecture: no findings; no boundary change.
• Performance: PR body documents before/after on tier B (list-iterate 62 s to 12 s, list-index within noise, allocations 22/22).

Non-blocking: the match must be extended by hand when an operation is added; the index-equals-table test catches a missing or wrong arm.

Approved. - Tests: ok. `bytecode.test.trb` already pinned "every operation maps to its index"; the new test pins the last operation and `last < kernelNativeBase`. CI green on this head (tier A/B, gates, pdisc, commit messages). - Correctness: ok. I checked the 91 `match` arms against `allKernelOperations`: same order, same numbers, and the set equals the `KernelOperation` cases, so the C `TORB_OPERATION_*` numbering is unchanged and the match is exhaustive. - Scope: ok. Issue #482 only: the fix plus the measurement guard in `tools/collection-cost.sh` (measurement only, exits 0). - Security/data/docs/architecture: no findings; no boundary change. - Performance: PR body documents before/after on tier B (`list-iterate` 62 s to 12 s, `list-index` within noise, allocations 22/22). Non-blocking: the match must be extended by hand when an operation is added; the index-equals-table test catches a missing or wrong arm.

argus merged commit 70cddb4324 into main 2026-10-27 09:33:45 +00:00

argus deleted branch loop/482-vm-list-iterate 2026-10-27 09:33:45 +00:00

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

No description provided.