NotificationsYou must be signed in to change notification settings
Fork0
Star2

Commit36af639

committed

Replace sort implementations

- `slice::sort` -> driftsorthttps://github.com/Voultapher/sort-research-rs/blob/main/writeup/driftsort_introduction/text.md- `slice::sort_unstable` -> ipnsorthttps://github.com/Voultapher/sort-research-rs/blob/main/writeup/ipnsort_introduction/text.mdReplaces the sort implementations with tailor made ones that strike abalance of run-time, compile-time and binary-size, yielding run-time andcompile-time improvements. Regressing binary-size for `slice::sort`while improving it for `slice::sort_unstable`. All while upholding theexisting soft and hard safety guarantees, and even extending the softguarantees, detecting strict weak ordering violations with a high chanceand reporting it to users via a panic.In addition the implementation of `select_nth_unstable` is also adaptedas it uses `slice::sort_unstable` internals.

1 parent4313a19 commit36af639Copy full SHA for 36af639

File tree

18 files changed

+2618

-1685

lines changed

alloc/src
- slice.rs
- slice
  - tests.rs
core
- src/slice
  - mod.rs
  - sort.rs
  - sort
    - mod.rs
    - select.rs
    - shared
    - stable
    - unstable
- tests
  - lib.rs
  - slice.rs

18 files changed

+2618

-1685

lines changed

`‎alloc/src/slice.rs‎`

Lines changed: 101 additions & 108 deletions

Large diffs are not rendered by default.

`‎alloc/src/slice/tests.rs‎`

Lines changed: 13 additions & 9 deletions

Original file line number	Diff line number	Diff line change
`@@ -34,7 +34,7 @@ macro_rules! do_test {`
`34`	`34`	`}`
`35`	`35`
`36`	`36`	`let v = $input.to_owned();`
`37`		`-let _ =std::panic::catch_unwind(move \|\|{`
	`37`	`+let _ = panic::catch_unwind(move \|\|{`
`38`	`38`	`letmut v = v;`
`39`	`39`	`letmut panic_countdown = panic_countdown;`
`40`	`40`	`v.$func(\|a, b\|{`
`@@ -197,8 +197,7 @@ fn panic_safe() {`
`197`	`197`
`198`	`198`	`letmut rng =test_rng();`
`199`	`199`
`200`		-// Miri is too slow (but still need to `chain` to make the types match)
`201`		`-let lens =ifcfg!(miri){(1..10).chain(0..0)}else{(1..20).chain(70..MAX_LEN)};`
	`200`	`+let lens =ifcfg!(miri){(1..10).chain(30..36)}else{(1..20).chain(70..MAX_LEN)};`
`202`	`201`	`let moduli:&[u32] =ifcfg!(miri){&[5]}else{&[5,20,50]};`
`203`	`202`
`204`	`203`	`for lenin lens{`
`@@ -294,15 +293,20 @@ fn test_sort() {`
`294`	`293`	`}`
`295`	`294`	`}`
`296`	`295`
`297`		`-// Sort using a completely random comparison function.`
`298`		`-// This will reorder the elements somehow, but won't panic.`
`299`		`-letmut v =[0;500];`
`300`		`-for iin0..v.len(){`
	`296`	`+constORD_VIOLATION_MAX_LEN:usize =500;`
	`297`	`+letmut v =[0;ORD_VIOLATION_MAX_LEN];`
	`298`	`+for iin0..ORD_VIOLATION_MAX_LEN{`
`301`	`299`	`v[i] = iasi32;`
`302`	`300`	`}`
`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`	`+`
`304`	`308`	`v.sort();`
`305`		`-for iin0..v.len(){`
	`309`	`+for iin0..ORD_VIOLATION_MAX_LEN{`
`306`	`310`	`assert_eq!(v[i], iasi32);`
`307`	`311`	`}`
`308`	`312`

`‎core/src/slice/mod.rs‎`

Lines changed: 109 additions & 84 deletions

Large diffs are not rendered by default.

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commit36af639

File tree

18 files changed

18 files changed

`‎alloc/src/slice.rs‎`

`‎alloc/src/slice/tests.rs‎`

`‎core/src/slice/mod.rs‎`

0 commit comments