gh-132762: Fix underallocation bug in dict.fromkeys() and expand test coverage #133627
Conversation
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
previously covered: - fast path for dictionary inputs - fast path when object's constructor returns non-empty dict (too small for good coverage) now additionally covered: - fast path for set inputs - slow path for non-set, non-dictionary inputs - fast path when object's constructor returns *large* non-empty dict - slow path when object is a proper subclass of dict
|
All commit authors signed the Contributor License Agreement. |
|
Most changes to Python require a NEWS entry. Add one using the blurb_it web app or the blurb command-line tool. If this change has little impact on Python users, wait for a maintainer to apply the |
|
Thanks @angela-tarantula for the PR, and @colesbury for merging it 🌮🎉.. I'm working now to backport this PR to: 3.13, 3.14. |
miss-islington
pushed a commit
to miss-islington/cpython
that referenced
this pull request
May 8, 2025
…h-133627) The function `dict_set_fromkeys()` adds elements of a set to an existing dictionary. The size of the expanded dictionary was estimated with `PySet_GET_SIZE(iterable)`, which did not take into account the size of the existing dictionary. (cherry picked from commit 421ba58) Co-authored-by: Angela Liss <59097311+angela-tarantula@users.noreply.github.com>
|
Sorry, @angela-tarantula and @colesbury, I could not cleanly backport this to |
|
GH-133685 is a backport of this pull request to the 3.14 branch. |
colesbury
pushed a commit
to colesbury/cpython
that referenced
this pull request
May 8, 2025
…ythongh-133627) The function `dict_set_fromkeys()` adds elements of a set to an existing dictionary. The size of the expanded dictionary was estimated with `PySet_GET_SIZE(iterable)`, which did not take into account the size of the existing dictionary. (cherry picked from commit 421ba58) Co-authored-by: Angela Liss <59097311+angela-tarantula@users.noreply.github.com>
|
GH-133686 is a backport of this pull request to the 3.13 branch. |
colesbury
pushed a commit
that referenced
this pull request
May 8, 2025
) (gh-133685) The function `dict_set_fromkeys()` adds elements of a set to an existing dictionary. The size of the expanded dictionary was estimated with `PySet_GET_SIZE(iterable)`, which did not take into account the size of the existing dictionary. (cherry picked from commit 421ba58) Co-authored-by: Angela Liss <59097311+angela-tarantula@users.noreply.github.com>
colesbury
added a commit
that referenced
this pull request
May 8, 2025
) (gh-133686) The function `dict_set_fromkeys()` adds elements of a set to an existing dictionary. The size of the expanded dictionary was estimated with `PySet_GET_SIZE(iterable)`, which did not take into account the size of the existing dictionary. (cherry picked from commit 421ba58) Co-authored-by: Angela Liss <59097311+angela-tarantula@users.noreply.github.com>
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.
Closes #132762
Summary
dict_set_fromkeys()was only sizing its new table by the size of theiterableinput, ignoring any existing entries in the dictionary. This triggered an infinite loop indictresize()whenever the new dictionary size was too small to reinsert those entries. This patch adds the samePy_MAX(…, DK_LOG_SIZE(mp->ma_keys))guard thatdict_dict_fromkeys()uses, so we never accidentally shrink the table below its current capacity. The relevant test casebaddict3has been updated to cover this edge case.For more background, see my proposal.
3 New Regression Tests
Ever since the fast path was updated, the slow path completely lost test coverage. To rectify this, I added 3 new tests:
iterableinput is neither a set nor a dictionaryfromkeys()is called on a proper subclass of dict,baddict4dict_dict_fromkeys()anddict_set_fromkeys()are separate)Thanks for the review! @DinoV @colesbury