Unstable sorting in standard library should be faster

[matklad]

Zig Version

0.11.0-dev.2685+fac120bc3

Steps to Reproduce and Observed Behavior

Reproducible benchmark here:

https://github.com/matklad/benchmarks/tree/2b07628b8bbf5c9258c807aa8a221a0797f247b9/sort

The interesting bits:

Rust + unstable:
424.10ms

Rust + stable:
765.45ms

Zig
1.147s

By itself, the number is not surprising. Zig's sort is both stable and in place, while Rust's stable sort allocates.

However, while stable sort is a good default choice, Zig strives for optimality, so the user should be able to choose better performance if stability is not a requirement.

Expected Behavior

std.sort.sortUnstable exists and it is as fast as state of the art. I noticed that

https://github.com/alichraghi/zort/blob/67493f9412c65526fd0a5db447b52d53e282a934/src/pdqsort.zig

actually is a tiny bit faster than even Rust on my benchmark, so perhaps we can add that to stdlib? cc @alichraghi

[matklad]

Also, if you have time @orlp, it would be great to pick your brain here!

My current understanding is that https://github.com/orlp/glidesort is the current state of the art, if you have some extra memory to spare. But for cases where you don't want/can't allocate, pdq is still the champion, right?

[voroskoi]

Well, https://github.com/scandum/crumsort could be interesting, but I can not understand quadsort code, so I gave up my porting efforts.

[andrewrk]

Keeping this open since std lib hash map sorting still uses insertion sort:

zig/lib/std/mem.zig

Lines 587 to 591 in 3db3cf7

	/// TODO: currently this just calls `insertionSortContext`. The block sort implementation
	/// in this file needs to be adapted to use the sort context.
	pub fn sortContext(a: usize, b: usize, context: anytype) void {
	std.sort.insertionContext(a, b, context);
	}

[alichraghi]

there is #11117

[andrewrk]

Ah. But, isn't rust's stable sort faster than zig's, as mentioned in the issue description?

[alichraghi]

yes. rust implements timsort as their main stable sort

[matklad]

Rust’s stable sort allocates, so it’s not immediately obvious that zig stable sort can be as fast, given that it doesn’t.

[andrewrk]

Ah I see. With that in mind, nice work, @alichraghi!