What
buffa/src/view.rs:1927 scans forward from every entry to decide whether a later occurrence of the same key exists:
entries.iter().enumerate().filter_map(move |(i, entry)| {
if entries[i + 1..].iter().any(|(later_k, _)| *later_k == entry.0) { None } else { Some(entry) }
})len_unique (:1945) is iter_unique().count(), so it inherits the same cost.
The work is quadratic in n, the total entry count — not in how many duplicates are present. A map with 16k entries and zero duplicate keys pays the same cost as one that is all duplicates.
The doc comment justifies the approach with "duplicate map keys are invalid per the protobuf encoding spec and only arise in adversarial or conformance-test wire data, so n is effectively always small." That reasoning holds for how often duplicates occur, but the runtime does not depend on that — only on how many entries the peer sent.
Why it matters
MapView is the borrowed half of a zero-copy decode, so its entry list is sized by untrusted input. Any consumer that needs the canonical last-wins map — what the wire format specifies, and what an owned HashMap decode produces — currently has to go through these helpers or hand-roll the deduplication.
Measured against main (0.9.1, arm64) on MapView<'_, &str, u32>, counting distinct keys and walking them once:
| entries |
len_unique + iter_unique |
| 64 |
17.95 µs |
| 256 |
123.41 µs |
| 1024 |
1.23 ms |
| 4096 |
18.76 ms |
| 16384 |
313.53 ms |
A single call at 16k entries is ~313 ms. On a decode path reachable from untrusted bytes, that is a denial-of-service primitive rather than a performance footnote. For reference, the same count-and-walk over an index built in one linear pass runs in ~210 µs at that size.
Constraints anything replacing this would have to respect
Noting these because they narrow the options and are easy to miss from outside the codebase:
no_std. MapView has to keep working under check-nostd, so a fix cannot reach for std::collections::HashMap directly. hashbrown is already a workspace dependency and __private::HashMap already aliases per-config, so this looks like it needs no new dependency.- MSRV 1.75, per
rust-version in the workspace manifest.
- The current bound is
K: PartialEq. Any approach based on hashing rather than scanning would need to tighten that, which is a breaking change to the signature and would want a Breaking changes changelog fragment. Adding separate canonical-iteration methods under the stricter bound would avoid that, if spending a break here is not wanted.
How this was found
Adding validator codegen for view types in protovalidate-buffa. map.min_pairs has to count distinct keys, and per-key rules must not fire on entries a canonical decode would have dropped, so a view-side validator needs exactly the canonical map these helpers produce. We build an index inline in the generated validator instead. That works, but it means every consumer that needs canonical map semantics reimplements the same thing, and the helpers that exist for this purpose are the ones that cannot be used.
Measurements are from a standalone harness against a local main checkout, not from benchmarks/ — it exercises a MapView method directly rather than a message shape.
What
buffa/src/view.rs:1927scans forward from every entry to decide whether a later occurrence of the same key exists:len_unique(:1945) isiter_unique().count(), so it inherits the same cost.The work is quadratic in
n, the total entry count — not in how many duplicates are present. A map with 16k entries and zero duplicate keys pays the same cost as one that is all duplicates.The doc comment justifies the approach with "duplicate map keys are invalid per the protobuf encoding spec and only arise in adversarial or conformance-test wire data, so
nis effectively always small." That reasoning holds for how often duplicates occur, but the runtime does not depend on that — only on how many entries the peer sent.Why it matters
MapViewis the borrowed half of a zero-copy decode, so its entry list is sized by untrusted input. Any consumer that needs the canonical last-wins map — what the wire format specifies, and what an ownedHashMapdecode produces — currently has to go through these helpers or hand-roll the deduplication.Measured against
main(0.9.1, arm64) onMapView<'_, &str, u32>, counting distinct keys and walking them once:len_unique+iter_uniqueA single call at 16k entries is ~313 ms. On a decode path reachable from untrusted bytes, that is a denial-of-service primitive rather than a performance footnote. For reference, the same count-and-walk over an index built in one linear pass runs in ~210 µs at that size.
Constraints anything replacing this would have to respect
Noting these because they narrow the options and are easy to miss from outside the codebase:
no_std.MapViewhas to keep working undercheck-nostd, so a fix cannot reach forstd::collections::HashMapdirectly.hashbrownis already a workspace dependency and__private::HashMapalready aliases per-config, so this looks like it needs no new dependency.rust-versionin the workspace manifest.K: PartialEq. Any approach based on hashing rather than scanning would need to tighten that, which is a breaking change to the signature and would want aBreaking changeschangelog fragment. Adding separate canonical-iteration methods under the stricter bound would avoid that, if spending a break here is not wanted.How this was found
Adding validator codegen for view types in
protovalidate-buffa.map.min_pairshas to count distinct keys, and per-key rules must not fire on entries a canonical decode would have dropped, so a view-side validator needs exactly the canonical map these helpers produce. We build an index inline in the generated validator instead. That works, but it means every consumer that needs canonical map semantics reimplements the same thing, and the helpers that exist for this purpose are the ones that cannot be used.Measurements are from a standalone harness against a local
maincheckout, not frombenchmarks/— it exercises aMapViewmethod directly rather than a message shape.