Skip to content

Commit 8a56dd5

Browse files
youknowoneyouknowone
committed
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
1 parent a27d812 commit 8a56dd5

File tree

10 files changed

+158
-31
lines changed

10 files changed

+158
-31
lines changed

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

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -41,7 +41,7 @@ impl PyPayload for PyComplex {
4141
}
4242

4343
#[inline]
44-
unsafe fn freelist_push(obj: *mut PyObject) -> bool {
44+
unsafe fn freelist_push(obj: *mut PyObject, _hint: usize) -> bool {
4545
COMPLEX_FREELIST
4646
.try_with(|fl| {
4747
let mut list = fl.take();
@@ -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: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -76,7 +76,7 @@ impl PyPayload for PyDict {
7676
}
7777

7878
#[inline]
79-
unsafe fn freelist_push(obj: *mut PyObject) -> bool {
79+
unsafe fn freelist_push(obj: *mut PyObject, _hint: usize) -> bool {
8080
DICT_FREELIST
8181
.try_with(|fl| {
8282
let mut list = fl.take();
@@ -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: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -48,7 +48,7 @@ impl PyPayload for PyFloat {
4848
}
4949

5050
#[inline]
51-
unsafe fn freelist_push(obj: *mut PyObject) -> bool {
51+
unsafe fn freelist_push(obj: *mut PyObject, _hint: usize) -> bool {
5252
FLOAT_FREELIST
5353
.try_with(|fl| {
5454
let mut list = fl.take();
@@ -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: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -69,7 +69,7 @@ impl PyPayload for PyInt {
6969
}
7070

7171
#[inline]
72-
unsafe fn freelist_push(obj: *mut PyObject) -> bool {
72+
unsafe fn freelist_push(obj: *mut PyObject, _hint: usize) -> bool {
7373
INT_FREELIST
7474
.try_with(|fl| {
7575
let mut list = fl.take();
@@ -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: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -88,7 +88,7 @@ impl PyPayload for PyList {
8888
}
8989

9090
#[inline]
91-
unsafe fn freelist_push(obj: *mut PyObject) -> bool {
91+
unsafe fn freelist_push(obj: *mut PyObject, _hint: usize) -> bool {
9292
LIST_FREELIST
9393
.try_with(|fl| {
9494
let mut list = fl.take();
@@ -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: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -84,7 +84,7 @@ impl PyPayload for PyRange {
8484
}
8585

8686
#[inline]
87-
unsafe fn freelist_push(obj: *mut PyObject) -> bool {
87+
unsafe fn freelist_push(obj: *mut PyObject, _hint: usize) -> bool {
8888
RANGE_FREELIST
8989
.try_with(|fl| {
9090
let mut list = fl.take();
@@ -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: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,7 @@ impl PyPayload for PySlice {
5959
}
6060

6161
#[inline]
62-
unsafe fn freelist_push(obj: *mut PyObject) -> bool {
62+
unsafe fn freelist_push(obj: *mut PyObject, _hint: usize) -> bool {
6363
SLICE_FREELIST
6464
.try_with(|fl| {
6565
let mut list = fl.take();
@@ -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: 94 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,103 @@ 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 MAXFREELIST 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<*mut PyObject>; Self::MAXSAVESIZE],
63+
}
64+
65+
impl TupleFreeList {
66+
/// Largest tuple size to cache on the freelist (sizes 1..=20).
67+
const MAXSAVESIZE: usize = 20;
68+
const fn new() -> Self {
69+
Self {
70+
buckets: [const { Vec::new() }; Self::MAXSAVESIZE],
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 *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_hint(obj: *mut PyObject) -> usize {
111+
let py_tuple = unsafe { &*(obj as *const crate::Py<PyTuple>) };
112+
py_tuple.elements.len()
113+
}
114+
115+
#[inline]
116+
unsafe fn freelist_push(obj: *mut PyObject, hint: usize) -> bool {
117+
let len = hint;
118+
if len == 0 || len > TupleFreeList::MAXSAVESIZE {
119+
return false;
120+
}
121+
TUPLE_FREELIST
122+
.try_with(|fl| {
123+
let mut list = fl.take();
124+
let bucket = &mut list.buckets[len - 1];
125+
let stored = if bucket.len() < Self::MAX_FREELIST {
126+
bucket.push(obj);
127+
true
128+
} else {
129+
false
130+
};
131+
fl.set(list);
132+
stored
133+
})
134+
.unwrap_or(false)
135+
}
136+
137+
#[inline]
138+
unsafe fn freelist_pop(payload: &Self) -> Option<NonNull<PyObject>> {
139+
let len = payload.elements.len();
140+
if len == 0 || len > TupleFreeList::MAXSAVESIZE {
141+
return None;
142+
}
143+
TUPLE_FREELIST
144+
.try_with(|fl| {
145+
let mut list = fl.take();
146+
let result = list.buckets[len - 1]
147+
.pop()
148+
.map(|p| unsafe { NonNull::new_unchecked(p) });
149+
fl.set(list);
150+
result
151+
})
152+
.ok()
153+
.flatten()
154+
}
64155
}
65156

66157
pub trait IntoPyTuple {

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

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

191+
// Capture freelist bucket hint before tp_clear empties the payload.
192+
// Size-based freelists (e.g. PyTuple) need the element count for bucket selection,
193+
// but clear() replaces elements with an empty slice.
194+
let freelist_hint = if T::HAS_FREELIST {
195+
unsafe { T::freelist_hint(obj) }
196+
} else {
197+
0
198+
};
199+
191200
// Extract child references before deallocation to break circular refs (tp_clear)
192201
let mut edges = Vec::new();
193202
if let Some(clear_fn) = vtable.clear {
@@ -198,7 +207,7 @@ pub(super) unsafe fn default_dealloc<T: PyPayload>(obj: *mut PyObject) {
198207
// Only exact types (not heaptype subclasses) go into the freelist,
199208
// because the pop site assumes the cached typ matches the base type.
200209
let pushed = if T::HAS_FREELIST && obj_ref.class().heaptype_ext.is_none() {
201-
unsafe { T::freelist_push(obj) }
210+
unsafe { T::freelist_push(obj, freelist_hint) }
202211
} else {
203212
false
204213
};
@@ -1008,6 +1017,11 @@ impl<T: PyPayload + core::fmt::Debug> PyInner<T> {
10081017
}
10091018
}
10101019

1020+
/// Returns the allocation layout for `PyInner<T>`, for use in freelist Drop impls.
1021+
pub(crate) const fn pyinner_layout<T: PyPayload>() -> core::alloc::Layout {
1022+
core::alloc::Layout::new::<PyInner<T>>()
1023+
}
1024+
10111025
/// Thread-local freelist storage for reusing object allocations.
10121026
///
10131027
/// Wraps a `Vec<*mut PyObject>`. On thread teardown, `Drop` frees raw
@@ -2076,24 +2090,34 @@ impl<T: PyPayload + crate::object::MaybeTraverse + core::fmt::Debug> PyRef<T> {
20762090

20772091
// Try to reuse from freelist (exact type only, no dict, no heaptype)
20782092
let cached = if !has_dict && !is_heaptype {
2079-
unsafe { T::freelist_pop() }
2093+
unsafe { T::freelist_pop(&payload) }
20802094
} else {
20812095
None
20822096
};
20832097

20842098
let ptr = if let Some(cached) = cached {
20852099
let inner = cached.as_ptr() as *mut PyInner<T>;
2086-
unsafe {
2087-
core::ptr::write(&mut (*inner).ref_count, RefCount::new());
2088-
(*inner).gc_bits.store(0, Ordering::Relaxed);
2089-
core::ptr::drop_in_place(&mut (*inner).payload);
2090-
core::ptr::write(&mut (*inner).payload, payload);
2091-
// typ, vtable, slots are preserved; dict is None, weak_list was
2092-
// cleared by drop_slow_inner before freelist push
2100+
// Verify the cached object's type matches the requested type.
2101+
// Subtypes sharing the same Rust payload (e.g. structseq -> PyTuple)
2102+
// may pop from the base type's freelist but need a different typ.
2103+
let cached_typ = unsafe { &*(*inner).typ };
2104+
if !core::ptr::eq(cached_typ as *const _, &*typ as *const _) {
2105+
// Type mismatch (e.g. structseq cached as PyTuple) - deallocate
2106+
unsafe { PyInner::dealloc(inner) };
2107+
let inner = PyInner::new(payload, typ, dict);
2108+
unsafe { NonNull::new_unchecked(inner.cast::<Py<T>>()) }
2109+
} else {
2110+
unsafe {
2111+
core::ptr::write(&mut (*inner).ref_count, RefCount::new());
2112+
(*inner).gc_bits.store(0, Ordering::Relaxed);
2113+
core::ptr::drop_in_place(&mut (*inner).payload);
2114+
core::ptr::write(&mut (*inner).payload, payload);
2115+
// typ and vtable are preserved from the cached object
2116+
}
2117+
// Drop the caller's typ since the cached object already holds one
2118+
drop(typ);
2119+
unsafe { NonNull::new_unchecked(inner.cast::<Py<T>>()) }
20932120
}
2094-
// Drop the caller's typ since the cached object already holds one
2095-
drop(typ);
2096-
unsafe { NonNull::new_unchecked(inner.cast::<Py<T>>()) }
20972121
} else {
20982122
let inner = PyInner::new(payload, typ, dict);
20992123
unsafe { NonNull::new_unchecked(inner.cast::<Py<T>>()) }

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

Lines changed: 14 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -55,14 +55,26 @@ pub trait PyPayload: MaybeTraverse + PyThreadingConstraint + Sized + 'static {
5555
/// Maximum number of objects to keep in the freelist.
5656
const MAX_FREELIST: usize = 0;
5757

58+
/// Capture a hint value from the payload before tp_clear runs.
59+
/// Used by size-based freelists (e.g. PyTuple) to remember the element
60+
/// count before clear empties the payload.
61+
///
62+
/// # Safety
63+
/// `obj` must be a valid pointer to a `PyInner<Self>` with the payload still intact.
64+
#[inline]
65+
unsafe fn freelist_hint(_obj: *mut PyObject) -> usize {
66+
0
67+
}
68+
5869
/// Try to push a dead object onto this type's freelist for reuse.
5970
/// Returns true if the object was stored (caller must NOT free the memory).
71+
/// `hint` is the value returned by `freelist_hint` before tp_clear.
6072
///
6173
/// # Safety
6274
/// `obj` must be a valid pointer to a `PyInner<Self>` with refcount 0,
6375
/// after `drop_slow_inner` and `tp_clear` have already run.
6476
#[inline]
65-
unsafe fn freelist_push(_obj: *mut PyObject) -> bool {
77+
unsafe fn freelist_push(_obj: *mut PyObject, _hint: usize) -> bool {
6678
false
6779
}
6880

@@ -75,7 +87,7 @@ pub trait PyPayload: MaybeTraverse + PyThreadingConstraint + Sized + 'static {
7587
/// whose payload is still initialized from a previous allocation. The caller
7688
/// will drop and overwrite `payload` before reuse.
7789
#[inline]
78-
unsafe fn freelist_pop() -> Option<NonNull<PyObject>> {
90+
unsafe fn freelist_pop(_payload: &Self) -> Option<NonNull<PyObject>> {
7991
None
8092
}
8193

0 commit comments

Comments
 (0)