关于golang:讲的是切片但好像又不只是切片

来自公众号：Gopher 指北

我心田始终有一个欲望，想要高声吆喝“我胡汉三又回来了”，而当初就是适合的机会。

正式开干之前有点手生，太久没有写技术类的文章，总有点怠惰，不得不说保持的确是一件很难的事件。如果不是因为愧疚和写点货色能让本人略微平静下来一些，我可能还将持续怠惰上来。

另外还有一件很有意思的事件分享一下。前一篇在公众号上的文章仅思考就花了近一个月，写只花了一天，而技术文章我个别边思考边写均匀耗时一周。后果是不会骗人的，前一篇文章浏览量首次冲破一千，果然这届读者的思维深度至多也有一个月那么多，老许拜服拜服。

其余不扯多了，咱们还是回归本篇主题。在正式理解切片底层构造之前，咱们先看几行代码。

type mySlice struct {
    data uintptr
    len  int
    cap  int
}

s := mySlice{}
fmt.Println(fmt.Sprintf("%+v", s))
// {data:0 len:0 cap:0}
s1 := make([]int, 10)
s1[2] = 2
fmt.Println(fmt.Sprintf("%+v, len(%d), cap(%d)", s1, len(s1), cap(s1))) // [0 0 2 0 0 0 0 0 0 0], len(10), cap(10)
s = *(*mySlice)(unsafe.Pointer(&s1))
fmt.Println(fmt.Sprintf("%+v", s)) // {data:824634515456 len:10 cap:10}
fmt.Printf("%p, %v\n", s1, unsafe.Pointer(s.data)) // 0xc0000c2000, 0xc0000c2000

在上述代码中，通过获取切片的地址，并将其转为*mySlice, 胜利取得了切片的长度和容量。以及一个相似于指针一样的货色。而这个指针就是指向存储实在数据的数组，上面咱们来进行验证。

//Data 强转为一个数组
s2 := (*[5]int)(unsafe.Pointer(s.data))
s3 := (*[10]int)(unsafe.Pointer(s.data))
// 批改数组中的数据后切片中对应地位的值也产生了变动
s2[4] = 4
fmt.Println(s1)  // [0 0 2 0 4 0 0 0 0 0]
fmt.Println(*s2) // [0 0 2 0 4]
fmt.Println(*s3) // [0 0 2 0 4 0 0 0 0 0]

到这里，切片的底层构造曾经跃然纸上了，不过为了做更进一步的验证，咱们持续测试构造体转为切片的过程。

var (
    // 一个长度为 5 的数组
    dt [5]int
    s4 []int)
s5 := mySlice{
    // 将数组地址赋值给 data
    data: uintptr(unsafe.Pointer(&dt)),
    len:  2,
    cap:  5,
}
// 构造体强转为切片
s4 = *((*[]int)(unsafe.Pointer(&s5)))
fmt.Println(s4, len(s4), cap(s4)) // [0 0] 2 5
// 批改数组中的值，切片内容也会发生变化
dt[1] = 3
fmt.Println(dt, s4) // [0 3 0 0 0] [0 3]

通过上述三段代码，咱们将切片的底层构造以构造体的模式更加清晰的表达出来。如下图所示，其中第一局部（Data）为指向数组的地址，第二局部（Len）为切片的长度即数组已应用的长度，第三局部（Cap）为数组的长度。

小结：切片是对数组的包装，底层仍应用数组存储数据。

额定再多说一嘴：

reflect 包要操作切片时通过 reflect.SliceHeader 构造体，详见 https://github.com/golang/go/…

runtime 对切片进行扩容时应用 slice 构造体, 详见 https://github.com/golang/go/…

在前一部分的 Demo 中简直离不开 unsafe 包的应用。当然本篇并不是介绍此包的用法，只是作为一个题外话简略看一下它为什么不平安。

func otherOP(a, b *int) {reflect.ValueOf(a)
    reflect.ValueOf(b)
}

