今天说说递归和循环调用的性能比较。
递归的优点是简化程序设计，结构简洁清晰，容易编程，可读性强，容易理解。在很多情况下使用递归是必要的，它往往能把复杂问题分解为更简单的步骤，而且能够反映问题的本质。又比如汉诺塔，用递归的话基本上可以理解，但是如果不用递归而用循环的话，程序根本不知道从何处着手！
但是递归的缺点也很明显：速度慢，运行效率低，对存储空间的占用比循环多。严格讲，循环几乎不浪费任何存储空间，而递归浪费的空间实在是太大了，而且速度慢。
因为递归是用栈机制实现的，每深入一层都要占用一块栈数据区域。对嵌套层数深的一些算法，递归就会显得力不从心，最后都会以内存崩溃而告终。而且递归也带来了大量的函数调用，这也有许多额外的时间开销。函数调用要发送实参，要为被调函数分配存储空间，还要保存返回的值，又要释放空间并将值返回给主调函数，这些都太浪费空间和时间。
虽然递归有那么多缺点，但是没有办法，有些问题太复杂，不用递归就解决不了！
与递归相比，循环的缺点是不容易理解，遇复杂问题时编写困难。但它的优点是速度快、效率高、不浪费空间。循环的运行时间只因循环次数增加而增加，没有其他额外开销，空间上同样。
那么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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
package funccall
import (
"runtime"
"testing"
)
// +++++++++++++++++++++++++
// 设定中间件处理函数的数量
var handlerLen = 20
var Users []User
func init() {
runtime.GOMAXPROCS(2)
initData()
}
// A. 递归嵌套调用中间件模式
func BenchmarkCall(b *testing.B) {
b.ReportAllocs()
b.ResetTimer()
for i := 0; i < b.N; i++ {
callModelFunc()
}
}
// B. 循环调用中间件模式
func BenchmarkLoop(b *testing.B) {
b.ReportAllocs()
b.ResetTimer()
for i := 0; i < b.N; i++ {
loopModelFunc()
}
}
// +++++++++++++++++++++++++
type User struct {
name string
age int
}
// 准备测试数据
func initData() {
for i := 0; i < handlerLen; i++ {
Users = append(Users, User{name: "sdx", age: i + 1})
}
}
// +++++++++++++++++++++++++
func callModelFunc() {
index := 0
next(index)
}
func next(index int) {
if index < handlerLen {
user := Users[index]
index++
handlerCall(user.name, user.age, index)
}
}
func handlerCall(name string, age int, index int) {
execCalc()
next(index)
execCalc()
}
// +++++++++++++++++++++++++
func loopModelFunc() {
for _, user := range Users {
handlerLoop(user.name, user.age)
}
}
func handlerLoop(name string, age int) {
execCalc()
execCalc()
}
// +++++++++++++++++++++++++
// 重点改变这里的 数组大小，模式业务代码的执行
func execCalc() {
// 栈空间申请
arr := [1]int{}
ctLen := len(arr)
for i := 0; i < ctLen; i++ {
arr[i] = i * 10
}
}
|
我们所有的基准测试都用下面的命令来跑：
go test -bench=. -run=none -benchmem -benchtime=2s
测试围绕下面两种编码方式进行，分别调整业务代码的CPU和堆栈内存使用繁重程度来模拟不同的情况。
- A. 递归嵌套调用中间件模式BenchmarkCall
- B. 循环调用中间件模式BenchmarkLoop
无业务
将中间件处理函数的调用全部注释掉，看运行结果：
1
2
3
4
5
6
7
8
9
|
func handlerCall(name string, age int, index int) {
//execCalc()
next(index)
//execCalc()
}
func handlerLoop(name string, age int) {
//execCalc()
//execCalc()
}
|
BenchmarkCall-2 37439686 62.5 ns/op 0 B/op 0 allocs/op
BenchmarkLoop-2 255215541 9.69 ns/op 0 B/op 0 allocs/op
轻量业务
运行上面的测试用例，数组长度只有1，会得到如下的结果：
1
2
3
4
5
6
7
|
func execCalc() {
arr := [1]int{}
ctLen := len(arr)
for i := 0; i < ctLen; i++ {
arr[i] = i * 10
}
}
|
BenchmarkCall-2 16107696 144 ns/op 0 B/op 0 allocs/op
BenchmarkLoop-2 17516955 133 ns/op 0 B/op 0 allocs/op
次轻量业务
把数据改成1000，相当于直接申请8KB左右的内存，后面看看运行结果：
1
2
3
4
5
6
7
|
func execCalc() {
arr := [1000]int{}
ctLen := len(arr)
for i := 0; i < ctLen; i++ {
arr[i] = i * 10
}
}
|
BenchmarkCall-2 172662 13843 ns/op 0 B/op 0 allocs/op
BenchmarkLoop-2 161072 13522 ns/op 0 B/op 0 allocs/op
重量业务
把数据改成100,000，相当于直接申请800KB左右的内存，后面看看运行结果：
1
2
3
4
5
6
7
|
func execCalc() {
arr := [100000]int{}
ctLen := len(arr)
for i := 0; i < ctLen; i++ {
arr[i] = i * 10
}
}
|
BenchmarkCall-2 1784 1335430 ns/op 0 B/op 0 allocs/op
BenchmarkLoop-2 1755 1313340 ns/op 0 B/op 0 allocs/op
小结
从上面分组测试的结果大致可以得出结论。函数嵌套调用会有性能的开销，但是比起业务逻辑代码的开销简直小巫见大巫，跟本不值一提。
结论真是这样的吗？不是说递归调用性能差吗？也没看出来啊！！！
上面的测试并没有考虑并发场景下，goroutine占用大量堆栈空间造成性能损耗的情况，下面我来并发测试。
并发基准测试
上面的测试都是非并发模式下进行的，如果我们模拟客户发起并发调用呢？可以使用并发模式的基准测试，改造代码如下：
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
package funccall
import (
"runtime"
"testing"
)
// +++++++++++++++++++++++++
// 设定中间件处理函数的数量
var handlerLen = 20
var Users []User
func init() {
runtime.GOMAXPROCS(4)
initData()
}
// A. 递归嵌套调用中间件模式
func BenchmarkCall(b *testing.B) {
b.ReportAllocs()
b.ResetTimer()
b.SetParallelism(20000)
b.RunParallel(func(pb *testing.PB) {
for pb.Next() {
callModelFunc()
}
})
}
// B. 循环调用中间件模式
func BenchmarkLoop(b *testing.B) {
b.ReportAllocs()
b.ResetTimer()
b.SetParallelism(20000)
b.RunParallel(func(pb *testing.PB) {
for pb.Next() {
loopModelFunc()
}
})
}
// +++++++++++++++++++++++++
type User struct {
name string
age int
}
// 准备测试数据
func initData() {
for i := 0; i < handlerLen; i++ {
Users = append(Users, User{name: "sdx", age: i + 1})
}
}
// +++++++++++++++++++++++++
func callModelFunc() {
index := 0
next(index)
}
func next(index int) {
if index < handlerLen {
user := Users[index]
index++
handlerCall(user.name, user.age, index)
}
}
func handlerCall(name string, age int, index int) int {
arr := [10000]int{}
ctLen := len(arr)
for i := 0; i < ctLen; i++ {
arr[i] = i * 10
}
next(index)
return arr[0]
}
// +++++++++++++++++++++++++
func loopModelFunc() {
for _, user := range Users {
handlerLoop(user.name, user.age)
}
}
func handlerLoop(name string, age int) int {
arr := [10000]int{}
ctLen := len(arr)
for i := 0; i < ctLen; i++ {
arr[i] = i * 10
}
return arr[0]
}
|
看看在我笔记本上的测试结果：
goos: windows
goarch: amd64
pkg: github.com/qinchende/gofast/fst/test/funccall
BenchmarkCall-4 31869 78478 ns/op 80 B/op 2 allocs/op
BenchmarkLoop-4 67587 31456 ns/op 37 B/op 1 allocs/op
PASS
ok github.com/qinchende/gofast/fst/test/funccall 6.035s
大家可以找到这段测试代码，改各种参数测试性能。很多因素影响结果，看的出来Go有很多编译优化。
上面的结果看出来了（你可以不断加大并发数量、或加大函数体内局部变量的大小），如果递归调用函数体中应用了大量的局部变量，在大并发量访问的时候会出现无法及时释放函数执行栈空间的情况，进而引起性能急剧下降。大家可以打开资源管理器，可以很明显看到内存使用的暴涨。
总结
大量占用内存肯定会影响性能的，特别是大并发量的时候特别明显。一般编译器会对嵌套调用做优化，这时递归代码和循环代码执行性能几乎无差异。但如果编译器无法在递归函数调用时释放局部变量，就会造成递归函数占用大量的栈空间，之后就是很明显的性能下降。
大并发量的场景一定要高效管理内存。可以这样理解：CPU的能力是无限的，而瓶颈在内存的调度。
（完）