【后台开发】Go语言萌新写了个跳表，综合性能完爆Github ...

DomDomm · 发表于 2022-9-2 12:40

以下内容来自于腾讯工程师phongchen。
导语：2022年3月，广大人民期盼已久的支持的泛型的go1.18发布了。但是目前基于泛型的容器实现还不多。我实现了一套类似C++中STL的容器和算法库。其中有序的Map选择用跳表来实现，并优化到了相当好的性能。在此分享一下优化的思路和心得，供大家参考借鉴。如果发现有错误也欢迎指出。
一、背景

首先为标题党致歉，不过确实没吹牛。
最近一年我所负责的业务系统中，用Go语言的实现的占了至少70%的比例，因此Review了大量的Go代码，也看了很多相关的技术资料。但是我确实没怎么写过Go的代码，因为一直以来我不太喜欢Go语言的主要有两点，一个是错误处理，另一个就是泛型。因此先前还是以写C++和Python代码为主，再加上一些Markdown文档什么的。
2022年3月，Go1.18发布，支持了泛型，我也打算自己一边学习，一边写一些有实际价值的Go代码。
前几周孩子放假回老家，家里没人打扰了，调研了一下有没有类似C++中STL的泛型库，发现要么很薄弱要么根本就不支持泛型。于是就花了几个周末和一些晚上的时间，写了个基于范型的容器和算法库，暂且起名叫stl4go（加，）。其中的有序 Map 我没有选择红黑树而是用了跳表，花了一些时间用了一些手法优化，测试了一下，基本上可以说是全 GitHub 上能找到的最快的 Go 的实现了。
二、跳表是什么

跳表（skiplist）是一种随机化的数据，由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出，跳表以有序的方式在层次化的链表中保存元素，效率和平衡树媲美 —— 查找、删除、添加等操作都可以在O(logN)期望时间下完成，综合能力相当于平衡二叉树，并且比起平衡树来说，跳跃表的实现要简单直观得多，核心功能在200行以内即可实现，遍历的时间复杂度是O(N)，代码简单，空间上也比较节省，因此在挺多的场景得到应用。比如Redis的Sorted Set、LevelDB，详细原理和算法请移步下面这文章：Skip List--跳表（全网最详细的跳表文章没有之一），不再赘述。
完整代码见https://github.com/chen3feng/stl4go/blob/master/skiplist.go，附带单元测试和性能测试。
SkipList用于需要有序的场合，在不需要有序的场景下，go自带的map容器依然是优先选择。
三、接口设计

（一）创建函数

主要考虑可以用 <、== 比较的类型，对一不可以的，需要支持自定义的比较函数。

（二）主要方法

还有迭代器和遍历区间查找等功能与本主题关系不大略去。
可以看得出，完全可以满足有序Map容器的要求。
（三）节点定义

虽然不少讲跳表原理示意图会把每层的索引节点单独列出来：

出处：Skip List--跳表（全网最详细的跳表文章没有之一）
但是一般的实现都会把索引节点实现为最底层节点的一个数组，这样每个元素只需要一个节点，节省了单独的索引节点的存储开销，也提高了性能。

图来源：https://en.wikipedia.org/wiki/Skip_list
因此节点定义如下：

四、代码优化

代码并非完全从头开始写的，我是以liyue201@github.com的gostl的实现为基础的。
https://github.com/liyue201/gostl/blob/master/ds/skiplist/skiplist.go
这个实现比较简洁，只有200多行代码，支持自定义数据类型比较，但是不支持泛型。
我在他的基础上做了一系列的算法和内存分配等方面的优化，并增加了迭代器、区间查找等功能。
（一）算法优化

1.生成随机Level的优化

每次跳表插入元素时，需要随机生成一个本次的层数，最朴素的实现方式是抛硬币：

也就是根据连续获得正面的次数来决定层数。
Redis里的算法类似，只不过用的是1/4的级数差，索引少一半，可以节省一些内存：
https://github.com/redis/redis/blob/7.0/src/t_zset.c#L118-L128

简单直白。但是存在两个问题：

math.Float64() （以及任何全局随机函数）内部为共享的随机数生成器对象，每次调用都会加锁解锁，在竞争情况下性能下降很厉害。详情参见源代码 https://cs.opensource.google/go/go/+/refs/tags/go1.19:src/math/rand/rand.go
多次生成随机数。下面我们将看到，其实只用生成一次就可以了。

所以在gostl的实现中，改用了生成一个某范围内的随机数，根据其均匀分布的特点，来计算level：

这段for循环有些拗口，改写一下就更清晰了：

也就是生成的随机数越小，level越高，比如maxLevel为10时，total=1023，那么：

