Skip to content

Fix O(depth²) namespace prefix resolution in NamespaceResolver#981

Open
AnayGarodia wants to merge 1 commit into
tafia:masterfrom
AnayGarodia:fix/980-resolve-prefix-linear-scan
Open

Fix O(depth²) namespace prefix resolution in NamespaceResolver#981
AnayGarodia wants to merge 1 commit into
tafia:masterfrom
AnayGarodia:fix/980-resolve-prefix-linear-scan

Conversation

@AnayGarodia

Copy link
Copy Markdown

Fixes #980.

Problem

NamespaceResolver::resolve_prefix did a reverse linear scan of the entire
in-scope bindings stack on every call:

let mut iter = self.bindings.iter().rev();
...
(None, true) => match iter.find(|n| n.prefix_len == 0) { ... }
...
(Some(p), _) => match iter.find(|n| n.prefix(&self.buffer) == prefix) { ... }

bindings grows by one entry per xmlns[:prefix] declaration on every
currently open ancestor element, so its length tracks nesting depth. A
lookup that misses -- the common case for an unprefixed name with no
default namespace, or a genuinely undeclared prefix -- costs O(depth); doing
that once per event (NsReader::read_resolved_event* resolves every
Start/Empty/End) down a depth-D document costs O(D²). A ~1.3 MB
crafted document with one xmlns:* declaration per level (no huge tag, no
huge attribute count -- just ordinary depth) drives multi-second single-core
CPU stalls.

This is the same shape of problem as #969/#971 (check_for_duplicates
scanning every previously-seen attribute name), just over a different axis
(nesting depth vs. attribute count on one tag), as the issue calls out.

Root cause

NamespaceBindings are stored as a flat Vec acting as a stack: push
(via add) always appends, and pop (via set_level) always truncates
from the back when an element closes. There was no index from prefix to
position, so every lookup had no choice but to scan.

Fix

Small stacks (up to SMALL_BINDING_COUNT = 32 bindings) keep the direct
linear scan -- for a handful of in-scope bindings it's faster than hashing
and needs no allocation, which covers the overwhelming majority of real
documents. Once the stack grows past that threshold, resolve_prefix is
backed by a HashMap<Vec<u8>, Vec<usize>> index (prefix bytes, or an empty
key for the default namespace, to ascending stack positions), so a lookup
is O(1) average instead of O(depth).

Unlike the #971 fix (where the per-tag attribute list is thrown away and
rebuilt from scratch on every start tag), the namespace binding stack
persists and shrinks across the whole document, so the index needs
pop-side maintenance too, as the issue's "suggested direction" section
called out:

  • add() (called by both the public API and push()) records each new
    binding into the index once it exists, seeding it from scratch (scanning
    every binding currently on the stack) the first time the threshold is
    crossed.
  • set_level() (called by pop() and directly) removes exactly the
    entries it's about to truncate from the index before truncating
    bindings/buffer, using the fact that bindings only ever grows by
    appending or shrinks by truncating from the back -- so for every prefix,
    the positions being removed are exactly the trailing entries of that
    prefix's index list.

No new data structure conventions were introduced beyond what #971 already
established (HashMap gated behind a small/large threshold); no_std /
zero-alloc behavior for shallow documents is preserved since the index is
None (and never allocated) below the threshold.

One behavioral edge case is preserved exactly: an explicit empty prefix
(reachable via QName(b":local").prefix(), i.e. a malformed name like
:local) never resolves, because NamespaceBinding::prefix already
represents "no prefix" (the default namespace) the same way
(prefix_len == 0) internally, and the original code's
n.prefix(&buffer) == Some(Prefix(b"")) comparison could never be true.
This is covered by a dedicated regression test.

Verification

Benchmark (benches/issue980.rs, cargo bench --bench issue980),
resolving one element name per nesting level across a range of depths:

On unpatched master (via git stash of just src/name.rs):

depth throughput
64 ~16.0 Melem/s
256 ~9.2 Melem/s
1024 ~3.4 Melem/s
4096 ~0.91 Melem/s
16384 ~0.23 Melem/s

