Performance: Sorting Slice vs Sorting Type (of Slice) with Sort implementation

Question

I was playing with some code challenges and found that custom sort (implementation of sort interface) work much faster than just for raw structure of slices. Why is that? Does slice conversion to type do some megic (like converting to slice of pointers to structs)?

I made some code to test my hipotesis

package sortingexample

import (
    "sort"
    "testing"
)

// Example of struct we going to sort.

type Point struct {
    X, Y int
}

// --- Struct / Raw Data
var TestCases = []Point{
    {10, 3},
    {10, 4},
    {10, 35},
    {10, 5},
    {10, 51},
    {10, 25},
    {10, 59},
    {10, 15},
    {10, 22},
    {10, 91},
}

// Example One - Sorting Slice Directly
// somehow - slowest way to sort it.
func SortSlice(points []Point) {
    sort.Slice(points, func(i, j int) bool {
        return points[i].Y < points[j].Y
    })
}

func BenchmarkSlice(b *testing.B) {
    tmp := make([]Point, len(TestCases))
    for i := 0; i < b.N; i++ {
        copy(tmp, TestCases)
        SortSlice(tmp)
    }
}

// Example Two - Sorting Slice Directly
// much faster performance
type Points []Point

// Sort interface implementation
func (p Points) Less(i, j int) bool { return p[i].Y < p[j].Y }
func (p Points) Len() int           { return len(p) }
func (p Points) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

func SortStruct(points []Point) {
    sort.Sort(Points(points))
}

func BenchmarkStruct(b *testing.B) {
    tmp := make([]Point, len(TestCases))
    for i := 0; i < b.N; i++ {
        copy(tmp, TestCases)
        SortStruct(tmp)
    }
}

// --- Pointers
var TestCasesPoints = []*Point{
    &Point{10, 3},
    &Point{10, 4},
    &Point{10, 35},
    &Point{10, 5},
    &Point{10, 51},
    &Point{10, 25},
    &Point{10, 59},
    &Point{10, 15},
    &Point{10, 22},
    &Point{10, 91},
}

// Example Three - Sorting Slice of Pointers

func SortSlicePointers(points []*Point) {
    sort.Slice(points, func(i, j int) bool {
        return points[i].Y < points[j].Y
    })
}

func BenchmarkSlicePointers(b *testing.B) {
    tmp := make([]*Point, len(TestCasesPoints))
    for i := 0; i < b.N; i++ {
        copy(tmp, TestCasesPoints)
        SortSlicePointers(tmp)
    }
}

// Example Four - Sorting Struct (with Slice of pointers beneath it)
type PointsPointer []*Point

func (pp PointsPointer) Less(i, j int) bool { return pp[i].Y < pp[j].Y }
func (pp PointsPointer) Len() int           { return len(pp) }
func (pp PointsPointer) Swap(i, j int)      { pp[i], pp[j] = pp[j], pp[i] }

func SortStructOfSlicePointers(points []*Point) {
    sort.Sort(PointsPointer(points))
}

func BenchmarkStructOfSlicePointers(b *testing.B) {
    tmp := make([]*Point, len(TestCasesPoints))

    for i := 0; i < b.N; i++ {
        copy(tmp, TestCasesPoints)
        SortStructOfSlicePointers(tmp)
    }
}

And here are results...

> go test -bench=.
goos: darwin
goarch: amd64
BenchmarkSlice-4                     3000000           542 ns/op
BenchmarkStruct-4                    5000000           318 ns/op
BenchmarkSlicePointers-4             5000000           280 ns/op
BenchmarkStructOfSlicePointers-4     5000000           321 ns/op

It's obvious that sorting a slice of pointers will work faster, but why does custom sort implementation faster? Are there any resources I can read about it?

Answer 1

The general sort.Slice() and sort.SliceStable() functions work on any slices. You have to pass your slice value as an interface{} value, and the implementation has to use reflection (the reflect package) to access its elements and length, and to perform the swaps of elements.

In contrast, when you implement the sort.Interface type yourself, in your implementation you have access to the static type of your slice, and you can provide the implementation of the sort.Interface without relfection, this is what will make it faster.

So if performance is critical / important, always provide the sort.Interface implementation yourself. If the slices are small or performance is not important, you may use the more convenient sort.Slice() function.