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

Aperta
  • Qualcosa non va?
#36 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
3/5
Tempo stimato
Mezza giornata
Idoneità per principianti
67/100
Tipo di issue
Bug
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
rust
Ambito
performance

Direzione di ricerca

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.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

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.

Lingua principale
Rust
Stelle
61
Fork
16
Nessuna PR unita negli ultimi 30g

Preparare l'ambiente

Questo progetto non fornisce container di sviluppo, Dockerfile né guida per i contributori, quindi l'ambiente è a tuo carico: parti dal suo README e consulta la nostra guida al primo contributo per i passaggi generali.

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di typst/subsetter

Tutte le issue di typst/subsetter

Issue simili

Altre issue su Rust

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.