vt: decode CSI parameter runs in a register #425

Merged

natsukium merged 3 commits from vt/faster-param-runs into main 2026-09-25 10:20:07 +09:00

Conversation 0 Commits 3 Files changed 6 +153 -14

natsukium commented 2026-09-25 08:44:02 +09:00

Owner

Copy link

Closes #417.

Params::push_run fed every byte through push_digit / next_slot, so each digit reloaded len, re-checked it, and did a saturating multiply on the slot in memory, reading back the previous digit's store. It now keeps the open slot's value and the slot count in registers and writes the slot once per separator and once at the end of the run (min(10v + d, u16::MAX) in u32 is the same fold as the per-byte saturating ops). The bulk arm in advance also takes the first parameter byte in CsiEntry (digit or ;; a leading : stays per-byte because start_empty opens no subparam slot), saving one advance_byte round trip per CSI.

Measurements

Floor bench measure_parse_into_grid_floor, 35x106 (DOOM-fire capture geometry), median of 5 interleaved runs, load ~3, instructions:u over the bench's two passes:

payload	MiB/s base → new	instructions
doom (56 MiB DOOM-fire capture)	218 → 241 (+10.8%)	10350M → 9409M (−9.1%)
truecolor (per-cell 38;2/48;2)	297 → 345 (+16.1%)	5257M → 4476M (−14.9%)
csi (kitten csi mix)	143 → 154 (+7.3%)	9315M → 8833M (−5.2%)
sparse scroll (y\r\n)	96.3 → 96.9 (+0.6%)	30542M → 30961M (+1.4%)

The sparse scroll floor is flat over 10 interleaved runs (96.9 vs 96.5 MiB/s median, cycles within 0.5%), so the accepted cost in cost-maps does not grow.

