Repository navigation
gh-136063: Fix quadratic complexity in email.header.decode_header() - #162002
Open
mountain-beaver wants to merge 1 commit into
Open
mountain-beaver wants to merge 1 commit into
mountain-beaver wants to merge 1 commit into
Conversation
…er() decode_header() popped items from the front of the ecre.split() result, deleted whitespace words from the middle of the word list one by one and built runs of encoded words with repeated bytes concatenation. All three are O(n) per step, making the function quadratic in the number of encoded words. Walk the split result by index, rebuild the word list in one pass and join each run once.
|
All commit authors signed the Contributor License Agreement. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
email.header.decode_header()is listed in gh-136063 among the functions with quadratic worst-case complexity. It had three separate O(n)-per-step operations:parts.pop(0)in a loop over the result ofecre.split();del words[d]in a loop to drop the whitespace between adjacent encoded words;last_word += wordonbytesto collapse runs of words with the same charset.The split result is now walked by index, the word list is rebuilt in one pass, and each run is joined once. The output is unchanged: I compared the old and new implementations on 200,000 random header values (encoded words, plain text, whitespace, line breaks, malformed words), checking both return values and raised exceptions.
Timings on a release build, one header line of
ncopies of=?us-ascii?q?a?=:The new test follows
test_get_param_linear_complexity: it uses 100,000 encoded words, which takes about a minute with the old code on a debug build.