Conversation
f59a745 to
17cfb98
Compare
isuffix
left a comment
There was a problem hiding this comment.
Overall this is quite nice! The implementation seems correct, and I can confirm the performance benefit when parsing for my local fonts 0.20s -> 0.10s, google-fonts 0.23s -> 0.16s and nerd-fonts 0.52s -> 0.21s.
I did add quite a few simplification and code style comments below that you should address. Feel free to let me know if you disagree with any of the smaller changes, our goal is just to ensure the code is idiomatic and maintainable :)
Stats
I also found some statistics to try to understand the performance effect myself. For the 17 embedded font faces (from the 4 embedded fonts), we have:
- Unique codepoints per face:
average 3240.8,min 1696(Libertinus),max 4989(NCMM) - The initial coverage vector length after 1 subtable:
average 308.5,min 148,max 508- Note that the number of codepoint ranges is the length divided by 2
- The coverage vector length increases exactly once after the initial subtable for each face:
- NCMM (3 font faces) increases the length by 124, 126, and 126
- The remaining 14 font faces increase the length by either 2, 4, or 6
- Total subtables were between 4 and 6, always with at least two pairs of duplicated mappings
So the coverage vector ends up usually being around 10x smaller than the total number of codepoints, and repeating the coverage vector building/merging for 3-5 subtables is cheaper than getting all of the codepoints first and sorting them before merging.
Iterating by Ranges
This isn't something to change with this PR, but we should really be iterating over codepoint ranges instead of iterating individual codepoints.
Most cmap subtable formats store ranges already. Right now we're effectively just asking ttf-parser to expand those ranges into codepoints before we then manually contract them. And a malicious font with a format 13 subtable could easily include every valid and invalid(!) codepoint to pessimize the coverage builder. I expect this is the likely cause of the 50s load time in #8561, since I don't get anywhere close to that even with all of google-fonts and nerd-fonts (~4000 ttf files, 0.99s -> 0.47s).
ttf-parser doesn't expose the raw codepoint ranges itself, and given that ttf-parser is now in maintenance mode, that's unlikely to change. It does look like fontations exposes cmap subtable internals more directly. So iterating over ranges is likely blocked on #8172, which is going to need a bit of work to properly revive.
| /// Returns an encoding of the set of codepoints covered by either `self` or `other`. | ||
| pub fn union(&self, other: &Coverage) -> Self { |
There was a problem hiding this comment.
Three suggestions for this signature:
- I think we should remove
pubsinceCoverageisn't really meant to be a library type- If we really want a library type, we should probably build/expose an ICU
CodePointInversionListinstead, although the builder doesn't have an optimized interface for our use-case :(
- If we really want a library type, we should probably build/expose an ICU
- After removing
pub, we can have this takeselfandotherby value since our only caller doesn't actually need to reuse either coverage vector- Although see below for more thoughts on optimizing
CoverageBuilder::new()
- Although see below for more thoughts on optimizing
- I would prefer
mergeoverunionsince it's a verb and more directly describes the function's internals, but I'm fine withunionas long as the doc-comment is updated to mention that it merges the two vectors
There was a problem hiding this comment.
- Done
- I don't think so, there is not actual benefit from moving ownership of
selfandother; When there is no actual need for that you get needless_pass_by_value from Clippy. Doubly so since it is no longer public, so the signature can be later changed at will (not that a piece of API in the compiler being public ever stopped it from being refactored). unionis IMO the correct method name.Coverageis a set (and the fact that it is implemented with a Vector doesn't remove from that), and the operation of merging two sets is always called union...
| fn new() -> Self { | ||
| Self { runs: vec![], next: 0 } | ||
| } |
There was a problem hiding this comment.
We should probably optimize building this instead of always creating a new vector with an empty capacity, but I'm not sure of the best approach.
One way is to replace new by with_capacity(capacity: usize) -> Self and call Vec::with_capacity(capacity). Then subtable_coverage could be initialized as CoverageBuilder::with_capacity(coverage.0.len()). This is the easier option, but it does have to call into the allocator to construct and destruct the vector on every loop.
The other way is to add a reset(&mut self) method that would set self.next = 0 and call self.runs.clear(). Then we could move subtable_coverage out of the subtable loop, call subtable_coverage.reset() at the loop start, and have merge take &mut subtable_coverage instead of trying to .build() it each time. But I feel like this makes the code kind of ugly, so it may be worth the first approach to keep the code simple.
LMK what your preference is or if you don't think it's worth changing.
There was a problem hiding this comment.
I would not worry too much about calling into the allocator. It's usually cheaper than it feels like.
There was a problem hiding this comment.
It is probably not worth the hassle. The main difference is from doing things O(|ranges|) times rather than O(|codepoints|). Further tweaking things in the prior category is really in the micro-optimization territory.
That said, the pre-compiled CLI is built for the musl target which has a notoriously bad memory allocator. Though I think still not worth it.
17cfb98 to
a429d33
Compare
|
@isuffix Many thanks for the very educational review. I've implemented most of your suggestions. |
isuffix
left a comment
There was a problem hiding this comment.
Only some smaller style notes now. Otherwise, I'm happy with the PR :)
|
@isuffix Hi, thanks again for the review. To be quite honest, the interesting part of this PR is now over, I don't have much vested interest in this being merged or not, and I've already blown through the amount of my limited FOSS time that I was willing to spend on it. I don't want to spend another back-and-forth cycle. The formatting was all done by Feel free to make any changes you'd like to this patch yourself, or drop it. I'm OK either way. Thanks! |
|
That's alright! Thanks for responding as much as you have. I've pushed a commit with my recently reviewed changes and I'll take on getting this merged. I really appreciate you letting us know that we can move this forward. That's sometimes hard to accept/admit, so thank you. Also note that some of the formatting problems are real limitations of |
| /// Add a single codepoint to the set being built. Codepoints must be added | ||
| /// in a strictly increasing order. | ||
| fn add_codepoint(&mut self, codepoint: u32) { | ||
| debug_assert!(codepoint >= self.next, "Codepoints provided in wrong order"); |
There was a problem hiding this comment.
can this panic for malformed fonts? If yes, then it should not be an assertion as assertions should only trigger for bugs in Typst.
A large chunk of the cold start time of the
typstCLI is the initialization of the font book by scanning system fonts. Profiling has shown that the run time of this phase is entirely dominated by calculating the font coverage maps, that indicate to the compiler which fonts have a glyph mapped for a specific Unicode code point.Currently this is done by collecting the individual codepoints covered by every scanned font face into a large vector, and then compressing it into a compact range-based representation. To do so, the vector is de-duplicated and sorted, which is required because it is assembled by reading each CMAP sub-table in turn, and very often more than one sub-table can include a glyph for the same codepoint. These vectors include tens, or even hundreds, of thousands of entries; both the incremental allocation of the vector (causing multiple re-allocations and copies) and the sorting have large overhead.
We can avoid that through the observation that the codepoints in each sub-table already come out of
ttf-parserunique and sorted (though see caveat). With this we can directly collect the codepoints covered by each sub-table into the compact representation without needing to keep a vector of all codepoints in memory, and form the final coverage map by taking the union of all the sub-table coverage maps. The union is calculated with a typical linear sorted array merge algorithm.Benchmarks
Measurements taken with
hyperfine(excluding warmup) with thedev-fastbuild configuration on a circa-2019 Intel-based Linux laptop with a relatively typical selection of 289 font families installed.Comparing time to run
typst fonts:Comparing the time to cold compile a small "Hello World" document to PDF:
We can see that on average this PR shaves ~140ms from the CLI run time, and is likely to be far more significant on pathological cases such as #8561.
Caveat
As noted above, this relies on the observation that "the codepoints in each sub-table already come out of
ttf-parserunique and sorted". This is actually not a structural property of all CMAP sub-table formats, e.g. formats 4 and 12 could be stored in an unsorted order or have duplicates. However this appears to be at least an implicit requirement of the TrueType/OpenType specifications, as the CMAP formats are expected to be laid out in a way that allows font engines to binary search for the corresponding glyph for a codepoint. It is possible that there are broken fonts out there that don't maintain this expectation, but I didn't find any among the fonts available to me.