Which function should you use to sort a slice?

Today, I want to explore different ways to sort a integer slice in Go.

We will compare three functions: slices.Sort, slices.SortFunc, and sort.Slice.

First, let’s take a look at the benchmark results.

func BenchmarkSortSlice(b *testing.B) {
 b.ReportAllocs()
 b.StopTimer()
 arr := make([]int, 1000000)
 for i := 0; i < 1000000; i++ {
  arr[i] = rand.Intn(1000)
 }
 b.StartTimer()
 for i := 0; i < b.N; i++ {
  sort.Slice(arr, func(i, j int) bool {
   return arr[i] < arr[j]
  })
 }
}

func BenchmarkSlicesSortFunc(b *testing.B) {
 b.ReportAllocs()
 b.StopTimer()
 arr := make([]int, 1000000)
 for i := 0; i < 1000000; i++ {
  arr[i] = rand.Intn(1000)
 }
 b.StartTimer()
 for i := 0; i < b.N; i++ {
  slices.SortFunc(arr, func(a, b int) int {
   return a - b
  })
 }
}

func BenchmarkSlicesSort(b *testing.B) {
 b.ReportAllocs()
 b.StopTimer()
 arr := make([]int, 1000000)
 for i := 0; i < 1000000; i++ {
  arr[i] = rand.Intn(1000)
 }
 b.StartTimer()
 for i := 0; i < b.N; i++ {
  slices.Sort(arr)
 }
}

// cpu: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
// BenchmarkSortSlice
// BenchmarkSortSlice-12               405    2796977 ns/op       56 B/op        2 allocs/op
// BenchmarkSlicesSortFunc
// BenchmarkSlicesSortFunc-12          535    2215764 ns/op        0 B/op        0 allocs/op
// BenchmarkSlicesSort
// BenchmarkSlicesSort-12             1105    1058691 ns/op        0 B/op        0 allocs/op      0 allocs/op

As you can see, when sorting an integer slice, slices.Sort performs the best, followed by slices.SortFunc, and then sort.Slice.

All of these functions are included in Go’s standard packages, but why is there a difference in performance?

sort.Slice vs slices.SortFunc

First, let’s compare sort.Slice and slices.SortFunc, both of which allow sorting with a custom function.

// sort.Slice
func Slice(x any, less func(i, j int) bool) {
 rv := reflectlite.ValueOf(x)
 swap := reflectlite.Swapper(x)
 length := rv.Len()
 limit := bits.Len(uint(length))
 pdqsort_func(lessSwap{less, swap}, 0, length, limit)
}

// slices.SortFunc
func SortFunc[S ~[]E, E any](x S, cmp func(a, b E) int) {
 n := len(x)
 pdqsortCmpFunc(x, 0, n, bits.Len(uint(n)), cmp)
}

Both functions use the pdqsort algorithm.

The difference is that sort.Slice uses the any keyword, while slices.SortFunc utilizes generics.

In my view, the only difference lies in reflectlite.ValueOf(x) and reflectlite.Swapper(x). It appears that these two methods internally call functions from the unsafe package, which may potentially lead to heap memory allocations. Allocating memory on the heap is a task with considerable overhead, which likely contributes to the observed performance degradation.

On the other hand, slices.SortFunc avoids this overhead because generics provide type safety, eliminating the need for such processes.

Functions that use generics are generated at compile time, so they don’t require reflection and thus avoid heap memory allocation. This results in better performance.

So, what is the difference between slices.SortFunc and slices.Sort?

// slices.Sort
func Sort[S ~[]E, E cmp.Ordered](x S) {
  n := len(x)
  pdqsortOrdered(x, 0, n, bits.Len(uint(n)))
}

// cmd.Ordered
type Ordered interface {
 ~int | ~int8 | ~int16 | ~int32 | ~int64 |
  ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
  ~float32 | ~float64 |
  ~string
}

func Less[T Ordered](x, y T) bool {
 return (isNaN(x) && !isNaN(y)) || x < y
}

func isNaN[T Ordered](x T) bool {
 return x != x
}

The algorithm used in slices.Sort is identical to the one in sort.Slice, and since it uses generics, no reflection occurs. Additionally, Ordered.Less is a predefined function used in slices.Sort, whereas slices.Sort accepts a function as an argument. Passing a function as an argument can introduce additional function call overhead, which may impact performance, especially when there are many comparison functions involved.

Conclusion

We have explored the three slice sorting functions provided by Go. In the past, only sort.Slice existed, which used Tim sort, though it wasn’t mentioned on this post. However, since 2022, Go has adopted pdqsort, a modern sorting algorithm that combines the fast average case performance of randomized quicksort with the efficient worst-case performance of heapsort, and achieves linear time for certain input patterns. This change improved performance, and subsequent versions, starting with Go 1.22, introduced slices.Sort and slices.SortFunc, further enhancing sorting performance.

Now, you can experience better sorting performance by using slices.Sort for sorting tasks, or slices.SortFunc when a custom comparison function is needed.

As Go continues to evolve, it is essential for us to keep an eye on these advancements.