var (a = new(int)
    b = new(int)
)
otherOP(a, b) // 如果正文此函数调用，最终输入后果会发生变化
*(*int)(unsafe.Pointer(uintptr(unsafe.Pointer(a)) + unsafe.Sizeof(int(*a)))) = 1
fmt.Println(*a, *b)

上述代在是否正文 otherOP 时，其输入后果是不统一的。

当变量逃逸至堆上时变量 a 和变量 b 内存地址相邻，故可能通过 a 变量地址去设置 b 变量的值。当未逃逸到堆上时，设置变量 b 的值并未失效，如此咱们根本无法得悉批改了哪一块儿内存的值，这种不确定性在老许看来即是咱们须要谨慎应用此包的起因。

对于上述 demo 的补充解释：

reflect.ValueOf 会调用底层的 escapes 办法以保障对象逃逸到堆中

Go 中采纳按大小宰割的闲暇链表内存分配器以及多级缓存，故 a，b 变量在大小统一且本 demo 变量较少的的状况下很有可能被调配到间断的内存空间中

创立切片形式有四种。第一种间接通过 var 进行变量申明，第二种通过类型推导，第三种通过 make 形式去创立，第四种通过切片表达式创立。

// 通过变量申明的形式创立
var a []int
// 类型推导
b := []int{1, 2, 3}
// make 创立
c := make([]int, 2) // c := make([]int, 0, 5)
// 切片表达式
d := c[:3]

上述例子中，前三种没什么特地好说的，老许次要介绍一下第四种, 以及它的相干限度和注意事项。

对于字符串、数组、数组指针和切片（切片指针不能应用上面的表达式）均可应用上面的表达式：

s[low:high] // 生成的切片长度为 high-low

通过上述表达式可创立新的子串或者切片。特地留神的是，对字符串应用此表达式时既不是生成字符串切片也不是生成字节切片而是生成 子字符串。另外，老许在 go 中字符串的编码问题中提到 Go 中的字符串存储的就是 utf8 字节切片，所以咱们在应用此办法获取蕴含中文等特殊字符时有可能会呈现意想不到的后果。正确失去子串的形式应该是先转为 rune 切片再截取。

上述表达式曾经能够非常不便地创立新的切片，然而更加不便地是 low 和high还能够省略。

s[2:]  // same as s[2 : len(a)]
s[:3]  // same as s[0 : 3]
s[:]   // same as s[0 : len(a)]

下标限度

对不同的类型应用切片表达式，low和 high 的取值范畴不同。对于字符串和数组 / 数组指针而言，low和 high 的取值范畴为 0 <= low <= len(s)。对于切片而言，low 和high的取值范畴为0 <= low <= cap(s)。在切片面试题系列一中正是对此知识点的考查。

切片容量

通过切片表达式生成的切片，其底层数组共享，因而切片的容量为底层数组的长度减去 low。由此能够推断下述代码输入后果为3 8 和3 13。

var (s1 [10]int
    s2 []int = make([]int, 10, 15)
)
s := s1[2:5]
fmt.Println(len(s), cap(s))
s = s2[2:5]
fmt.Println(len(s), cap(s))
return

说实话这种形式真的不罕用，尽管它能够管制切片的容量，但老许在理论开发中并未应用过。其残缺表达式如下：

s[low : high : max]

这种表达式有几个须要留神的点别离是：

只实用于数组、数组指针和切片不适用于字符串。
和简略切片表达式不同的是，它只能疏忽 low 这个下标且疏忽后该下标默认值为 0。
和简略切片表达式一样，通过残缺切片表达式生成的切片底层数组共享

下标限度

对数组 / 数组指针而言，下标取值范畴为0 <= low <= high <= max <= len(s)。对切片而言，下标取值范畴为0 <= low <= high <= cap(s)。在切片面试题系列二中正是对此知识点的考查。

切片容量

