Faster sort implementation

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:

  1. Code is copied for types which are not constraints.Ordered and types which can be ordered with a less func(a, b *T) bool.
  2. API isn’t quite the same as the standard library sort.

Upsides:

  1. Roughly 2x faster

Any thoughts on speeding up the standard library sort using generics?

1 Like