Skip to content

Reuse stored hashes when building a set from a set/frozenset/dict #8491

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
youknowone merged 3 commits into from
Aug 12, 2026
Merged

Reuse stored hashes when building a set from a set/frozenset/dict #8491

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
2924f86
Reuse stored hashes when building a set from a set/frozenset/dict
fregataa Aug 11, 2026
561d16b
Rename the hash-carrying variants to *_known_hash
fregataa Aug 11, 2026
e27697d
Narrow visibility of the new helpers and trim their docs
fregataa Aug 12, 2026
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Narrow visibility of the new helpers and trim their docs 
from_object() and ArgIterable::as_object() had no caller outside their own
file and crate respectively, so drop them to private and pub(crate). The
dict_inner helpers stay pub(crate) because builtins::set calls them.

Also shorten the doc comments to match the density of the surrounding
code; only insert_known_hash keeps a real note, since a wrong hash there
corrupts the table silently.

Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
  • Loading branch information
@fregataa @claude
fregataa and claude committed Aug 12, 2026
commit e27697d0a8c18a79cb1199d80bb9dd0bffd7062a
24 changes: 9 additions & 15 deletions crates/vm/src/builtins/set.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -195,20 +195,17 @@ impl PySetInner {
Ok(set)
}

/// Build a set from an arbitrary object, reusing the source's stored
/// hashes when it is a set/frozenset/dict.
pub(super) fn from_object(iterable: PyObjectRef, vm: &VirtualMachine) -> PyResult<Self> {
/// Build a set from an arbitrary object, reusing stored hashes when the
/// source is a set/frozenset/dict.
fn from_object(iterable: PyObjectRef, vm: &VirtualMachine) -> PyResult<Self> {
let set = Self::default();
set.update_internal(iterable, vm)?;
Ok(set)
}

/// Elements of `obj` paired with the hash already stored alongside them,
/// or `None` if `obj` keeps no such hashes and has to be iterated
/// generically (which calls `__hash__` on every element again).
///
/// Mirrors the `PyAnySet_Check` / `PyDict_CheckExact` fast paths in
/// CPython's `set_update_internal`.
/// Elements of `obj` with their stored hashes, or `None` if `obj` keeps
/// none and must be iterated generically. Mirrors the `PyAnySet_Check` /
/// `PyDict_CheckExact` fast paths in CPython's `set_update_internal`.
fn cached_hashes(obj: &PyObject, vm: &VirtualMachine) -> Option<Vec<(PyObjectRef, PyHash)>> {
if let Some(set) = extract_set(obj) {
Some(set.content.keys_with_hashes())
Expand Down Expand Up @@ -251,9 +248,8 @@ impl PySetInner {
Self::wrap_unhashable_error(result, needle, vm)
}

/// [`Self::contains`] for a needle whose hash was read from another
/// set/dict. Such a needle is hashable by construction, so there is no
/// set-to-frozenset retry to do.
/// [`Self::contains`] with a known hash. Such a needle came out of a
/// set/dict, so it is hashable and needs no frozenset retry.
fn contains_known_hash(
&self,
needle: &PyObject,
Expand Down Expand Up @@ -398,7 +394,7 @@ impl PySetInner {
Self::wrap_unhashable_error(result, &item, vm)
}

/// [`Self::add`] for an item whose hash was read from another set/dict.
/// [`Self::add`] with a known hash.
fn add_known_hash(&self, item: PyObjectRef, hash: PyHash, vm: &VirtualMachine) -> PyResult<()> {
let result = self.content.insert_known_hash(vm, &*item, hash, ());
Self::wrap_unhashable_error(result, &item, vm)
Expand Down Expand Up @@ -1098,8 +1094,6 @@ impl Constructor for PyFrozenSet {
}

fn py_new(_cls: &Py<PyType>, iterable: Self::Args, vm: &VirtualMachine) -> PyResult<Self> {
// built from the object itself, so a set/frozenset/dict source can
// hand over its stored hashes instead of being re-hashed
let inner = match iterable {
OptionalArg::Present(iterable) => PySetInner::from_object(iterable, vm)?,
OptionalArg::Missing => PySetInner::default(),
Expand Down
35 changes: 13 additions & 22 deletions crates/vm/src/dict_inner.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -468,11 +468,9 @@ impl<T: Clone> Dict<T> {

/// Store a key whose hash the caller already knows.
///
/// `hash` MUST be the value `key.key_hash(vm)` would return. Passing a
/// different hash corrupts the table: the entry is stored in a bucket no
/// lookup will probe, so the key silently goes missing. Only pass a hash
/// read out of another dict/set entry holding this very key object, e.g.
/// via [`Self::keys_with_hashes`].
/// `hash` must equal `key.key_hash(vm)`; a wrong one lands the entry in a
/// bucket no lookup probes, silently losing the key. Only pass a hash from
/// [`Self::keys_with_hashes`] on a container holding this same key.
pub(crate) fn insert_known_hash<K>(
&self,
vm: &VirtualMachine,
Expand Down Expand Up @@ -535,10 +533,8 @@ impl<T: Clone> Dict<T> {
self.contains_known_hash(vm, key, key_hash)
}

/// [`Self::contains`] with a caller-supplied hash.
///
/// Same contract as [`Self::insert_known_hash`]: a wrong `hash` makes the
/// lookup probe the wrong bucket and report a present key as missing.
/// [`Self::contains`] with a known hash. Same contract as
/// [`Self::insert_known_hash`].
pub(crate) fn contains_known_hash<K: DictKey + ?Sized>(
&self,
vm: &VirtualMachine,
Expand Down Expand Up @@ -730,9 +726,8 @@ impl<T: Clone> Dict<T> {
self.remove_if_exists(vm, key).map(|opt| opt.is_some())
}

/// [`Self::delete_if_exists`] with a caller-supplied hash.
///
/// Same contract as [`Self::insert_known_hash`].
/// [`Self::delete_if_exists`] with a known hash. Same contract as
/// [`Self::insert_known_hash`].
pub(crate) fn delete_if_exists_known_hash<K>(
&self,
vm: &VirtualMachine,
Expand Down Expand Up @@ -777,9 +772,8 @@ impl<T: Clone> Dict<T> {
self.remove_if_known_hash(vm, key, hash, pred)
}

/// [`Self::remove_if`] with a caller-supplied hash.
///
/// Same contract as [`Self::insert_known_hash`].
/// [`Self::remove_if`] with a known hash. Same contract as
/// [`Self::insert_known_hash`].
fn remove_if_known_hash<K, F>(
&self,
vm: &VirtualMachine,
Expand Down Expand Up @@ -811,9 +805,8 @@ impl<T: Clone> Dict<T> {
self.delete_or_insert_known_hash(vm, key, hash, value)
}

/// [`Self::delete_or_insert`] with a caller-supplied hash.
///
/// Same contract as [`Self::insert_known_hash`].
/// [`Self::delete_or_insert`] with a known hash. Same contract as
/// [`Self::insert_known_hash`].
pub(crate) fn delete_or_insert_known_hash(
&self,
vm: &VirtualMachine,
Expand Down Expand Up @@ -967,10 +960,8 @@ impl<T: Clone> Dict<T> {
.collect()
}

/// All keys paired with the hash already stored in their entry.
///
/// Lets a caller move keys into another dict/set without calling
/// `__hash__` again; see [`Self::insert_known_hash`].
/// All keys paired with the hash stored in their entry, for feeding
/// [`Self::insert_known_hash`] without re-calling `__hash__`.
pub(crate) fn keys_with_hashes(&self) -> Vec<(PyObjectRef, HashValue)> {
self.read()
.entries
Expand Down
2 changes: 1 addition & 1 deletion crates/vm/src/function/protocol.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -87,7 +87,7 @@ unsafe impl<T: Traverse> Traverse for ArgIterable<T> {

impl<T> ArgIterable<T> {
#[must_use]
pub fn as_object(&self) -> &PyObject {
pub(crate) fn as_object(&self) -> &PyObject {
&self.iterable
}

Expand Down
Loading