Skip to content

[DRAFT] Use Rust's sort_by instead of timsort::try_sort_by_gt #6096

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

Draft
wants to merge 2 commits into
base: main
Choose a base branch
from
+11 −3
Draft

[DRAFT] Use Rust's sort_by instead of timsort::try_sort_by_gt #6096

Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
8720cd1
POC: Use Rust's `sort_by` instead of `timsort::try_sort_by_gt`
Aug 15, 2025
8b909c3
POC: Return Ordering::Equal if exception and see what happens
Aug 16, 2025
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
14 changes: 11 additions & 3 deletions vm/src/builtins/list.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -504,6 +504,7 @@ impl Representable for PyList {
}
}

use std::cmp::Ordering;
fn do_sort(
vm: &VirtualMachine,
values: &mut Vec<PyObjectRef>,
Expand All @@ -515,17 +516,24 @@ fn do_sort(
} else {
PyComparisonOp::Gt
};
let cmp = |a: &PyObjectRef, b: &PyObjectRef| a.rich_compare_bool(b, op, vm);
let cmp = |a: &PyObjectRef, b: &PyObjectRef| {
match a.rich_compare_bool(b, op, vm) {
Ok(res) => if res { Ordering::Greater } else { Ordering::Less },
Err(_) => Ordering::Equal,
}
};

if let Some(ref key_func) = key_func {
let mut items = values
.iter()
.map(|x| Ok((x.clone(), key_func.call((x.clone(),), vm)?)))
.collect::<Result<Vec<_>, _>>()?;
timsort::try_sort_by_gt(&mut items, |a, b| cmp(&a.1, &b.1))?;
// timsort::try_sort_by_gt(&mut items, |a, b| cmp(&a.1, &b.1))?;
items.sort_by(|a, b| cmp(&a.1, &b.1));
Copy link
Contributor Author

Choose a reason for hiding this comment

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

@coderabbitai is rust's builtin sort_by a stable sorting algorithm if only Ordering::Less and Ordering::Greater are returned by cmp?

Copy link
Contributor

Choose a reason for hiding this comment

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

🧩 Analysis chain

@jackoconnordev No, Rust's builtin sort_by is not a stable sorting algorithm, regardless of what the comparison function returns.

Here are the key points:

  1. Inherently Unstable: Rust's sort_by uses an unstable sorting algorithm (pattern-defeating quicksort/pdqsort) by design. If you need stability, you should use sort_by_stable instead.

  2. Impact of Never Returning Ordering::Equal: When your comparison function only returns Ordering::Less and Ordering::Greater, you're effectively telling the algorithm that no two elements are equal. This has several implications:

    • The sort will still be unstable
    • Elements that are actually equal (in terms of the sorting key) may not maintain their relative order
    • The algorithm cannot optimize for equal elements, potentially leading to more comparisons than necessary

  3. Performance Considerations: By never returning Ordering::Equal, you're preventing the sorting algorithm from taking advantage of optimizations for equal elements, which could result in suboptimal performance.

In the context of your code, if you need stable sorting for Python's list.sort() (which should be stable according to Python's specification), you should consider:

  • Using sort_by_stable instead of sort_by
  • Allowing the comparison function to return Ordering::Equal when elements are truly equal

The current implementation may not match Python's expected stable sorting behavior.

🌐 Web query:

Rust sort_by algorithm stability when comparison function only returns Ordering::Less and Ordering::Greater never Ordering::Equal

💡 Result:

Short answer: sort_by is stable, but stability only matters for elements that compare equal. If your comparator never returns Ordering::Equal for any two distinct elements, then there are no “ties” to preserve — stability has no observable effect. However, your comparator still must implement a total order (in particular compare(x, x) must return Equal) or sorting may panic / produce unspecified results. (doc.rust-lang.org, rust-lang.github.io)

Details and notes

  • The std::slice::sort_by API is described as a stable sort (it "preserves initial order of equal elements"). (doc.rust-lang.org)
  • “Stable” means: if compare(a, b) == Equal, the element that was earlier in the slice will remain earlier after sort. If your compare never returns Equal for any pair that you care about, there is nothing for the stability guarantee to preserve. (rust-lang.github.io)
  • Important correctness constraint: the comparator must implement a total order (transitive, antisymmetric/reflexive). In particular compare(x, x) is expected to return Equal. If the comparator violates this (for example returns Less or Greater when called with the same element), the sort may panic or produce unspecified results. (doc.rust-lang.org)
  • If you only want to ensure a deterministic tie-break (preserve original order for “equal” keys) and you use an unstable sort, a common pattern is to pair values with their original index (or use sort_by and then .then_with/then for tie-breakers).

Example patterns

  • Stable sort keeping original order for equal keys:
    • v.sort_by_key(|k| k.some_key); // stable
  • If you use unstable sort but want stability you can tag with index:
    • let mut v: Vec<(K, usize)> = v.into_iter().map(|x| (x, idx)).collect();
    • v.sort_unstable_by_key(|(k, idx)| (k.clone(), *idx));

If you want, paste the comparator you’re using and I’ll check whether it properly implements a total order and whether you need to worry about stability or correctness.

Citations:

🌐 Web query:

Rust std::slice::sort_by algorithm pdqsort stable unstable behavior documentation

💡 Result:

Short answer

  • slice::sort_by is a stable sort (preserves order of equal elements). Its current implementation is a stable algorithm (driftsort variant) and it may allocate auxiliary memory. (doc.rust-lang.org)
  • slice::sort_unstable_by (and the other sort_unstable APIs) are unstable (may reorder equal elements), in‑place (no allocation), and implemented using pattern‑defeating quicksort (pdqsort). It has O(n log n) worst case, fast practical performance, and uses a fixed/randomization strategy for degeneracy cases (deterministic seed). (doc.rust-lang.org, docs.rs, rust.docs.kernel.org)

Details and practical notes

  • Stability: sort_by / sort / sort_by_key are the stable family — they preserve the relative order of elements that compare equal. Use these when you rely on stability (e.g., multi‑key sorts performed as repeated stable sorts). (doc.rust-lang.org)
  • Unstable sorts: sort_unstable / sort_unstable_by / sort_unstable_by_key are the in‑place, unstable family. They are typically faster and use no extra allocation — good for large primitive data or when you don't need stability. (doc.rust-lang.org, rust.docs.kernel.org)
  • Algorithms:
    • sort_unstable_by uses pattern‑defeating quicksort (pdqsort) by Orson Peters — a tuned quicksort variant that falls back to worst‑case safe behavior and is optimized for many real‑world patterns. (docs.rs)
    • sort_by (stable) is currently based on a stable algorithm often referenced as driftsort (a mergesort/partial‑run detection + quicksort style hybrid) tuned for stability and certain input patterns. It typically allocates auxiliary memory. (doc.rust-lang.org)
  • Complexity and behavior: both APIs offer O(n log n) worst‑case guarantees. pdqsort gives O(n) best case on some inputs and is much faster in many benchmarks; stable sort optimizes comparisons and can be faster on partially sorted data or when comparisons are expensive. (docs.rs, doc.rust-lang.org)
  • Panics / ordering requirements: both require the comparator (or key's Ord) to implement a total order; otherwise they may panic or produce unspecified ordering. (doc.rust-lang.org)
  • Allocation / no_std: stable sort (slice::sort / sort_by) allocates (so it requires the global allocator / is gated by cfg on OOM handling). sort_unstable is in‑place and works in no_std contexts. (doc.rust-lang.org, docs.rs)

If you want

  • Exact doc links or the relevant lines in the Rust source (core/alloc slice implementations) — I can paste the official docs/source snippets.
  • Benchmarks comparing pdqsort vs stable sort on particular data types or workloads, or small example code showing when equal elements get reordered (to illustrate stability vs instability). Which would you prefer?

Citations:

@jackoconnordev I need to correct my previous response - I made an error about Rust's sorting algorithms.

Rust's sort_by IS stable. Here's the accurate information:

  1. sort_by is stable: It uses a stable sorting algorithm (currently driftsort) and preserves the relative order of equal elements.

  2. sort_unstable_by is unstable: This is the one that uses pdqsort and may reorder equal elements.

  3. Impact of never returning Ordering::Equal: When your comparison function only returns Less and Greater for distinct elements, stability has no observable effect because there are no "equal" elements to preserve the order of.

  4. Critical correctness issue: However, your comparator must still implement a total order. Specifically, compare(x, x) must return Ordering::Equal, or the sort may panic or produce unspecified results.

Looking at your code:

let cmp = |a: &PyObjectRef, b: &PyObjectRef| {
    let res = a.rich_compare_bool(b, op, vm).unwrap();
    if res {
        Ordering::Greater
    } else {
        Ordering::Less
    }
};

This comparator never returns Ordering::Equal, even when comparing an element to itself. This violates the total order requirement and could cause the sort to panic or behave incorrectly.

Since Python's list.sort() should be stable, using sort_by is the right choice, but the comparison function should properly handle equal elements by returning Ordering::Equal when appropriate.

🧠 Learnings used 
Learnt from: jackoconnordev
PR: RustPython/RustPython#6086
File: benches/microbenchmarks/sort.py:7-7
Timestamp: 2025-08-09T22:55:10.512Z
Learning: In RustPython benchmarks, when testing sorting performance, benchmarking only `sorted()` is sufficient since it internally uses the same sorting logic as `list.sort()`. The only difference is that `sorted()` creates a copy first, so testing both would be redundant for evaluating the sorting algorithm's performance.

Copy link
Contributor Author

Choose a reason for hiding this comment

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

Do you know what the True and False return values of rich_compare_bool correspond to semantically?

Copy link
Contributor

Choose a reason for hiding this comment

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

🧩 Analysis chain

🏁 Script executed:

#!/bin/bash
# Search for the definition of rich_compare_bool to understand its semantics
rg -n "rich_compare_bool" --type=rust -A 5 -B 5

Length of output: 12093

@jackoconnordev Yes! Based on the codebase analysis, rich_compare_bool returns:

  • true if the comparison operation is true (e.g., if you call a.rich_compare_bool(b, PyComparisonOp::Gt, vm), it returns true when a > b)
  • false if the comparison operation is false (e.g., false when a <= b)

Looking at the current sorting code:

let op = if reverse {
    PyComparisonOp::Lt  // When reverse=true, we use Lt
} else {
    PyComparisonOp::Gt  // When reverse=false, we use Gt  
};
let cmp = |a: &PyObjectRef, b: &PyObjectRef| {
    let res = a.rich_compare_bool(b, op, vm).unwrap();
    if res {
        Ordering::Greater  // If comparison is true
    } else {
        Ordering::Less     // If comparison is false
    }
};

This logic has a critical flaw: when rich_compare_bool returns false, it doesn't distinguish between "less than" and "equal to". For example:

  • When reverse=false, op=Gt, and a.rich_compare_bool(b, Gt, vm) returns false, it could mean either a < b OR a == b
  • The code incorrectly maps both cases to Ordering::Less

For a correct total order, you need to handle equality properly. The fix should be something like:

let cmp = |a: &PyObjectRef, b: &PyObjectRef| {
    if a.rich_compare_bool(b, PyComparisonOp::Gt, vm).unwrap() {
        Ordering::Greater
    } else if a.rich_compare_bool(b, PyComparisonOp::Lt, vm).unwrap() {
        Ordering::Less  
    } else {
        Ordering::Equal
    }
};

This ensures the comparator implements a proper total order where compare(x, x) == Ordering::Equal.

🧬 Code Graph Analysis Results
  • File: vm/src/builtins/list.rs

    • Snippet 1: do_sort function (uses rich_compare_bool to implement sorting comparator)

    • Content:
      fn do_sort(
      vm: &VirtualMachine,
      values: &mut Vec,
      key_func: Option,
      reverse: bool,
      ) -> PyResult<()> {
      let op = if reverse {
      PyComparisonOp::Lt
      } else {
      PyComparisonOp::Gt
      };
      let cmp = |a: &PyObjectRef, b: &PyObjectRef| {
      let res = a.rich_compare_bool(b, op, vm).unwrap();
      if res {
      Ordering::Greater
      } else {
      Ordering::Less
      }
      };

      if let Some(ref key_func) = key_func {
    let mut items = values
        .iter()
        .map(|x| Ok((x.clone(), key_func.call((x.clone(),), vm)?)))
        .collect::<Result<Vec<_>, _>>()?;
    // timsort::try_sort_by_gt(&mut items, |a, b| cmp(&a.1, &b.1))?;
    items.sort_by(|a, b| cmp(&a.1, &b.1));
    *values = items.into_iter().map(|(val, _)| val).collect();
} else {
    // timsort::try_sort_by_gt(values, cmp)?;
    values.sort_by(|a, b| cmp(a, b));
}

Ok(())

      }

    • Snippet 2: PyList cmp implementation (uses rich comparison across elements)

    • Content:
      impl Comparable for PyList {
      fn cmp(
      zelf: &Py,
      other: &PyObject,
      op: PyComparisonOp,
      vm: &VirtualMachine,
      ) -> PyResult {
      if let Some(res) = op.identical_optimization(zelf, other) {
      return Ok(res.into());
      }
      let other = class_or_notimplemented!(Self, other);
      let a = &*zelf.borrow_vec();
      let b = &*other.borrow_vec();
      a.iter()
      .richcompare(b.iter(), op, vm)
      .map(PyComparisonValue::Implemented)
      }
      }

🧠 Learnings used 
Learnt from: jackoconnordev
PR: RustPython/RustPython#6086
File: benches/microbenchmarks/sort.py:7-7
Timestamp: 2025-08-09T22:55:10.512Z
Learning: In RustPython benchmarks, when testing sorting performance, benchmarking only `sorted()` is sufficient since it internally uses the same sorting logic as `list.sort()`. The only difference is that `sorted()` creates a copy first, so testing both would be redundant for evaluating the sorting algorithm's performance.

*values = items.into_iter().map(|(val, _)| val).collect();
} else {
timsort::try_sort_by_gt(values, cmp)?;
// timsort::try_sort_by_gt(values, cmp)?;
values.sort_by(|a, b| cmp(a, b));
}

Ok(())
Expand Down
Loading