Skip to content

Conversation

@laurmaedje
Copy link
Member

@laurmaedje laurmaedje commented Jul 30, 2025

This PR resolves a problem that can cause a lot of slowdown in compilation. The impact of this problem varies from document to document, but context-heavy documents are generally more affected by it. The root cause lies in comemo where cache validation could take quadratic time in N, where N is a number that used to be low most of the time, but that is increasingly not low anymore with heavy context usage.

The fix for the problem is a new tree-based constraint validation implementation in comemo. There's some more details on this in the accompanying comemo PR.

The performance impact of this change:

  • Huge speedup in cases where the quadratic runtime of cache validation used to dominate compile time.

  • Solid speedup in incremental compiles on documents where cache performance is a bottleneck (this also depends a lot on the document; it was 15% faster on one document I tested, but only 2% on another).

  • Mixed changes in clean compiles: A few percent of speedup in some cases and a few percent of slowdown in others. Depends a lot on the document. There is definitely some overhead in inserting into the new tree data structure, which happens on a cache miss. Meanwhile, the improved validation performance kicks in when there's a cache hit. Probably, in the documents with slowdown, there are few cache hits in the clean compile and in the ones with speedup, there's a fair number of cache hits in the clean compile (across layout iterations).

Fixes #5220

@laurmaedje laurmaedje force-pushed the comemo-tree branch 2 times, most recently from d8af54c to cbbeba8 Compare July 31, 2025 08:44
@laurmaedje laurmaedje changed the title Faster constraint checking in comemo Faster constraint checking in comemo (bumps comemo & krilla) Jul 31, 2025
@laurmaedje laurmaedje enabled auto-merge July 31, 2025 09:17
@laurmaedje laurmaedje added this pull request to the merge queue Jul 31, 2025
Merged via the queue into main with commit 492bd27 Jul 31, 2025
16 checks passed
@laurmaedje laurmaedje deleted the comemo-tree branch July 31, 2025 10:06
Myriad-Dreamin pushed a commit to Myriad-Dreamin/tinymist that referenced this pull request Aug 3, 2025
+ several fixes to `nightly.yml`
+ update `comemo` for typst/typst#6683
ParaN3xus added a commit to ParaN3xus/tinymist that referenced this pull request Aug 7, 2025
+ several fixes to `nightly.yml`
+ update `comemo` for typst/typst#6683
Myriad-Dreamin pushed a commit to Myriad-Dreamin/tinymist that referenced this pull request Sep 9, 2025
+ several fixes to `nightly.yml`
+ update `comemo` for typst/typst#6683
ParaN3xus added a commit to ParaN3xus/tinymist that referenced this pull request Sep 20, 2025
+ several fixes to `nightly.yml`
+ update `comemo` for typst/typst#6683
ParaN3xus added a commit to ParaN3xus/tinymist that referenced this pull request Sep 24, 2025
+ several fixes to `nightly.yml`
+ update `comemo` for typst/typst#6683
hiandy24 pushed a commit to hiandy24/typst that referenced this pull request Sep 27, 2025
… upstream (#1)

* Numbering implementation refactor (typst#6122)

* Pin colspan and rowspan for blank cells (typst#6401)

* Clean up some parser comments (typst#6398)

* Autocomplete fixes for math mode (typst#6415)

* Update docs for gradient.repeat (typst#6385)

* Document how to escape lr delimiter auto-scaling (typst#6410)

Co-authored-by: Laurenz <[email protected]>

* Improve number lexing (typst#5969)

* Report errors in external files (typst#6308)

Co-authored-by: Laurenz <[email protected]>

* Table multiple headers and subheaders (typst#6168)

* Use the shaper in math (typst#6336)

* Standardize trailing slashes in docs route paths (typst#6420)

* Make a more descriptive definition of `module` (typst#6380)

* Specify which CSL style is not suitable for bibliographies (typst#6306)

Co-authored-by: Laurenz <[email protected]>

* Adjust source file API surface (typst#6423)

* Do not force `math.mid` elements to have the Large math class (typst#5980)

* List both YAML file extensions in bibliography docs (typst#6426)

* Fix panic when test source is not found in world (typst#6428)

* Use `codex::ModifierSet` (typst#6159)

Co-authored-by: Laurenz <[email protected]>

* Render `#super` as `<sup>`, `#sub` as `<sub>` in HTML (typst#6422)

* Warning when watching stdin (typst#6381)

Co-authored-by: Laurenz <[email protected]>

* Fix untidy Cargo.lock

* Warn when using variable fonts (typst#6425)

* Check that all translation files are added to TRANSLATIONS and ends with newline (typst#6424)

Co-authored-by: Laurenz <[email protected]>

* Unify `EvalMode` and `LexMode` into `SyntaxMode` (typst#6432)

* Consume `data` argument in `pdf.embed()` (typst#6435)

* Better error message for compile time string interning failure (typst#6439)

* Ensure that label repr is syntactically valid (typst#6456)

* Hint for label in both document and bibliography (typst#6457)

* Prefer `.yaml` over `.yml` in the docs (typst#6436)

* Fix align link in layout documentation (typst#6451)

* Fix param autocompletion false positive (typst#6475)

* Encode empty attributes with shorthand syntax

* Add `Duration::decompose`

* Generic casting for `Axes<T>`

* More type-safe color conversions

* Add  `typst_utils::display`

* Support for generating native functions at runtime

* Typed HTML API (typst#6476)

* Consistent codepoint formatting in HTML and PDF error messages

* Test runner support for HTML export errors

* Turn non-empty void element into export error

* Handle pre elements that start with a newline

* Extract `write_children` function

* Properly handle raw text elements

* Fix stroke cap of shapes with partial stroke (typst#5688)

* Adding Croatian translations entries (typst#6413)

* Rewrite `outline.indent` example (typst#6383)

Co-authored-by: Laurenz <[email protected]>

* Use ICU data to check if accent is bottom (typst#6393)

Co-authored-by: Laurenz <[email protected]>

* Add docs for `std` module (typst#6407)

Co-authored-by: Laurenz <[email protected]>

* Improve equation reference example (typst#6481)

* Add page reference customization example (typst#6480)

Co-authored-by: Laurenz <[email protected]>

* Bump `krilla` to current Git version (typst#6488)

Co-authored-by: Laurenz <[email protected]>

* Check that git tree is clean after build (typst#6495)

* Also fix encoding of `<textarea>` (typst#6497)

* Minor fixes to doc comments (typst#6500)

* Fix typos in page-setup.md (typst#6499)

* Support `in` operator on strings and modules (typst#6498)

* Consistent sizing for `html.frame` (typst#6505)

* Allow deprecating symbol variants (typst#6441)

* Disallow empty labels and references (typst#5776) (typst#6332)

Co-authored-by: Laurenz <[email protected]>

* Fix nested HTML frames (typst#6509)

* Basic support for text decoration functions in HTML (typst#6510)

* Improve sentence in guide for LaTeX users (typst#6511)

* Sort line items by logical order when constructing frame (typst#5887)

Co-authored-by: Laurenz <[email protected]>

* Fix panic when sampling across two coincident gradient stops (typst#6166)

* Bump `typst-dev-assets` (typst#6514)

* Acknowledgements (typst#6528)

* Support HTML tests in test-helper extension (typst#6504)

* Fix typo in Advanced Styling docs tutorial (typst#6517)

* Fix typo in PDF standard CLI help (typst#6518)

* Fix typo in PDF standard CLI help part 2 (typst#6531)

* Fix minor typo in `array.product` docs (typst#6532)

* Fix typos in calc module docs (typst#6535)

* Use "subs" and "sups" font features for typographic scripts (typst#5777)

* Use punctuation math class for Arabic comma (typst#6537)

* Remove duplicate language computation (typst#6557)

* Fix typo in PackageStorage (typst#6556)

* Fix nightly warnings (typst#6558)

* Fix minor typo in function docs (typst#6542)

* Refer to json function instead of deprecated json.decode in groups docs (typst#6552)

* Rewrite foundations of native elements (typst#6547)

* Target-specific native show rules (typst#6569)

* Construct library via extension trait instead of default & inherent impl (typst#6576)

* Move `html` module to `typst-html` crate (typst#6577)

* Fix typo of Typst domain in quote docs (typst#6573)

* Anti-alias clip paths (typst#6570)

* Use "displayed" instead of "repeated" to avoid ambiguity in numbering docs (typst#6565)

* Ignore spans when checking for RawElem equality (typst#6560)

* Add `default` argument for `str.first` and `str.last` (typst#6554)

Co-authored-by: Laurenz <[email protected]>

* Add completions subcommand (typst#6568)

* Update Swedish translations based on defaults used for LaTeX and cleveref (typst#6519)

* Move math styling to codex and add `math.scr` (typst#6309)

* More consistent `Packed<T>` to `Content` conversion methods (typst#6579)

* Support images in HTML export (typst#6578)

* Fix tooltip for figure reference (typst#6580)

* Complete movement of HTML export code to `typst-html` (typst#6584)

* Handle `lower` and `upper` in HTML export (typst#6585)

* Deduplicate labels for code completion (typst#6516)

* Fix regression in reference autocomplete (typst#6586)

* Use "whitespace" instead of "space" to denote block-level equation in docs (typst#6591)

* Fix minor typo in text docs (typst#6589)

* Rephrase docs for truncation of float/decimal to integer (typst#6543)

* HTML frame improvements (typst#6605)

* Change `enum.item.number` to `Smart` instead of `Option` (typst#6609)

* Support setting fonts repeatedly with different `covers` (typst#6604)

* Support intra-doc links in HTML (typst#6602)

* Partially automate span assignment in native show rule (typst#6613)

* Bump `zip` dependency (typst#6615)

* Restore timing scopes for native show rules (typst#6616)

* Slightly improve selector docs (typst#6544)

* Add show rule for smallcaps in HTML (typst#6600)

* Mention Tinymist in README.md (typst#6601)

* Fix documentation oneliners (typst#6608)

* Add rust-analyzer to flake devShell (typst#6618)

* Add Lithuanian translations (typst#6587)

* Bump CI Rust to 1.88

* Bump MSRV to 1.88

* Migrate to 2024 edition

* Fix 2024 clippy warnings

* Yeet `if_chain` macro

* Reformat with 2024 edition

* Add support for PDF embedding (typst#6623)

Co-authored-by: Laurenz <[email protected]>

* Add `pdf` extension to image autocompletions (typst#6643)

* Fix bounding box computation for lines in curves (typst#6647)

Co-authored-by: Laurenz <[email protected]>

* Lint for iterations over hash types (typst#6652)

* Create constructor methods for manifest types (typst#6625)

* Remove unnecessary `comemo` dependency in `typst-syntax` (typst#6668)

* Remove duplicate center alignment style for equations (typst#6667)

* Fix incorrect `vline.x` docs (typst#6657)

* Miscellaneous minor docs improvements (typst#6651)

Co-authored-by: Laurenz <[email protected]>

* Allow explicit autocomplete immediately after comma and colon (typst#6550)

* Improve Guide for LaTeX users, Query Function, and replace invisible emojis (typst#6620)

Co-authored-by: PgBiel <[email protected]>
Co-authored-by: Laurenz <[email protected]>

* Hint that deprecated items will be removed in `0.15.0` (typst#6617)

* Specify the standard smart quotes for `Arabic` (typst#6626)

* Use `rustc-hash` for hash maps and sets (typst#6678)

* Faster constraint checking in comemo (bumps comemo & krilla) (typst#6683)

* Add `--target` argument for `typst query` (typst#6405)

Co-authored-by: Laurenz <[email protected]>

* Require parentheses in all function-like sub/superscripts (typst#6442)

Co-authored-by: Laurenz <[email protected]>

* Fix several wrong anchors in `$` docs link resolution  (typst#6684)

* Add `cargo testit` alias for running integration tests (typst#6682)

Co-authored-by: Laurenz <[email protected]>

* Update guides welcome text to refer to list instead of specific guides (typst#6685)

Co-authored-by: Laurenz <[email protected]>

* Prevent broken glyph assemblies when font data is incorrect (typst#6688)

* Allow custom element names in HTML tag syntax  (typst#6676)

Co-authored-by: Laurenz <[email protected]>

* Add interface to disable timer (typst#6695)

Co-authored-by: Derived Cat <[email protected]>

* Add support for drawing COLR glyphs in SVG export (typst#6693)

* Apply aspect ratio correction for linear gradients in PDF export (typst#6689)

* Wrap raw blocks in `<code>` tag additionally to `<pre>` tag (typst#6701)

* Support for raw syntax highlighting in HTML export (typst#6691)

* Ensure that whitespace is not collapsed in inline raw blocks (typst#6703)

* Show aliases of citation styles in docs and completions (typst#6696)

* Correct CeTZ spelling (typst#6706)

* Add `title` element (typst#5618)

Co-authored-by: Laurenz <[email protected]>

* Make HTML data structures cheaper to clone (typst#6708)

* Move `par`, `box`, and `block` to show rules in HTML export (typst#6709)

* Support smartquotes in HTML export (typst#6710)

Co-authored-by: Malo <[email protected]>

* Avoid dangling reference output for HTML tests (typst#6711)

* Support multiple fonts in math (typst#6365)

* Add link to position field of grid.hline and grid.vline docs (typst#6670)

* Rename `pdf.embed` to `pdf.attach` (typst#6705)

* Include numbering in PDF bookmark (typst#6622)

Co-authored-by: Laurenz <[email protected]>

* Document escaping semicolon, valid identifiers, and `state` tips (typst#6674)

Co-authored-by: Andrew Voynov <[email protected]>
Co-authored-by: Yaksher <[email protected]>
Co-authored-by: Laurenz <[email protected]>

* Ensure table headers trigger rowbreak (typst#6687)

* Fix phrasing of iff (if and only if) in docs (typst#6713)

* Remove redundant "This can be" from stroke docs of curve and polygon (typst#6715)

* Fix curve docs for fill (refer to curve instead of rectangle) (typst#6714)

* Add span to `html.frame` node (typst#6716)

* Fix return type of `missing_method` (typst#6718)

* Encoding fixes for HTML raw text elements (typst#6720)

* Update RelativeTo to include tiling in docs (typst#6730)

* Add missing "the" for cmyk function of color docs (typst#6731)

* Remove use of "last" and "end" for conic gradient circle docs (typst#6733)

* Fix broken links in docs (typst#6734)

* Simplify links in docs (typst#6732)

Co-authored-by: Laurenz <[email protected]>

* Bump hayro and krilla (typst#6741)

* Deduplicate fallback smart quotes (typst#6747)

* Move `is_inline` to `HtmlElem` (typst#6748)

* Move grid cell locator creation to GridLayouter (typst#6746)

* HTML whitespace protection (typst#6750)

* Improve code snippets in Table Guide (typst#6658)

* More accessible color scheme for raw blocks (typst#6754)

Co-authored-by: Laurenz <[email protected]>

* Use `stylistic-set: 1` in favor of `ss01` in docs and tests (typst#6766)

* Implement fraction styles: vertical, skewed, and horizontal. (typst#6672)

* Bump Rust to 1.89 in CI (typst#6775)

Co-authored-by: Drodt <[email protected]>
Co-authored-by: Daniel Drodt <[email protected]>

* Fix typo in doc on quotes parameter of smartquote (typst#6779)

* Fix logical order in bidirectional lines (typst#6796)

* Extract `trim_weak_spacing` function (typst#6797)

* Separate items for hyphens, fixing style of repeated hyphen (typst#6798)

* Fix Unicode mapping of hyphenation artifacts (typst#6799)

* Do not consider default ignorables when picking last resort font (typst#6805)

* Compute width of shaped text on-demand (typst#6806)

* Fix `sub` and `super` oneliners (typst#6791)

* Ensure that hyphenation is possible after a tag (typst#6807)

* Make links to `$grid` in `table` docs more specific (typst#6776)

Co-authored-by: PgBiel <[email protected]>

* Fix `repr` of `foo.with(..)` (typst#6773)

* Fix case in docs serialization (typst#6808)

* Add links and examples in the docs of `str` (typst#6751)

Co-authored-by: Laurenz <[email protected]>

* Hash page instead of frame for watch command (typst#6810)

* Update nix flake and use nixfmt (typst#6827)

* Update & fix tutorial part 3 & 4 example code (typst#6778)

* Improve docs on customizing `raw` (typst#6000)

Co-authored-by: Malo <[email protected]>
Co-authored-by: Laurenz <[email protected]>

* Better handle large numbers (u128/i128) in deserialization (typst#6836)

* Follow the comment on setting the `State`'s mask (typst#6642)

* Allow augment line at the beginning and end of a matrix (typst#5806)

Co-authored-by: Laurenz <[email protected]>

* Fix slicing last n elements using count (typst#6838)

* Fix auto hanging-indent for centered headings (typst#6839)

* Use rust-analyzer from fenix toolchain in flake (typst#6826)

* Type safety for logical indices in line layout (typst#6848)

* Load linked bitmap images in SVG images (typst#6794)

Co-authored-by: Laurenz <[email protected]>

* Fix CJ-Latin space at manual line breaks (typst#6700)

Co-authored-by: Laurenz Mädje <[email protected]>

* Allow multi-character symbols (typst#6489)

Co-authored-by: Max <[email protected]>
Co-authored-by: Laurenz <[email protected]>

* Keep end of line whitespace glyphs (typst#6866)

* Fix punctuation in HTML placeholder (typst#6854)

* Unify and document the behaviours of `{json,yaml,toml,cbor}.encode` (typst#6743)

Co-authored-by: Laurenz <[email protected]>

* Improve docs of various numbering parameters (typst#6757)

Co-authored-by: Laurenz <[email protected]>

* Document and test `Sides<T>` parameters (typst#6862)

Co-authored-by: Laurenz <[email protected]>

* Remove unused `Styles::set_family` (typst#6879)

* Make clear that `Content::query_first` is naive (typst#6880)

* Ensure correct tag nesting with grouping rules (typst#6881)

* Avoid breaking after an empty frame (typst#6335)

* Add test for default ignorables before a breakpoint (typst#6782)

* Fix typos (typst#6878)

* Improve the docs on function params of `array.{sorted,dedup}` (typst#6756)

* Add a link from `math.vec` to `math.{arrow,bold}` in docs (typst#6867)

* Add a disclaimer about embedding PDFs (typst#6888)

Co-authored-by: Laurenz <[email protected]>

* Improve examples in the docs for under/over functions (typst#6889)

* Improve docs of `Celled<T>` params of `table` and `grid` (typst#6764)

Co-authored-by: Laurenz <[email protected]>

* Fix off by one in tag expansion (typst#6900)

* More useful `Debug` impls for `Tag` and `Location` (typst#6901)

* Fix potential crash in `Debug` impl of `Property` (typst#6902)

* Fix `Debug` impl for end tags (typst#6906)

* Make `select_where!` usable outside of typst-library (typst#6910)

* Fix footnote links in presence of styling (typst#6912)

* Consistently ignore styles for tags (typst#6911)

* Expand tags even a bit more around groupings (typst#6909)

* Don't warn for zero-sized horizontal spacing in HTML export

* Use `singleton!` for `HElem::hole`

* Add way to attach role to closest element in HTML export

* Add logical parent mechanism to HTML export

* Generalize mechanism for root styles to HTML export

* Support footnotes in HTML export

* Add `default` argument to `array.join` (typst#6932)

* Replace the non-existent `$math.arrow` with `$math.accent` in the docs for vector (typst#6918)

* Initial Hayagriva bump (typst#6920)

Co-authored-by: Laurenz <[email protected]>

* Use different colors for object keys and string-based values in JSON listings (typst#6873)

* Support for outline in HTML (typst#6606)

* Use Title Case for Doc Pages (typst#6936)

* Improve the docs for dictionary (typst#6899)

* Add an illustration for `par.{leading,spacing}` in docs (typst#6915)

Co-authored-by: Andrew Voynov <[email protected]>
Co-authored-by: Laurenz <[email protected]>

* Initial plan

---------

Co-authored-by: Sam Ireson <[email protected]>
Co-authored-by: PgBiel <[email protected]>
Co-authored-by: Ian Wrzesinski <[email protected]>
Co-authored-by: cAttte <[email protected]>
Co-authored-by: Andrew Voynov <[email protected]>
Co-authored-by: Laurenz <[email protected]>
Co-authored-by: Tobias Schmitz <[email protected]>
Co-authored-by: Max <[email protected]>
Co-authored-by: 3w36zj6 <[email protected]>
Co-authored-by: Malo <[email protected]>
Co-authored-by: T0mstone <[email protected]>
Co-authored-by: Lachlan Kermode <[email protected]>
Co-authored-by: Y.D.X. <[email protected]>
Co-authored-by: Ilia <[email protected]>
Co-authored-by: Noam Zaks <[email protected]>
Co-authored-by: Wannes Malfait <[email protected]>
Co-authored-by: Ivica Nakić <[email protected]>
Co-authored-by: +merlan #flirora <[email protected]>
Co-authored-by: Connor K <[email protected]>
Co-authored-by: Said A. <[email protected]>
Co-authored-by: Florian Bohlken <[email protected]>
Co-authored-by: Robin <[email protected]>
Co-authored-by: Adrián Delgado <[email protected]>
Co-authored-by: frozolotl <[email protected]>
Co-authored-by: Jassiel Ovando <[email protected]>
Co-authored-by: Patrick Massot <[email protected]>
Co-authored-by: Erik <[email protected]>
Co-authored-by: pog102 <[email protected]>
Co-authored-by: Laurenz Stampfl <[email protected]>
Co-authored-by: Niklas Eicker <[email protected]>
Co-authored-by: Marcono1234 <[email protected]>
Co-authored-by: Igor Khanin <[email protected]>
Co-authored-by: hpcfzl <[email protected]>
Co-authored-by: zefr0x <[email protected]>
Co-authored-by: Abdul-Rahman Sibahi <[email protected]>
Co-authored-by: 枚鴉 <[email protected]>
Co-authored-by: Myriad-Dreamin <[email protected]>
Co-authored-by: Derived Cat <[email protected]>
Co-authored-by: Sebastian Eberle <[email protected]>
Co-authored-by: Johann Birnick <[email protected]>
Co-authored-by: Yaksher <[email protected]>
Co-authored-by: Tau <[email protected]>
Co-authored-by: Martin Haug <[email protected]>
Co-authored-by: Théophile Cailliau <[email protected]>
Co-authored-by: Drodt <[email protected]>
Co-authored-by: Daniel Drodt <[email protected]>
Co-authored-by: ultimatile <[email protected]>
Co-authored-by: Poh <[email protected]>
Co-authored-by: Clemens Koza <[email protected]>
Co-authored-by: Siddhant Agarwal <[email protected]>
Co-authored-by: Philipp Niedermayer <[email protected]>
Co-authored-by: Toon Verstraelen <[email protected]>
Co-authored-by: Eric Biedert <[email protected]>
Co-authored-by: Jan Romann <[email protected]>
Co-authored-by: copilot-swe-agent[bot] <[email protected]>
Myriad-Dreamin pushed a commit to Myriad-Dreamin/tinymist that referenced this pull request Oct 21, 2025
+ several fixes to `nightly.yml`
+ update `comemo` for typst/typst#6683
Myriad-Dreamin pushed a commit to Myriad-Dreamin/tinymist that referenced this pull request Oct 21, 2025
+ several fixes to `nightly.yml`
+ update `comemo` for typst/typst#6683
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Quadratic runtime of cache validation

2 participants