dict_set_fromkeys() calculates size of dictionary improperly

Bug report

Bug description:

The function dict_set_fromkeys() in the file dictobject.c adds elements of an iterable to an existing dictionary. The size of the expanded dictionary is estimated as PySet_GET_SIZE(iterable) and the size of the existing dictionary is not considered.

This is unlogical.

A more resonable estimation is "mp->ma_used + PySet_GET_SIZE(iterable)". What turns this into a bug is the fact that a large dictionary plus a small iterable can cause the function to loop forever.

The following code is adopted from the official tests, file test_dict.py. Official binaries for Python 3.13.3 compiled with MSVC will loop forever when running this modified test (the official test has range(10)). Other platforms may be affected as well.

class baddict3(dict):
    def __new__(cls):
        return d
d = {i : i for i in range(17)}
res = d.copy()
res.update(a=None, b=None, c=None)
print(res)
q = baddict3.fromkeys({"a", "b", "c"})
print(q)

A minor error is in the function calculate_log2_keysize(minsize) which has three branches for calculating its result. However, when minsize < 10 the results of the three branches can differ. Since _BitScanReverse64() is Windows-only other platforms might be unaffected.

A final unrelated note. PEP 11 – CPython platform support states that aarch64-unknown-linux-gnu and x86_64-unknown-linux-gnu are Tier 1 AND Tier 2.

CPython versions tested on:

3.13

Operating systems tested on:

Windows

Linked PRs

@DinoV

Looks like a 3.13 regression. On a debug build, this assertion fails:

