blitz-dom: removing or moving a node costs O(siblings), so n of them cost n²

From the repository

This page is repros/blitz-dom-child-list-quadratic/README.md, included when the site is built. Edit it there.

What niso does

Works around it where it can. crates/niso-core/src/tree.rs takes a fragment’s children out of it in one step before inserting them (take_children), and replace-all (textContent, replaceChildren, innerHTML) hands each child to remove_node as the only one left in its parent (detach_children). crates/niso-core/src/loading.rs does the same for the fragment the HTML parser fills. A single removeChild, or an insertBefore that moves a node out of a wide parent, still costs O(siblings) in blitz: removing 200k children one at a time from the end takes about 9.4 s.

Expected vs actual

DocumentMutator::remove_node, remove_and_drop_node_with and add_children_to_parent (packages/blitz-dom/src/mutator.rs:618-619,653-654,896-897) find the node with index_of_child (a linear position scan) and then take it out with children.retain(|id| *id != node_id), which visits and shifts every sibling even once the node is found. Removing or moving each of a parent’s n children is O(n²). The DOM does each in O(1) (browsers keep sibling links).

remove_node, each child from the end: 20k children 179 ms, 80k 2302 ms; expected under 8x (linear is 4x), actual 12.8x
append_children, each child to another parent: 20k children 603 ms, 80k 5688 ms; expected under 8x (linear is 4x), actual 9.4x

Run

CARGO_TARGET_DIR=~/.capy/work/repro-target cargo run --release

Upstream main

Same code. Blitz main was at b6ace6a0c33e17b654e8e6d0b14a7e04e83756fe when checked (2026-11-09): the same index_of_child and retain pairs are at mutator.rs:618-619,653-654,896-897.

Existing issue or PR

DioxusLabs/blitz#1232 (open) caches each node’s index in its parent, which would make index_of_child O(1) but leaves the retain; #1308 (closed) did the same. No issue covers the removal itself.

Issue text

Title: Removing or moving a node is O(siblings): retain after index_of_child

Body:

remove_node, remove_and_drop_node_with and add_children_to_parent detach a node from its parent with index_of_child followed by children.retain(|id| *id != node_id). retain visits every sibling, so removing or moving all n children of a parent one at a time is O(n²): 80k children take 13x as long as 20k to remove from the end, where linear would be 4x. Since the index is already known, children.remove(index) avoids the second pass, and with a cached index (#1232) removing from the end becomes O(1).

use std::time::Instant;

use blitz_dom::{BaseDocument, DocumentConfig, LocalName, NodeId, QualName, ns};
use blitz_html::HtmlDocument;

fn parent_with_children(doc: &mut BaseDocument, n: usize) -> (NodeId, Vec<NodeId>) {
    let mut m = doc.mutate();
    let parent = m.create_element(QualName::new(None, ns!(html), LocalName::from("div")), vec![]);
    let children: Vec<NodeId> = (0..n).map(|_| m.create_element(QualName::new(None, ns!(html), LocalName::from("p")), vec![])).collect();
    m.append_children(parent, &children);
    (parent, children)
}

/// Milliseconds to remove each of n children from the end, and to move each
/// of n children to another parent one at a time.
fn time(n: usize) -> [f64; 2] {
    let mut doc = HtmlDocument::from_html("<!DOCTYPE html><body></body>", DocumentConfig::default());
    let (_, children) = parent_with_children(&mut doc, n);
    let t = Instant::now();
    let mut m = doc.mutate();
    for &c in children.iter().rev() {
        m.remove_node(c);
    }
    drop(m);
    let remove = t.elapsed().as_secs_f64() * 1000.0;

    let (_, children) = parent_with_children(&mut doc, n);
    let (to, _) = parent_with_children(&mut doc, 0);
    let t = Instant::now();
    let mut m = doc.mutate();
    for &c in &children {
        m.append_children(to, &[c]);
    }
    drop(m);
    [remove, t.elapsed().as_secs_f64() * 1000.0]
}

fn main() {
    let (small, large) = (time(20_000), time(80_000));
    let mut failed = false;
    for (i, what) in ["remove_node, each child from the end", "append_children, each child to another parent"].into_iter().enumerate() {
        let ratio = large[i] / small[i];
        println!("{what}: 20k children {:.0} ms, 80k {:.0} ms; expected under 8x (linear is 4x), actual {ratio:.1}x", small[i], large[i]);
        failed |= ratio >= 8.0;
    }
    if failed {
        std::process::exit(1);
    }
}