• 104498

    文章

  • 803

    评论

  • 12

    友链

  • 最近新加了换肤功能,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

golang slice的append的“坑”

撸了今年阿里、腾讯和美团的面试,我有一个重要发现.......>>

golang中的slice有一个很多人都知道的“坑”:

package main

func main() {
    //初始化两个slice
    s1 := make([]int, 3, 4)
    s2 := s1[: 2]

    s2[0] ++
    println(s1[0] == s2[0]) //true

    s1 = append(s1, 0)
    s2[0] ++
    println(s1[0] == s2[0]) //true

    s1 = append(s1, 0)
    s2[0] ++
    println(s1[0] == s2[0]) //false
}

s2是s1的slice(或者说是从s1衍生出的切片),原本二者引用同一片空间(对s2[0]的改动同步到了s1[0]),但随着s1的不断append,两次之后二者就“脱节”了,之后对一个的元素改动就不能同步到另一个了

对于熟悉slice机制的人来说这没什么秘密可言,原理差不多是这样:

初始化时,s1的make创建了一个匿名数组,大小为4,s1引用前三个元素,s2通过s1[:2]的切片引用到了数组的前两个元素,这时候对s2[0]的改动自然会影响到s1[0](第一个true):

第一次对s1 append时,由于s1的cap是4,所引用的数组切片后面还有空间,所以直接在原空间上append,然后append的返回值就是修改过len的s1自身,append后的布局:

可以看到,s1和s2还是引用同个数组,所以s2[0]的修改还是通过s1可见的(第二个true)

不过第二次append就不一样了,数组空间不够了,所以s1就申请了一个新的数组,但是s2还引用着老的数组:

在此之后对s2的元素改动就和s1没啥关系了

当然,以上是我们自己make的时候指定了len和cap做测试,这个坑的实际表现就是,每次对一个slice做append后,这个slice可能更换了引用的数组,也可能不更换,官方说法叫“潜在的副作用”,由于这和引用的数组空间有关,所以程序员自己控制第一个创建的slice的cap大小(make)或每次append前后检查cap都是可以规避的

这个设计的合理性姑且不做讨论,不过既然是潜在的行为,就让人觉得是“坑”(实际也有相当数量新手掉坑)了

于是有人提出,能否填掉这个坑呢,换句话说,能否有一种结构,使得从某个存储衍生出的所有slice(当然包括第一次make产生的slice,它并无特殊之处)永远都引用这同一块存储,而不管通过其中哪个slice去append任意多次?如果有的话,为啥不采用这种方式,而非要留个坑呢?这其实是个数据结构和其操作接口的设计问题,跟具体语言关系就不大了

话说这种结构并不难想:如果s1和s2要引用同一块存储空间,意味着其中一个通过append新申请了空间,需要将信息同步给另一个,可以有两种思路:

1 换空间的时候,同步更新所有引用到老空间的slice,比如上面的例子,s1换新空间的时候,“通知”一下s2以及其他相关slice,让它们都改引用到新空间就好了,然而问题就是s1咋知道哪些slice和自己一组呢,而且代价似乎有点大(跟相关slice数量正比)

2 也可以采用间接引用的方式,即slice不直接引用空间,而是引用管理空间的一个对象,这个对象就类似一个vector,空间的扩张由其代理进行,这个方法可行,示意图:

slice中引用store,位置信息字段也要改动,将原先的指针改为用下标表示的start,访问s[x]的时候,实际访问的是store.array[s.start + x],由于空间被store对象托管了,所以slice的cap就没太大意义了,基本就等同于cap无限大,可以随意append,熟悉vector结构的同学都知道,这里的append和下标访问都是O(1)(append是平摊)

这样设计从接口上讲是比较完美了,但是有一个潜在的问题,假设我们反复对一个store的相关slice做append后,又生成新的“右移”后的slice引用,原先的slice则抛弃掉,例如:

for ... {
    s = append(s, x)
    s = s[i :]
}

在上面的设计中,很多次操作后就可能变成这副模样:

根据slice的操作规则,它已经无法引用到前面跳过的那些元素了(负下标和负的切片开头位置都不行,除非你去unsafe),当然一个store是可能有很多slice引用的,但至少最靠前的那个slice前面的数据在逻辑上已经是垃圾了,但它们需要等到store没有被任何slice引用的时候才会随着store的销毁而被清理,如果我们将slice当成一个queue来用(这场景还不算罕见),那么store永远不会释放,只会一直吃内存

而同样应用场景下,golang的slice就没这个问题,因为有cap的存在,每次新换数组后老的数组只要没被引用就会gc掉(对应上面的“最靠前的slice前面的数据是逻辑垃圾”),内存耗费只是当前所引用的store空间+cap预留空间

那既然空间是store托管,是否可以由store自己去解决这个问题呢,例如新申请一块空间,然后扔掉左边的垃圾区段,只拷贝右边的有效区段,类似vector的缩容过程,这个做法细究起来会有两个问题:

1 slice中的start是不会随着这个过程去变的,所以store在改变后要保证逻辑下标不变,这很简单,因为只是扔掉了左半部分,所以store自己保存一个当前空间下标开始序号(也就是从第一次创建到现在扔掉了左边多少个垃圾元素)就好了,访问s[x]的时候实际会访问到store.array[start + x - store.start]

