Brtdku

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?

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.