Skip to content

Add per-size tuple freelist (20 buckets × 2000 each)#7361

Open
youknowone wants to merge 1 commit intoRustPython:mainfrom
youknowone:freelist-more-types
Open

Add per-size tuple freelist (20 buckets × 2000 each)#7361
youknowone wants to merge 1 commit intoRustPython:mainfrom
youknowone:freelist-more-types

Conversation

@youknowone
Copy link
Member

@youknowone youknowone commented Mar 5, 2026

Summary

  • Add TupleFreeList with 20 per-size buckets matching CPython's tuples[PyTuple_MAXSAVESIZE] (sizes 1..=20, 2000 capacity each)
  • freelist_push reads element count from the object and stores in buckets[len-1]
  • freelist_pop takes &Self payload reference to select the correct size bucket
  • Add pyinner_layout<T>() helper for custom freelist Drop impls
  • Update freelist_pop trait signature to accept &Self across all freelist types

CPython alignment

Aspect CPython RustPython
PyTuple_MAXSAVESIZE 20 TUPLE_MAXSAVESIZE = 20
Py_tuple_MAXFREELIST 2000 TUPLE_MAXFREELIST = 2000
Bucket structure tuples[20] array buckets: [Vec; 20]
Push-time type check Py_IS_TYPE(op, &PyTuple_Type) vtable dispatch (HAS_FREELIST=false for structseq) + heaptype_ext.is_none()
Index calculation Py_SIZE(op) - 1 elements.len() - 1
Empty tuple skip Implicit (singleton return) Explicit len == 0 check

Test plan

  • cargo build --release
  • cargo clippy --release
  • test_tuple — pass
  • test_structseq — pass (structseq types correctly excluded from freelist)
  • test_os, test_time, test_stat — pass (structseq-heavy tests)
  • test_sys — pass

🤖 Generated with Claude Code

Summary by CodeRabbit

  • Performance

    • Improved tuple memory management with per-size caching to reduce allocations for common small/medium tuples.
  • Refactor

    • Unified and modernized internal object reuse across several built-in types for more consistent memory reuse and safer reuse checks; no changes to external behavior.

@coderabbitai
Copy link
Contributor

coderabbitai bot commented Mar 5, 2026

Note

Reviews paused

It looks like this branch is under active development. To avoid overwhelming you with review comments due to an influx of new commits, CodeRabbit has automatically paused this review. You can configure this behavior by changing the reviews.auto_review.auto_pause_after_reviewed_commits setting.

Use the following commands to manage reviews:

  • @coderabbitai resume to resume automatic reviews.
  • @coderabbitai review to trigger a single review.

Use the checkboxes below for quick actions:

  • ▶️ Resume reviews
  • 🔍 Trigger review
📝 Walkthrough

Walkthrough

This PR revises the freelist API: adds freelist_hint, changes PyPayload::freelist_push to accept a hint and PyPayload::freelist_pop to accept a payload reference; updates call sites and core helpers; and implements a per-size, thread-local freelist for small PyTuple instances.

Changes

Cohort / File(s) Summary
Trait & Core Infrastructure
crates/vm/src/object/payload.rs, crates/vm/src/object/core.rs
Added freelist_hint(_obj) -> usize; changed freelist_push(obj, _hint: usize) and freelist_pop(_payload: &Self) signatures; added pyinner_layout<T: PyPayload>() -> Layout; updated call sites (e.g., PyRef::new_ref) to pass hint and payload reference and to handle type-mismatch on reuse.
Per-size Tuple Freelist
crates/vm/src/builtins/tuple.rs
Added TupleFreeList with per-length buckets (1..=20), TLS TUPLE_FREELIST, constants MAX_FREELIST/HAS_FREELIST, and implemented freelist_hint, freelist_push(obj, hint), and freelist_pop(&payload) to cache small tuples.
Builtin Types — Signature Updates
crates/vm/src/builtins/complex.rs, crates/vm/src/builtins/dict.rs, crates/vm/src/builtins/float.rs, crates/vm/src/builtins/int.rs, crates/vm/src/builtins/list.rs, crates/vm/src/builtins/range.rs, crates/vm/src/builtins/slice.rs
Updated impl PyPayload signatures to freelist_push(obj, _hint: usize) and freelist_pop(_payload: &Self) across multiple builtins; implementations preserved but parameters added (currently unused in many).

