Skip to content

BS-02: strict scans make the certified lexer quadratic #373

Closed

Description

@humuhumu33

lex takes 680 s on 343 KB against 3.8 ms for its oracle (bootstrap/PERFORMANCE.md, #277). In bootstrap/src/TokenAudit.lex.tex, stepLexAt, stepLexToken, stepLexIdent and scanSegmentsStep bind each candidate scan before branching, so block comment, string, raw string, line comment and quoted name scans run whether or not they are used.

Fix: move each scan into the branch that reads it. A copy of the generated Rust with those scans guarded by their first byte returned the same 42,236 lexemes on TargetSemantics.lean, in 42 ms against 205 s in the same build.

Done when: the lexer grows linearly on that module, the proofs and BS-02 still pass, and PERFORMANCE.md shows the new row.

Activity

  1. added a commit that references this issue on Nov 9, 2026
  2. afflom commented on Nov 9, 2026

    @afflom
    Member

    Completed by #394, now landed on release/v0.4 as 4318b17. The exact contributor lexer source and committed PERFORMANCE rows retain the documented d34/WSL measurement scope and comparison caveats. The measured lexer growth rows, the proof products and BS-02 all accompany the landing.

    Final-head CI 42688365239 passed all 45 expected jobs and reproducibility 42688244759 passed. Actual landed tree 897999743ac4348711b86058832a1666dc88f572 matches both the independently reviewed source/products and the tested merge tree. No new timing measurement or broader release completion is claimed.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions