go语言递归优化,go语言进阶
为什么要使用 Go 语言?Go 语言的优势在哪里
1、学习曲线
网站建设哪家好,找创新互联!专注于网页设计、网站建设、微信开发、重庆小程序开发、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了岱山免费建站欢迎大家使用!
它包含了类C语法、GC内置和工程工具。这一点非常重要,因为Go语言容易学习,所以一个普通的大学生花一个星期就能写出来可以上手的、高性能的应用。在国内大家都追求快,这也是为什么国内Go流行的原因之一。
2、效率
Go拥有接近C的运行效率和接近PHP的开发效率,这就很有利的支撑了上面大家追求快速的需求。
3、出身名门、血统纯正
之所以说Go语言出身名门,是因为我们知道Go语言出自Google公司,这个公司在业界的知名度和实力自然不用多说。Google公司聚集了一批牛人,在各种编程语言称雄争霸的局面下推出新的编程语言,自然有它的战略考虑。而且从Go语言的发展态势来看,Google对它这个新的宠儿还是很看重的,Go自然有一个良好的发展前途。我们看看Go语言的主要创造者,血统纯正这点就可见端倪了。
4、组合的思想、无侵入式的接口
Go语言可以说是开发效率和运行效率二者的完美融合,天生的并发编程支持。Go语言支持当前所有的编程范式,包括过程式编程、面向对象编程以及函数式编程。
5、强大的标准库
这包括互联网应用、系统编程和网络编程。Go里面的标准库基本上已经是非常稳定,特别是我这里提到的三个,网络层、系统层的库非常实用。
6、部署方便
我相信这一点是很多人选择Go的最大理由,因为部署太方便,所以现在也有很多人用Go开发运维程序。
7、简单的并发
它包含降低心智的并发和简易的数据同步,我觉得这是Go最大的特色。之所以写正确的并发、容错和可扩展的程序如此之难,是因为我们用了错误的工具和错误的抽象,Go可以说这一块做的相当简单。
8、稳定性
Go拥有强大的编译检查、严格的编码规范和完整的软件生命周期工具,具有很强的稳定性,稳定压倒一切。那么为什么Go相比于其他程序会更稳定呢?这是因为Go提供了软件生命周期的各个环节的工具,如go
tool、gofmt、go test。
go语言 使用递归与循环两种方式计算斐波那契数列
给定一个正整数n计算出对应斐波那契数列对应的值
说明:
用mackbookpro i7 2.7GHZ笔记本进行测试,结果如下:
备注: 当n=80时,由于测试等待时间过长,强制中断了执行。
从测试结果看出,当n逐渐增大,递归方式计算斐波拉契数列的时间复杂性急剧增加。当n值较大时可以考虑用循环方式代替。
类似的方式也可以用于,求阶乘、遍历目录、汉诺塔等问题的解决。在后期的文章中,我将这些内容进行补充,敬请期待,谢谢。
1.14版本defer性能大幅度提升,内部实现了开放编码优化
GO中的defer会在当前函数返回前执行传入的函数,常用于关闭文件描述符,关闭链接及解锁等操作。
Go语言中使用defer时会遇到两个常见问题:
接下来我们来详细处理这两个问题。
官方有段对defer的解释:
这里我们先来一道经典的面试题
你觉得这个会打印什么?
输出结果:
这里是遵循先入后出的原则,同时保留当前变量的值。
把这道题简化一下:
输出结果
上述代码输出似乎不符合预期,这个现象出现的原因是什么呢?经过分析,我们发现调用defer关键字会立即拷贝函数中引用的外部参数,所以fmt.Println(i)的这个i是在调用defer的时候就已经赋值了,所以会直接打印1。
想要解决这个问题也很简单,只需要向defer关键字传入匿名函数
这里把一些垃圾回收使用的字段忽略了。
中间代码生成阶段cmd/compile/internal/gc/ssa.go会处理程序中的defer,该函数会根据条件不同,使用三种机制来处理该关键字
开放编码、堆分配和栈分配是defer关键字的三种方法,而Go1.14加入的开放编码,使得关键字开销可以忽略不计。
call方法会为所有函数和方法调用生成中间代码,工作内容:
defer关键字在运行时会调用deferproc,这个函数实现在src/runtime/panic.go里,接受两个参数:参数的大小和闭包所在的地址。
编译器不仅将defer关键字转成deferproc函数,还会通过以下三种方式为所有调用defer的函数末尾插入deferreturn的函数调用
1、在cmd/compile/internal/gc/walk.go的walkstmt函数中,在遇到ODEFFER节点时会执行Curfn.Func.SetHasDefer(true),设置当前函数的hasdefer属性
2、在ssa.go的buildssa会执行s.hasdefer = fn.Func.HasDefer()更新hasdefer
3、在exit中会根据hasdefer在函数返回前插入deferreturn的函数调用
runtime.deferproc为defer创建了一个runtime._defer结构体、设置它的函数指针fn、程序计数器pc和栈指针sp并将相关参数拷贝到相邻的内存空间中
最后调用的return0是唯一一个不会触发延迟调用的函数,可以避免deferreturn的递归调用。
newdefer的分配方式是从pool缓存池中获取:
这三种方式取到的结构体_defer,都会被添加到链表的队头,这也是为什么defer按照后进先出的顺序执行。
deferreturn就是从链表的队头取出并调用jmpdefer传入需要执行的函数和参数。
该函数只有在所有延迟函数都执行后才会返回。
如果我们能够将部分结构体分配到栈上就可以节约内存分配带来的额外开销。
在call函数中有在栈上分配
在运行期间deferprocStack只需要设置一些未在编译期间初始化的字段,就可以将栈上的_defer追加到函数的链表上。
除了分配的位置和堆的不同,其他的大致相同。
Go语言在1.14中通过开放编码实现defer关键字,使用代码内联优化defer关键的额外开销并引入函数数据funcdata管理panic的调用,该优化可以将 defer 的调用开销从 1.13 版本的 ~35ns 降低至 ~6ns 左右。
然而开放编码作为一种优化 defer 关键字的方法,它不是在所有的场景下都会开启的,开放编码只会在满足以下的条件时启用:
如果函数中defer关键字的数量多于8个或者defer处于循环中,那么就会禁用开放编码优化。
可以看到这里,判断编译参数不用-N,返回语句的数量和defer数量的乘积小于15,会启用开放编码优化。
延迟比特deferBitsTemp和延迟记录是使用开放编码实现defer的两个最重要的结构,一旦使用开放编码,buildssa会在栈上初始化大小为8个比特的deferBits
延迟比特中的每一个比特位都表示该位对应的defer关键字是否需要被执行。延迟比特的作用就是标记哪些defer关键字在函数中被执行,这样就能在函数返回时根据对应的deferBits确定要执行的函数。
而deferBits的大小为8比特,所以该优化的条件就是defer的数量小于8.
而执行延迟调用的时候仍在deferreturn
这里做了特殊的优化,在runOpenDeferFrame执行开放编码延迟函数
1、从结构体_defer读取deferBits,执行函数等信息
2、在循环中依次读取执行函数的地址和参数信息,并通过deferBits判断是否要执行
3、调用reflectcallSave执行函数
1、新加入的defer放入队头,执行defer时是从队头取函数调用,所以是后进先出
2、通过判断defer关键字、return数量来判断是否开启开放编码优化
3、调用deferproc函数创建新的延迟调用函数时,会立即拷贝函数的参数,函数的参数不会等到真正执行时计算
分享标题:go语言递归优化,go语言进阶
文章起源:http://myzitong.com/article/hoshsd.html