Header values: single-line fast path in the vendored `get_value`, drop the double key allocation in `collect_headers`

[kurok]

Problem

Every header value this library reads goes through mailparse's two-stage tokenizer: tokenize_header splits the value into lines and allocates a Vec<HeaderToken> per line plus an outer Vec, normalize_header_whitespace builds a second Vec, and normalize_header then grows a String from the tokens with push_str and no capacity hint. That machinery exists for folded values and RFC 2047 encoded words. The common case is neither: on tests/data/large_message.eml the root block has 24 headers, 8 folded continuation lines and exactly one encoded word (the Subject), and every part-level Content-Type, Content-Transfer-Encoding, Content-Disposition, Content-ID, Date, MIME-Version, X-* value is one physical line with no =?.

The tokenizer is paid more than once per header. collect_headers calls get_value() for all ~35 headers of the fixture; mailparse itself then calls get_first_value -- a linear scan that re-tokenises the matching header -- for Content-Type on every part, Content-Transfer-Encoding on every get_body_encoded() (two to three times per leaf), Content-Disposition on get_content_disposition(); and our three flat parsers add Subject, Date, Content-ID and a second Content-Disposition lookup that exists only to test presence. That is roughly 60 get_value calls per full parse, ~55 of them for values the fast path below handles with a single to_owned(). collect_headers additionally allocates the key twice (get_key() then key.clone() for the position map) when the raw key bytes would do.

