Reuse stored hashes in dict.fromkeys()

fregataa · claude · fregataa · commit fe77067ed6ec · 2026-08-12T22:15:33.000+09:00
dict.fromkeys() recomputed __hash__ for every key even when the source already stored a hash per entry. CPython's _PyDict_FromKeys branches on PyDict_CheckExact / PyAnySet_CheckExact and feeds the hash read from the source table straight into insertdict; RustPython always iterated generically through __setitem__. Take the same fast path in the exact-dict arm of fromkeys, reusing the insert_known_hash() / keys_with_hashes() pair added for #8489. ArgIterable::as_object() gives the pre-__iter__ object, so the dispatch needs no signature change. The checks are the exact ones CPython uses: a set or dict subclass may override __iter__, so reading its table directly would change what the call observes. exact_set_keys_with_hashes() is therefore separate from extract_set(), which stays subclass-inclusive for the set operations. Closes #8490. With #8489 already landed, test_do_not_rehash_dict_keys now passes in both directions, so its expectedFailure marker is dropped and the 4 subclasses inheriting it stop failing. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
diff --git a/Lib/test/test_set.py b/Lib/test/test_set.py
@@ -330,7 +330,6 @@ def test_cyclical_repr(self):
             name = repr(s).partition('(')[0]    # strip class name
             self.assertEqual(repr(s), '%s({%s(...)})' % (name, name))
 
-    @unittest.expectedFailure  # TODO: RUSTPYTHON
     def test_do_not_rehash_dict_keys(self):
         n = 10
         d = dict.fromkeys(map(HashCountingInt, range(n)))
diff --git a/crates/vm/src/builtins/dict.rs b/crates/vm/src/builtins/dict.rs
@@ -1,6 +1,6 @@
 use super::{
     IterStatus, PositionIterInternal, PyBaseExceptionRef, PyGenericAlias, PyMappingProxy, PySet,
-    PyStr, PyStrRef, PyTupleRef, PyType, PyTypeRef, set::PySetInner,
+    PyStr, PyStrRef, PyTupleRef, PyType, PyTypeRef, set, set::PySetInner,
 };
 use crate::common::lock::LazyLock;
 use crate::object::{Traverse, TraverseFn};
@@ -9,7 +9,7 @@ use crate::{
     TryFromObject, atomic_func,
     builtins::{PyList, PyTuple, iter::builtins_iter, type_::PyAttributes},
     class::{PyClassDef, PyClassImpl},
-    common::ascii,
+    common::{ascii, hash::PyHash},
     dict_inner::{self, DictKey},
     function::{ArgIterable, FuncArgs, KwArgs, OptionalArg, PyArithmeticValue, PyComparisonValue},
     iter::PyExactSizeIterator,
@@ -356,6 +356,20 @@ impl PyDict {
     }
 }
 
+/// Keys of `obj` with their stored hashes, or `None` if it must be iterated
+/// generically. Only exact dicts and sets qualify, as in CPython's
+/// `_PyDict_FromKeys`: a subclass may override `__iter__`.
+fn fromkeys_known_hashes(
+    obj: &PyObject,
+    vm: &VirtualMachine,
+) -> Option<Vec<(PyObjectRef, PyHash)>> {
+    if let Some(dict) = obj.downcast_ref_if_exact::<PyDict>(vm) {
+        Some(dict.entries.keys_with_hashes())
+    } else {
+        set::exact_set_keys_with_hashes(obj, vm)
+    }
+}
+
 // Python dict methods:
 #[pyclass(
     with(
@@ -384,8 +398,16 @@ impl PyDict {
         let d = PyType::call(&class, ().into(), vm)?;
         match d.downcast_exact::<Self>(vm) {
             Ok(pydict) => {
-                for key in iterable.iter(vm)? {
-                    pydict.__setitem__(key?, value.clone(), vm)?;
+                if let Some(keys) = fromkeys_known_hashes(iterable.as_object(), vm) {
+                    for (key, hash) in keys {
+                        pydict
+                            .entries
+                            .insert_known_hash(vm, &*key, hash, value.clone())?;
+                    }
+                } else {
+                    for key in iterable.iter(vm)? {
+                        pydict.__setitem__(key?, value.clone(), vm)?;
+                    }
                 }
                 Ok(pydict.into_pyref().into())
             }
diff --git a/crates/vm/src/builtins/set.rs b/crates/vm/src/builtins/set.rs
@@ -605,6 +605,23 @@ fn extract_set(obj: &PyObject) -> Option<&PySetInner> {
     })
 }
 
+/// Elements of `obj` with their stored hashes, or `None` unless `obj` is exactly
+/// a `set` or `frozenset` — `PyAnySet_CheckExact`, where [`extract_set`] is the
+/// subclass-inclusive `PyAnySet_Check`.
+pub(super) fn exact_set_keys_with_hashes(
+    obj: &PyObject,
+    vm: &VirtualMachine,
+) -> Option<Vec<(PyObjectRef, PyHash)>> {
+    let inner = obj
+        .downcast_ref_if_exact::<PySet>(vm)
+        .map(|set| &set.inner)
+        .or_else(|| {
+            obj.downcast_ref_if_exact::<PyFrozenSet>(vm)
+                .map(|frozen| &frozen.inner)
+        })?;
+    Some(inner.content.keys_with_hashes())
+}
+
 fn reduce_set(zelf: &PyObject, vm: &VirtualMachine) -> (PyTypeRef, PyTupleRef, Option<PyDictRef>) {
     (
         zelf.class().to_owned(),
