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

Đang mở
  • Có gì không ổn?
#36 0 bình luận 0 reaction 0 người được giao Xem trên GitHub

Chưa có ai nhận issue này.

Đánh giá

Độ khó
3/5
Thời gian dự kiến
Nửa ngày
Mức phù hợp với người mới
67/100
Loại issue
Lỗi
Độ rõ ràng
Đặc tả rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
rust
Lĩnh vực
performance

Hướng nghiên cứu

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.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

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.

Ngôn ngữ chính
Rust
Star
61
Fork
16
Không có pull request nào được merge trong 30 ngày

Chuẩn bị môi trường

Dự án này không cung cấp dev container, Dockerfile hay hướng dẫn đóng góp, nên bạn cần tự thiết lập môi trường: hãy bắt đầu từ README và xem hướng dẫn đóng góp lần đầu của chúng tôi để biết các bước chung.

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của typst/subsetter

Tất cả issue của typst/subsetter

Issue tương tự

Thêm issue về Rust

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.