512<k<1023之间的概率为1/2，level=1
256<k<511之间的概率为1/4，level=2
128<k<255之间的概率为1/8，level=3
...

当level比较高时，循环次数就会增加。不过可以观察到在生成的随机二进制中，数值增减一半正好等于改变一个bit位，因此我改用直接调用math/bits里的Len64()函数来计算生成的随机数的最小位数的方式来实现：

而Len64函数是用查表实现的，相当的快：
https://github.com/golang/go/blob/go1.19/src/math/bits/bits.go#L330-L345

这样当level>1时，时间开销就从循环变成固定开销，会快一点点。
2.自适应Level

很多实现都把level硬编码成全局或者实例级别的常量，比如在gostl中就是如此。
sl.maxLevel是一个实例级别的固定常量，跳表创建后便不再修改，因此有两个问题：

当实际元素很少时，查找函数中循环的前几次cur变量基本上都是空指针，白白浪费时间查找，所以他的实现里defaultMaxLevel设置的很小。
由于默认的maxLevel很小，只有10，插入1024个元素后，最上层基本上就接近平衡二叉树的情况了，如果再继续插入大量的元素，每层索引节点数量都快速增加，性能急剧下降。如果在构造时就根据预估容量设置一个足够大的maxLevel既可避免这个问题，但是很多时候这个数不是那么好预估，而且用起来不方便，漏了设置又可能会导致意料之外的性能恶化。

因此我把level设计为根据元素的个数动态自适应调整：

设置一个level成员记录最高的level值
当插入元素时，如果出现了更高的层，再插入后就调大level
当删除元素时，如果最顶层的索引变空了，就减少level。

通过这种方式，就解决了上述问题。

另外为了防止万一在一开始元素个数很小时就生成了很大的随机level，在randomLevel里做了一下限制，最大允许生成的level为log2(Len())+2。2是个拍脑袋决定的余量。
3.插入删除优化

插入时如果key不存在或者删除时节点存在，都需要找到每层索引中的前一个节点，放入prevs数组返回，用于插入或者删除节点后各层链表的重新组织。
gostl的实现中，是先在findPrevNodes函数里的循环中得到所有的prevs，然后再比较[0]层的值来判断key是否相等决定更新或者返回。
https://github.com/liyue201/gostl/blob/e5590f19a43ac53f35893c7c679b37d967c4859c/ds/skiplist/skiplist.go#L186-L201
这个函数会从顶层遍历到最底层：

插入时再取最底层的节点的下一个进一步比较是否相等

但是再插入key时如果已经节点存在，或者删除key时节点不存在，是不需要调整每层节点的，前面辛辛苦苦查找的prevs就没用了。
我在这里做了个优化，在这种情况下提前返回，不再继续找所有的prevs。以插入为例：

node和prevs只会有一个不空。

删除操作的优化方式类似，不再赘述。
4.数据类型特有的优化

对于Ordered类型的跳表，如果是升序的，可以直接用NewSkipList来创建。对于用得较少的降序或者Key是不可比较的类型，就需要通过传入的比较函数来比较Key。
一开始的实现为了简化，对于Ordered的SkipList，内部是通过调用SkipListFunc来实现的，这样可以节省不少代码，实现起来很简单。
但是Benchmark时，跑不过一些较快地实现。分析主要原因就在比较函数的函数调用上。以查找为例：

在C++中，比较函数可以是无状态的函数对象，其()运算符是可以inline的。但是在Go中，比较函数只能是函数指针，sl.keyCmp调用无法被inline。因此对简单的类型，这部分开销占的比例很大。
我一开始用的优化手法是在运行期间，根据硬编码的key的类型，进行类型转换后调优化的实现
https://github.com/chen3feng/stl4go/commit/1d444f1530cc43c99a978dcf0b1d7f83bcb575ee#diff-37795d4525025da36a8f77e3e5d0b3f6593fd121960e1d563008a6700fb08473
这种方式虽然凑效但是代码很丑陋，用到了硬编码的类型列表，运行期类型switch等机制，甚至还需要代码生成。
后来我摸索出通过同一个接口，根据Key是作为Ordered还是通过Func的方式来比较，来提供了不同实现的方式，就更优雅地解决了这个问题，不需要任何强制类型转换：

对于 Len()、IsEmpty()等，则不放进接口里，有利于编译器inline优化。
（二）内存分配优化

无论是理论上还是实测，内存分配对性能的影响还是挺大的。Go不像Java和C#的堆内存分配那么简单，因此应当减少不必要的内存分配。

来源：Go 生态下的字节跳动大规模微服务性能优化实践
1.Cache Prevs节点

在插入时如果节点先前不存在，或者删除时节点存在，那么就需要获得所有层的指向该位置的节点数组，这倒不是我原创的，因为看到的好几个实现中都采用了在SkipList实例级别预先分配一个slice的办法，经测试比起每次都创建slice返回确实有相当明显的性能提升。
2.节点分配优化