Rejected (numbers in the commit body and cost-maps): SWAR digit windows (+7% instructions on doom: SGR params are 1–3 digits), loading values[0] on an empty list (store-forward block against clear's zeroing store once per CSI), and a ||-joined two-state guard (~8% csi cycles).

Guards

• Kani push_run_equals_per_byte_primitives: push_run vs push_digit/next_slot over every 8-byte input (mutation-checked: a wrong clamp fails it).
• Proptest csi_param_runs_match_per_byte_dispatch_at_any_chunking: CSI-dense streams (long digit runs, :, >16 params, private markers, C0/CAN/ESC mid-sequence) cut at random chunk boundaries, whole Parser and dispatch log compared against advance_byte.
• Existing chunk-invariance test and Kani split-invariance proof pass; vt_parser fuzz target 33M runs in 240 s clean; just check green.

Review

pi (sol) on origin/main...HEAD: PASS, no findings.

Closes #417. `Params::push_run` fed every byte through `push_digit` / `next_slot`, so each digit reloaded `len`, re-checked it, and did a saturating multiply on the slot in memory, reading back the previous digit's store. It now keeps the open slot's value and the slot count in registers and writes the slot once per separator and once at the end of the run (`min(10v + d, u16::MAX)` in `u32` is the same fold as the per-byte saturating ops). The bulk arm in `advance` also takes the first parameter byte in `CsiEntry` (digit or `;`; a leading `:` stays per-byte because `start_empty` opens no subparam slot), saving one `advance_byte` round trip per CSI. ## Measurements Floor bench `measure_parse_into_grid_floor`, 35x106 (DOOM-fire capture geometry), median of 5 interleaved runs, load ~3, `instructions:u` over the bench's two passes: | payload | MiB/s base → new | instructions | |---|---|---| | doom (56 MiB DOOM-fire capture) | 218 → 241 (+10.8%) | 10350M → 9409M (−9.1%) | | truecolor (per-cell `38;2`/`48;2`) | 297 → 345 (+16.1%) | 5257M → 4476M (−14.9%) | | csi (kitten csi mix) | 143 → 154 (+7.3%) | 9315M → 8833M (−5.2%) | | sparse scroll (`y\r\n`) | 96.3 → 96.9 (+0.6%) | 30542M → 30961M (+1.4%) | The sparse scroll floor is flat over 10 interleaved runs (96.9 vs 96.5 MiB/s median, cycles within 0.5%), so the accepted cost in cost-maps does not grow. Rejected (numbers in the commit body and cost-maps): SWAR digit windows (+7% instructions on doom: SGR params are 1–3 digits), loading `values[0]` on an empty list (store-forward block against `clear`'s zeroing store once per CSI), and a `||`-joined two-state guard (~8% csi cycles). ## Guards - Kani `push_run_equals_per_byte_primitives`: `push_run` vs `push_digit`/`next_slot` over every 8-byte input (mutation-checked: a wrong clamp fails it). - Proptest `csi_param_runs_match_per_byte_dispatch_at_any_chunking`: CSI-dense streams (long digit runs, `:`, >16 params, private markers, C0/CAN/ESC mid-sequence) cut at random chunk boundaries, whole `Parser` and dispatch log compared against `advance_byte`. - Existing chunk-invariance test and Kani split-invariance proof pass; `vt_parser` fuzz target 33M runs in 240 s clean; `just check` green. ## Review pi (sol) on `origin/main...HEAD`: PASS, no findings.

natsukium added 2 commits 2026-09-25 08:44:02 +09:00

vt: decode CSI parameter runs in a register ... d49b43ad63

Under DOOM-fire about 85% of the stream is `38;5;N` / `48;5;N` SGR
parameters, and `Params::push_run` was the largest self-time frame of
the doom floor bench (~20% of cycles and instructions). It fed each byte
through `push_digit` / `next_slot`, so every digit reloaded `len`,
re-checked it, and did a saturating multiply on the slot in memory,
reading back the store of the previous digit.

`push_run` now keeps the open slot's value and the slot count in
registers and writes the slot once per separator and once at the end of
the run. The saturation is `min(10v + d, u16::MAX)` in `u32`, which is
the same fold as the per-byte `saturating_mul(10).saturating_add(d)`.
The bulk arm in `advance` also takes the first parameter byte in
`CsiEntry`, where every SGR used to spend one `advance_byte` round trip
on `start_with`. A leading `:` stays per-byte because `start_empty`
opens no subparam slot. When the list is empty the run starts from 0
instead of loading `values[0]`: that load read `clear`'s wide zeroing
store, which blocked store forwarding once per CSI (6.4M blocked loads
vs 3.6M on the doom floor).

SWAR-decoding each digit run from an 8-byte window was rejected: at the
1–3 digit parameters SGR carries, the per-parameter mask, shift and
multiply cost more instructions than the digits they replace (+7% on
the doom floor). Spelling the arm as two state tests joined by `||`
instead of one `CsiEntry | CsiParam` range test cost the csi floor ~8%
of cycles against the single-range form.

Floor bench (`measure_parse_into_grid_floor`, 35x106 capture geometry,
median of 5 interleaved runs at load ~3, instructions:u over the bench's
two passes; base -> new):

  doom       218 -> 241 MiB/s (+10.8%)  10350M ->  9409M  (-9.1%)
  truecolor  297 -> 345 MiB/s (+16.1%)   5257M ->  4476M (-14.9%)
  csi        143 -> 154 MiB/s  (+7.3%)   9315M ->  8833M  (-5.2%)
  scroll      96 ->  97 MiB/s  (+0.6%)  30542M -> 30961M  (+1.4%)

The sparse scroll floor is flat over 10 interleaved runs (median 96.9
vs 96.5 MiB/s, cycles within 0.5%), so the recorded accepted cost of
the bulk arm does not grow.

Equivalence is pinned three ways: a Kani proof of `push_run` against the
per-byte primitives over every 8-byte input, a proptest comparing the
whole parser against `advance_byte` over CSI-dense streams cut at random
chunk boundaries, and the existing chunk-invariance test. The
`vt_parser` fuzz target ran 33M executions (240 s) clean.

Assisted-by: Claude Code

skills: record the register-decoded CSI parameter floor ... 044bba2cc1

The SGR-flood cost map still described `push_run` as the per-byte
primitive loop. It now carries the floor figures after the register
decode and the `CsiEntry` bulk arm, and the three shapes that measured
worse (SWAR digit windows, loading the empty slot from `clear`'s store,
a two-test `||` state guard) so the next pass over the arm does not
re-run them.

Assisted-by: Claude Code

natsukium added 1 commit 2026-09-25 09:29:42 +09:00

Merge remote-tracking branch 'origin/main' into vt/faster-param-runs 5d72af778d

natsukium merged commit fec864bf14 into main 2026-09-25 10:20:07 +09:00

natsukium deleted branch vt/faster-param-runs 2026-09-25 10:20:07 +09:00

natsukium referenced this pull request from a commit 2026-09-25 10:20:09 +09:00

vt: decode CSI parameter runs in a register (#425)

natsukium referenced this pull request 2026-09-25 13:15:57 +09:00

bench: follow up the 9d1d842f cross-terminal run #405

Commenting is not possible because the repository is archived.

Reviewers

No reviewers

Labels

Clear labels   

priority/P0

Must be resolved before the v0.1.0 tag

  

priority/P1

Must be settled before the first public contract freezes

  

priority/P2

Explicitly deferred until after v0.1.0

  

release/v0.1.0

Work tracked for the first tagged release

  

status/blocked

Cannot start now: waits on an upstream release, another issue, or a recorded revisit trigger

  

status/planned

Triaged with a source-grounded plan and a passed pi review; ready to implement

  

type/bug

Shipped behavior that contradicts the docs or the code's own intent; needs a product code change

  

type/design

An open scope or trade-off question; needs a recorded decision in the owning explanation doc before code

  

type/test-gap

Documented or reviewed behavior that no test pins; usually split from a review finding, needs no product code change

  

type/tracker

Parent issue that tracks child work

No labels

priority/P0

priority/P1

priority/P2

release/v0.1.0

status/blocked

status/planned

type/bug

type/design

type/test-gap

type/tracker

Milestone

Clear milestone

No items

No milestone

Projects

Clear projects

No items

No project

Assignees

Clear assignees

No assignees

1 participant

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

natsukium/felis!425

No description provided.