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

Abierto
  • ¿Algo no está bien?
#36 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
3/5
Tiempo estimado
Medio día
Aptitud para principiantes
67/100
Tipo de issue
Error
Claridad
Bien especificado
Estado de actividad
Activo
Stack tecnológico
rust
Área
performance

Línea de trabajo

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.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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.

Lenguaje dominante
Rust
Estrellas
61
Forks
16
Sin PR fusionados en 30 d

Preparar el entorno

Este proyecto no incluye contenedor de desarrollo, Dockerfile ni guía de contribución, así que la configuración corre por tu cuenta: empieza por su README y consulta nuestra guía para la primera contribución para los pasos generales.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de typst/subsetter

Todos los issues de typst/subsetter

Issues similares

Más issues de Rust

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.