后面提到此切片表达式能够管制切片的容量。在 low 肯定的状况下，通过扭转 max 在容许范畴内的值即可扭转切片的容量，其容量计算形式为max - low。

runtime/slice.go文件的 growslice 函数实现了切片的扩容逻辑, 在正式剖析外部逻辑之前咱们先看看 growslice 的函数签名：

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

func growslice(et *_type, old slice, cap int) slice

第一个参数 _type 是 Go 语言类型的运行时示意，其中蕴含了很多元信息，例如：类型大小、对齐以及品种等。

第二个参数为待扩容切片的信息。

第三个参数为实在须要的容量，即原容量和新增元素数量之和，老许对其简称为所需容量。为了更加容易了解所需容量的含意，咱们先看一段代码：

s := []int{1,2,3} // 此时切片长度和容量均为 3
s = append(s, 4) // 此时所需容量为 3 + 1
s1 := []int{1,2,3} // 此时切片长度和容量均为 3
s1 = append(s1, 4, 5, 6) // 此时所需容量为 3 + 3

有了下面的概念之后，上面咱们看看切片扩容算法：

上图逻辑总结如下：

首先，如果所需容量大于 2 倍以后容量则新容量为所需容量。

其次，判断以后容量是否大于 1024。如果以后容量小于 1024 则新容量等于 2 倍以后容量。如果以后容量大于等于 1024 则新容量循环减少 1 / 4 倍新容量直到新容量大于等于所需容量。

老许在这里特地提醒，和 0 的比拟是有用的。初始时，老许也感觉这逻辑非常多余，起初有一天忽然顿悟，这实际上是对整形溢出的判断。因为平时开发中很少会思考这个问题，一时间惊为天人。兴许咱们和大神之间的代码差距仅仅是少了对溢出的判断。

另外一个有意思的事件是，切片的逻辑最开始也不是这样的。这逻辑并不简单，即便是刚入门的人写起来也毫无压力。然而即使是这样简略的逻辑，也是通过多个版本的迭代才有了现在的模样。

有一说一，在老许看来 1.6 中的扩容逻辑并不算优雅。想到这儿，一种“我赢了”的感觉油然而生，程序猿的高兴就是如此简略。

前文中的扩容逻辑是现实的内存调配容量，而实在的内存调配十分复杂。在 Go1.6 中切片扩容分配内存时分为四种状况，别离是类型大小为 1 字节、类型大小为指针大小、类型大小为 2 的 n 次幂和其余。而切片扩容分配内存时在不同的 Go 版本中又略有不同，这里只介绍 1.16 中类型大小为 2 的 n 次幂时内存调配。

上面间接上代码：

var shift uintptr
if sys.PtrSize == 8 {
    // Mask shift for better code generation.
    // et.size = 1 << n
    // shift = n
    // &63 是因为 uint64 中 1 最大左移 63，再大就溢出了
    shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
} else {shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
}

上述代码中，通过对指针大小判断以辨别以后运行的是 32 位还是 64 位平台。Ctz64和 Ctz32 函数是针对不同类型计算最低位 0 的个数。又因为类型大小是 2 的 n 次幂，则 0 的个数即为 n。

类型大小为 2 的 n 次幂，则类型大小肯定为 1 << n，因而计算最低位 0 的个数即可失去左移的位数。

源码中通过 x&(x-1) == 0 表达式判断一个无符号整数是否为 2 的 n 次幂。咱们平时开发中如果有相似的逻辑，请参考切片扩容源码开始装逼之旅。

接下来是计算内存容量的逻辑：

capmem = roundupsize(uintptr(newcap) << shift)
newcap = int(capmem >> shift)

联合前文易知，uintptr(newcap) << shift实际上能够了解为 uintptr(newcap) * et.size，capmem >> shift 可了解为 capmem / et.size。uintptr(newcap) << shift 是最现实的所需内存大小，而理论分配内存时因为内存对齐等问题无奈达到现实情况，所以通过 roundupsize 计算出理论须要的内存大小, 最初再计算出实在容量。有了这个了解之后咱们接下来着重剖析 roundupsize 函数。

