Specialize list.sort() comparisons for homogeneous lists - #8464
Merged
Conversation
Scan the sort keys once before sorting; when every element is exactly str, int, or float, compare wtf8 bytes / BigInt / f64 directly instead of going through rich_compare_bool dispatch, mirroring CPython's pre-sort check in listsort.c (unsafe_latin_compare and friends). Subclasses and mixed-type lists keep the generic __lt__ path.
Contributor
|
No actionable comments were generated in the recent review. 🎉 ℹ️ Recent review info⚙️ Run configurationConfiguration used: Path: .coderabbit.yml Review profile: CHILL Plan: Pro Plus Run ID: 📒 Files selected for processing (2)
🚧 Files skipped from review as they are similar to previous changes (1)
📝 WalkthroughWalkthroughList sorting now classifies keys and selects specialized comparators for homogeneous types, tuples, custom objects, and generic values. Keyed and unkeyed sorting use the new path. Tests cover Unicode, numeric, tuple, bytes, NaN, subclass, and invalid comparisons. ChangesList sort specialization
Estimated code review effort: 4 (Complex) | ~45 minutes Sequence Diagram(s)sequenceDiagram
participant Caller
participant do_sort
participant timsort_specialized
participant rich_compare_bool
Caller->>do_sort: sort keyed or unkeyed values
do_sort->>timsort_specialized: provide values and extracted keys
timsort_specialized->>timsort_specialized: classify keys and compare values
timsort_specialized->>rich_compare_bool: fall back for generic comparisons
timsort_specialized-->>do_sort: return sorted values
do_sort-->>Caller: return sorted result
Possibly related PRs
Suggested reviewers: 🚥 Pre-merge checks | ✅ 5✅ Passed checks (5 passed)
✨ Finishing Touches🧪 Generate unit tests (beta)
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. Comment |
Contributor
There was a problem hiding this comment.
Actionable comments posted: 1
🧹 Nitpick comments (2)
extra_tests/snippets/builtin_list.py (2)
254-254: 📐 Maintainability & Code Quality | 🔵 Trivial | 💤 Low valueAssert element types, not only values, for the
intsubclass case.
IntSub(1) == 1is true, so this assertion passes even if the sort loses the subclass instances. Add a type check to prove the generic fallback keeps the original objects.♻️ Proposed test change
-assert sorted([IntSub(2), 3, IntSub(1)]) == [1, 2, 3] +_sub_sorted = sorted([IntSub(2), 3, IntSub(1)]) +assert _sub_sorted == [1, 2, 3] +assert [type(x) for x in _sub_sorted] == [IntSub, IntSub, int]🤖 Prompt for AI Agents
Verify each finding against current code. Fix only still-valid issues, skip the rest with a brief reason, keep changes minimal, and validate. In `@extra_tests/snippets/builtin_list.py` at line 254, Update the assertion covering sorted IntSub values to also verify that the resulting elements retain their original IntSub/int types, not merely equal the expected numeric values. Keep the existing ordering check and use explicit type assertions to confirm the generic fallback preserves subclass instances.
245-247: 📐 Maintainability & Code Quality | 🔵 Trivial | ⚡ Quick winAdd coverage for
reverse=True,key=, and a custom__lt__tier.The assertions are correct. Three new code paths in
crates/vm/src/builtins/list.rshave no coverage here.
reverse=True:timsort_specializedswaps the comparator operands in every tier. No test exercises that branch. A reverse test also pins stability for equal elements.key=:do_sortclassifies the key vector, not the values. No test exercises the keyed specialized path.PreSort::Objectwith a Python-level__lt__: line 259 coversbytes, which uses a built-in slot. A user class that returnsNotImplementedfrom__lt__exercises the fallback inobject_lt.💚 Proposed additional tests
assert sorted([3, 1, 2], reverse=True) == [3, 2, 1] assert sorted(["b", "a", "c"], reverse=True) == ["c", "b", "a"] assert sorted([(2, 9), (1, 5), (2, 1)], reverse=True) == [(2, 9), (2, 1), (1, 5)] # reverse=True must stay stable for equal keys. pairs = [(1, "a"), (0, "b"), (1, "c")] assert sorted(pairs, key=lambda p: p[0], reverse=True) == [(1, "a"), (1, "c"), (0, "b")] # key= classifies the key vector, not the values. assert sorted(["bbb", "a", "cc"], key=len) == ["a", "cc", "bbb"] assert sorted([3, 1, 2], key=float) == [1, 2, 3] class Cmp: def __init__(self, v): self.v = v def __lt__(self, other): if not isinstance(other, Cmp): return NotImplemented return self.v < other.v def __eq__(self, other): return isinstance(other, Cmp) and self.v == other.v assert [c.v for c in sorted([Cmp(2), Cmp(1), Cmp(3)])] == [1, 2, 3]Run
pytest -vfromextra_testsafter adding these, using a debug-modecargo runfor snippet execution.As per coding guidelines: "When changes touch snippet tests, run
pytest -vfromextra_tests; use debug-modecargo runfor snippet execution."Also applies to: 250-264
🤖 Prompt for AI Agents
Verify each finding against current code. Fix only still-valid issues, skip the rest with a brief reason, keep changes minimal, and validate. In `@extra_tests/snippets/builtin_list.py` around lines 245 - 247, Extend the builtin list sorting tests around the existing sorted assertions to cover reverse=True, keyed sorting, and a custom class with Python-level __lt__ returning NotImplemented for unrelated types. Include reverse stability for equal keys and assertions that exercise both value and key-vector classification paths, then run pytest -v from extra_tests with debug-mode cargo run snippet execution.Source: Coding guidelines
🤖 Prompt for all review comments with AI agents
Verify each finding against current code. Fix only still-valid issues, skip the
rest with a brief reason, keep changes minimal, and validate.
Inline comments:
In `@crates/vm/src/builtins/list.rs`:
- Around line 813-862: Refactor the six `PreSort` arms around `timsort` to share
the reverse-aware key operand swap and sorting invocation. Add a generic helper
such as `run_timsort` that accepts `items`, `reverse`, `key`, and the
tier-specific comparator, then have each arm supply only its comparator
(`str_lt`, `int_lt`, `float_lt`, `object_lt`, `tuple_lt`, or
`rich_compare_bool`) while preserving monomorphized comparator types.
---
Nitpick comments:
In `@extra_tests/snippets/builtin_list.py`:
- Line 254: Update the assertion covering sorted IntSub values to also verify
that the resulting elements retain their original IntSub/int types, not merely
equal the expected numeric values. Keep the existing ordering check and use
explicit type assertions to confirm the generic fallback preserves subclass
instances.
- Around line 245-247: Extend the builtin list sorting tests around the existing
sorted assertions to cover reverse=True, keyed sorting, and a custom class with
Python-level __lt__ returning NotImplemented for unrelated types. Include
reverse stability for equal keys and assertions that exercise both value and
key-vector classification paths, then run pytest -v from extra_tests with
debug-mode cargo run snippet execution.
🪄 Autofix
Fix all unresolved CodeRabbit comments on this PR:
- Push a commit to this branch (recommended)
- Create a new PR with the fixes
ℹ️ Review info
⚙️ Run configuration
Configuration used: Path: .coderabbit.yml
Review profile: CHILL
Plan: Pro Plus
Run ID: ae3f2b61-acdf-41a6-9e64-440d517dd850
📒 Files selected for processing (2)
crates/vm/src/builtins/list.rsextra_tests/snippets/builtin_list.py
kyokuping
pushed a commit
to kyokuping/RustPython
that referenced
this pull request
Aug 9, 2026
…8464) * Use type-specialized comparators for homogeneous list sorts Scan the sort keys once before sorting; when every element is exactly str, int, or float, compare wtf8 bytes / BigInt / f64 directly instead of going through rich_compare_bool dispatch, mirroring CPython's pre-sort check in listsort.c (unsafe_latin_compare and friends). Subclasses and mixed-type lists keep the generic __lt__ path. * Add edge-case tests for specialized list sorts * Cache the richcompare slot for homogeneous list sorts * Specialize tuple sorts on their first elements * Apply ruff formatting to the new list sort tests * Deduplicate the reverse swap across sort dispatch arms
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
Implements CPython's pre-sort check for
list.sort(), as promised in the follow-ups of #8421.Before sorting, the keys are scanned once (O(n)); when they are homogeneous in exact type, the O(n log n) comparisons skip
rich_compare_bool's dispatch (recursion guard, subclass/reflected-op resolution, slot lookup, NotImplemented retry) and use a comparator specialized for that type. This mirrors theunsafe_latin_compare/unsafe_long_compare/unsafe_float_compare/unsafe_object_compare/unsafe_tuple_comparefamily in CPython'sObjects/listobject.c.What changed
crates/vm/src/builtins/list.rs:pre_sort_checkscans the keys (the key function results whenkey=is given, matching CPython'slo.keysscan) and picks a tier:Str,Int,Float,Object(cached richcompare slot),Tuple(with a nested tier for first elements), orGeneric.sorting.rsis untouched — specialization only decides whichis_ltclosure the existing powersort receives.timsortcall, so the comparator monomorphizes into the merge loop — no per-comparison indirect call, unlike CPython's function-pointer approach.Objecttier guards each comparison with a pointer check against the cached slot and falls back torich_compare_boolon mismatch orNotImplemented, so a stale cache can only cost speed, never correctness.Tupletier follows CPython exactly: elements are walked with==(identity shortcut included), only index 0 may use the specialized comparator (the scan verified nothing about later elements), later differences fall back to generic<, and nested tuples are not recursed into. The element-tier enum has no tuple variant, so that rule is enforced by the type system.extra_tests/snippets/builtin_list.py: non-ASCII code point order, huge ints,bool/subclass rejection, mixed-typeTypeError, NaN ordering, bytes, and five tuple cases (empty, nested, mixed first elements, ties at and past index 0).Differences from CPython, and why they hold
BigInts throughOrdis already dispatch-free, so all-int lists qualify regardless of magnitude.boolis excluded by the exact-type check (as in CPython), and subclasses never qualify since they may override__lt__.Results
Release build, best of 5, seed 42, vs CPython 3.14. "generic" is the same build with the scan defeated by one subclass element, i.e. the previous behavior on otherwise identical data.
1M elements:
300k elements, and the speedup CPython itself gets from the same trick on the same data as a cross-check that the port is faithful:
(For str/int/float the CPython-side ratios are ×1.33/×1.07/×1.53 — same pattern.) The gap vs CPython on random ints narrows from 2.4× to 1.7×.
Follow-ups
The remaining gap is dominated by two things outside this PR's scope: merges are clone-based (
T: Cloneinsorting.rs), so every element move pays an atomic refcount operation where CPython memmoves bare pointers — I plan to address this with move-based merges as a follow-up; andPyStrkeeps its bytes in a separate allocation (CPython inlines them since PEP 393), which is an object-representation question to be filed separately.Notes
Despite mirroring CPython's
unsafe_*comparator family, the port is entirely safe Rust: the invariants those comparators trust are still re-checked by cheap typed downcasts, so a violated invariant degrades to a panic or a fallback, never to undefined behavior.The
Objecttier compares function pointers, which rustc flags (unpredictable_function_pointer_comparisons). Both failure modes are harmless here: a duplicated function makes the guard fail into the fallback path (slower, still correct), and merged functions have identical bodies.Summary by CodeRabbit
New Features
list.sort()andsorted()handling for strings, numbers, tuples, custom objects, and other key types.Bug Fixes