Skip to content

Quadratic runtime of cache validation #5220

@jbirnick

Description

@jbirnick

Right now, to get the value of a counter in the current context, Typst queries the previous counters and computes the value accordingly. Unfortunately, this has a quadratic runtime in the number of counters. When you furthermore put the step and get methods of the counter inside your own created functions, this quadratic runtime is clearly noticeable.

For example, if you write a math book with 1000 pages and 1-3 theorems per page, then having those theorems numbered vs not numbered makes a huge difference in compile time (many seconds on my laptop).

I would be very happy if counter evaluation could be somehow sequentialized, so that it has a linear runtime.

Having a parallelized layout engine is great to get a 2-3x constant speedup, but it doesn't help if it increases the asymptotic runtime of e.g. counter evaluation from linear to quadratic, which has a much bigger impact in the end.

I think there even must be a way to keep the parallelized layout engine but still make counter evaluation have linear runtime, through some sort of cache/table-lookup.

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't workingincrementalAbout Typst's incremental compilation.introspectionRelated to the introspection categoryperfRelated to performance and optimization.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions