# 120,001 introspections, 3 distinct: making Typst's convergence check 334 faster > Source: > Published: 2026-07-26 16:12:16+00:00 *This is a submission for DEV's Summer Bug Smash: Clear the Lineup powered by Sentry.* *Written with AI assistance (Claude). The measurements, negative controls and verification below are real and reproducible — every number was taken from the runs described.* [Typst](https://github.com/typst/typst) is a markup-based typesetting system written in Rust — think LaTeX, but with a sane language and compile times measured in milliseconds. You write `= Heading` , it produces a PDF. The interesting part for this challenge is how Typst handles **introspection**. Documents can ask questions about their own finished layout: "what page is this heading on?", "how many figures are there?", "give me every `` label". That's circular by nature — the answer depends on the layout, and the layout depends on the answer. Typst resolves it by compiling the document repeatedly (up to 5 times) until the answers stop changing. When they *don't* stop changing, Typst has to tell you which lookup failed to settle. That's the step this post is about. [Issue #8611](https://github.com/typst/typst/issues/8611) reports a brutal regression between 0.15.0 and 0.14.2 on a 300-page document: The reporter profiled it with Perfetto and found all the time going into a single step called `analyze introspections` — which is new in 0.15. A Typst maintainer confirmed the shape of it: "This is actually very interesting because 'analyze introspections' is a new step and it's not supposed to be particularly expensive. So it taking this long is very unexpected." "There are 11,618,776 individual introspections and, with 0.15, Typst records and analyzes all of these for convergence to give hints. All of this machinery in Typst could probably be optimized… My gut feeling is that maybe there's even some quadratic complexity." Then it stalled, for a very human reason: the document is confidential and the profile was **13.8GB of JSON**. Nobody could reproduce it. Reading the code, the cost has three multiplying layers: ``` // crates/typst-library/src/engine.rs — recording self.introspections.push(introspection); // push-only. no dedup. // crates/typst-library/src/introspection/convergence.rs — analysis pub fn analyze(...) -> EcoVec { for introspection in introspections { // every single one if let Some(warning) = introspection.0.diagnose(world, introspectors) { sink.warn(warning); } } ``` and `diagnose` does this: ``` js const INSTANCES: usize = MAX_ITERS + 1; // = 6 let history = History::compute(world, introspectors, |engine, introspector| { self.introspect(engine, introspector) // re-executed once per instance }); ``` So every recorded introspection is **re-executed 6 times**, each time building a fresh `Engine` , `Sink` and `Traced` . With the reporter's 11.6 million introspections, that's roughly **70 million re-executions and 70 million engine allocations** — in a step whose only job is producing warning messages. The bit that stood out: `Sink::push_introspection` is push-only with no deduplication, yet `Introspection` already implements `PartialEq` and `Hash` (via `dyn_eq` /`dyn_hash` ). The machinery for collapsing duplicates was already there and unused. That's the whole question, and it isn't obvious. Look at what the introspection types carry: | Type | Fields | Can duplicate? | |---|---|---| `CounterAtIntrospection` | `(Counter, Location, Span)` | ❌ `Location` is per-element | `PositionIntrospection` | `(Location, Span)` | ❌ | `QueryIntrospection` | `(Selector, Span)` | ✅ no `Location` | `QueryFirstIntrospection` | `(Selector, Span)` | ✅ | `StateFinalIntrospection` | `(State, Span)` | ✅ | `BibliographyIntrospection` | `(Span)` | ✅ | A `Span` is a *source code* location, not a document location. So a `query()` inside a loop has **one span for every iteration** — twenty thousand iterations produce twenty thousand byte-identical introspections. That's precisely the glossary pattern the reporter described: one helper function, called once per entry. I couldn't get their document. But I didn't need it — I could build the condition myself. [PR: Analyze each distinct introspection only once →](https://github.com/Booyaka101/typst/pull/1) The change is small: ``` js let mut sink = Sink::new(); // Analyze each distinct introspection only once. Equal introspections // observe the same data, so they have equal histories and produce equal // diagnostics. A document that issues the same query or state lookup from // one call site records that introspection once per execution, and each // analysis re-runs it once per iteration, so the duplicates dominate. let mut seen = FxHashSet::default(); for introspection in introspections { if !seen.insert(introspection) { continue; } if let Some(warning) = introspection.0.diagnose(world, introspectors) { sink.warn(warning); } } ``` Plus `impl Eq for Introspection {}` , because only `PartialEq` existed. **This PR deliberately lives on a fork.** Typst's `CONTRIBUTING.md` states that contributions implemented with AI assistance will not be accepted, and I'm not going to spend a volunteer maintainer's limited time arguing with their own stated policy. The measurement stands on its own; if it's useful to them, the analysis is public. `analyze` only runs when convergence validation *fails*, so a benchmark needs a document that genuinely can't settle, plus a lot of introspections. Two knobs: ``` js #let headings = 400 // makes each individual query expensive #let n = 60000 // introspection volume, all from one span // non-convergence driver: this state depends on its own resolved value #let osc = state("osc", 0) #context osc.update(osc.final() + 1) #for i in range(headings) [ = Heading #i ] #for _ in range(n) [ #context { let _ = query(heading) } ] #for _ in range(n) [ #context { let _ = osc.final() } ] ``` My first attempt reported `analyze introspections: 0.00s across 0 spans` , which I nearly believed. Two things were wrong: Typst's trace emits `ph:"B"` /`ph:"E"` **pairs**, not `ph:"X"` spans with a `dur` field, so my parser counted nothing — and the span wasn't in the trace at all. So I stopped trusting the tracer and instrumented the function directly: ``` PROBE analyze: 40001 introspections, 3 distinct, elapsed 61.99ms ``` **40,001 recorded, 3 distinct.** A 13,334× duplication factor, measured rather than assumed. Same binary, both code paths behind one env toggle so a single build produced both numbers: | introspections analysed | `analyze introspections` | wall clock | | |---|---|---|---| Upstream | 120,001 | 1.078 s | 2.63 s | Deduped | 3 | 0.0032 s | 1.44 s | **~334× on the step. ~1.8× end to end.** A perf win that changes output is not a win. **Diagnostics byte-identical.** `diff` clean over all 34 lines — *including* the `see 2 additional warnings` count. I'd worried dedup would change that count; it doesn't, because Typst already runs `deduplicate()` on diagnostics downstream. Duplicate warnings were being computed and then thrown away. **PDF content identical.** All outputs exactly 162,464 bytes. Raw hashes differ, which looked alarming until I ran the control: **two consecutive baseline runs also differ from each other.** The differing bytes are the timestamp: ``` region A: /ModDate(D:20260726232403+08'00)/CreationDate(D:20260726232403+08'00) region C: /ModDate(D:20260726232407+08'00)/CreationDate(D:20260726232407+08'00) ``` 92 bytes differ baseline-vs-baseline; 88 baseline-vs-deduped. Same region, same magnitude. Pre-existing non-determinism. **Test suite neutral.** `1555 passed, 2167 failed` — *identical with and without the patch*. Those 2167 failures are environmental, not mine: `tests/src/run.rs:520` calls `std::os::windows::fs::symlink_file(...).unwrap()` , which returns Windows error **1314 (ERROR_PRIVILEGE_NOT_HELD)** without Developer Mode. I confirmed it by stashing the patch and getting the same count. It fails `array-basic-syntax` , which has nothing to do with introspection. `cargo fmt --check` and `cargo clippy --workspace --all-targets` both clean. Deduplication belongs in `analyze` , **not** at record time in `Sink::push_introspection` . It's tempting to dedupe at the source — but `push_introspection` runs on *every* compile, while `analyze` only runs when a document fails to converge. Deduping at the record site would tax every successful compile in order to speed up the failure path. Wrong layer. Being straight about the limits: **This is my synthetic document, not theirs.** My per-introspection cost is ~1.55µs; their queries run over 300 pages and are far heavier. The total saving is `duplication_factor × per_introspection_cost` . I've proven the mechanism and that the factor can be enormous — I have not proven how much of their specific 10.9× this recovers, and I'm not going to claim otherwise. **Location-carrying introspections can't collapse.** If their 11.6 million are mostly `CounterAtIntrospection` , this helps far less. The evidence that it won't be is their own description — a glossary whose entries reference each other, which hits `QueryIntrospection` and `StateFinalIntrospection` , neither of which carries a `Location` . **A push-only collection plus an expensive per-item operation is a latent multiplier.** Nobody wrote a quadratic loop here. Someone added a recording buffer, someone else added a 6× analysis, and the bug is the product of two individually reasonable decisions. **Verify the benchmark before trusting the benchmark.** My first measurement said zero. If I'd reported that, I'd have concluded there was nothing to optimise — in a step that was in fact burning a full second. **Run the control.** The PDFs differed and my instinct was that I'd broken something. Two baseline runs differing from each other took thirty seconds to check and saved me chasing a phantom. *Submitted for DEV's Summer Bug Smash — Clear the Lineup.*