不同level的节点数据类型是相同的，但是其next指针数组的长度不同，一些简单粗暴的实现是设置为固定的最大深度，由于跳表中绝大多数节点都只落在最低几层，浪费了较多的内存。
另外一种做法是改为动态分配，那么就多一次内存分配。
我的做法是根据不同的深度，定义不同的结构体，额外包含一个相应长度的nexts节点指针数组，然后在node的next切片指向这个数组，可以就减少一次内存分配。并且由于nexts数组和node的地址是在一起的，cache局部性也更好。
https://github.com/chen3feng/stl4go/blob/master/skiplist_newnode.go

这么多啰嗦的代码显然不适合手写，是弄个bash脚本通过go generate生成的。
https://github.com/chen3feng/stl4go/blob/master/skiplist_newnode_generate.sh
另外我在调试这段代码时发现go的switch case语句即使对简单的全数值居然也是通过二分法而非C++常用的跳转表来实现的。不过估计是因为有更耗时的内存分配的原因，尝试把case 1，2等单独拿出来也没有提升，因此估计这里对性能没有影响。如果case非常多的话可以考虑对最常见的case单独处理，或者用函数指针数组来优化。
五、C++实现

类似的代码在C++中由于支持模板非类型参数，可以简单不少：

用C（当然在C++中也可以用）的flexible array代码则会更简单一些：

而且由于C和C++中的next数组不需要通过切片（相当于指针）来指向nexts数组，少了一次内存寻址，理论上性能更好一些。
C++实现为Go代码的手工转译，功能未做充分的验证，仅供对比评测，代码在：
https://github.com/chen3feng/skiplist-survey/tree/master/skiplist
六、Benchmark

sean-public@github.com实现了一个以float64为key的跳表：https://github.com/sean-public/fast-skiplist
并和其他实现做了个比较证明自己的最快：
https://github.com/sean-public/skiplist-survey
我在他的基础上添加了一些其他的实现和我的实现，做了benchmark，上述优化的数据类型优化就是基于此评测结果做的。
https://github.com/chen3feng/skiplist-survey
以下是部分评测结果，数值越小越好：

虽然也有少量指标不是最快的，但是总体上在大部分指标上，超越了我在github上找到的其他实现。并且大部分其他实现key只支持int64或者float64，使得无法用于string等类型。
另外也对C++的实现测了一下性能：

七、心得

1）go1.18 引入的泛型还可以，虽然功能上不算很强大，但是已经能满足挺大一部分的需求。我们组现在正在升级到go1.19，很快就能用得上。
2）Go的开发生态还是不错的，github上大量垂手可得的库，VS Code高度集成，各种便利的工具，这是我写C++代码很难体验到的。大部分优化是基于benchmark test来做的。
3）很多编程语言需要的基础知识都是相通的，打好基础，学习新技术并不太难。
4）跳出自己的舒适区，多学习一些编程语言开阔视野涨见识，有利于持续提高自己的技术能力。
参考资料

Wikipedia -- Skip list
Go 生态下的字节跳动大规模微服务性能优化实践
Skip List--跳表（全网最详细的跳表文章没有之一）
https://github.com/liyue201/gostl/blob/master/ds/skiplist/skiplist.go
https://github.com/sean-public/skiplist-survey

RhinoFreak · 发表于 2022-9-2 12:45

我不是沙发哈！

fwalker · 发表于 2022-9-2 12:50

真牛！

ChuanXin · 发表于 2022-9-2 12:57

看了一眼源码, 感觉有点难绷, 建议作者还是再多学习

量子计算9 · 发表于 2022-9-2 12:58

尤其是newSkipListNode里, 竟然有40个case, 作者连申请一块内存然后强制类型转换都不会吗?

LiteralliJeff · 发表于 2022-9-2 13:01

这个数据结构线程安全吗？操作的时候需要加锁吗？

IT圈老男孩1 · 发表于 2022-9-2 13:10

说归说，别强调go，这是数据结构的功劳[思考]

RedZero9 · 发表于 2022-9-2 13:16

不是线程安全的

xiaozongpeng · 发表于 2022-9-2 13:17

说说你的方案，unsafe 类型转换成什么呢？next应该是个数组还是slice？
newSkipListNode 是 go generate 生成的，40个case又有什么关系呢？

xiangtingsl · 发表于 2022-9-2 13:26

就像C++ STL的容器一样，本身不自带线程（或者）安全。

		自动登录	找回密码
密码			立即注册

【后台开发】Go语言萌新写了个跳表，综合性能完爆Github ...

本帖子中包含更多资源