The default sort package utilizes lessSwap
which is a wrapper around a sort-able object. Specifically it’s a struct defined like:
type lessSwap struct {
Less func(i, j int) bool
Swap func(i, j int)
}
This means that, on each swap and compare in the default library sort functions, we wrap slice accesses in function calls. Implementing this using generics instead is around 2x faster in my testing. See an implementation here: GitHub - jordan-bonecutter/sort: A faster implementation of Go's sort for Ordered types
Downsides:
- Code is copied for types which are not
constraints.Ordered
and types which can be ordered with aless func(a, b *T) bool
. - API isn’t quite the same as the standard library sort.
Upsides:
- Roughly 2x faster
Any thoughts on speeding up the standard library sort using generics?