Skip to content

Specialize list.sort() comparisons for homogeneous lists #8463

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

Closed
kangdora wants to merge 11 commits into from
Closed

Specialize list.sort() comparisons for homogeneous lists #8463

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
11 commits
Select commit Hold shift + click to select a range
6e1c04e
Add powersort implementation for list sorting
kangdora Jul 31, 2026
5b52036
Use powersort for list.sort() and drop rust-timsort
kangdora Jul 31, 2026
e5a5247
Fix usize underflow in merge_hi Succeed path
kangdora Jul 31, 2026
189e6e7
Fix clippy warnings and formatting in sorting.rs
kangdora Jul 31, 2026
526820b
Drop redundant test_ prefixes in sorting tests
kangdora Aug 1, 2026
ecbda8e
Restore buffered elements when a comparison fails mid-merge
kangdora Aug 1, 2026
b4fda72
Copy one run-A element per gallop round in merge_lo
kangdora Aug 1, 2026
6a153dd
Use type-specialized comparators for homogeneous list sorts
kangdora Aug 5, 2026
b92659d
Add edge-case tests for specialized list sorts
kangdora Aug 5, 2026
3010dd4
Cache the richcompare slot for homogeneous list sorts
kangdora Aug 5, 2026
fc58bdf
Specialize tuple sorts on their first elements
kangdora Aug 5, 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
Restore buffered elements when a comparison fails mid-merge
  • Loading branch information