Sequence Diagram(s)

sequenceDiagram
    participant Caller as Caller
    participant PyRef as PyRef::new_ref
    participant Payload as T (payload)
    participant Freelist as Thread-local Freelist
    participant Alloc as Allocator

    Caller->>PyRef: request new PyRef<T>
    PyRef->>Payload: construct payload (type info)
    PyRef->>Freelist: call T::freelist_pop(&payload)
    alt freelist hit
        Freelist-->>PyRef: return cached PyObject ptr
        PyRef->>PyRef: initialize reused inner (drop caller typ if needed)
    else freelist miss
        PyRef->>Alloc: allocate PyInner<T> (pyinner_layout)
        Alloc-->>PyRef: return new PyObject
    end
    PyRef-->>Caller: return initialized PyRef<T>
Loading

Estimated code review effort

🎯 4 (Complex) | ⏱️ ~45 minutes

Possibly related PRs

Poem

🐰 I tunneled through code and tucked tuples tight,
I counted little lengths and hid them out of sight,
With hints I whisper, with payloads I know,
I stash and pop so allocations go slow—
🥕 A hop, a cache, a rabbit’s delight!

🚥 Pre-merge checks | ✅ 3
✅ Passed checks (3 passed)
Check name Status Explanation
Description Check ✅ Passed Check skipped - CodeRabbit’s high-level summary is enabled.
Title check ✅ Passed The PR title directly matches the main change: it adds a per-size tuple freelist with 20 buckets of 2000 entries each, which is the primary feature introduced in the changeset.
Docstring Coverage ✅ Passed Docstring coverage is 100.00% which is sufficient. The required threshold is 80.00%.

✏️ Tip: You can configure your own custom pre-merge checks in the settings.

✨ Finishing Touches
🧪 Generate unit tests (beta)
  • Create PR with unit tests
  • Post copyable unit tests in a comment

Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out.

❤️ Share

Comment @coderabbitai help to get the list of available commands and usage tips.

Copy link
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

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

Actionable comments posted: 1

🤖 Prompt for all review comments with AI agents
Verify each finding against the current code and only fix it if needed.

Inline comments:
In `@crates/vm/src/builtins/tuple.rs`:
- Around line 113-118: The freelist_push implementation in unsafe fn
freelist_push currently reads the tuple size from py_tuple.elements.len(), but
default_dealloc calls tp_clear (which calls PyTuple::clear) before push so
elements are already cleared and len becomes 0; change the code so the tuple
length is captured before clearing (or modify the call site to pass the
pre-clear size into freelist_push), then use that captured size for the bucket
selection and the TUPLE_MAXSAVESIZE check; ensure you still skip caching when
the original size was 0 or >TUPLE_MAXSAVESIZE and keep the rest of freelist_push
logic unchanged.

ℹ️ Review info
⚙️ Run configuration

Configuration used: Path: .coderabbit.yml

Review profile: CHILL

Plan: Pro

Run ID: 65df5403-da34-438f-9eec-53a4d53aae14

📥 Commits

Reviewing files that changed from the base of the PR and between 3b91466 and ea854ba.

📒 Files selected for processing (10)
  • crates/vm/src/builtins/complex.rs
  • crates/vm/src/builtins/dict.rs
  • crates/vm/src/builtins/float.rs
  • crates/vm/src/builtins/int.rs
  • crates/vm/src/builtins/list.rs
  • crates/vm/src/builtins/range.rs
  • crates/vm/src/builtins/slice.rs
  • crates/vm/src/builtins/tuple.rs
  • crates/vm/src/object/core.rs
  • crates/vm/src/object/payload.rs

@youknowone youknowone force-pushed the freelist-more-types branch from ea854ba to 33f54e0 Compare March 5, 2026 16:21
Copy link
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

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

