Skip to content

Header value decoding is Θ(N²) in the number of encoded words #149

Closed

Description

@A-Mavericks

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

  1. staktrace commented on Nov 13, 2026

    @staktrace
    Owner

    Fixed by #150

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions