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

オープン
  • 何か問題がありますか？
#36 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

まだ誰も着手していません。

評価

難易度
3/5
見積もり時間
半日
初心者へのやさしさ
67/100
issue の種類
バグ
明瞭さ
明確に書かれている
活発さ
活発
技術スタック
rust
領域
performance

調査の方向性

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.

索引モデルが issue の本文から書いたものです。

説明

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.

主要言語
Rust
スター
61
フォーク
16
30日以内にマージされた PR はありません

環境構築

このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

typst/subsetter のほかの issue

typst/subsetter の issue をすべて見る

似ている issue

Rust の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。