Glyph closure takes time quadratic in a composite's repeated components

Open
  • Is something wrong?
#36 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
3/5
Estimated time
Half a day
Newbie friendliness
67/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
rust
Domain
performance

Research direction

Start by reading glyf::closure, identified in the issue as the source of the repeated component reads. Use the supplied Rust reproducer with cargo run --release to confirm the growth as n increases, then verify that closure preserves remapping and errors while avoiding repeated reads. Done when the reported quadratic slowdown is removed.

Written by the indexing model from the issue text.

Description

subset takes time quadratic in the size of a composite glyph whose components repeat, in any build. Measured with cargo run --release (the program below):

  5000 uses,   60152 bytes: Ok(60144) in 53.6ms
 10000 uses,  120152 bytes: Ok(120144) in 210.5ms
 20000 uses,  240152 bytes: Ok(240152) in 836.6ms
 40000 uses,  480152 bytes: Ok(480152) in 3.44s

glyf::closure pushes a component every time it reads it while the component is not remapped yet, and remaps a glyph only when it pops it. So a composite that uses one glyph n times pushes it n times, and the closure reads that glyph's components again at each of the n pops: n × (its components) readings. The second and later readings find every component remapped already and push nothing. This happens with 0.2.6 and with main (b0adcc1).

To reproduce with subsetter 0.2.6 (default-features = false). The font is built for this report: three tables, glyf, head and loca, where .notdef uses glyph 1 n times and glyph 1 uses glyph 2 n times.

use std::time::Instant;

/// A TrueType font of three tables, built for this report: `.notdef` is a composite that
/// uses glyph 1 `n` times, glyph 1 one that uses glyph 2 `n` times, and glyph 2 is empty.
fn font(n: usize) -> Vec<u8> {
    let composite = |component: u16| {
        let mut entry = vec![0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0]; // numberOfContours -1, bbox
        for i in 0..n {
            let flags: u16 = if i + 1 == n { 0x0002 } else { 0x0022 }; // MORE_COMPONENTS
            entry.extend(flags.to_be_bytes());
            entry.extend(component.to_be_bytes());
            entry.extend([0, 0]); // byte arguments
        }
        entry
    };
    let glyphs = [composite(1), composite(2), Vec::new()];
    let mut glyf = Vec::new();
    let mut loca = Vec::new();
    for glyph in &glyphs {
        loca.extend((glyf.len() as u32).to_be_bytes());
        glyf.extend(glyph);
    }
    loca.extend((glyf.len() as u32).to_be_bytes());
    let mut head = vec![0; 54];
    head[51] = 1; // indexToLocFormat: long
    let tables: [(&[u8; 4], Vec<u8>); 3] = [(b"glyf", glyf), (b"head", head), (b"loca", loca)];
    let mut font = vec![0, 1, 0, 0, 0, 3, 0, 32, 0, 1, 0, 16];
    let mut offset = 12 + 16 * tables.len();
    for (tag, table) in &tables {
        font.extend(*tag);
        font.extend([0; 4]); // checksum, not checked
        font.extend((offset as u32).to_be_bytes());
        font.extend((table.len() as u32).to_be_bytes());
        offset += table.len().next_multiple_of(4);
    }
    for (_, table) in &tables {
        font.extend(table);
        font.resize(font.len().next_multiple_of(4), 0);
    }
    font
}

fn main() {
    for n in [5_000, 10_000, 20_000, 40_000] {
        let data = font(n);
        let remapper = subsetter::GlyphRemapper::new();
        let start = Instant::now();
        let result = subsetter::subset(&data, 0, &remapper).map(|font| font.len());
        println!("{n:>6} uses, {:>7} bytes: {result:?} in {:?}", data.len(), start.elapsed());
    }
}

It was found by the independent review of a officewright PR that mirrors the closure to check glyphs before subsetting.

A possible fix: skip a popped glyph whose components were read already (a set of glyphs read); since every component it has was remapped at its first reading, skipping gives the same remapping and the same errors. Or push a component only once, when it is first seen.

Dominant language
Rust
Stars
61
Forks
16
No merged PRs in 30d

Getting set up

This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from typst/subsetter

All issues in typst/subsetter

Similar issues

More Rust issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.