Feature or enhancement

Proposal:

Summary

dict.fromkeys(d, value) is significantly slower than it should be when d is a regular dict. The current implementation always iterates through every key and calls insertdict() on the new empty dict, which performs a full hash lookup + collision probing per key — even though the target dict is empty and all keys are guaranteed unique.

Root Cause

In Objects/dictobject.c, dict_dict_fromkeys() does:

while (_PyDict_Next(iterable, &pos, &key, &oldvalue, &hash)) {
    if (insertdict(mp, Py_NewRef(key), hash, Py_NewRef(value))) { ... }
}

For a source dict with N keys, this means N calls to insertdict(), each doing a hash table probe on the target dict. The target is always empty at the start, so all these probes are guaranteed misses — pure wasted work.

Meanwhile, dict.copy() and {}.update(other) already have a fast clone path (clone_combined_dict_keys) that copies the entire PyDictKeysObject in one memcpy when the source is a clean, combined dict. dict.fromkeys() does not use this path at all.

Proposed Fix

Add a clone_combined_dict_keys_with_value() helper that works identically to clone_combined_dict_keys() but, instead of copying each entry's value from the source, fills every active slot with a new reference to the fill_value argument.

In dict_dict_fromkeys(), add a fast path: when the source dict is combined (ma_values == NULL) and compact (no deleted entries: ma_used == dk_nentries), call the new helper instead of the insertdict loop.

This reduces the cost from O(n) hash lookups to O(n) refcount bumps + one memcpy.

Benchmark

1000-key string dict, 10,000 iterations of dict.fromkeys(d, None):

Affected file

Objects/dictobject.c

Has this already been discussed elsewhere?

No response given

Links to previous discussion of this feature:

No response

Linked PRs

• gh-153229: Optimize dict.fromkeys() fast-clone path for combined dicts #153234