[Go语言]binary tree算法的华山论剑

erlib · · 505 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

版权声明:本文为Sunface(孙飞)原创文章,转载请注明出处 https://blog.csdn.net/abv123456789/article/details/53956732

前言

  在benchmarkgame(世界上最火的性能对比网站)上,Go语言一直有一个槽点,就是极其慢的binary tree性能,执行用时40秒 (我的机器上,16秒),与此对比,Java版本是6秒,那么问题来了:为什么慢得令人发指?我们来深入研究下慢的原因,然后看看能否对其进行改进。

  对于binary tree算法中,最耗性能的地方就是海量的node分配和bottomUpTree()递归函数的调用,与这两项对应的go的特性就是gc的goroutine的堆栈分配。

GC

这个世界没有完美的GC,任何选择都有代价,一般来说就是低延迟和高吞吐的权衡。


问题描述

   Java采用的是分代GC,优点是node的分配非常轻量,缺点就是分代gc需要使用更多的内存空间,同时当对象被移动到tenured堆时,会发生大量的内存拷贝。

  Go的gc不是分代的,因此在node的分配上需要消耗更多的资源。Go的gc选择了超低的延迟,同时牺牲了部分吞吐,对于绝大多数应用来说,Go的选择是非常正确的,但是对于binary tree这种算法来说,就不是很适合了。

解决方案

  针对GC的优化,有两个通用的解决方案就是提前分配合适的堆栈空间和对象复用。对于binary tree算法,就是Nodes的预先分配和复用。


Goroutine的堆栈

轻量的Goroutine是Go语言的灵魂所在


问题描述

  为了让goroutine尽可能轻量,go仅仅为每个goroutine分配了2KB的初始堆栈大小,在之后Go会根据需要动态的扩展堆栈大小。同样,对于绝大多数场景,这种选择都是非常正确的,但是针对binary tree算法,这种选择就有了一些问题。

  Go是在每次函数调用之前检查goroutine的堆栈大小,如果发现当前堆栈不够用,就会重新分配一个新的堆栈空间,然后将旧的堆栈拷贝到新的里。这种操作开销是很小的,但是在binary tree中,bottomUpTree()基本上不做什么工作,调用却是极其频繁,这样一来再小的开销累积起来也会非常可观。而且这个函数的调用是深递归,当堆栈需要增长时,可能会拷贝几次,不仅仅是一次!

解决方案

  将bottomUpTree()改为非递归的函数,虽然不易实现,但是还是可以做到的。


新旧Binary tree实现对比

没有对比,就没有伤害!


旧版本代码链接

运行用时:

 > time go run old.go 20
stretch tree of depth 21     check: -1
2097152  trees of depth 4    check: -2097152
524288   trees of depth 6    check: -524288
131072   trees of depth 8    check: -131072
32768    trees of depth 10   check: -32768
8192     trees of depth 12   check: -8192
2048     trees of depth 14   check: -2048
512  trees of depth 16   check: -512
128  trees of depth 18   check: -128
32   trees of depth 20   check: -32
long lived tree of depth 20  check: -1

real    0m16.279s
user    1m47.569s
sys 0m2.663s

新版本代码链接

运行用时

time go run new.go 20
stretch tree of depth 21     check: -1
2097152  trees of depth 4    check: -2097152
524288   trees of depth 6    check: -524288
131072   trees of depth 8    check: -131072
32768    trees of depth 10   check: -32768
8192     trees of depth 12   check: -8192
2048     trees of depth 14   check: -2048
512  trees of depth 16   check: -512
128  trees of depth 18   check: -128
32   trees of depth 20   check: -32
long lived tree of depth 20  check: -1
dur: 1.71074946s

real    0m1.914s
user    0m10.149s
sys 0m0.157s


结论

  性能从16.28秒提升到了1.91秒,提升巨大!

  这里提出的解决方案看似是针对binary tree,其实对于任何GC语言和使用场景来说都是通用的。

  牢记这两种解决方案吧:

  • 内存空间预分配
  • 对象复用

有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:erlib

查看原文:[Go语言]binary tree算法的华山论剑

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

505 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传