♻️ Duplicate comments (1)
crates/vm/src/builtins/tuple.rs (1)

110-130: ⚠️ Potential issue | 🔴 Critical

Per-size tuple freelist is effectively bypassed at push time.

At Line 112, bucket selection uses py_tuple.elements.len(), but default_dealloc (in core.rs:191-194) calls tp_clear before freelist_push. The PyTuple::clear implementation (lines 52-55) does core::mem::take(&mut self.elements), which empties the elements. When freelist_push runs, len == 0, so lines 113-114 return false and tuples are never cached in size buckets.

To fix this, the tuple length must be captured before tp_clear runs. One approach is to store the original size in the PyTuple payload (e.g., an original_len: usize field set at construction) or pass the pre-clear size into freelist_push via a different mechanism.

,

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

In `@crates/vm/src/builtins/tuple.rs` around lines 110 - 130, freelist_push
currently reads the tuple length from py_tuple.elements, but PyTuple::clear
(called by default_dealloc) empties elements before freelist_push runs so len is
always 0; fix by capturing the tuple size before clearing and passing it to
freelist_push (or storing it in the PyTuple payload set at construction) so
bucket selection uses the pre-clear size. Update freelist_push signature (or add
original_len field) and all call sites (notably default_dealloc / tp_clear path)
to supply the original length, and keep the existing bounds check against
TupleFreeList::MAXSAVESIZE and TUPLE_FREELIST bucket logic.
🤖 Prompt for all review comments with AI agents
Verify each finding against the current code and only fix it if needed.

Duplicate comments:
In `@crates/vm/src/builtins/tuple.rs`:
- Around line 110-130: freelist_push currently reads the tuple length from
py_tuple.elements, but PyTuple::clear (called by default_dealloc) empties
elements before freelist_push runs so len is always 0; fix by capturing the
tuple size before clearing and passing it to freelist_push (or storing it in the
PyTuple payload set at construction) so bucket selection uses the pre-clear
size. Update freelist_push signature (or add original_len field) and all call
sites (notably default_dealloc / tp_clear path) to supply the original length,
and keep the existing bounds check against TupleFreeList::MAXSAVESIZE and
TUPLE_FREELIST bucket logic.

ℹ️ Review info
⚙️ Run configuration

Configuration used: Path: .coderabbit.yml

Review profile: CHILL

Plan: Pro

Run ID: 1463f3a8-1b7c-461f-9c0c-57ad8b07ed56

📥 Commits

Reviewing files that changed from the base of the PR and between ea854ba and 33f54e0.

📒 Files selected for processing (10)
  • crates/vm/src/builtins/complex.rs
  • crates/vm/src/builtins/dict.rs
  • crates/vm/src/builtins/float.rs
  • crates/vm/src/builtins/int.rs
  • crates/vm/src/builtins/list.rs
  • crates/vm/src/builtins/range.rs
  • crates/vm/src/builtins/slice.rs
  • crates/vm/src/builtins/tuple.rs
  • crates/vm/src/object/core.rs
  • crates/vm/src/object/payload.rs
🚧 Files skipped from review as they are similar to previous changes (3)
  • crates/vm/src/builtins/list.rs
  • crates/vm/src/builtins/range.rs
  • crates/vm/src/builtins/dict.rs

@youknowone youknowone force-pushed the freelist-more-types branch 3 times, most recently from 6be1e32 to 8a56dd5 Compare March 6, 2026 00:30
Copy link
Contributor

@coderabbitai coderabbitai bot left a comment

Choose a reason for hiding this comment

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

Actionable comments posted: 1

🧹 Nitpick comments (1)
crates/vm/src/builtins/tuple.rs (1)

62-63: Store NonNull<PyObject> in the buckets.

That makes the non-null invariant explicit and removes the unchecked conversion on Line 148.

♻️ Suggested cleanup
 struct TupleFreeList {
-    buckets: [Vec<*mut PyObject>; Self::MAXSAVESIZE],
+    buckets: [Vec<NonNull<PyObject>>; Self::MAXSAVESIZE],
 }
