Summary
Follow-up to #8421. The sorting algorithm now matches CPython's powersort, but every comparison still goes through full rich_compare_bool dispatch. Most of CPython's remaining speed advantage on list.sort() comes from its pre-scan type specialization, not from the algorithm itself.
Details
CPython's listsort.c scans the list once before sorting and, when every element is the same exact type, swaps the generic safe_object_compare for a direct comparison function that skips method dispatch entirely:
unsafe_long_compare for intunsafe_latin_compare for latin-1 strunsafe_float_compare for floatunsafe_tuple_compare for tuples of the above
Plan for RustPython:
- Implement the pre-scan and specialized comparators in
do_sort (crates/vm/src/builtins/list.rs), where the comparison closure is built — crates/vm/src/sorting.rs stays generic over is_lt.
- When
key= is used, apply the scan to the key vector instead of the elements.
- Correctness guard: any subclass (which may override
__lt__) must fall back to the generic path, matching CPython's exact-type check.
The O(n) scan is negligible next to the O(n log n) comparisons it speeds up. I'd validate with benchmarks across sizes (1k / 100k / 1M) and element types (int / float / str / arbitrary objects).
Summary
Follow-up to #8421. The sorting algorithm now matches CPython's powersort, but every comparison still goes through full
rich_compare_booldispatch. Most of CPython's remaining speed advantage onlist.sort()comes from its pre-scan type specialization, not from the algorithm itself.Details
CPython's
listsort.cscans the list once before sorting and, when every element is the same exact type, swaps the genericsafe_object_comparefor a direct comparison function that skips method dispatch entirely:unsafe_long_compareforintunsafe_latin_comparefor latin-1strunsafe_float_compareforfloatunsafe_tuple_comparefor tuples of the abovePlan for RustPython:
do_sort(crates/vm/src/builtins/list.rs), where the comparison closure is built —crates/vm/src/sorting.rsstays generic overis_lt.key=is used, apply the scan to the key vector instead of the elements.__lt__) must fall back to the generic path, matching CPython's exact-type check.The O(n) scan is negligible next to the O(n log n) comparisons it speeds up. I'd validate with benchmarks across sizes (1k / 100k / 1M) and element types (int / float / str / arbitrary objects).