Skip to content

Commit 2266ba7

Browse files
youknowoneyouknowone
authored
Add per-size tuple freelist (20 buckets × 2000 each) (#7361)
* Add per-size tuple freelist (20 buckets × 2000 each) Implement PyTuple freelist matching tuples[PyTuple_MAXSAVESIZE]: - TupleFreeList with 20 per-size buckets (sizes 1..=20, 2000 capacity each) - freelist_push uses pre-clear size hint for correct bucket selection - freelist_pop takes &Self payload to select bucket by size - Type guard in new_ref handles structseq types sharing PyTuple vtable - Add pyinner_layout<T>() helper for custom freelist Drop impls - Update freelist_pop/push signatures across all freelist types * freelist: exact type check at pop call-site Move exact-type filtering from freelist_pop implementations to the single call-site in new_ref. This prevents structseq and other subtypes from popping tuple freelist entries entirely, rather than popping and then deallocating on type mismatch. Add Context::try_genesis() that returns None during bootstrap to avoid deadlock when genesis() is called during Context initialization. * Move exact type check from freelist_push to call-site in default_dealloc Remove typ parameter from freelist_push trait signature. The exact type check is now done once at the call-site alongside the heaptype check, simplifying all freelist_push implementations. * Remove freelist_hint; call freelist_push before tp_clear By calling freelist_push before tp_clear, the payload is still intact and can be read directly (e.g. tuple element count for bucket selection). This eliminates freelist_hint and the hint parameter entirely.
1 parent 6c12152 commit 2266ba7

11 files changed

Lines changed: 129 additions & 29 deletions

File tree

‎.cspell.dict/cpython.txt‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -154,6 +154,7 @@ prec
154154
preinitialized
155155
pybuilddir
156156
pycore
157+
pyinner
157158
pydecimal
158159
Pyfunc
159160
pylifecycle

‎crates/vm/src/builtins/complex.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -58,7 +58,7 @@ impl PyPayload for PyComplex {
5858
}
5959

6060
#[inline]
61-
unsafe fn freelist_pop() -> Option<NonNull<PyObject>> {
61+
unsafe fn freelist_pop(_payload: &Self) -> Option<NonNull<PyObject>> {
6262
COMPLEX_FREELIST
6363
.try_with(|fl| {
6464
let mut list = fl.take();

‎crates/vm/src/builtins/dict.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -93,7 +93,7 @@ impl PyPayload for PyDict {
9393
}
9494

9595
#[inline]
96-
unsafe fn freelist_pop() -> Option<NonNull<PyObject>> {
96+
unsafe fn freelist_pop(_payload: &Self) -> Option<NonNull<PyObject>> {
9797
DICT_FREELIST
9898
.try_with(|fl| {
9999
let mut list = fl.take();

‎crates/vm/src/builtins/float.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -65,7 +65,7 @@ impl PyPayload for PyFloat {
6565
}
6666

6767
#[inline]
68-
unsafe fn freelist_pop() -> Option<NonNull<PyObject>> {
68+
unsafe fn freelist_pop(_payload: &Self) -> Option<NonNull<PyObject>> {
6969
FLOAT_FREELIST
7070
.try_with(|fl| {
7171
let mut list = fl.take();

‎crates/vm/src/builtins/int.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -86,7 +86,7 @@ impl PyPayload for PyInt {
8686
}
8787

8888
#[inline]
89-
unsafe fn freelist_pop() -> Option<NonNull<PyObject>> {
89+
unsafe fn freelist_pop(_payload: &Self) -> Option<NonNull<PyObject>> {
9090
INT_FREELIST
9191
.try_with(|fl| {
9292
let mut list = fl.take();

‎crates/vm/src/builtins/list.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -105,7 +105,7 @@ impl PyPayload for PyList {
105105
}
106106

107107
#[inline]
108-
unsafe fn freelist_pop() -> Option<NonNull<PyObject>> {
108+
unsafe fn freelist_pop(_payload: &Self) -> Option<NonNull<PyObject>> {
109109
LIST_FREELIST
110110
.try_with(|fl| {
111111
let mut list = fl.take();

‎crates/vm/src/builtins/range.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -101,7 +101,7 @@ impl PyPayload for PyRange {
101101
}
102102

103103
#[inline]
104-
unsafe fn freelist_pop() -> Option<NonNull<PyObject>> {
104+
unsafe fn freelist_pop(_payload: &Self) -> Option<NonNull<PyObject>> {
105105
RANGE_FREELIST
106106
.try_with(|fl| {
107107
let mut list = fl.take();

‎crates/vm/src/builtins/slice.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -76,7 +76,7 @@ impl PyPayload for PySlice {
7676
}
7777

7878
#[inline]
79-
unsafe fn freelist_pop() -> Option<NonNull<PyObject>> {
79+
unsafe fn freelist_pop(_payload: &Self) -> Option<NonNull<PyObject>> {
8080
SLICE_FREELIST
8181
.try_with(|fl| {
8282
let mut list = fl.take();

‎crates/vm/src/builtins/tuple.rs‎

Lines changed: 86 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,8 @@ use crate::{
2727
vm::VirtualMachine,
2828
};
2929
use alloc::fmt;
30+
use core::cell::Cell;
31+
use core::ptr::NonNull;
3032

3133
#[pyclass(module = false, name = "tuple", traverse = "manual")]
3234
pub struct PyTuple<R = PyObjectRef> {
@@ -53,14 +55,95 @@ unsafe impl Traverse for PyTuple {
5355
}
5456
}
5557

56-
// No freelist for PyTuple: structseq types (stat_result, struct_time, etc.)
57-
// are static subtypes sharing the same Rust payload, making type-safe reuse
58-
// impractical without a type-pointer comparison at push time.
58+
// spell-checker:ignore MAXSAVESIZE
59+
/// Per-size freelist storage for tuples, matching tuples[PyTuple_MAXSAVESIZE].
60+
/// Each bucket caches tuples of a specific element count (index = len - 1).
61+
struct TupleFreeList {
62+
buckets: [Vec<NonNull<PyObject>>; Self::MAX_SAVE_SIZE],
63+
}
64+
65+
impl TupleFreeList {
66+
/// Largest tuple size to cache on the freelist (sizes 1..=20).
67+
const MAX_SAVE_SIZE: usize = 20;
68+
const fn new() -> Self {
69+
Self {
70+
buckets: [const { Vec::new() }; Self::MAX_SAVE_SIZE],
71+
}
72+
}
73+
}
74+
75+
impl Default for TupleFreeList {
76+
fn default() -> Self {
77+
Self::new()
78+
}
79+
}
80+
81+
impl Drop for TupleFreeList {
82+
fn drop(&mut self) {
83+
// Same safety pattern as FreeList<T>::drop — free raw allocation
84+
// without running payload destructors to avoid TLS-after-destruction panics.
85+
let layout = crate::object::pyinner_layout::<PyTuple>();
86+
for bucket in &mut self.buckets {
87+
for ptr in bucket.drain(..) {
88+
unsafe {
89+
alloc::alloc::dealloc(ptr.as_ptr() as *mut u8, layout);
90+
}
91+
}
92+
}
93+
}
94+
}
95+
96+
thread_local! {
97+
static TUPLE_FREELIST: Cell<TupleFreeList> = const { Cell::new(TupleFreeList::new()) };
98+
}
99+
59100
impl PyPayload for PyTuple {
101+
const MAX_FREELIST: usize = 2000;
102+
const HAS_FREELIST: bool = true;
103+
60104
#[inline]
61105
fn class(ctx: &Context) -> &'static Py<PyType> {
62106
ctx.types.tuple_type
63107
}
108+
109+
#[inline]
110+
unsafe fn freelist_push(obj: *mut PyObject) -> bool {
111+
let len = unsafe { &*(obj as *const crate::Py<PyTuple>) }.elements.len();
112+
if len == 0 || len > TupleFreeList::MAX_SAVE_SIZE {
113+
return false;
114+
}
115+
TUPLE_FREELIST
116+
.try_with(|fl| {
117+
let mut list = fl.take();
118+
let bucket = &mut list.buckets[len - 1];
119+
let stored = if bucket.len() < Self::MAX_FREELIST {
120+
bucket.push(unsafe { NonNull::new_unchecked(obj) });
121+
true
122+
} else {
123+
false
124+
};
125+
fl.set(list);
126+
stored
127+
})
128+
.unwrap_or(false)
129+
}
130+
131+
#[inline]
132+
unsafe fn freelist_pop(payload: &Self) -> Option<NonNull<PyObject>> {
133+
let len = payload.elements.len();
134+
if len == 0 || len > TupleFreeList::MAX_SAVE_SIZE {
135+
return None;
136+
}
137+
TUPLE_FREELIST
138+
.try_with(|fl| {
139+
let mut list = fl.take();
140+
let result = list.buckets[len - 1].pop();
141+
fl.set(list);
142+
result
143+
})
144+
.ok()
145+
.flatten()
146+
}
64147
}
65148

66149
pub trait IntoPyTuple {

‎crates/vm/src/object/core.rs‎

Lines changed: 31 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -188,27 +188,32 @@ pub(super) unsafe fn default_dealloc<T: PyPayload>(obj: *mut PyObject) {
188188
);
189189
}
190190

191-
// Extract child references before deallocation to break circular refs (tp_clear)
191+
// Try to store in freelist for reuse BEFORE tp_clear, so that
192+
// size-based freelists (e.g. PyTuple) can read the payload directly.
193+
// Only exact base types (not heaptype or structseq subtypes) go into the freelist.
194+
let typ = obj_ref.class();
195+
let pushed = if T::HAS_FREELIST
196+
&& typ.heaptype_ext.is_none()
197+
&& core::ptr::eq(typ, T::class(crate::vm::Context::genesis()))
198+
{
199+
unsafe { T::freelist_push(obj) }
200+
} else {
201+
false
202+
};
203+
204+
// Extract child references to break circular refs (tp_clear).
205+
// This runs regardless of freelist push — the object's children must be released.
192206
let mut edges = Vec::new();
193207
if let Some(clear_fn) = vtable.clear {
194208
unsafe { clear_fn(obj, &mut edges) };
195209
}
196210

197-
// Try to store in freelist for reuse; otherwise deallocate.
198-
// Only exact types (not heaptype subclasses) go into the freelist,
199-
// because the pop site assumes the cached typ matches the base type.
200-
let pushed = if T::HAS_FREELIST && obj_ref.class().heaptype_ext.is_none() {
201-
unsafe { T::freelist_push(obj) }
202-
} else {
203-
false
204-
};
205211
if !pushed {
206212
// Deallocate the object memory (handles ObjExt prefix if present)
207213
unsafe { PyInner::dealloc(obj as *mut PyInner<T>) };
208214
}
209215

210216
// Drop child references - may trigger recursive destruction.
211-
// The object is already deallocated, so circular refs are broken.
212217
drop(edges);
213218

214219
// Trashcan: decrement depth and process deferred objects at outermost level
@@ -1089,6 +1094,11 @@ impl<T: PyPayload + core::fmt::Debug> PyInner<T> {
10891094
}
10901095
}
10911096

1097+
/// Returns the allocation layout for `PyInner<T>`, for use in freelist Drop impls.
1098+
pub(crate) const fn pyinner_layout<T: PyPayload>() -> core::alloc::Layout {
1099+
core::alloc::Layout::new::<PyInner<T>>()
1100+
}
1101+
10921102
/// Thread-local freelist storage for reusing object allocations.
10931103
///
10941104
/// Wraps a `Vec<*mut PyObject>`. On thread teardown, `Drop` frees raw
@@ -2168,9 +2178,9 @@ impl<T: PyPayload + crate::object::MaybeTraverse + core::fmt::Debug> PyRef<T> {
21682178
let has_dict = dict.is_some();
21692179
let is_heaptype = typ.heaptype_ext.is_some();
21702180

2171-
// Try to reuse from freelist (exact type only, no dict, no heaptype)
2181+
// Try to reuse from freelist (no dict, no heaptype)
21722182
let cached = if !has_dict && !is_heaptype {
2173-
unsafe { T::freelist_pop() }
2183+
unsafe { T::freelist_pop(&payload) }
21742184
} else {
21752185
None
21762186
};
@@ -2182,11 +2192,16 @@ impl<T: PyPayload + crate::object::MaybeTraverse + core::fmt::Debug> PyRef<T> {
21822192
(*inner).gc_bits.store(0, Ordering::Relaxed);
21832193
core::ptr::drop_in_place(&mut (*inner).payload);
21842194
core::ptr::write(&mut (*inner).payload, payload);
2185-
// typ, vtable, slots are preserved; dict is None, weak_list was
2186-
// cleared by drop_slow_inner before freelist push
2195+
// Freelist only stores exact base types (push-side filter),
2196+
// but subtypes sharing the same Rust payload (e.g. structseq)
2197+
// may pop entries. Update typ if it differs.
2198+
let cached_typ: *const Py<PyType> = &*(*inner).typ;
2199+
if core::ptr::eq(cached_typ, &*typ) {
2200+
drop(typ);
2201+
} else {
2202+
let _old = (*inner).typ.swap(typ);
2203+
}
21872204
}
2188-
// Drop the caller's typ since the cached object already holds one
2189-
drop(typ);
21902205
unsafe { NonNull::new_unchecked(inner.cast::<Py<T>>()) }
21912206
} else {
21922207
let inner = PyInner::new(payload, typ, dict);

0 commit comments

Comments
 (0)