...
                 let bucket = &mut list.buckets[len - 1];
                 let stored = if bucket.len() < Self::MAX_FREELIST {
-                    bucket.push(obj);
+                    bucket.push(NonNull::new_unchecked(obj));
                     true
                 } else {
                     false
                 };
...
-                let result = list.buckets[len - 1]
-                    .pop()
-                    .map(|p| unsafe { NonNull::new_unchecked(p) });
+                let result = list.buckets[len - 1].pop();
             for ptr in bucket.drain(..) {
                 unsafe {
-                    alloc::alloc::dealloc(ptr as *mut u8, layout);
+                    alloc::alloc::dealloc(ptr.as_ptr() as *mut u8, layout);
                 }
             }

Also applies to: 125-127, 146-148

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

In `@crates/vm/src/builtins/tuple.rs` around lines 62 - 63, Change the buckets
field from Vec<*mut PyObject> to Vec<NonNull<PyObject>> (keeping the array type
[Vec<...>; Self::MAXSAVESIZE]) and update all places that push or construct
entries (e.g., where raw pointers are inserted) to create NonNull values via
NonNull::new(ptr).expect("non-null pointer") or otherwise handle the Option
instead of storing raw *mut; likewise replace the unchecked conversion at its
usage site with NonNull::as_ptr() (or .get()) to obtain a *mut when needed and
adjust any initializations/clears to work with NonNull<PyObject> instead of
*mut.
🤖 Prompt for all review comments with AI agents
Verify each finding against the current code and only fix it if needed.

Inline comments:
In `@crates/vm/src/object/core.rs`:
- Around line 2091-2119: Currently code calls T::freelist_pop(&payload) whenever
!has_dict && !is_heaptype, but that lets shared-Rust-payload subtypes (e.g.
structseq) drain base-type freelists and then get deallocated on type mismatch;
fix by only probing the freelist when the requested PyType exactly matches the
freelist bucket or by passing the requested typ into the freelist pop so it can
decline non-exact matches. Concretely, update the condition around the cached
lookup to require an exact-type match (use the existing typ variable) or change
T::freelist_pop signature to T::freelist_pop(&payload, &typ) and have it return
None if the bucket’s stored typ != typ; then remove the mismatch deallocation
path (or guard it) so freelist entries for other PyTypes are never popped.

---

Nitpick comments:
In `@crates/vm/src/builtins/tuple.rs`:
- Around line 62-63: Change the buckets field from Vec<*mut PyObject> to
Vec<NonNull<PyObject>> (keeping the array type [Vec<...>; Self::MAXSAVESIZE])
and update all places that push or construct entries (e.g., where raw pointers
are inserted) to create NonNull values via NonNull::new(ptr).expect("non-null
pointer") or otherwise handle the Option instead of storing raw *mut; likewise
replace the unchecked conversion at its usage site with NonNull::as_ptr() (or
.get()) to obtain a *mut when needed and adjust any initializations/clears to
work with NonNull<PyObject> instead of *mut.

ℹ️ Review info
⚙️ Run configuration

Configuration used: Path: .coderabbit.yml

Review profile: CHILL

Plan: Pro

Run ID: 0a5e6be4-676c-4497-8b86-e2f0b1a131e7

📥 Commits

Reviewing files that changed from the base of the PR and between 6be1e32 and 8a56dd5.

📒 Files selected for processing (10)
  • crates/vm/src/builtins/complex.rs
  • crates/vm/src/builtins/dict.rs
  • crates/vm/src/builtins/float.rs
  • crates/vm/src/builtins/int.rs
  • crates/vm/src/builtins/list.rs
  • crates/vm/src/builtins/range.rs
  • crates/vm/src/builtins/slice.rs
  • crates/vm/src/builtins/tuple.rs
  • crates/vm/src/object/core.rs
  • crates/vm/src/object/payload.rs
🚧 Files skipped from review as they are similar to previous changes (1)
  • crates/vm/src/builtins/float.rs

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
@youknowone youknowone force-pushed the freelist-more-types branch from 8a56dd5 to 417dde4 Compare March 6, 2026 00:47
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant