最近一年我所负责的业务系统中,用 Go 语言的实现的占了至少 70%的比例,因此 Review 了大量的 Go 代码,也看了很多相关的技术资料。但是我确实没怎么写过 Go 的代码,因为一直以来我不太喜欢 Go 语言的主要有两点,一个是错误处理,另一个就是泛型。因此先前还是以写 C++和 Python 代码为主,再加上一些 Markdown 文档什么的。
2022 年 3 月,Go1.18 发布,支持了泛型,我也打算自己一边学习,一边写一些有实际价值的 Go 代码。
IsEmpty() bool// 表是否为空 Len() int// 返回表中元素的个数 Clear() // 清空跳表 Has(K) bool// 检查跳表中是否存在指定的key Find(K) *V // Finds element with specific key. Insert(K, V) // Inserts a key-value pair in to the container or replace existing value. Remove(K) bool// Remove element with specific key.
/* Returns a random level for the new skiplist node we are going to create. * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL * (both inclusive), with a powerlaw-alike distribution where higher * levels are less likely to be returned. */ intzslRandomLevel(void){ staticconstint threshold = ZSKIPLIST_P*RAND_MAX; int level = 1; while (random() level += 1; return (level}
// Len64 returns the minimum number of bits required to represent x; // the result is 0 for x == 0. funcLen64(x uint64)(n int) { // ... return n + int(len8tab[x]) }
这样当 level>1 时,时间开销就从循环变成固定开销,会快一点点。
2.自适应 Level
很多实现都把 level 硬编码成全局或者实例级别的常量,比如在 gostl 中就是如此。
sl.maxLevel 是一个实例级别的固定常量,跳表创建后便不再修改,因此有两个问题:
当实际元素很少时,查找函数中循环的前几次 cur 变量基本上都是空指针,白白浪费时间查找,所以他的实现里 defaultMaxLevel 设置的很小。
// Insert inserts a key-value pair into the skiplist. // If the key is already in the skip list, it's value will be updated. func(sl *SkipList[K, V])Insert(key K, value V) { // 处理key已存在的情况,略去
// findInsertPoint returns (*node, nil) to the existed node if the key exists, // or (nil, []*node) to the previous nodes if the key doesn't exist func(sl *skipListOrdered[K, V])findInsertPoint(key K)(*skipListNode[K, V], []*skipListNode[K, V]) { prevs := sl.prevsCache[0:sl.level] prev := &sl.head for i := sl.level - 1; i >= 0; i-- { for next := prev.next[i]; next != nil; next = next.next[i] { if next.key == key { // Key 已经存在,停止搜索 return next, nil } if next.key > key { // All other node in this level must be greater than the key, // search the next level. break } prev = next } prevs[i] = prev } returnnil, prevs }
node和prevs只会有一个不空:
// Insert inserts a key-value pair into the skiplist. // If the key is already in the skip list, it's value will be updated. func(sl *SkipList[K, V])Insert(key K, value V) { node, prevs := sl.impl.findInsertPoint(key) if node != nil { // Already exist, update the value node.value = value return } // 生成及插入新节点,略去 }
// Get returns the value associated with the passed key if the key is in the skiplist, otherwise returns nil func(sl *Skiplist)Get(key interface{})interface{} { var pre = &sl.head for i := sl.maxLevel - 1; i >= 0; i-- { cur := pre.next[i] for ; cur != nil; cur = cur.next[i] { cmpRet := sl.keyCmp(cur.key, key) if cmpRet == 0 { return cur.value } if cmpRet > 0 { break } pre = &cur.Node } } returnnil }
在 C++中,比较函数可以是无状态的函数对象,其()运算符是可以 inline 的。但是在 Go 中,比较函数只能是函数指针,sl.keyCmp 调用无法被 inline。因此对简单的类型,这部分开销占的比例很大。
另外我在调试这段代码时发现 go 的 switch case 语句即使对简单的全数值居然也是通过二分法而非 C++常用的跳转表来实现的。不过估计是因为有更耗时的内存分配的原因,尝试把 case 1,2 等单独拿出来也没有提升,因此估计这里对性能没有影响。如果 case 非常多的话可以考虑对最常见的 case 单独处理,或者用函数指针数组来优化。
五、C++实现
类似的代码在 C++中由于支持模板非类型参数,可以简单不少:
template <typename K, typename V> structNode { K key; V value; size_t level; Node* nexts[0]; SkipListNode(key, V value) : level(level), key(std::move(key)), value(std::move(value)) {} };
template <typename K, typename V, int N> // 注意 N 可以作为模板参数 structNodeN :public Node { NodeN(K key, V value) : Node(N, key, value) {} Node* nexts[N] = {}; };