Bug report

Bug description:

The performance regression suite I run against CPython builds picked up a slowdown in email header folding after #134271 (gh-87720). The fix itself is important, since it stops encoded words with specials from losing their quoting when refolded, so the goal here is only to make the new check cheaper, with exactly the same output.

The new check calls contains_token_type('vtext') for most parts while folding, and that walks the whole subtree of the part every time. Parts that don't fit are then split and their subparts are walked again, so headers without any vtext, which is the common case, have their tree walked several times. For a 50-recipient To header that's about 3,000 calls over 1,500 tokens.

It shows up whenever new messages are generated, since every header gets folded:

import email.policy
from email.message import EmailMessage

POLICY = email.policy.SMTP.clone(max_line_length=78)

message = EmailMessage(policy=POLICY)
message["From"] = "Orders <orders@example.com>"
message["To"] = ", ".join(f"Customer {i:02d} <customer-{i:02d}@example.net>" for i in range(50))
message["Subject"] = "Your order has been processed"
message.set_content("Your order was processed successfully.\n")
message.as_bytes(policy=POLICY)

as_bytes() time per message, before and after the change:

To check this isn't just a microbenchmark, I also ran a more realistic workload: 2,000 generated messages with a mix of 1 to 50 recipients, Received, DKIM-Signature and List-Unsubscribe headers, about 40% of them replies with References, and plain-text or HTML bodies. Generating and serializing them got about 17% slower overall (+0.22 ms per message). Re-serializing parsed messages is barely affected (about +2%), since unchanged headers keep their original lines.

This only affects messages using the new policies (EmailMessage, policy.default, policy.SMTP, also through smtplib.send_message()). Messages using compat32 go through the old folding code and aren't affected.

This isn't specific to any platform. The numbers above are local (arm64), and I validated the same on AWS Lambda, where a 50-recipient serialization was about 64% slower on 3.12 (arm64, PGO+LTO). The change is now in 3.12, 3.13, 3.14 and main.

I think the repeated walks can be avoided without changing the result. A part can only contain vtext if the whole tree does, so the tree can be checked once per header and the per-part check skipped when there is none. When there is, the per-part check can walk the tree iteratively instead of with a recursive method call per token. With that, the realistic workload goes from +17% to about +6%, the 50-recipient case from +64% to about +18%, and headers that do contain encoded words stay as fast as they are now.

The folded output stays byte-for-byte identical to the current code (I compared the benchmark messages, the realistic workload and a few hundred foldings with encoded words, specials, quoted strings and comments), and test_email passes on main, 3.12 and 3.13. Happy to send a PR. cc @bitdancer

CPython versions tested on:

3.12, 3.13, CPython main branch

Operating systems tested on:

Linux