优化GO语言sort.Slice排序

介绍

众所周知，go对复杂Slice排序有两种方法，分别是：

  1. sort.Slice(x any, cmp func(i, j int))
  2. 实现sort.Interface接口，调用sort.Sort()进行排序

今天在写Gazelle时候，写到了一个需要Slice排序的场景。突发奇想，将上列两种方法对比，哪一种速度更快。Ps. Benchmark写法和go test -bench命令自行百度

开始

新建一个sort_test.go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

package sort

import (
	"sort"
	"testing"
)

type testSlice []struct {
	order int
}

func (t testSlice) Len() int {
	return len(t)
}

func (t testSlice) Less(i, j int) bool {
	// > 是倒序
	// < 是升序
	return t[i].order < t[j].order
}

func (t testSlice) Swap(i, j int) {
	t[i], t[j] = t[j], t[i]
}

func BenchmarkSort(b *testing.B) {

	getSliceFn := func() testSlice {
		return []struct {
			order int
		}{
			{order: 9},
			{order: 1},
			{order: 20},
			{order: 30},
			{order: 86},
			{order: 2},
		}
	}

	b.Run("interface", func(b *testing.B) {
		b.ResetTimer()

		for i := 0; i < b.N; i++ {
			ss := getSliceFn()
			sort.Sort(ss)
		}
	})

	b.Run("slice", func(b *testing.B) {
		b.ResetTimer()

		for i := 0; i < b.N; i++ {
			ss := getSliceFn()
			sort.Slice(ss, func(i, j int) bool {
				return ss[i].order > ss[j].order
			})
		}
	})
}

执行benchmark查看指标

1

go test -bench=BenchmarkSort -benchmem -count=3 ./...

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

goos: darwin
goarch: amd64
pkg: github.com/lazychanger/gazelle/pkg/utils/sort
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
BenchmarkSort/interface-16              10207401                98.83 ns/op           72 B/op          2 allocs/op
BenchmarkSort/interface-16              12086794                97.47 ns/op           72 B/op          2 allocs/op
BenchmarkSort/interface-16              12114966               102.0 ns/op            72 B/op          2 allocs/op
BenchmarkSort/slice-16                   7233543               167.5 ns/op           104 B/op          3 allocs/op
BenchmarkSort/slice-16                   7298635               162.4 ns/op           104 B/op          3 allocs/op
BenchmarkSort/slice-16                   6608888               160.1 ns/op           104 B/op          3 allocs/op
PASS
ok      github.com/lazychanger/gazelle/pkg/utils/sort       8.071s

结论

可以从benchmark指标看出，sort.Sort(sort.Interface)比sort.Slice快70%。 这就是我们接下来的优化

优化代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

package sort


type _sort[S ~[]V, V any] struct {
	s   S
	cmp func(a, b V) bool
}

func (s *_sort[T, V]) Len() int {
	return len(s.s)
}

func (s *_sort[T, V]) Less(i, j int) bool {
	return s.cmp(s.s[i], s.s[j])
}

func (s *_sort[T, V]) Swap(i, j int) {
	s.s[i], s.s[j] = s.s[j], s.s[i]
}

func Slice[S ~[]V, V any](s S, cmp func(a, b V) bool) {
	_s := &_sort[S, V]{s, cmp}
	sort.Sort(_s)
}

解析来将优化代码加入benchmark一同测试

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func BenchmarkSort(b *testing.B) {
	// 新加入我们用`struct`伪装的slice排序
    b.Run("struct_interface", func(b *testing.B) {
        b.ResetTimer()
        
        for i := 0; i < b.N; i++ {
            ss := getSliceFn()
            Slice(ss, func(a, b struct {
                order int
            }) bool {
                return a.order > b.order
            })
        }
    })
}

优化后结果

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

goos: darwin
goarch: amd64
pkg: github.com/lazychanger/gazelle/pkg/utils/sort
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
BenchmarkSort/slice_interface-16                 9549462               117.9 ns/op            72 B/op          2 allocs/op
BenchmarkSort/slice_interface-16                10389150               116.5 ns/op            72 B/op          2 allocs/op
BenchmarkSort/slice_interface-16                10160624               116.1 ns/op            72 B/op          2 allocs/op
BenchmarkSort/struct_interface-16                9111044               125.0 ns/op            80 B/op          2 allocs/op
BenchmarkSort/struct_interface-16                9385653               128.1 ns/op            80 B/op          2 allocs/op
BenchmarkSort/struct_interface-16                9045031               132.1 ns/op            80 B/op          2 allocs/op
BenchmarkSort/slice-16                           6766309               167.5 ns/op           104 B/op          3 allocs/op
BenchmarkSort/slice-16                           7167823               161.9 ns/op           104 B/op          3 allocs/op
BenchmarkSort/slice-16                           7361931               170.1 ns/op           104 B/op          3 allocs/op
PASS
ok      github.com/lazychanger/gazelle/pkg/utils/sort       12.222s

优化后结论

  1. 直接从slice类型实现sort.Interface使用sort.Sort最快;比sort.Slice快30%
  2. 其次是使用我们新加的sortPkg.Slice()；比第一种稍慢，比sort.Slice快20%
  3. 最慢的就是使用sort.Slice.