Skip to content

freelist optimization #7337

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 7 commits into from
Mar 4, 2026
Merged

freelist optimization #7337

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
7 commits
Select commit Hold shift + click to select a range
4c030e9
Add object freelist infrastructure and PyFloat freelist
youknowone Mar 3, 2026
ad49638
Add PyList freelist and GC-safe freelist infrastructure
youknowone Mar 3, 2026
c706c9e
Add PyDict freelist and exact-type guard for freelist push
youknowone Mar 3, 2026
e4d4d11
Add PySlice freelist (max 1, matching PySlice_MAXFREELIST)
youknowone Mar 3, 2026
c0b33a6
Add FreeList<T> wrapper to drain cached objects on thread teardown
youknowone Mar 4, 2026
5b78ad5
Add manual Traverse impl for PySlice with clear() and fix comment
youknowone Mar 4, 2026
2266d94
Deduplicate allocation fallback in PyRef::new_ref
youknowone Mar 4, 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
Next Next commit
Add PySlice freelist (max 1, matching PySlice_MAXFREELIST)
  • Loading branch information
@youknowone
youknowone committed Mar 4, 2026
commit e4d4d116ce2927f54d1803f7eb033ad9d3faa553
1 change: 1 addition & 0 deletions .cspell.dict/cpython.txt
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -70,6 +70,7 @@ finalizers
firsttraceable
flowgraph
formatfloat
freelist
freevar
freevars
fromlist
Expand Down
5 changes: 2 additions & 3 deletions crates/vm/src/builtins/dict.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -62,13 +62,12 @@ impl fmt::Debug for PyDict {
}
}

const PYDICT_MAXFREELIST: usize = 80;

thread_local! {
static DICT_FREELIST: Cell<Vec<*mut PyObject>> = const { Cell::new(Vec::new()) };
}

