Tree builder: leftover active-formatting markers make each formatting end tag O(list length)

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

Maintainers usually reply within 1 day

Nobody has claimed this yet.

Assessment

Difficulty
3/5
Estimated time
1-2 days
Newbie friendliness
62/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
rust
Domain
backend, performance

Research direction

Start in tree_builder/mod.rs at position_in_active_formatting and check how the active formatting list stores element entries and markers. Reproduce the slowdown with the Rust example in the issue, then inspect existing tree builder tests for adoption agency cases. Done when formatting end tags avoid scanning the full marker-filled list and the regression is covered by a test.

Written by the indexing model from the issue text.

Description

Summary

Markers left in the list of active formatting elements are never removed when the element that pushed them is closed implicitly, and position_in_active_formatting scans the whole list from the front. Together they make every formatting end tag cost O(list length), so a document that first leaves many markers behind and then closes many formatting elements parses in quadratic time. About 1 MB of input takes over a second, growing roughly 4× per doubling.

Reproduction

html5ever = "=0.39.0", markup5ever_rcdom = "=0.39.0", cargo run --release:

use html5ever::tendril::TendrilSink;
use html5ever::{parse_document, ParseOpts};
use markup5ever_rcdom::RcDom;
use std::time::Instant;

fn parse(html: &str) {
    let _ = parse_document(RcDom::default(), ParseOpts::default())
        .from_utf8()
        .read_from(&mut html.as_bytes())
        .unwrap();
}

fn main() {
    let shapes: [(&str, fn(usize) -> String); 3] = [
        ("<template><object></template> then </b>", |n| {
            format!("{}{}", "<template><object></template>".repeat(n), "<b></b>".repeat(4 * n))
        }),
        ("<div><object></div> then </b>", |n| {
            format!("{}{}", "<div><object></div>".repeat(n), "<b></b>".repeat(4 * n))
        }),
        ("control: <template></template> then </b>", |n| {
            format!("{}{}", "<template></template>".repeat(n), "<b></b>".repeat(4 * n))
        }),
    ];
    for (name, mk) in shapes {
        for n in [5_000usize, 10_000, 20_000] {
            let html = mk(n);
            let t = Instant::now();
            parse(&html);
            println!("{name:<44} n={n:>6}  bytes={:>8}  {:>10.3?}", html.len(), t.elapsed());
        }
    }
}

Output (release build, x86_64 Windows):

<template><object></template> then </b>      n=  5000  bytes=  285000    97.174ms
<template><object></template> then </b>      n= 10000  bytes=  570000   278.783ms
<template><object></template> then </b>      n= 20000  bytes= 1140000      1.384s
<div><object></div> then </b>                n=  5000  bytes=  235000   130.773ms
<div><object></div> then </b>                n= 10000  bytes=  470000   362.008ms
<div><object></div> then </b>                n= 20000  bytes=  940000      1.509s
control: <template></template> then </b>     n=  5000  bytes=  245000    21.775ms
control: <template></template> then </b>     n= 10000  bytes=  490000    44.684ms
control: <template></template> then </b>     n= 20000  bytes=  980000    87.848ms

Where the time goes

  1. <object> inserts a marker (the spec treats applet and marquee the same way). When the element is popped implicitly, for example by </div> or </template>, nothing clears that marker. </template> clears only up to the last marker. As far as I can tell this follows the spec, so each repetition above leaves one more marker in the list.
  2. Each </b> then runs the adoption agency algorithm. Step 1 checks whether the current node is in the list of active formatting elements via position_in_active_formatting (tree_builder/mod.rs, around line 646), which is self.active_formatting.borrow().iter().position(...). That is a forward scan over the entire list, markers included, even though the entry it looks for, when present, was usually pushed last.

The lookup in step 5 (active_formatting_end_to_marker()) stops at the last marker, so it stays cheap. The quadratic term is the full forward scan.

Suggestion

  • Search from the end (rposition) in position_in_active_formatting. The common case of a just-pushed formatting element then becomes O(1).
  • To bound the case where the element is not in the list at all, mark membership on the entry, for example with a flag or set kept in sync with active_formatting, instead of scanning.

Related observation for embedders: TreeBuilder::trace_handles reports only FormatEntry::Element handles, so a sink cannot observe how many markers the list holds. We ran into this while trying to bound parse cost from outside the parser for an HTML sanitizer (via ammonia). See also #788 and #800 (open-element stack scans), #796 (tokenizer duplicate-attribute check) and #289 (linear-time goal).

Dominant language
Rust
Stars
2.7k
Forks
303
Avg merge
17h 29m
Merged PRs (30d)
4

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 servo/html5ever

All issues in servo/html5ever

Similar issues

More Rust issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.