func roundupsize(size uintptr) uintptr {
    if size < _MaxSmallSize {
        if size <= smallSizeMax-8 {return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
        } else {return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
        }
    }
    if size+_PageSize < size {return size}
    return alignUp(size, _PageSize)
}

下面函数有很多含意不分明的变量，老许接下来会对其一一解释。

_MaxSmallSize: 其值为32768，即 32kb 大小。在 Go 中，当对象大小超过 32kb 时，内存调配策略和小于等于 32kB 时是有区别的。

smallSizeMax: 其值为 1024 字节。

smallSizeDiv: 其值为 8 字节。

largeSizeDiv: 其值为 128 字节。

_PageSize: 8192 字节，即 8kb 大小。Go 按页来治理内存，而每一页的大小就为 8kb。

class_to_size: Go 中的内存调配会依照不同跨度（也可了解为内存大小）将内存宰割成不同内存块链表。当须要分配内存时，依照对象大小去匹配最合适的跨度找到闲暇的内存块儿。Go 中总共分为 67 个跨度，class_to_size是一个长度为 68 的数组，别离记录 0 和这 67 个跨度的值。源码详见sruntime/izeclasses.go。

size_to_class8: 这是一个长度为 129 的数组，代表的内存大小区间为 0~1024 字节。以索引 i 为例，此地位的对象大小 m 为i * smallSizeDiv，size_to_class8[i]的值为 class_to_size 数组中跨度最靠近 m 的下标。

size_to_class128：这是一个长度为 249 的数组，代表的内存大小区间为 1024~32768 字节。以索引 i 为例，此地位的对象大小 m 为smallSizeMax + i*largeSizeDiv, size_to_class128[i]的值为 class_to_size 数组中跨度最靠近 m 的下标。

divRoundUp: 此函数返回 a/b 向上舍入最靠近的整数。

alignUp: alignUp(size, _PageSize) = _PageSize * divRoundUp(size, _PageSize)。

最终将计算理论须要内存大小的逻辑示意如下：

到这里，切片扩容的外围逻辑就曾经剖析结束。本篇不对类型大小为 1 字节、类型大小为指针大小以及其余大小进行扩容逻辑剖析的起因是整体逻辑差异不大。在老许看来源码中对类型大小辨别的次要目标是为了尽可能减少除法和乘法运算。每每浏览这些优良的源码都令老许直呼细节怪物。

为了加深印象咱们以切片面试题系列三中的一个例子进行一次演算。

s3 := []int{1, 2}
s3 = append(s3, 3, 4, 5)
fmt.Println(cap(s3))

依据前文知，所需容量为 5，又因所需容量大于 2 倍以后容量，故新容量也为 5。

又因为 int 类型大小为 8（等于 64 位平台上的指针大小），所以理论须要的内存大小为 5 * 8 = 40 字节。而 67 个跨度中最靠近 40 字节的跨度为 48 字节，所以理论调配的内存容量为 48 字节。

最终计算实在的容量为48 / 8 = 6，和老许理论运行输入统一。

最初，衷心希望本文可能对各位读者有肯定的帮忙。

注：

写本文时，笔者所用 go 版本为: go1.16.6

文章中所用残缺例子：https://github.com/Isites/go-…

关于golang:讲的是切片但好像又不只是切片

切片底层构造

切片和构造体的互转

unsafe 题外话

创立切片

简略的切片表达式

残缺的切片表达式

切片扩容

扩容逻辑

计算内存容量

Just My Socks（注册教程内含优惠码）

关于golang:讲的是切片但好像又不只是切片

切片底层构造

切片和构造体的互转

unsafe 题外话

创立切片

简略的切片表达式

残缺的切片表达式

切片扩容

扩容逻辑

计算内存容量

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）