impl PyPayload for PyDict {
const MAX_FREELIST: usize = 80;
const HAS_FREELIST: bool = true;

#[inline]
Expand All @@ -80,7 +79,7 @@ impl PyPayload for PyDict {
unsafe fn freelist_push(obj: *mut PyObject) -> bool {
DICT_FREELIST.with(|fl| {
let mut list = fl.take();
let stored = if list.len() < PYDICT_MAXFREELIST {
let stored = if list.len() < Self::MAX_FREELIST {
list.push(obj);
true
} else {
Expand Down
5 changes: 2 additions & 3 deletions crates/vm/src/builtins/float.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -34,13 +34,12 @@ impl PyFloat {
}
}

const PYFLOAT_MAXFREELIST: usize = 100;

thread_local! {
static FLOAT_FREELIST: Cell<Vec<*mut PyObject>> = const { Cell::new(Vec::new()) };
}

impl PyPayload for PyFloat {
const MAX_FREELIST: usize = 100;
const HAS_FREELIST: bool = true;

#[inline]
Expand All @@ -52,7 +51,7 @@ impl PyPayload for PyFloat {
unsafe fn freelist_push(obj: *mut PyObject) -> bool {
FLOAT_FREELIST.with(|fl| {
let mut list = fl.take();
let stored = if list.len() < PYFLOAT_MAXFREELIST {
let stored = if list.len() < Self::MAX_FREELIST {
list.push(obj);
true
} else {
Expand Down
5 changes: 2 additions & 3 deletions crates/vm/src/builtins/list.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -74,13 +74,12 @@ unsafe impl Traverse for PyList {
}
}

const PYLIST_MAXFREELIST: usize = 80;

thread_local! {
static LIST_FREELIST: Cell<Vec<*mut PyObject>> = const { Cell::new(Vec::new()) };
}

impl PyPayload for PyList {
const MAX_FREELIST: usize = 80;
const HAS_FREELIST: bool = true;

#[inline]
Expand All @@ -92,7 +91,7 @@ impl PyPayload for PyList {
unsafe fn freelist_push(obj: *mut PyObject) -> bool {
LIST_FREELIST.with(|fl| {
let mut list = fl.take();
let stored = if list.len() < PYLIST_MAXFREELIST {
let stored = if list.len() < Self::MAX_FREELIST {
list.push(obj);
true
} else {
Expand Down
34 changes: 34 additions & 0 deletions crates/vm/src/builtins/slice.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,5 +1,7 @@
// sliceobject.{h,c} in CPython
// spell-checker:ignore sliceobject
use core::cell::Cell;
use core::ptr::NonNull;
use rustpython_common::wtf8::{Wtf8Buf, wtf8_concat};

use super::{PyGenericAlias, PyStrRef, PyTupleRef, PyType, PyTypeRef};
Expand All @@ -23,11 +25,43 @@ pub struct PySlice {
pub step: Option<PyObjectRef>,
}

thread_local! {
static SLICE_FREELIST: Cell<Vec<*mut PyObject>> = const { Cell::new(Vec::new()) };
}

impl PyPayload for PySlice {
const MAX_FREELIST: usize = 1;
const HAS_FREELIST: bool = true;

#[inline]
fn class(ctx: &Context) -> &'static Py<PyType> {
ctx.types.slice_type
}

#[inline]
unsafe fn freelist_push(obj: *mut PyObject) -> bool {
SLICE_FREELIST.with(|fl| {
let mut list = fl.take();
let stored = if list.len() < Self::MAX_FREELIST {
list.push(obj);
true
} else {
false
};
fl.set(list);
stored
})
}

#[inline]
unsafe fn freelist_pop() -> Option<NonNull<PyObject>> {
SLICE_FREELIST.with(|fl| {
let mut list = fl.take();
let result = list.pop().map(|p| unsafe { NonNull::new_unchecked(p) });
fl.set(list);
result
})
}
Comment on lines +48 to +84
Copy link
Copy Markdown
Contributor

@coderabbitai coderabbitai Bot Mar 4, 2026

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

⚠️ Potential issue | 🔴 Critical

🧩 Analysis chain

🏁 Script executed:

#!/bin/bash
# Check if PySlice has a proper clear/tp_clear implementation

# Search for Traverse impl on PySlice
echo "=== PySlice Traverse implementation ==="
rg -nA 15 'impl Traverse for PySlice' crates/vm/src/builtins/slice.rs

# Check the pyclass attribute for traverse behavior
echo -e "\n=== PySlice pyclass attributes ==="
rg -nB 2 'pub struct PySlice' crates/vm/src/builtins/slice.rs

# Check if there's a manual clear implementation
echo -e "\n=== Manual clear implementations in slice.rs ==="
rg -n 'fn clear' crates/vm/src/builtins/slice.rs

# Also check the full struct definition to see field types
echo -e "\n=== Full PySlice struct definition ==="
rg -nA 10 'pub struct PySlice' crates/vm/src/builtins/slice.rs

Repository: RustPython/RustPython

Length of output: 673

🏁 Script executed:

#!/bin/bash
# Look at other PyPayload implementations with both traverse and freelist
echo "=== PyPayload implementations with freelist ==="
rg -l 'impl PyPayload' crates/vm/src/builtins/ | head -5

# Check one of them to see if they have explicit clear impls
echo -e "\n=== Example: PyTuple with traverse and freelist ==="
rg -nB 5 'TUPLE_FREELIST' crates/vm/src/builtins/tuple.rs | head -30

# Look for Traverse trait definition to understand what it provides
echo -e "\n=== Traverse trait definition ==="
rg -nA 20 'pub trait Traverse' crates/vm/object/mod.rs

# Search for how traverse macro generates clear
echo -e "\n=== Search for clear generation in macro or docs ==="
rg -n 'fn clear' crates/vm/src/builtins/tuple.rs | head -10

Repository: RustPython/RustPython

Length of output: 556

🏁 Script executed:

#!/bin/bash
# Find where Traverse trait is defined
echo "=== Locate Traverse trait ==="
rg -n 'pub trait Traverse' crates/

# Look at PyTuple's clear implementation in detail
echo -e "\n=== PyTuple clear implementation ==="
rg -nB 3 -A 10 'fn clear\(&mut self' crates/vm/src/builtins/tuple.rs

# Check if PyTuple has freelist and traverse
echo -e "\n=== PyTuple pyclass and freelist setup ==="
rg -nB 2 'pub struct PyTuple' crates/vm/src/builtins/tuple.rs | head -20

# Check what the traverse attribute does in the macro
echo -e "\n=== Search for traverse attribute handling ==="
rg -n 'traverse' crates/vm/src/builtins/tuple.rs | head -5

Repository: RustPython/RustPython

Length of output: 1097

🏁 Script executed:

#!/bin/bash
# Search for Traverse trait more broadly
echo "=== Find Traverse trait definition ==="
fd -e rs -x rg -l 'trait Traverse' {} \;

# Look at the actual imports in slice.rs to understand what's being used
echo -e "\n=== Imports in slice.rs ==="
head -20 crates/vm/src/builtins/slice.rs

# Check if there's a Traverse impl somewhere for PySlice or if it's generated
echo -e "\n=== All Traverse impls in builtins ==="
rg -n 'impl.*Traverse' crates/vm/src/builtins/slice.rs crates/vm/src/builtins/tuple.rs

# Look at other traverse implementations to understand the pattern
echo -e "\n=== Other examples with 'traverse' attribute ==="
rg -B 2 'traverse\)' crates/vm/src/builtins/weakref.rs | head -20

Repository: RustPython/RustPython

Length of output: 1091

🏁 Script executed:

#!/bin/bash
# Look at Traverse trait definition
echo "=== Traverse trait definition ==="
cat crates/vm/src/object/traverse.rs | head -60

# Check if PySlice explicitly implements Traverse anywhere
echo -e "\n=== Explicit Traverse impl for PySlice ==="
rg -n 'impl.*Traverse.*PySlice' crates/vm/src/builtins/slice.rs

# Look at the macro to see what traverse attribute generates
echo -e "\n=== Search for pyclass macro handling of traverse ==="
fd -name '*.rs' -type f crates/pyclass/ | head -5

# Check if there's auto-generation documented
echo -e "\n=== Check if traverse generates Traverse impl automatically ==="
rg -n 'unsafe impl Traverse' crates/vm/src/builtins/ | head -10

Repository: RustPython/RustPython

Length of output: 3825

🏁 Script executed:

#!/bin/bash
# Look for pyclass macro documentation or implementation
echo "=== Search for pyclass macro procedural macro code ==="
find crates -name "*.rs" -path "*pyclass*" | grep -E "(proc|macro)" | head -10

# Check if there are examples where traverse attribute auto-generates clear
echo -e "\n=== Look for generated Traverse impl patterns in builtins ==="
rg -A 8 'unsafe impl Traverse' crates/vm/src/builtins/ | grep -E '(impl Traverse|fn clear)' | head -20

# Specifically check what traverse attribute value PySlice uses vs others
echo -e "\n=== Compare traverse attribute values ==="
rg '#\[pyclass.*traverse' crates/vm/src/builtins/ | head -10

# Check if there's a default/generated Traverse impl somewhere
echo -e "\n=== Look for MaybeTraverse impl on PySlice ==="
rg -A 15 'impl MaybeTraverse' crates/vm/src/builtins/slice.rs

Repository: RustPython/RustPython

Length of output: 2607

🏁 Script executed:

#!/bin/bash
# Check if there's auto-generated Traverse impl or if it relies on MaybeTraverse
echo "=== Check for any Traverse impl for PySlice or if it's missing ==="
rg -n 'Traverse' crates/vm/src/builtins/slice.rs

# Look at how freelist_push is used in other types to see the pattern
echo -e "\n=== Example: Look at PyTuple freelist (even though commented) ==="
rg -B 5 -A 15 'freelist_push' crates/vm/src/builtins/tuple.rs | head -30

# Check how freelist_pop/push interact with Traverse in other payload types
echo -e "\n=== Look at list.rs freelist with Traverse ==="
rg -B 3 -A 15 'freelist_push' crates/vm/src/builtins/list.rs | head -35

# Check if there's any documentation about freelist and Traverse interaction
echo -e "\n=== Search for freelist documentation or comments ==="
rg -B 2 -A 2 'freelist' crates/vm/src/builtins/list.rs | head -20

Repository: RustPython/RustPython

Length of output: 1057

🏁 Script executed:

#!/bin/bash
# Check if there's any generated code or if traverse attribute is just declarative
echo "=== Search for how pyclass macro processes traverse attribute ==="
find crates -name "*.toml" | xargs grep -l "proc-macro\|proc_macro" | head -5

# Look at actual pyclass macro crate
echo -e "\n=== Find pyclass macro crate ==="
find . -type d -name "*pyclass*" | grep -v target

# Check if PySlice should have Traverse but doesn't
echo -e "\n=== Verify PySlice has NO Traverse impl anywhere ==="
rg 'unsafe impl Traverse for PySlice' crates/

# Check if there's a compile-time verification that Traverse is needed
echo -e "\n=== Look at PyPayload trait to understand freelist requirements ==="
rg -B 5 -A 25 'pub trait PyPayload' crates/vm/src/object/

# Check if there are any build/compile errors related to PySlice
echo -e "\n=== Check if PySlice Traverse impl exists in expanded macros ==="
grep -r 'impl.*Traverse.*PySlice' crates/ 2>/dev/null | head -10

Repository: RustPython/RustPython

Length of output: 2411

🏁 Script executed:

#!/bin/bash
# Check the pyclass macro implementation to understand traverse attribute handling
echo "=== Check derive crate for pyclass macro ==="
cat crates/derive/Cargo.toml | grep -A 5 "\[package\]"

# Look at the macro implementation
echo -e "\n=== Search for traverse handling in derive macro ==="
find crates/derive-impl -name "*.rs" -type f | head -10

# Check if there's code that generates Traverse impl
echo -e "\n=== Look for Traverse impl generation ==="
rg -l 'Traverse' crates/derive-impl/ | head -5

# Check whether types with just "traverse" attribute get auto-generated impl
echo -e "\n=== Look at simple types with traverse attribute ==="
rg -B 3 -A 20 '#\[pyclass.*traverse\]\]' crates/vm/src/builtins/iter.rs | head -40

# Check if iter types have Traverse impl
echo -e "\n=== Check if iter.rs types have explicit Traverse impl ==="
rg 'unsafe impl Traverse' crates/vm/src/builtins/iter.rs

Repository: RustPython/RustPython

Length of output: 969

🏁 Script executed:

#!/bin/bash
# Look at the pytraverse macro implementation
echo "=== Check pytraverse.rs which generates Traverse impls ==="
cat crates/derive-impl/src/pytraverse.rs

# Also check pyclass.rs to see how traverse attribute is handled
echo -e "\n=== Check pyclass.rs for traverse attribute handling ==="
rg -n 'traverse' crates/derive-impl/src/pyclass.rs | head -20

Repository: RustPython/RustPython

Length of output: 5653

🏁 Script executed:

#!/bin/bash
# Now check what actually happens when freelist_push is called
# Let's look at where freelist_push is called in the allocation/deallocation flow
echo "=== Search for where freelist_push is called ==="
rg -n 'freelist_push' crates/vm/src/ | head -10

# Check if tp_dealloc or similar calls clear before freelist_push
echo -e "\n=== Look at object deallocation logic ==="
rg -B 10 -A 10 'freelist_push' crates/vm/src/object/payload.rs | head -40

# Verify if the auto-generated Traverse impl includes clear or just traverse
echo -e "\n=== Check if derived Traverse includes clear method ==="
rg -A 20 'impl_pytraverse' crates/derive-impl/src/pytraverse.rs | grep -E '(clear|fn)' | head -10

Repository: RustPython/RustPython

Length of output: 1807

🏁 Script executed:

#!/bin/bash
# The key is the safety comment - let's find where tp_clear is actually called
echo "=== Search for tp_clear implementation ==="
rg -n 'tp_clear' crates/vm/src/object/ | head -20

# Look for where tp_clear is invoked before freelist_push
echo -e "\n=== Search for drop_slow_inner which is mentioned in the safety comment ==="
rg -B 5 -A 15 'drop_slow_inner' crates/vm/src/object/core.rs | head -50

# Check if Traverse::clear is explicitly called anywhere
echo -e "\n=== Check if Traverse::clear is called in deallocation ==="
rg -n 'Traverse::clear\|\.clear\(' crates/vm/src/object/core.rs | head -20

Repository: RustPython/RustPython

Length of output: 3659

🏁 Script executed:

#!/bin/bash
# Let's see the full deallocation flow to understand when clear is called
echo "=== Look at the full default_dealloc function ==="
rg -A 50 'pub\(super\) unsafe fn default_dealloc' crates/vm/src/object/core.rs | head -80

# Also check the traverse_object.rs for tp_clear implementation
echo -e "\n=== Check traverse_object.rs ==="
cat crates/vm/src/object/traverse_object.rs | head -100

Repository: RustPython/RustPython

Length of output: 5659

🏁 Script executed:

#!/bin/bash
# Check what the pyclass macro generates for try_clear
echo "=== Look at pyclass.rs MaybeTraverse generation more carefully ==="
rg -B 5 -A 30 'fn try_clear' crates/derive-impl/src/pyclass.rs

# Also check what the actual generated MaybeTraverse should look like
echo -e "\n=== Check if there's a default try_clear that calls Traverse::clear ==="
rg -n 'try_clear' crates/vm/src/object/core.rs

Repository: RustPython/RustPython

Length of output: 2069

🏁 Script executed:

#!/bin/bash
# Find the try_clear_body generation in pyclass.rs
echo "=== Find try_clear_body generation ==="
rg -B 10 'try_clear_body' crates/derive-impl/src/pyclass.rs | head -40

# Check if there's a template for what try_clear_body should be
echo -e "\n=== Search for all try_clear mentions in pyclass.rs ==="
rg -n 'try_clear' crates/derive-impl/src/pyclass.rs

Repository: RustPython/RustPython

Length of output: 1230

🏁 Script executed:

#!/bin/bash
# Get the actual try_clear_body content
echo "=== Get try_clear_body content ==="
rg -A 3 'let try_clear_body = if has_clear' crates/derive-impl/src/pyclass.rs

Repository: RustPython/RustPython

Length of output: 247

Implement explicit Traverse::clear() for PySlice to extract child references before freelist caching.

PySlice contains PyObjectRef fields (start, stop, step) and has HAS_FREELIST = true. The #[pyclass(traverse)] attribute auto-generates only the traverse() method; the default clear() implementation does nothing. Before a PySlice is pushed to the freelist, tp_clear (called during deallocation) must extract these child references to avoid caching objects with stale references. Add an explicit unsafe impl Traverse for PySlice that implements a clear() method to extract all three fields into the output vector, similar to how PyTuple, PyList, and PyDict handle this.

🤖 Prompt for AI Agents 
Verify each finding against the current code and only fix it if needed.

In `@crates/vm/src/builtins/slice.rs` around lines 28 - 64, PySlice currently has
HAS_FREELIST = true but relies on the auto-generated traverse() only, so
tp_clear won't extract its PyObjectRef fields before freelist caching; add an
explicit unsafe impl Traverse for PySlice that implements clear(&mut self, out:
&mut Vec<PyObjectRef>) and pushes self.start, self.stop, and self.step (if
present) into out (mirroring PyTuple/PyList/PyDict patterns) so child references
are removed prior to freelist_push; ensure the impl coexists with the existing
traverse() and freelist_* methods (freelist_push, freelist_pop) so tp_clear
behavior is correct before objects are cached.

}

#[pyclass(with(Comparable, Representable, Hashable))]
Expand Down
3 changes: 3 additions & 0 deletions crates/vm/src/object/payload.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -52,6 +52,9 @@ pub trait PyPayload: MaybeTraverse + PyThreadingConstraint + Sized + 'static {
/// race conditions when the object is reused.
const HAS_FREELIST: bool = false;

/// Maximum number of objects to keep in the freelist.
const MAX_FREELIST: usize = 0;

/// Try to push a dead object onto this type's freelist for reuse.
/// Returns true if the object was stored (caller must NOT free the memory).
///
Expand Down
Loading