@kangdora
kangdora committed Aug 1, 2026
commit ecbda8e5a52eaa84d078b04a389c04b738def05c
5 changes: 4 additions & 1 deletion crates/vm/src/builtins/list.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -642,7 +642,10 @@ fn do_sort(
reverse: bool,
) -> PyResult<()> {
// CPython uses __lt__ for all comparisons in sort.
// try_sort_by_gt expects is_gt(a, b) = true when a should come AFTER b.
// `timsort` expects is_lt(a, b) = true when a must be placed BEFORE b.
// For reverse=True, swapping the operands yields a descending order that is
// still stable in the original relative order, matching CPython's
// reverse-sort-reverse approach.
let mut is_lt = |a: &PyObjectRef, b: &PyObjectRef| {
if reverse {
b.rich_compare_bool(a, PyComparisonOp::Lt, vm)
Expand Down
141 changes: 67 additions & 74 deletions crates/vm/src/sorting.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2,12 +2,16 @@
const MIN_GALLOP: usize = 7;
const MAX_MINRUN: usize = 64;

enum Breakout {
enum LoBreakout {
Succeed,
CopyA,
CopyB,
}

enum HiBreakout {
Succeed,
CopyA,
}

#[derive(Clone, Copy)]
struct Run {
base: usize,
Expand Down Expand Up @@ -62,23 +66,25 @@ impl<T: Clone> MergeState<T> {
}

let mut min_gallop = self.min_gallop;
let mut breakout: Option<Breakout> = None;

loop {
let breakout: Result<LoBreakout, E> = 'merging: loop {
let mut a_count = 0;
let mut b_count = 0;

loop {
if is_lt(&values[cursor_b], &self.buf[cursor_a])? {
let b_wins = match is_lt(&values[cursor_b], &self.buf[cursor_a]) {
Ok(v) => v,
Err(e) => break 'merging Err(e),
};
if b_wins {
values[dest] = values[cursor_b].clone();
dest += 1;
cursor_b += 1;
len_b -= 1;
b_count += 1;
a_count = 0;
if len_b == 0 {
breakout = Some(Breakout::Succeed);
break;
break 'merging Ok(LoBreakout::Succeed);
}
if b_count >= min_gallop {
break;
Expand All @@ -91,90 +97,84 @@ impl<T: Clone> MergeState<T> {
a_count += 1;
b_count = 0;
if len_a == 1 {
breakout = Some(Breakout::CopyB);
break;
break 'merging Ok(LoBreakout::CopyB);
}
if a_count >= min_gallop {
break;
}
}
}

if breakout.is_some() {
break;
}

min_gallop += 1;
loop {
if min_gallop > 1 {
min_gallop -= 1;
}
self.min_gallop = min_gallop;
let mut k = gallop_right(&self.buf, is_lt, &values[cursor_b], cursor_a, len_a, 0)?;
let mut k =
match gallop_right(&self.buf, is_lt, &values[cursor_b], cursor_a, len_a, 0) {
Ok(k) => k,
Err(e) => break 'merging Err(e),
};
a_count = k;
if k > 0 {
values[dest..dest + k].clone_from_slice(&self.buf[cursor_a..cursor_a + k]);
dest += k;
cursor_a += k;
len_a -= k;
if len_a == 1 {
breakout = Some(Breakout::CopyB);
break;
break 'merging Ok(LoBreakout::CopyB);
}
if len_a == 0 {
breakout = Some(Breakout::Succeed);
break;
break 'merging Ok(LoBreakout::Succeed);
}
}
values[dest] = values[cursor_b].clone();
dest += 1;
cursor_b += 1;
len_b -= 1;
if len_b == 0 {
breakout = Some(Breakout::Succeed);
break;
break 'merging Ok(LoBreakout::Succeed);
}
k = gallop_left(values, is_lt, &self.buf[cursor_a], cursor_b, len_b, 0)?;
k = match gallop_left(values, is_lt, &self.buf[cursor_a], cursor_b, len_b, 0) {
Ok(k) => k,
Err(e) => break 'merging Err(e),
};
b_count = k;
if k > 0 {
copy_within_clone(values, cursor_b, dest, k);
dest += k;
cursor_b += k;
len_b -= k;
if len_b == 0 {
breakout = Some(Breakout::Succeed);
break;
break 'merging Ok(LoBreakout::Succeed);
}
}
if len_a == 1 {
breakout = Some(Breakout::CopyB);
break;
break 'merging Ok(LoBreakout::CopyB);
}
if a_count < MIN_GALLOP && b_count < MIN_GALLOP {
break;
}
}
if breakout.is_some() {
break;
}

min_gallop += 1;
self.min_gallop = min_gallop;
}
};

match breakout {
Some(Breakout::Succeed) => {
Ok(LoBreakout::CopyB) => {
copy_within_clone(values, cursor_b, dest, len_b);
values[dest + len_b] = self.buf[cursor_a].clone();
Ok(())
}
other => {
if len_a > 0 {
values[dest..dest + len_a]
.clone_from_slice(&self.buf[cursor_a..cursor_a + len_a]);
}
Ok(())
other.map(|_| ())
}
Some(Breakout::CopyB) => {
copy_within_clone(values, cursor_b, dest, len_b);
values[dest + len_b] = self.buf[cursor_a].clone();
Ok(())
}
_ => unreachable!(),
}
}

Expand Down Expand Up @@ -220,21 +220,22 @@ impl<T: Clone> MergeState<T> {
}

let mut min_gallop = self.min_gallop;
let mut breakout: Option<Breakout> = None;

loop {
let breakout: Result<HiBreakout, E> = 'merging: loop {
let mut a_count = 0;
let mut b_count = 0;

loop {
if is_lt(&self.buf[cursor_b], &values[cursor_a])? {
let b_wins = match is_lt(&self.buf[cursor_b], &values[cursor_a]) {
Ok(v) => v,
Err(e) => break 'merging Err(e),
};
if b_wins {
values[dest] = values[cursor_a].clone();
dest -= 1;
len_a -= 1;

if len_a == 0 {
breakout = Some(Breakout::Succeed);
break;
break 'merging Ok(HiBreakout::Succeed);
}

cursor_a -= 1;
Expand All @@ -252,42 +253,39 @@ impl<T: Clone> MergeState<T> {
b_count += 1;
a_count = 0;
if len_b == 1 {
breakout = Some(Breakout::CopyA);
break;
break 'merging Ok(HiBreakout::CopyA);
}
if b_count >= min_gallop {
break;
}
}
}

if breakout.is_some() {
break;
}

min_gallop += 1;
loop {
if min_gallop > 1 {
min_gallop -= 1;
}
self.min_gallop = min_gallop;
let mut k = gallop_right(
let mut k = match gallop_right(
values,
is_lt,
&self.buf[cursor_b],
start_a,
len_a,
len_a - 1,
)?;
) {
Ok(k) => k,
Err(e) => break 'merging Err(e),
};
k = len_a - k;
a_count = k;
if k > 0 {
copy_within_clone(values, cursor_a + 1 - k, dest + 1 - k, k);
dest -= k;
len_a -= k;
if len_a == 0 {
breakout = Some(Breakout::Succeed);
break;
break 'merging Ok(HiBreakout::Succeed);
}
cursor_a -= k;
}
Expand All @@ -296,10 +294,12 @@ impl<T: Clone> MergeState<T> {
cursor_b -= 1;
len_b -= 1;
if len_b == 1 {
breakout = Some(Breakout::CopyA);
break;
break 'merging Ok(HiBreakout::CopyA);
}
k = gallop_left(&self.buf, is_lt, &values[cursor_a], 0, len_b, len_b - 1)?;
k = match gallop_left(&self.buf, is_lt, &values[cursor_a], 0, len_b, len_b - 1) {
Ok(k) => k,
Err(e) => break 'merging Err(e),
};
k = len_b - k;
b_count = k;
if k > 0 {
Expand All @@ -309,23 +309,20 @@ impl<T: Clone> MergeState<T> {
len_b -= k;

if len_b == 0 {
breakout = Some(Breakout::Succeed);
break;
break 'merging Ok(HiBreakout::Succeed);
}
cursor_b -= k;

if len_b == 1 {
breakout = Some(Breakout::CopyA);
break;
break 'merging Ok(HiBreakout::CopyA);
}
}
values[dest] = values[cursor_a].clone();
dest -= 1;
len_a -= 1;

if len_a == 0 {
breakout = Some(Breakout::Succeed);
break;
break 'merging Ok(HiBreakout::Succeed);
}

cursor_a -= 1;
Expand All @@ -334,28 +331,24 @@ impl<T: Clone> MergeState<T> {
break;
}
}
if breakout.is_some() {
break;
}
min_gallop += 1;
self.min_gallop = min_gallop;
}
};

match breakout {
Some(Breakout::Succeed) => {
if len_b > 0 {
values[(dest + 1) - len_b..=dest].clone_from_slice(&self.buf[0..len_b]);
}
Ok(())
}
Some(Breakout::CopyA) => {
Ok(HiBreakout::CopyA) => {
let src = cursor_a + 1 - len_a;
let dst = dest + 1 - len_a;
copy_within_clone(values, src, dst, len_a);
values[dst - 1] = self.buf[cursor_b].clone();
Ok(())
}
_ => unreachable!(),
other => {
if len_b > 0 {
values[(dest + 1) - len_b..=dest].clone_from_slice(&self.buf[0..len_b]);
}
other.map(|_| ())
}
}
}

Expand Down