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 - would you please take a look at this?

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