Fix O(depth²) namespace prefix resolution in NamespaceResolver#981
Fix O(depth²) namespace prefix resolution in NamespaceResolver#981AnayGarodia wants to merge 1 commit into
Conversation
7091f24 to
ee794d4
Compare
|
Codecov Report❌ Patch coverage is
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
Flags with carried forward coverage won't be shown. Click here to find out more. ☔ View full report in Codecov by Harness. 🚀 New features to boost your workflow:
|
| 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. |
There was a problem hiding this comment.
Please make this a bit more concise, it's a bit excessive. Could even just keep the very first sentence.
There was a problem hiding this comment.
Cut to just the first sentence.
| /// `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, |
There was a problem hiding this comment.
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.
There was a problem hiding this comment.
Rewritten to your wording: two implementations, switched on the number of bindings, both need to be correct.
| /// 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 |
There was a problem hiding this comment.
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.
There was a problem hiding this comment.
Trimmed to what the field is, dropped the description of how it's maintained. That now lives on index_binding.
|
|
||
| /// 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`]). |
There was a problem hiding this comment.
Same. This is enough information.
There was a problem hiding this comment.
Dropped the second paragraph, first one kept.
| /// 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]) { |
There was a problem hiding this comment.
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.
There was a problem hiding this comment.
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.
|
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.
ee794d4 to
e7bac3e
Compare
|
@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: The rule I applied: the threshold behaviour is explained once, on 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:
Happy to trim further if any of it still reads long. |
Fixes #980.
Problem
NamespaceResolver::resolve_prefixdid a reverse linear scan of the entirein-scope
bindingsstack on every call:bindingsgrows by one entry perxmlns[:prefix]declaration on everycurrently 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 everyStart/Empty/End) down a depth-D document costs O(D²). A ~1.3 MBcrafted document with one
xmlns:*declaration per level (no huge tag, nohuge attribute count -- just ordinary depth) drives multi-second single-core
CPU stalls.
This is the same shape of problem as #969/#971 (
check_for_duplicatesscanning 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 flatVecacting as a stack:push(via
add) always appends, andpop(viaset_level) always truncatesfrom 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 = 32bindings) keep the directlinear 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_prefixisbacked by a
HashMap<Vec<u8>, Vec<usize>>index (prefix bytes, or an emptykey 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 andpush()) records each newbinding 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 bypop()and directly) removes exactly theentries it's about to truncate from the index before truncating
bindings/buffer, using the fact thatbindingsonly ever grows byappending 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 (
HashMapgated 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, becauseNamespaceBinding::prefixalreadyrepresents "no prefix" (the default namespace) the same way
(
prefix_len == 0) internally, and the original code'sn.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(viagit stashof justsrc/name.rs):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:
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 caseabove both below and above the indexing threshold).
Ran locally and all pass:
cargo test --all-features --benches --tests(1494 lib+doctest + allintegration test binaries, 0 failures)
cargo test --no-default-featurescargo test --features serializecargo test --features serialize,encodingcargo +1.79.0 check(pinned MSRV toolchain)cargo fmt -- --checkcargo clippy --all-features --all-targets(no new warnings; the lib'sonly warning at HEAD, an
unnecessary_unwrapin my first draft ofset_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), andindependently confirmed the O(depth²) behavior with the benchmark above
before writing the fix.