# Libs Meeting 2023-02-08

###### tags: `Libs Meetings` `Minutes`

**Meeting Link**: https://meet.jit.si/rust-libs-meeting-ujepnbwg2lzqgt6wvrndwimi
**Attendees**: Amanieu, Josh Triplett, The 8472, Mara, Chris Denton, Orson Peters, Urgau

## Agenda

- Triage
- glidesort

## Triage

### Nominated

- rust.tf/107680 *Hide repr attribute from doc of types without guaranteed repr*
- (Nothing to discuss. Just an announcement.)

### Regressions

- rust.tf/107466 *MPSC Sender channel not dropping buffer when all Receivers are dropped during a thread panic unwind*
- Not a leak, just dropped at a different point.
- Marked at low priority.

## Glidesort

orlp joined us to discuss glidesort.

Current situation in Rust:

- `sort()` in `alloc`: timsort
- `sort_unstable()` in `core`: pdqsort (quicksort with tricks)

glidesort is faster than both, in most cases.

`sort_unstable()` is in `core` and can't allocate.

Proposal is to replace `sort()` but not `sort_unstable()`.

Josh: If we make sort_unstable stable, then people might start to rely on it (when called indirectly through some library that doesn't expose the `unstable` in API name).

test results: https://gist.github.com/orlp/591fa659fbca24b6733804270247af82

Right now `sort_unstable()` is preferable over `sort()` if stability is not required. But after this change, `sort()` will often be preferable if allocation is available.

Allocation:
- currently: sort() allocates space for 50% of the elements
- glidesort: does 100% until 1 megabyte. 50% for the next 1 GiB. 1/8th for anything about that.
- This is all tweakable. It needs at least 48 elements though. (Could be an issue for absolutely huge elements. (But if your `size_of<T>` is a megabyte or something, you're probably doing something wrong.))

Code size, both in source code and binary size:
- Glidesort is about 2kLOC, includes a bunch of unsafe code.
- A lot of `#[inline]` right now, resulting in larger binary sizes. But many of those might be removable without much impact on performance.
- Didn't run binary size benchmarks yet.

Other relevant work going on: https://github.com/Voultapher/sort-research-rs :
- More focus on code size.
- Difference with glidesort:
- interior mutablity/panic safety:
- glidesort takes this into account everywhere with Drop impls for internal state
- this other work copies the entire state and drops/cancels the whole operation on panic.
- glidesort handles many duplicates much better

Glidesort's worst case is O(N log N). Average case is O(N log K), where K is the amount of unique values. Optimal case is O(N), e.g. for a presorted array or two presorted arrays that get merged.

Stable sort on `core` (without alloc) is possible with a fixed stack buffer, but then the complexity becomes O(N (log N)^2)

Glidesort makes use of tricks that work well on architectures that can do instructions in parallel, merging multiple things at once etc. But on architectures that just execute one instruction at a time, that might actually slow things down a bit.

Orson notes: Rust has likely() and unlikely(), but not unpredictable(). (llvm has it)

Mara: If we do this, do we expect sort_unstable() to outperform sort() again in the future after improvements to sort_unstable? It might become hard to give clear advice on when to prefer one over the other.

Josh: Where does the name "glidesort" come from?
Orson: birds. (only flapping wings when necessary, gliding otherwise)

Initial binary size tests don't look great, but can be improved a lot. No proper numbers yet. But probably not a big concern for `std`.

Orson: Lots of low-hanging fruit on binary size, will look at that.

Potential concerns:

Mara: We need figure out the story around `sort_unstable` and core vs alloc. (Binary size is very relevant for no_std.) Do we need four versions (stable/unstable and alloc/no alloc)?

Josh: Add a 'medium big' benchmark to see where the crossover point is.