2 store如何检测当前引用自己的所有slice中最小的开始下标?如果没有gc的介入,这才是真正的大问题,因为store是个被引用者,如果不保存额外信息的话,就无法得知自身的引用情况了

如果有gc介入,那问题2就简单了,只要gc过程识别slice和store对象,分析store中的左段垃圾,然后控制store自己去换空间

如果只用库能否实现呢?由于store只是想知道各个相关slice的start,我们可以采用类似引用计数的方法,让slice在建立和销毁的时候通知一下store自己start的改动情况,这里建立时的通知好说,直接通知就行,但如何感知销毁事件呢,总不能每次建立一个slice就defer吧,再说slice也可以赋值,所以可能需要用到finalizer(这也意味着我们只能通过slice的指针去操作了)

我们可以给store加个链表来管理被引用的信息,只要有序存放各slice的start值就行了:

store.refs是一个有序链表,新建slice的时候,在store.refs里面增加新slice的start,而某个slice销毁的时候,用其finalizer通知引用的store,从refs里面去掉其start,这样refs里面第一个(也就是最小的)start即指示了有效空间的起始点,store在适当的时候(一般是第一个start被删除的时候)缩一下就好,很明显,由于分片语法不支持负下标,所以任何新插入的start都不可能比refs第一个start小

这个链表长度会和引用store的slice数量相关,如果数量很多的话插入和删除就比较慢,可以用hash表使得插入删除为O(1),但找最小值又是个问题,所以折中一下可以用平衡树来保持有序和快速操作,不过一般来说同时引用到一个store的slice数量不会太多,也可以根据运行时的具体情况来变更结构(达到一定长度改成平衡树),这只是一个局部优化,就不做讨论了

然而这样就解决问题了么?别忘了我们在这个方案中用到了finalizer,而关于finalizer有个限制,文档是这样说的:

If a cyclic structure includes a block with a finalizer, that cycle is not guaranteed to be garbage collected and the finalizer is not guaranteed to run, because there is no ordering that respects the dependencies.

就是说如果出现一个环形垃圾,并且环中有对象有finalizer,则会由于不知道依赖关系而不保证他们被回收,这样一来就内存泄露了

上面设计中slice对象是有finalizer的,如果store中又引用了某个引用它的slice(比如元素类型是interface{}就可以),那么就可能造成问题了,所以finalizer通知的方式行不通(如果考虑用其他语言实现这个结构,也是类似问题,比如python中的__del__,C++中的析构等,这跟语言关系不大)

那么如果不用finalizer,也就是说store层感知不到引用情况,就无法自行自动管理空间了,那我们的路子貌似就又回到了原始状态:让slice直接引用存储空间,这样slice的销毁自然就解除了对其区段的引用,由于一整块空间需要整体释放,所以只好将空间打散了,用单链表:

嗯,目的的确达到了,只要s1销毁,左边两个节点也自然会被回收,而付出的代价就是操作耗时O(1)降为O(N),而且链表节点会有额外的空间消耗

性能当然是可以再优化的,有两个事情可以做:

1 每个链表节点不是保存一个元素,而是保存固定数量的一批,比如100个,这样可以减少空间的额外浪费,遍历时速度也会提高,不过还有个小问题,slice自己还要保存一下自己的start,因为引用的节点数据下标总是100的倍数,得自己保存下内部位置,加上100来计算具体开始位置,当然了,如果你只存1个元素,也会申请至少1个节点,考虑头尾都有浪费,平均算下来每个store会浪费50到100个元素空间,大量小store的话就划不来了,不过我们也可以根据store的大小来动态选择不同的存储方式,这个就不提了

2 链表改成跳表,但注意改后也只能是像单链表一样单向引用,保证左边垃圾节点可以被回收,这样可以将时间复杂度降到平均O(lgN):

熟悉跳表的同学可能会说诶不对呀,跳表不是需要一个足够高度的head?其实不要也可以的,只要每个节点知道自己的高度,可以先上再下跳着找:

这样做法有时候比有一个head要慢一倍的样子,不过复杂度依然是O(lgN)的

P.S.:为啥要强调每个节点需要知道自己高度呢,因为有些跳表实现是不保存高度的,比如redis的skiplist

总结:

关于这个“坑”的针对性改进其实是来源于日常讨论中的脑洞,并不代表将其做出来真有多少实用价值,更多的是一种理想化的设计讨论,像golang的slice实现选择算是比较平衡的一个点,毕竟实践中碰到的很多情况下,slice都是拿来当一个数组用的,即便用其切片生成相关的slice,也可能只是临时用一下,很少有多个点引用同一个store还需要同步append结果的,真碰到了就自己多写点代码去封装实现好了

本文的方案可能不是最优,也许是有O(1)时间append和下标访问并且解决了文中所涉及问题的,不过我想不出来了


695856371Web网页设计师②群 | 喜欢本站的朋友可以收藏本站,或者加入我们大家一起来交流技术!

0条评论

Loading...


自定义皮肤 主体内容背景
打开支付宝扫码付款购买视频教程
遇到问题联系客服QQ:419400980
注册梁钟霖个人博客