python: Objects/dictobject.c:2025: dictresize: Assertion `newkeys->dk_usable >= mp->ma_used' failed.

I'm pretty sure the regressing PR was gh-114508 (cc @DinoV @colesbury).

@DinoV

@DinoV - would you please take a look at this?

@DinoV

I'd like to help with this one. I've done some homework.

TL;DR

dict_set_fromkeys() indeed under-allocates because it only considers the iterable's size. Fix by replacing estimate_log2_keysize(PySet_GET_SIZE(iterable)) with Py_MAX(estimate_log2_keysize(PySet_GET_SIZE(iterable)), DK_LOG_SIZE(mp->ma_keys)) to be consistent with dict_dict_fromkeys().

Repro & scope

Cross-platform: I reproduced the infinite-loop/assertion error on macOS (CPython 3.13.3), so this is not a Windows-only _BitScanReverse64() issue.
Trigger: The bug occurs whenever dict's __new__() is overridden to return a non-empty dictionary, and fromkeys() is called with a much smaller set argument (when the argument is a dict it's fine). This triggers _PyDict_FromKeys() to call dict_set_fromkeys(), which tries to shrink the table with dictresize() and fails. The dictresize() fails because its log2_newsize parameter must be large enough to allocate a new table in which all previously active items can be reinserted. That is where Assertion 'newkeys->dk_usable >= mp->ma_used' failed. comes from.

Root cause

In gh-114508, the fromkeys() fast path was loosened:

--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -2341,63 +2341,27 @@ PyObject *_PyDict_FromKeys(PyObject *cls, PyObject *iterable, PyObject *value) {

-    if (PyDict_CheckExact(d) && ((PyDictObject*)d)->ma_used == 0) {
+    if (PyDict_CheckExact(d)) {

Now any dict object, even if it is pre-populated, takes the fast path. Note that baddict3 is not strictly a subclass of dict, because its __new__() returns a dict. baddict3 is actually just an overridden dict class, so it passes the PyDict_CheckExact(d) check. And since baddict3 pre-populates the dict, it would not have passed the (PyDictObject*)d)->ma_used == 0 check back in 3.12, hence the regression. But dropping this check was no accident:

Yes, we read it out of the lock, and avoiding the fast path here doesn't make a ton of sense, it just means multiple resizes in the slow path versus presumably less in the fast path. It does seem like I probably need to make sure we don't attempt to make the dict smaller once we have it's lock and can stably take the size.

Originally posted by @DinoV in #114508 (comment)

To accommodate the looser fast path, _PyDict_FromKeys() was refactored into dict_dict_fromkeys() and dict_set_fromkeys() to handle dict and set arguments respectively, and a sizing guard was added to dict_dict_fromkeys() to handle overridden dict classes like so:

/* before */
dictresize(interp, mp,
    estimate_log2_keysize(PyDict_GET_SIZE(iterable)), unicode);

/* after */
uint8_t new_size = Py_MAX(
    estimate_log2_keysize(PyDict_GET_SIZE(iterable)),
    DK_LOG_SIZE(mp->ma_keys)
);
dictresize(interp, mp, new_size, unicode);

That code prevents accidentally shrinking below the existing table when dictresize() is called.

What's missing is the corresponding Py_MAX() guard on dict_set_fromkeys(), which still calls:

dictresize(interp, mp,
    estimate_log2_keysize(PySet_GET_SIZE(iterable)), unicode);

So it fails to prevent accidental table-shrinking. This is also why the bug is unique to set arguments, not both set and dict.

Why Py_MAX() is preferred over “old + new” sizing

It's certainly more intuitive to do this instead:

uint8_t new_size = estimate_log2_keysize(mp->ma_used + PySet_GET_SIZE(iterable));
dictresize(interp, mp, new_size, unicode);

But this strategy eagerly reserves memory for all old+new entries (plus headroom) upfront, even when the current table already has plenty of headroom. With the Py_MAX() guard, a single standard incremental resize is only triggered when necessary. There's also a TODO to reimplement dictresize() so that it reuses old keys whenever oldkeys->dk_size == newsize, which would further optimize this choice.

My Proposal

In dict_set_fromkeys(), replace the estimate_log2_keysize(PySet_GET_SIZE(iterable)) call with the corresponding Py_MAX() guard:

/* before */
dictresize(interp, mp, estimate_log2_keysize(PySet_GET_SIZE(iterable)), unicode);

/* after */
uint8_t new_size = Py_MAX(
    estimate_log2_keysize(PySet_GET_SIZE(iterable)),
    DK_LOG_SIZE(mp->ma_keys)
);
dictresize(interp, mp, new_size, unicode);

Add a regression test in Lib/test/test_dict.py using the baddict3 example to confirm no infinite-loop and correct output.

Would love a 👍 or any feedback (cc @DinoV @colesbury) before opening a PR. This would be my first CPython contribution, so thanks for your guidance!

Go for it! You can @ me on the PR to review it

gh-132762: Fix underallocation bug in `dict.fromkeys()`(gh-133627)

pythongh-132762: Fix underallocation bug in `dict.fromkeys()`(pythong…

[3.13] pythongh-132762: Fix underallocation bug in `dict.fromkeys()`(p…

[3.14] gh-132762: Fix underallocation bug in `dict.fromkeys()`(gh-133627

[3.13] gh-132762: Fix underallocation bug in `dict.fromkeys()`(gh-133627

I'm going to close this now that dict_set_fromkeys bug is fixed. Let's track the calculate_log2_keysize issues in #133703

@ThomasBr0

Thanks @ThomasBr0 for the bug report and @angela-tarantula for fixing this!

pythongh-132762: Fix underallocation bug in `dict.fromkeys()`(pythong…

Navigation Menu

Repository navigation

dict_set_fromkeys() calculates size of dictionary improperly #132762

Bug report

Bug description:

CPython versions tested on:

Operating systems tested on:

Linked PRs

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

dict_set_fromkeys() calculates size of dictionary improperly #132762

Description

Bug report

Bug description:

CPython versions tested on:

Operating systems tested on:

Linked PRs

Activity

ZeroIntensity commented on Apr 21, 2025

colesbury commented on Apr 21, 2025

angela-tarantula commented on May 6, 2025

colesbury commented on May 6, 2025

colesbury commented on May 8, 2025

colesbury commented on May 8, 2025

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions