slice 使用总结, 持续更新于我的 GitHub
介绍
我们都知道 array 是固定长度的数组, slice 是对 array 的扩展, 本质上是基于数组实现的, 主要特点是定义完一个 slice 变量之后, 不需要为它的容量而担心. 本文记录直接深入 slice 的底层实现原理, 不再介绍 slice 的基本使用.
slice 结构
slice 中 array 是一个指针, 它指向的是一个 array
len 代表的是这个 slice 中的元素长度
cap 是 slice 的容量
参考 Golang slice 源码
- type slice struct {
- array unsafe.Pointer
- len int
- cap int
- }
slice 扩容
- s := []int{
- 1,2,3,4,5,6
- }
- s = append(s, 6)
如果新的 slice 大小是当前大小 2 倍以上, 则大小增长为新大小
如果当前 slice cap 小于 1024, 按每次 2 倍增长, 否则每次按当前大小 1/4 增长. 直到增长的大小超过或等于新大小
append 的实现是在内存中将 slice 的 array 值赋值到新申请的 array 上
扩容源码实现
性能
通过上面我们知道 slice 的扩容涉及到内存的拷贝, 这样带来的好处是数据存储在连续内存上, 比随机访问快很多, 最直接的性能提升就是缓存命中率会高很多, 这也就是为什么 slice 不采用动态链表实现的原因吧
我们知道拷贝内存数据是有开销的, 而其中最大的开销不在 memmove 数据上, 而是在开辟一块新内存 malloc 及之后的 GC 压力
拷贝连续内存是很快的, 随着 cap 变大, 拷贝总成本还是 O(N) , 只是常数大了
假如不想发生拷贝, 那你就没有连续内存. 此时随机访问开销会是: 链表 O(N), 2 倍增长块链 O(LogN), 二级表一个常数很大的 O(1)
当你能大致知道所需的最大空间 (在大部分时候都是的) 时, 在 make 的时候预留相应的 cap 就好
如果需要的空间很大, 而且每次都不确定, 那就要在浪费内存和耗 CPU 在 malloc + gc 上做权衡
链表的查找操作是从第一个元素开始, 所以相对数组要耗时间的多, 因为采用这样的结构对读的性能有很大的提高
选择
slice 是很灵活的, 大部分情况都能表现的很好
但也有特殊情况, slice 的容量超大并且需要频繁的更改 slice 的内容时, 改用 list 更合适
来源: https://juejin.im/post/5c8f30f3f265da612b1aad29