Skip to content

Commit 36af639

Browse files
committed
Replace sort implementations
- `slice::sort` -> driftsort https://github.com/Voultapher/sort-research-rs/blob/main/writeup/driftsort_introduction/text.md - `slice::sort_unstable` -> ipnsort https://github.com/Voultapher/sort-research-rs/blob/main/writeup/ipnsort_introduction/text.md Replaces the sort implementations with tailor made ones that strike a balance of run-time, compile-time and binary-size, yielding run-time and compile-time improvements. Regressing binary-size for `slice::sort` while improving it for `slice::sort_unstable`. All while upholding the existing soft and hard safety guarantees, and even extending the soft guarantees, detecting strict weak ordering violations with a high chance and reporting it to users via a panic. In addition the implementation of `select_nth_unstable` is also adapted as it uses `slice::sort_unstable` internals.
1 parent 4313a19 commit 36af639

File tree

18 files changed

+2618
-1685
lines changed

18 files changed

+2618
-1685
lines changed

alloc/src/slice.rs

+101-108
Large diffs are not rendered by default.

alloc/src/slice/tests.rs

+13-9
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,7 @@ macro_rules! do_test {
3434
}
3535

3636
let v = $input.to_owned();
37-
let _ = std::panic::catch_unwind(move || {
37+
let _ = panic::catch_unwind(move || {
3838
let mut v = v;
3939
let mut panic_countdown = panic_countdown;
4040
v.$func(|a, b| {
@@ -197,8 +197,7 @@ fn panic_safe() {
197197

198198
let mut rng = test_rng();
199199

200-
// Miri is too slow (but still need to `chain` to make the types match)
201-
let lens = if cfg!(miri) { (1..10).chain(0..0) } else { (1..20).chain(70..MAX_LEN) };
200+
let lens = if cfg!(miri) { (1..10).chain(30..36) } else { (1..20).chain(70..MAX_LEN) };
202201
let moduli: &[u32] = if cfg!(miri) { &[5] } else { &[5, 20, 50] };
203202

204203
for len in lens {
@@ -294,15 +293,20 @@ fn test_sort() {
294293
}
295294
}
296295

297-
// Sort using a completely random comparison function.
298-
// This will reorder the elements *somehow*, but won't panic.
299-
let mut v = [0; 500];
300-
for i in 0..v.len() {
296+
const ORD_VIOLATION_MAX_LEN: usize = 500;
297+
let mut v = [0; ORD_VIOLATION_MAX_LEN];
298+
for i in 0..ORD_VIOLATION_MAX_LEN {
301299
v[i] = i as i32;
302300
}
303-
v.sort_by(|_, _| *[Less, Equal, Greater].choose(&mut rng).unwrap());
301+
302+
// Sort using a completely random comparison function. This will reorder the elements *somehow*,
303+
// it may panic but the original elements must still be present.
304+
let _ = panic::catch_unwind(move || {
305+
v.sort_by(|_, _| *[Less, Equal, Greater].choose(&mut rng).unwrap());
306+
});
307+
304308
v.sort();
305-
for i in 0..v.len() {
309+
for i in 0..ORD_VIOLATION_MAX_LEN {
306310
assert_eq!(v[i], i as i32);
307311
}
308312

core/src/slice/mod.rs

+109-84
Large diffs are not rendered by default.

0 commit comments

Comments
 (0)