vm: cap dict/set table shrink and compact holes on resize

asyncio's eager task path (and its per-task bookkeeping sets in general) repeatedly adds and discards distinct task objects from a handful of long-lived sets (_eager_tasks, _scheduled_tasks). Two dict_inner issues turned that steady-state churn into the dominant cost of async_tree_eager: 1. resize() picked a target size of `used * 2` with no floor, so once a churny set settled around 1-2 live entries it shrank to a table that the very next insert would already overflow, forcing a resize on almost every single add. Clamping to the original minimum table size (8) restores the headroom dict/set start with. 2. `entries` only ever grows (holes from deletions are never reclaimed), so resize()'s rebuild pass scanned every entry ever inserted into the dict's lifetime, not just the live ones - a set with a stable working set size but heavy churn grew this scan, and the dict's memory, without bound. resize() now compacts holes out of `entries` first, matching CPython's compacting hash table and keeping the shape-stamp fast path (which already requires a hole-free layout) reachable more often. Measured with a standalone async_tree micro-benchmark (6 levels x 6 branches, pyperformance's bm_async_tree "none"/"eager" shape) run inside one process for 10 asyncio.run() iterations, comparing medians of interleaved binary runs on an otherwise idle machine: - eager: ~2.91s -> ~0.86s median (about 3.4x) - none: ~1.98s -> ~1.23s median (about 1.6x) A single fresh-process run (no in-process accumulation) still improves by roughly 15-20% for eager, since the resize-storm from point 1 hits even a single run's worth of task churn. test_asyncio (34 files, all passing), test_dict, test_set, test_weakref, test_weakset, test_ordered_dict, test_gc, test_descr, test_class, and `cargo test -p rustpython-vm -p rustpython-stdlib` all pass. Assisted-by: Claude Code:claude-fable-5-1
youknowone · Sep 19, 2026 · Sep 7, 2026 · Sep 7, 2026 · Sep 7, 2026 · Sep 7, 2026
commit 6ed9a1a1b44e783fbfef0b9c2f3a9c9663c91fbb
diff --git a/crates/vm/src/dict_inner.rs b/crates/vm/src/dict_inner.rs
@@ -275,34 +275,52 @@ impl GenIndexes {
 
 impl<T> DictInner<T> {
     fn resize(&mut self, new_size: usize) {
+        // Never shrink below the initial minimum table size (8). Without this
+        // floor, a dict/set that repeatedly adds and removes distinct keys
+        // (e.g. asyncio's per-task bookkeeping sets) settles at a tiny table
+        // after a resize and then re-triggers a resize on almost every single
+        // insert afterward, turning O(1) inserts into a resize storm.
+        let new_size = new_size.max(8);
         let new_size = {
             let mut i = 1;
             while i < new_size {
                 i <<= 1;
             }
             i
         };
+        // Compact away holes left by deleted entries. `entries` only ever
+        // grows via `unchecked_push`, so a dict/set that repeatedly inserts
+        // and removes distinct keys (e.g. asyncio's per-task bookkeeping
+        // sets) would otherwise keep every tombstoned entry forever, making
+        // this scan - and the dict's memory footprint - grow without bound
+        // relative to the live key count. Compacting here mirrors CPython's
+        // own compacting hash table and keeps entry positions dense, which
+        // is required for the hole-free shape-stamp fast path below.
+        if self.entries.len() != self.used {
+            let mut compacted = Vec::with_capacity(self.used);
+            compacted.extend(self.entries.drain(..).filter(Option::is_some));
+            self.entries = compacted;
+        }
         self.indices = vec![IndexEntry::FREE; new_size];
         let mask = (new_size - 1) as i64;
         for (entry_idx, entry) in self.entries.iter_mut().enumerate() {
-            if let Some(entry) = entry {
-                let mut idxs = GenIndexes::new(entry.hash, mask);
-                loop {
-                    let index_index = idxs.next();
-                    unsafe {
-                        // Safety: index is always valid here
-                        // index_index is generated by idxs
-                        // entry_idx is saved one
-                        let idx = self.indices.get_unchecked_mut(index_index);
-                        if *idx == IndexEntry::FREE {
-                            *idx = IndexEntry::from_index_unchecked(entry_idx);
-                            entry.index = index_index;
-                            break;
-                        }
+            // SAFETY: compaction above removed every hole, so every slot is
+            // occupied here.
+            let entry = entry.as_mut().unwrap();
+            let mut idxs = GenIndexes::new(entry.hash, mask);
+            loop {
+                let index_index = idxs.next();
+                unsafe {
+                    // Safety: index is always valid here
+                    // index_index is generated by idxs
+                    // entry_idx is saved one
+                    let idx = self.indices.get_unchecked_mut(index_index);
+                    if *idx == IndexEntry::FREE {
+                        *idx = IndexEntry::from_index_unchecked(entry_idx);
+                        entry.index = index_index;
+                        break;
                     }
                 }
-            } else {
-                //removed entry
             }
         }
         self.filled = self.used;
@@ -336,9 +354,9 @@ impl<T> DictInner<T> {
                 self.resize(new_size)
             }
         }
-        // A resize keeps entry positions and rewrites only the index-index, so
-        // this stays the entry's index afterwards.
-        entry_index
+        // A resize may compact holes out of `entries`, shifting earlier
+        // positions, but the entry pushed above is always the last one.
+        self.entries.len() - 1
     }
 
     const fn size(&self) -> DictSize {