Something went wrong. Try again.
The Monad language. Dependent types, functional programming compiled with LLVM. Hobby project. monad-lang.org
dependent-types language compiler programming-language functional-programming
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141/// Isolated micro-benchmark for `take_while`/// (`lang/parser/combinators.mo`), the self-hosted parser's single/// hottest loop — every whitespace skip, identifier, number and string/// literal in the whole grammar goes through it.////// Exists because AGENTS.md item 27 measured `load_file_modules`/// (read + parse) at 2519ms of `elaborate_loaded_modules`' 3732ms (67%)/// on `check examples/hello.mo`, i.e. two thirds of elaboration is the/// parser running interpreted over ~1529 lines of prelude/init/std. That/// number says WHERE the time goes but not what shape it has, and the/// same rule that governs every other perf change in this codebase/// applies here (see AGENTS.md's BTreeMap-regression writeup, item 4):/// measure the specific loop before rewriting it, because chain-depth/// and Big-O reasoning have twice failed to predict this interpreter.////// What `take_while_loop` does per CHARACTER today: `is_empty input`,/// `utf8_char_width input` (a `String.get` native plus up to four/// `U8.lt`), `String.slice input 0 width` (a native that ALLOCATES a/// fresh one-character string), the predicate call, and a `String.drop`/// to recurse. The predicates are themselves comparison chains over/// one-character strings — `is_space` up to four `String.beq`,/// `is_ident_char` reaching `is_alphanumeric` -> `is_alpha` -> four/// helpers, `is_digit` a ten-way chain.////// Two dimensions are measured separately because they answer different/// questions:////// - **short**: many calls over a token-sized run (8 chars). This is/// what real parsing actually does — every token is short and the/// call volume is enormous — so it mixes per-CALL overhead with/// per-character cost, and is the number that should track a real/// `check` speedup./// - **long**: few calls over a long run (2048 chars). Isolates/// per-CHARACTER cost with per-call overhead amortized away, which/// is what a change to the scanning strategy itself should move.////// Runs stay well under the interpreter's recursion limit either way:/// `take_while_loop` is deliberately self-tail-recursive (see its own/// doc comment) and `core_eval.rs` has tail-call optimization (item 8),/// but `lang/parser/position.mo`'s own note records that scanning a/// whole large file in one call used to blow the stack, so this/// benchmark does not try to.use std::bench {Bench.now, Bench.report_since}use parsec::core {ParseResult}use parsec::combinators {take_while, take_while_byte}use parsec::char_preds {is_ident_char, is_ident_char_byte, is_space, is_space_byte}open ParseResult {fail, success}/// Repeatedly double `s` until it reaches `target` bytes. Doubling, not/// append-one-at-a-time: `String.concat` allocates a fresh string per/// call, so building an n-byte input one character at a time would be/// O(n^2) in allocation and would dominate the thing being measured.#[partial]def grow_to (s : String) (target : I64) : String := if I64.lt (String.length s) target then grow_to (String.concat s s) target else s/// How much `take_while` consumed. Also the reason the loops below/// accumulate: without consuming the result the whole call could in/// principle be skipped, and a benchmark that measures nothing is worse/// than one that measures the wrong thing (AGENTS.md item 25).#[partial]def consumed (r : ParseResult String) : I64 := match r { success _ out => String.length out, fail _ => 0 }#[terminating]def scan_spaces (i : I64) (n : I64) (input : String) (acc : I64) : I64 := if I64.beq i n then acc else scan_spaces (i + 1) n input (acc + consumed (take_while is_space input))#[terminating]def scan_idents (i : I64) (n : I64) (input : String) (acc : I64) : I64 := if I64.beq i n then acc else scan_idents (i + 1) n input (acc + consumed (take_while is_ident_char input))#[terminating]def scan_spaces_byte (i : I64) (n : I64) (input : String) (acc : I64) : I64 := if I64.beq i n then acc else scan_spaces_byte (i + 1) n input (acc + consumed (take_while_byte is_space_byte input))#[terminating]def scan_idents_byte (i : I64) (n : I64) (input : String) (acc : I64) : I64 := if I64.beq i n then acc else scan_idents_byte (i + 1) n input (acc + consumed (take_while_byte is_ident_char_byte input))/// `calls` * `run_len` characters scanned by each predicate, so the two/// shapes below are directly comparable per character.def run_bench (calls : I64) (run_len : I64) (label : String) : IO Bool := do { let spaces : String := grow_to " " run_len; let idents : String := grow_to "a" run_len; let sp_start : I64 <- Bench.now; let sp_total := scan_spaces 0 calls spaces 0; Bench.report_since (String.concat "take_while is_space " label) sp_start; let id_start : I64 <- Bench.now; let id_total := scan_idents 0 calls idents 0; Bench.report_since (String.concat "take_while is_ident_char " label) id_start; let spb_start : I64 <- Bench.now; let spb_total := scan_spaces_byte 0 calls spaces 0; Bench.report_since (String.concat " BYTE is_space_byte " label) spb_start; let idb_start : I64 <- Bench.now; let idb_total := scan_idents_byte 0 calls idents 0; Bench.report_since (String.concat " BYTE is_ident_char_byte " label) idb_start; // All four totals are `calls * consumed-per-call` and must be // positive -- proof the loops actually ran and the predicates // actually matched. The byte totals must EQUAL their string // counterparts: the two scanners are required to consume exactly the // same input, and a byte scan that stopped early would show up here // rather than as a silently faster wrong answer. return (I64.gt sp_total 0 && I64.gt id_total 0 && I64.beq spb_total sp_total && I64.beq idb_total id_total)}/// Token-shaped: short runs, high call volume. `grow_to` rounds up to a/// power of two, so this is 8 characters per call.#[test]def bench_take_while_short_runs : IO Bool := run_bench 4000 8 "short (4000 calls x 8 chars)"/// Character-cost-shaped: long runs, low call volume. Same total/// characters scanned as the short case (32000), so the two numbers/// differ only by per-call overhead.#[test]def bench_take_while_long_runs : IO Bool := run_bench 16 2048 "long (16 calls x 2048 chars)"