Tree builder and RcDom take time growing with the square of the input on four simple inputs

Open
  • Is something wrong?
#812 1 comment 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 1 day

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
45/100
Issue type
Bug
Clarity
Mostly clear
Activity status
Active
Tech stack
rust
Domain
performance

Research direction

Start by running the provided cargo run --release reproduction, then inspect tree_builder/rules.rs and RcDom's add_attrs_if_missing implementation. Compare timings for each input as its size doubles, and investigate the reported formatting, nesting, and table-text cases. Done means the identified parsing workloads no longer show roughly quadratic time growth, with the reproduction confirming the improvement.

Written by the indexing model from the issue text.

Description

Hi,

These four inputs make parse_document with markup5ever_rcdom take time that roughly quadruples each time the input doubles. None of them crashes. A program parsing untrusted HTML can limit the input size, so I'm filing this as a performance report.

Measured with html5ever 0.39.0 and markup5ever_rcdom 0.39.0+unofficial (the newest pair that build together; html5ever 0.40.1 needs a newer rcdom), release build, Apple M-series:

Input Size Time
1,000 <body> start tags, each with 64 new attribute names 489 KB 1.35 s
2,000 of them 1.0 MB 5.05 s
<p><b x{i}>t</p> repeated 4,000 times (i counts up) 65 KB 1.02 s
repeated 8,000 times 131 KB 4.12 s
40,000 nested <div> 195 KB 1.69 s
80,000 nested <div> 390 KB 9.00 s
<table>x</table> repeated 40,000 times 625 KB 0.44 s
repeated 80,000 times 1.25 MB 1.73 s

Where the time seems to go, from reading the code (I have not profiled every case):

  1. Repeated <body> (and <html>) tags. The tree builder calls TreeSink::add_attrs_if_missing for each repeated start tag (tree_builder/rules.rs). RcDom's implementation builds a HashSet of every attribute the element already has, on every call, so each new tag pays again for all the attributes the earlier ones added.
  2. Misnested formatting tags. Each <p> closes over an open <b>, so the <b> is reconstructed in the next paragraph. With distinct attributes, none of the entries in the list of active formatting elements match, and the list and the reconstruction work grow with the number already seen.
  3. Deep nesting. Each new element appears to cost time in the depth of the stack of open elements.
  4. Text directly inside tables. The text is foster-parented, and RcDom appears to scan the parent's children to place it, so each new piece costs time in the number already placed.

The attribute-name check in the tokenizer is already covered by #796 and #804, so it isn't repeated here.

Reproduction (cargo run --release):

[dependencies]
html5ever = "0.39"
markup5ever_rcdom = "=0.39.0+unofficial"

use std::time::Instant;

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

fn time(label: &str, html: String) {
    let start = Instant::now();
    let _dom = parse_document(RcDom::default(), ParseOpts::default())
        .one(html.as_str());
    println!("{label}: {:.2?} ({} KB)", start.elapsed(), html.len() / 1024);
}

fn main() {
    for n in [500, 1_000, 2_000] {
        let html = (0..n)
            .map(|i| {
                let attrs: String =
                    (0..64).map(|j| format!(" b{i}_{j}")).collect();
                format!("<body{attrs}>")
            })
            .collect();
        time(&format!("{n} <body> tags x 64 new attributes"), html);
    }
    for n in [2_000, 4_000, 8_000] {
        let html = (0..n).map(|i| format!("<p><b x{i}>t</p>")).collect();
        time(&format!("{n} x <p><b x{{i}}>t</p>"), html);
    }
    for n in [20_000, 40_000, 80_000] {
        time(&format!("{n} nested <div>"), "<div>".repeat(n));
    }
    for n in [20_000, 40_000, 80_000] {
        time(&format!("{n} x <table>x</table>"), "<table>x</table>".repeat(n));
    }
}

Happy to test patches.

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.