Why it matters for a library whose reason to exist is speed: in mode="metadata" (0.030 ms on the M4 fixture) the boundary memmem accounts for roughly 17-20 us, so the header path is a large share of what is left; and on the 2000 x ~0.8 KiB batch the benchmarks call the mailbox-sweep case (#96), header work is essentially all the Rust-side work per message. None of the known profile hot spots (decode_base_mut 53%, whitespace strip 27%, memmem 7.5%) touches this; it is the next layer down, and it is the layer every mode pays.

Evidence

All citations are from master 73f56da.

• vendor/mailparse/src/lib.rs:213-240 -- pub fn get_value(&self) -> String { let chars = self.decode_utf8_or_latin1(); self.normalize_header(chars) } and fn normalize_header(...) -> String { let mut result = String::new(); for tok in header::normalized_tokens(&chars) { ... result.push_str(t) ... } }. Every value is tokenised; the result String starts empty. get_value_utf8 (lib.rs:258-263) goes through the same normalize_header.
• vendor/mailparse/src/header.rs:137-151 -- fn tokenize_header(value: &str) -> Vec<HeaderToken> { let mut tokens = Vec::new(); let mut lines = value.lines(); ... while let Some(line) = lines.next().map(str::trim_start) { ... let mut line_tokens = tokenize_header_line(line); tokens.append(&mut line_tokens); } }: one Vec per physical line plus the outer one.
• vendor/mailparse/src/header.rs:75-129 -- tokenize_header_line: match find_from(line, ix_search, "=?") { ... None => { result.push(maybe_whitespace(&line[ix_search..])); break; } } (122-125). With no =? in the line the whole (already trim_started) line is one Text or Whitespace token. find_from is line[ix_start..].find(key) (lib.rs:118-120).
• vendor/mailparse/src/header.rs:160-217 -- normalize_header_whitespace: let mut result = Vec::<HeaderToken>::new(); (161); a lone Text is pushed unchanged (168-179), a lone Whitespace is pushed unchanged because saved_token is None (180-191); " ".to_string() at 196/201/203 allocates per fold. normalized_tokens at 219-221 chains the two.
• vendor/mailparse/src/lib.rs:371-377 -- HeaderParseState::Value => { if c == b'\n' { state = ValueNewline } else if c != b'\r' { ix_value_end = ix + 1; } }: a header value slice never ends in \r (only a non-CR non-LF byte advances ix_value_end), so str::lines() on a value with no \n yields exactly the value itself, once (or nothing for "").
• vendor/mailparse/src/lib.rs:464-472 -- fn get_first_value(&self, key: &str) -> Option<String> { for x in self { if x.get_key_ref().eq_ignore_ascii_case(key) { return Some(x.get_value()); } } None }: each lookup re-runs the tokenizer on the hit.
• Callers inside mailparse, per part: lib.rs:943-947 headers.get_first_value("Content-Type"); lib.rs:825-832 get_body_encoded: self.headers.get_first_value("Content-Transfer-Encoding").map(|s| s.to_lowercase()); lib.rs:845-850 get_content_disposition: self.headers.get_first_value("Content-Disposition").
• Callers in this crate: src/mail_parser.rs:1312-1319 (get_first_value("Subject"), ("Date")), 1356 (part.get_content_disposition()), 1386-1389 (get_first_value("Content-ID")), 1396 (disposition_token); the same shape in metadata mode at 603-611, 640, 656-658 and lazy mode at 773-781, 807, 827-834; tree at 948-954, 1121-1127.
• src/mail_parser.rs:473-481 -- fn disposition_token(part, kind) -> Option<String> { part.get_headers().get_first_value("Content-Disposition")?; Some(match kind { ... }) }: line 474 builds and drops a normalised String purely to test presence; get_first_header(..).is_some() (lib.rs:474-477) answers the same question with no get_value.
• src/mail_parser.rs:501-517 -- collect_headers: let mut headers = Vec::new(); let mut positions: HashMap<String, usize> = HashMap::new(); for header in part.get_headers() { let key = header.get_key(); match positions.get(&key).copied() { Some(position) => headers[position].1.push(header.get_value()), None => { positions.insert(key.clone(), headers.len()); headers.push((key, vec![header.get_value()])); } } }. get_key() is decode_latin1(self.key).into_owned() (lib.rs:174-176, whose doc says "Prefer using get_key_ref where possible for better performance"); get_key_raw() returns &[u8] (lib.rs:273-275). part.get_headers() iterates &MailHeader (vendor/mailparse/src/headers.rs:51-58); ParsedMail.headers is pub (lib.rs:722), so the count is known up front.
• vendor/mailparse/src/addrparse.rs:286-291 -- addrparse_header calls crate::header::normalized_tokens(&chars) directly: the five address headers need the token stream and are unaffected by (and not slowed by) a fast path in normalize_header.
• tests/data/large_message.eml lines 1-32: root header block, separator at line 33; 8 continuation lines (4-5, 8-9, 11-13, 31); one =? (line 15). Part header blocks at 35-36, 39-40, 56-57, 145-149, 3946-3950. About 35 headers total, ~60 get_value calls per full parse counting the per-part lookups above.
• vendor/mailparse/Cargo.toml:40-41 -- [dependencies.memchr] version = "2.7.0" is already a dependency of the vendored copy (Cargo.lock:74-77 resolves 2.8.3); no new dependency is needed for the fast-path check.
• vendor/mailparse/PATCH.md -- "with two functions changed (one via a new module)" and the sync procedure ("keep src/bytescan.rs, the mod bytescan; line, the two call sites and memchr"): a change here makes it three and the file must say so.
• Known profile (do not re-measure): full parse 0.225 ms M4 / 0.604 ms EPYC; metadata 0.030 ms; remaining dominant loops decode_base_mut 53%, whitespace strip 27%, memmem 7.5%; everything else <5% each. memmem at 7.5% of 225 us is ~17 us, which in metadata mode leaves ~10-13 us for headers, per-part work and the Python call.

Proposal

Three changes, no new dependency, no output change.

1. Fast path in normalize_header (vendored, vendor/mailparse/src/lib.rs). Before tokenising, take the single-line, no-encoded-word case directly:

fn normalize_header(&'a self, chars: Cow<'a, str>) -> String {
    let bytes = chars.as_bytes();
    // One physical line with no encoded word: `lines()` yields exactly this
    // string (a header value never ends in CR, see parse_header), the line
    // becomes one Text/Whitespace token, and normalize_header_whitespace
    // passes a lone token through unchanged. Same result as the tokenizer,
    // one allocation instead of ~6.
    if memchr::memchr2(b'\n', b'\r', bytes).is_none()
        && memchr::memmem::find(bytes, b"=?").is_none()
    {
        return chars.trim_start().to_owned();
    }
    self.normalize_header_tokens(chars)
}

fn normalize_header_tokens(&'a self, chars: Cow<'a, str>) -> String {
    let mut result = String::with_capacity(chars.len());
    for tok in header::normalized_tokens(&chars) { /* unchanged body */ }
    result
}

Equivalence argument, to go in the comment: tokenize_header calls value.lines().map(str::trim_start); with no \n that is one line (none for ""), and with the value never ending in \r the line is the whole value; tokenize_header_line with no =? pushes exactly one maybe_whitespace(line) token; normalize_header_whitespace pushes a lone Text or Whitespace unchanged. The fast path uses the same str::trim_start (Unicode White_Space) as tokenize_header. Checking \r as well as \n is redundant for values produced by parse_header but keeps the fast path correct for a MailHeader built any other way. with_capacity(chars.len()) on the slow path is a hint, not a bound (decoded words can shrink or grow the value) -- it is fine either way. Keep normalize_header_tokens as a named function: it is the oracle for the differential test.

2. collect_headers (src/mail_parser.rs:501-517). Key the position map by raw bytes, size both containers, allocate the owned key once:

fn collect_headers(part: &ParsedMail<'_>) -> Vec<(String, Vec<String>)> {
    let count = part.headers.len();
    let mut headers: Vec<(String, Vec<String>)> = Vec::with_capacity(count);
    // Latin-1 decoding is injective, so raw-byte equality is exactly the
    // String equality this map had; keys stay case-sensitive as before.
    let mut positions: HashMap<&[u8], usize> = HashMap::with_capacity(count);
    for header in part.get_headers() {
        match positions.get(header.get_key_raw()).copied() {
            Some(position) => headers[position].1.push(header.get_value()),
            None => {
                positions.insert(header.get_key_raw(), headers.len());
                headers.push((header.get_key(), vec![header.get_value()]));
            }
        }
    }
    headers
}

Behaviour that must stay identical: first-appearance key order, all values kept per key, case-sensitive key grouping (Received and received remain separate entries, as today), Latin-1 fallback for non-UTF-8 key bytes via get_key().

3. disposition_token (src/mail_parser.rs:473-481). Replace the presence test part.get_headers().get_first_value("Content-Disposition")?; with part.get_headers().get_first_header("Content-Disposition")?; -- same case-insensitive first-match semantics (lib.rs:474-477), no tokenizer, no String.

What this deliberately does not do: dedupe get_body_encoded() per part (round-1 issue "Evaluate Body once per part"), read Subject/Date out of the collect_headers table (the comment at src/mail_parser.rs:1308-1311 explains #28; round-1 "Share one envelope/part-classification helper pair" is where that code moves), or rewrite parse_header (see Out of scope).

Implementation notes for the agent

1. vendor/mailparse/src/lib.rs: split normalize_header into the fast-path dispatcher and normalize_header_tokens as sketched. memchr is already imported for find_from_u8; reuse the crate path. Do not touch header.rs -- the equivalence argument depends on its current behaviour, and every changed vendored file is one more hand-merge.
2. Add a differential test in lib.rs's mod tests (it has use super::* and can construct MailHeader { key, value } directly): generate a corpus in the style of vendor/mailparse/src/bytescan.rs:105-122 (xorshift over a small alphabet, lengths 0..80, several draws per length) with alphabet b"ab =?\t\r\n_Q?B\xe9\xff" so encoded-word delimiters, folds, tabs, Unicode-whitespace-after-Latin-1 and invalid UTF-8 all occur at every alignment; assert h.get_value() == h.normalize_header_tokens(h.decode_utf8_or_latin1()) and the same for get_value_utf8 where the bytes are valid UTF-8. Also assert a hand-written table: "", " ", "\tfoo", "foo ", "a\rb", "=?", "x =?utf-8?Q?y?= z", "\u{a0}foo" (NBSP is White_Space: both paths trim it).
3. Run the vendored suite the CI way: cargo test --manifest-path vendor/mailparse/Cargo.toml --target-dir /tmp/vendor-target. Never cargo inside vendor/mailparse without --target-dir elsewhere -- a target/ there is swept into the sdist by the vendor/mailparse/**/* include (pyproject.toml:46-48).
4. vendor/mailparse/PATCH.md: change "two functions changed" to three, add a numbered item 3 describing normalize_header (what it skips, why the output is identical, which test proves it), and add it to the "Keeping this in sync" list. Also fix the stale "one function changed" in the root Cargo.toml:53-55 comment while there (relates to round-1 "Make the vendored mailparse delta a CI invariant"; if that lands first, regenerate its upstream.patch).
5. src/mail_parser.rs: rewrite collect_headers and disposition_token as above. HashMap<&[u8], usize> borrows from part, which outlives the function -- no lifetime plumbing needed. Clippy runs with -D warnings -W clippy::cast_possible_truncation; there are no casts here.
6. Oracles for the Python surface (no API moves, so __init__.pyi, tests/test_contract.py frozen sets and docs/compatibility.md stay untouched): tests/test_headers.py, tests/test_multivalue_headers.py (key order, repeated keys -- headers key order is nondeterministic across parses of identical bytes #157, fast_mail_parser should return all headers #12, Duplicate headers silently dropped by HashMap<String,String> collapse #23), tests/test_stdlib_parity.py (its DIVERGENCES table must neither gain nor lose an entry: a new unexplained divergence or a STALE entry both fail), tests/test_metadata_mode.py, tests/test_lazy_mode.py, tests/test_mime_tree.py, tests/test_tree_modes.py, tests/test_attachments.py (disposition token), tests/test_rfc_corpus.py.
7. fuzz/Cargo.toml patches the same ../vendor/mailparse, so cargo fuzz run parse_agreement -- -max_total_time=300 is a free extra check that flat and tree parses still agree on headers.
8. CHANGELOG.md under ## [Unreleased] / ### Changed: one entry with the local before/after numbers, in the style of the 0.9.0 entry.
9. Do not add memchr to the root Cargo.toml; nothing in src/ needs it for this change.

Harness -- how to prove it

Build both sides once, then measure interleaved (the build cycle alone moves numbers ~16%, .github/scripts/ab_median.py docstring):

# base
git worktree add /tmp/fmp-base master
(cd /tmp/fmp-base && uv venv .venv && . .venv/bin/activate && uv pip install maturin pytest pytest-benchmark mail-parser && maturin develop --release)
# head (this branch)
uv venv .venv && . .venv/bin/activate && uv pip install maturin pytest pytest-benchmark mail-parser && maturin develop --release

# interleaved rounds, both sides, same machine, nothing else running
for r in 1 2 3 4 5; do
  /tmp/fmp-base/.venv/bin/pytest -q tests/benchmark --benchmark-min-rounds=25 --benchmark-json=base-$r.json
  .venv/bin/pytest -q tests/benchmark --benchmark-min-rounds=25 --benchmark-json=head-$r.json
done
AB_THRESHOLD_PCT=7 python .github/scripts/ab_median.py \
  --a-label head --b-label base --informational test__threaded___ \
  --a head-*.json --b base-*.json

Benchmarks expected to move (tests/benchmark/test_read_message.py):

• test__fast_mail_parser___parse_metadata (260-283) and test__fast_mail_parser___parse_tree_metadata (331): expected -5 to -15%. This is the primary number; if it moves less than the control noise floor the fast path is not earning its PATCH.md entry and the issue should be closed with the measurement.
• test__fast_mail_parser___parse_many_metadata (373-388, threads=1): same direction.
• test__fast_mail_parser___parse_message, parse_tree, parse_lazy_*: expected -1 to -3%, i.e. within noise; must not regress > 7%.
• test__threaded___parse_many_small, test__threaded___parse_many_metadata_small (227-232, 391-399): informational in the gate (test.yml:466-470 passes --informational test__threaded___) because thread scheduling dominates. To see the effect, add single-threaded variants test__fast_mail_parser___parse_many_small and test__fast_mail_parser___parse_many_metadata_small calling parse_many(batch, threads=1[, mode="metadata"]) on [_small_message()] * SMALL_BATCH, modelled on 157-165 and 373-388 (guarded with the same pytest.skip on TypeError so a base predating mode= does not take the gate down). Relates to round-1 "Benchmark gate only sees one 767 KiB base64 message: add gated small, QP and RFC 2047-heavy benchmarks" -- if that lands first, use its gated small benchmark instead of adding one. Expected: a few percent end to end (Python object construction per message is a large share there); report whatever is measured.
• Controls (test__mail_parser___*, test__mailparser_lib___*, test__stdlib_email___*) must stay flat; a treatment delta counts only when it clears their spread.

Correctness and lint surface, all required green:

pytest tests --ignore=tests/benchmark
cargo fmt --all -- --check
cargo clippy --all-targets -- -D warnings -W clippy::cast_possible_truncation
mypy --strict fast_mail_parser/
ruff check .
cargo test --manifest-path vendor/mailparse/Cargo.toml --target-dir /tmp/vendor-target

Put the local before/after table (machine, rounds, every benchmark, control noise floor) in the PR body. The Apple M4 is not a proxy for the x86 CI gate: this touches the per-header loop in a crate where code placement on the runners' Zen CPUs has swung results up to 96% (CONTRIBUTING.md, "Performance"), so the PR gate's interleaved A/B and, if it reports anything surprising, a toolchain-ab.yml run are the verdict. Re-run a large failure before acting on it.

Acceptance criteria

• vendor/mailparse/src/lib.rs: normalize_header returns chars.trim_start().to_owned() when the value contains no \n, no \r and no =?, and otherwise delegates to the unchanged tokenizer path, kept as a separately named function.
• A differential test in the vendored crate compares the fast path against the tokenizer path over a generated corpus at every alignment plus the hand-written edge table above, and passes under cargo test --manifest-path vendor/mailparse/Cargo.toml --target-dir /tmp/vendor-target.
• vendor/mailparse/PATCH.md lists three changed functions, describes the third, and its sync procedure names it; the root Cargo.toml [patch.crates-io] comment no longer says "one function changed". diff -r against the registry 0.16.1 copy shows only src/bytescan.rs, src/lib.rs, src/body.rs, Cargo.toml and PATCH.md.
• collect_headers performs no key.clone(), keys its position map by get_key_raw(), pre-sizes both containers, and tests/test_headers.py, tests/test_multivalue_headers.py, tests/test_stdlib_parity.py pass with no change to DIVERGENCES.
• disposition_token tests presence with get_first_header, not get_first_value; tests/test_attachments.py, tests/test_metadata_mode.py, tests/test_lazy_mode.py, tests/test_mime_tree.py pass.
• No memchr (or any) dependency added to the root Cargo.toml; Cargo.lock unchanged apart from nothing.
• Interleaved local A/B (>= 5 rounds, controls reported): test__fast_mail_parser___parse_metadata improves by at least the control noise floor; no benchmark regresses more than 7%; the table is in the PR body.
• Single-threaded small-batch benchmarks (threads=1, full and metadata) exist -- added here or via the round-1 benchmark issue -- and their before/after is reported.
• The PR benchmark gate (x86 runner) passes; the run's CPU line is quoted in the PR.
• Full lint/test surface green: pytest tests --ignore=tests/benchmark, cargo fmt --all -- --check, cargo clippy --all-targets -- -D warnings -W clippy::cast_possible_truncation, mypy --strict fast_mail_parser/, ruff check ., vendored suite.
• CHANGELOG.md [Unreleased] entry with the measured numbers.

Out of scope

• Rewriting parse_header (vendor/mailparse/src/lib.rs:320-412) on memchr, and repair_missing_separator's position scan (src/mail_parser.rs:275): ~2.2 KB of header bytes per fixture parse, an expected 1-2 us against a 30 us metadata parse, with the highest edge-case surface in the crate (trailing-CR exclusion at 371-377, key-only lines at 346-360, PreValue skipping spaces but not tabs at 363-369) and a fourth hand-merged vendored function. Revisit only if a profile taken after this change shows parse_header above a few percent of metadata mode.
• Evaluating get_body_encoded() once per part (round-1 "Evaluate Body once per part").
• Reading Subject/Date/Content-ID out of the collect_headers table instead of get_first_value (round-1 "Share one envelope/part-classification helper pair"; see the subject/date are derived from the lossy header map #28 comment at src/mail_parser.rs:1308-1311).
• Making tokenize_header_line push into a caller-supplied Vec to save the per-line allocation on the folded/encoded slow path: a change to header.rs, which this issue deliberately leaves byte-identical to upstream.
• Any change to the Python-visible headers dict, its construction or caching (round-1 "Cache the headers dict per object").

Related issues

• Cache the headers dict per object, collapse the six identical getters, and mark the result classes frozen #231 — the Python dict cache above this
• Evaluate Body once per part: drop the redundant text-body copy, the second Content-Transfer-Encoding lookup, and the scalar '=' scan on quoted-printable parts #230
• Make the vendored mailparse delta a CI invariant (upstream.patch + registry diff) and fix the three stale comments describing it #235
• Benchmark gate only sees one 767 KiB base64 message: add gated small, quoted-printable and RFC 2047-heavy benchmarks #223 — parse_qp_metadata isolates collect_headers