Throughput drops ~70x over a 256x depth increase -- the O(depth²) signature
(each doubling of depth should roughly quarter throughput if the whole
document is O(depth²), matching the issue's own measurements).

With this fix, on the same range:

depth throughput
64 ~10.4 Melem/s
256 ~11.6 Melem/s
1024 ~11.8 Melem/s
4096 ~13.5 Melem/s
16384 ~13.6 Melem/s

Throughput stays flat, confirming the fix.

Tests: two new regression tests in src/name.rs (resolve_prefix_past_index_threshold,
covering a hit near the bottom of a >32-deep stack, a hit at the top, a
miss, the default namespace, and -- the key regression check for pop-side
maintenance -- that popping back out of scope correctly un-resolves a
previously-found prefix without panicking or returning stale data; and
resolve_prefix_with_empty_prefix_never_resolves, covering the edge case
above both below and above the indexing threshold).

Ran locally and all pass:

  • cargo test --all-features --benches --tests (1494 lib+doctest + all
    integration test binaries, 0 failures)
  • cargo test --no-default-features
  • cargo test --features serialize
  • cargo test --features serialize,encoding
  • cargo +1.79.0 check (pinned MSRV toolchain)
  • cargo fmt -- --check
  • cargo clippy --all-features --all-targets (no new warnings; the lib's
    only warning at HEAD, an unnecessary_unwrap in my first draft of
    set_level, is fixed in this PR's version)

Note

I'm the account submitting this PR (not the issue reporter); I read the
full issue thread, confirmed no other open/merged PR already addresses
this axis of the namespace resolver (only the sibling push-side fixes in
#970/#972/#974/#977/#979 exist, none of which touch resolve_prefix), and
independently confirmed the O(depth²) behavior with the benchmark above
before writing the fix.

Copilot AI review requested due to automatic review settings July 19, 2026 20:38

Copilot AI left a comment

Copy link
Copy Markdown

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Copilot was unable to review this pull request because the user who requested the review has reached their quota limit.

@AnayGarodia
AnayGarodia force-pushed the fix/980-resolve-prefix-linear-scan branch from 7091f24 to ee794d4 Compare July 21, 2026 09:30
@codecov-commenter

Copy link
Copy Markdown

⚠️ Please install the 'codecov app svg image' to ensure uploads and comments are reliably processed by Codecov.

Codecov Report

❌ Patch coverage is 80.81395% with 33 lines in your changes missing coverage. Please review.
✅ Project coverage is 57.17%. Comparing base (e00ae5c) to head (ee794d4).
⚠️ Report is 8 commits behind head on master.

Files with missing lines Patch % Lines
benches/issue980.rs 0.00% 27 Missing ⚠️
src/name.rs 95.86% 6 Missing ⚠️
❗ Your organization needs to install the Codecov GitHub app to enable full functionality.
Additional details and impacted files
@@            Coverage Diff             @@
##           master     #981      +/-   ##
==========================================
- Coverage   57.31%   57.17%   -0.14%     
==========================================
  Files          46       48       +2     
  Lines       18197    18675     +478     
==========================================
+ Hits        10429    10678     +249     
- Misses       7768     7997     +229     
Flag Coverage Δ
unittests 57.17% <80.81%> (-0.14%) ⬇️

Flags with carried forward coverage won't be shown. Click here to find out more.

☔ View full report in Codecov by Harness.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:
  • ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

Comment thread Changelog.md Outdated
to `SMALL_BINDING_COUNT` (32) bindings keep the previous linear scan;
larger ones are backed by a `HashMap` index from prefix to stack
positions, maintained incrementally on both push and pop, so lookups stay
O(1) average regardless of nesting depth.

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please make this a bit more concise, it's a bit excessive. Could even just keep the very first sentence.

Copy link
Copy Markdown
Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Cut to just the first sentence.

Comment thread src/name.rs Outdated
/// `bindings` stack, making a lookup O(depth). Once the stack grows past
/// `SMALL_BINDING_COUNT`, `NamespaceResolver` switches to a `HashMap`
/// index (built and maintained by `index_binding` / `set_level`); this
/// checks that resolution stays correct once that switch has happened,

@dralley dralley Jul 24, 2026

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Simplify all this language. The implementation details don't matter much beyond the very highest level - these are tests. All that needs to be said is that there are two implementations, they are switched based on the number of namespace bindings, and we want to check that both are correct.

Copy link
Copy Markdown
Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Rewritten to your wording: two implementations, switched on the number of bindings, both need to be correct.

Comment thread src/name.rs Outdated
/// An index from prefix bytes (empty slice for the default namespace) to
/// ascending positions in [`Self::bindings`], used by
/// [`resolve_prefix`](Self::resolve_prefix) to avoid a linear scan of the
/// whole stack once it grows past [`SMALL_BINDING_COUNT`]. `None` until

@dralley dralley Jul 24, 2026

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Again, it's not needed to describe the implementation multiple times in different places - here we are just defining the variable, it's enough to say what it's for rather than exactly what will be done with it later. The details can be provided at the place where it is being used.

Copy link
Copy Markdown
Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Trimmed to what the field is, dropped the description of how it's maintained. That now lives on index_binding.

Comment thread src/name.rs

/// Number of [`NamespaceBinding`]s that may sit on [`NamespaceResolver::bindings`]
/// before [`NamespaceResolver::resolve_prefix`] switches from a direct reverse
/// linear scan to a `HashMap` index (see [`NamespaceResolver::prefix_index`]).

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Same. This is enough information.

Copy link
Copy Markdown
Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Dropped the second paragraph, first one kept.

Comment thread src/name.rs
/// binding currently on the stack, including the one just pushed); after
/// that it is kept up to date on every subsequent push, and truncated in
/// lock-step on pop by [`Self::set_level`].
fn index_binding(&mut self, key: &[u8]) {

@dralley dralley Jul 24, 2026

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Detail is fine here so long as it's not duplicative and flows well. Please read through the rest of this yourself and make sure it makes sense as-written, I'll take another look after you've done a pass on everything.

I assume the code is AI generated as well - that's fine - but please make sure you've done a review yourself and understand exactly what it's doing before submitting if you haven't already.

Copy link
Copy Markdown
Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Kept the detail here but removed what it duplicated from the field and const docs, so this is now the one place the threshold behaviour is explained.

@dralley

dralley commented Jul 24, 2026

Copy link
Copy Markdown
Collaborator

Cut the commit message down a bit as well, there is no need to repeat every detail.

`resolve_prefix` scanned the whole in-scope `bindings` stack on every call.
That stack grows by one entry per `xmlns[:prefix]` declaration on each open
ancestor element, so a lookup that misses cost O(depth), and reading a
depth-D document cost O(D²) (tafia#980).

Stacks up to `SMALL_BINDING_COUNT` (32) keep the linear scan. Past that,
`resolve_prefix` is backed by a `HashMap` index from prefix to stack
positions, extended on push and truncated on pop, so lookups stay O(1)
average regardless of depth.
@AnayGarodia
AnayGarodia force-pushed the fix/980-resolve-prefix-linear-scan branch from ee794d4 to e7bac3e Compare July 26, 2026 20:40
@AnayGarodia

Copy link
Copy Markdown
Author

@dralley done, force-pushed as e7bac3e. Net effect is -105/+51 on prose, no code changes.

Beyond the five inline comments, I did the full pass you asked for and cut the same kind of duplication everywhere else it had crept in: last_binding's doc, the set_level truncation comment, the empty-prefix arm in resolve_prefix, the unwrap justification, the inline comments in the new test, and the issue980 bench header (which had drifted longer than issue971's, so I brought it back in line). The commit message is cut down too.

The rule I applied: the threshold behaviour is explained once, on index_binding, and everything else just says what it is and points there.

On the AI question: yes, this was AI-assisted. I've read and understand the whole change, and re-verified it locally on the final tree rather than assuming the earlier runs still held:

  • cargo test --all-features --benches --tests — all suites pass
  • cargo test --no-default-features and cargo test --features serialize,encoding — pass
  • cargo fmt -- --check clean, cargo clippy --all-features --all-targets adds no new warnings (the 8 remaining are pre-existing, none in name.rs or the new bench)

Happy to trim further if any of it still reads long.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

4 participants