Repository navigation
Description
Summary
Decoding an encoded-word-heavy header value is quadratic in the number of encoded words. On a 2.56 MB Subject: line containing 160,000 =?UTF-8?B?SEE?= words, parse_mail itself returns in about 5 ms, but reading the value with get_first_value("Subject") takes about 30 s:
| encoded words | header length | parse_mail |
get_first_value |
|---|---|---|---|
| 40,000 | 640,018 B | 2.15 ms | 1.854 s |
| 80,000 | 1.28 MB | 4.91 ms | 7.425 s |
| 160,000 | 2.56 MB | ~5 ms | 29.99 s |
Each doubling of the word count roughly quadruples the time. The same path is used by get_value and addrparse_header.
Root cause
src/header.rs:
fn is_boundary(line: &str, ix: Option<usize>) -> bool {
ix.and_then(|v| line.chars().nth(v))
.map(|c| c.is_whitespace() || c == '"' || ...)
.unwrap_or(true)
}chars().nth(v) walks from the start of the line, which is O(v). tokenize_header_line calls is_boundary twice per encoded word (at the word start and end), so for N words the total character stepping is Θ(N²). The base64/quoted-printable decoding is linear; the time is in tokenization.
Reproduction
[dependencies]
mailparse = "=0.15.0"use mailparse::MailHeaderMap;
fn main() {
let n: usize = std::env::args().nth(1).and_then(|s| s.parse().ok()).unwrap_or(160_000);
let mut mail = String::from("Subject:");
for _ in 0..n { mail.push_str(" =?UTF-8?B?SEE?="); }
mail.push_str("\r\n\r\nbody\r\n");
let t0 = std::time::Instant::now();
let parsed = mailparse::parse_mail(mail.as_bytes()).expect("parse");
let t_parse = t0.elapsed();
let t1 = std::time::Instant::now();
let v = parsed.headers.get_first_value("Subject");
println!("n={} parse_mail={:?} get_first_value={:?} value_len={:?}",
n, t_parse, t1.elapsed(), v.as_deref().map(str::len));
}$ cargo run --release -- 40000
n=40000 parse_mail=2.15ms get_first_value=1.854s value_len=Some(639999)
$ cargo run --release -- 160000
n=160000 parse_mail=~5ms get_first_value=29.99s value_len=Some(2559999)Suggested fix
Do not walk the line from the start for every boundary check. Keep a byte cursor in tokenize_header_line (or check the adjacent character as the scan advances) so the boundary test is O(1) per word. The indices passed to is_boundary already come from find_from as byte offsets, so they can be used without re-counting characters from the start of the line.
Activity
staktrace commentedon Nov 13, 2026
Fixed by #150