golang slice的扩容给你整明白的

堆栈future 2021-07-05

1513

感激每一个新的挑战，因为它会锻造你的意志和品格。——佚名

1 切片的数据结构定义

type SliceHeader struct {
    Data uintptr
    Len  int
    Cap  int
}

2 append追加

很多网上资料说这块内容很笼统或者说千篇一律的复制别人的东西，完全没有自己去实践，那我这次我专门讲解追加和扩容，让大家有一个直观的认识。

2.1 append的追加不需要返回

一下源码就展示了append一个slice，但是没有返回值接受的情况

// append(slice, 1, 2, 3)
ptr, len, cap := slice
newlen := len + 3
if newlen > cap {
    ptr, len, cap = growslice(slice, newlen)
    newlen = len + 3
}
*(ptr+len) = 1
*(ptr+len+1) = 2
*(ptr+len+2) = 3
return makeslice(ptr, newlen, cap)

我们会先对切片结构体进行解构获取它的数组指针、大小和容量，如果在追加元素后切片的大小大于容量，那么就会调用 runtime.growslice 对切片进行扩容并将新的元素依次加入切片，注意没有赋值的操作。

2.2 append需要返回值接受

一下源码就展示了append一个slice，但是有返回值接受的情况

// slice = append(slice, 1, 2, 3)
a := &slice
ptr, len, cap := slice
newlen := len + 3
if uint(newlen) > uint(cap) {
   newptr, len, newcap = growslice(slice, newlen)
   vardef(a)
   *a.cap = newcap //赋值cap
   *a.ptr = newptr  //复制底层s数组地址指向新的地址
}
newlen = len + 3
*a.len = newlen //修改len属性
*(ptr+len) = 1
*(ptr+len+1) = 2
*(ptr+len+2) = 3

2.3 小结

是否覆盖原变量的逻辑其实差不多，最大的区别在于最后的结果是不是赋值给原有的变量，如果我们选择覆盖原有的变量，也不需要担心切片的拷贝，因为 Go 语言的编译器已经对这种情况作了优化和处理。

3 growslice扩容

首先看下如下代码：

package main
import"fmt"
func main(){
    s :=[]int{1,2}
    s = append(s,4,5,6)
    fmt.Printf("len=%d, cap=%d",len(s),cap(s))
}

运行结果是：

len=5, cap=6

如果按网上各种文章中总结的那样：小于原 slice 长度小于 1024 的时候，容量每次增加 1 倍。大于1024，增加0.25倍。按上例分析，添加元素 4 的时候，容量变为4；添加元素 5 的时候不变；添加元素 6 的时候容量增加 1 倍，变成 8。

那上面代码的运行结果就是：

len=5, cap=8

这是错误的！我们来仔细看看，为什么会这样，因为他们给你展示如下代码：

func growslice(et *_type, old slice, cap int) slice {
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            for 0 < newcap && newcap < cap {
                newcap += newcap  4
            }
            if newcap <= 0 {
                newcap = cap
            }
        }
    }

但是却忽略了后面还有一块代码：

    capmem = roundupsize(uintptr(newcap)* ptrSize)
    newcap =int(capmem  ptrSize)

这个growslice函数的参数依次是元素的类型，老的slice，新slice最小求的容量。例子中s原来只有2个元素，len和cap都为2，append了三个元素后，长度变为5，容量最小要变成5，即调用growslice函数时，传入的第三个参数应该为5。即cap=5。而一方面，doublecap是原slice容量的2倍，等于4。满足第一个if条件，所以newcap变成了5。

接着调用了roundupsize函数，传入40。（代码中ptrSize是指一个指针的大小，在64位机上是8）

我们再看内存对齐，搬出 roundupsize 函数的代码：

// src/runtime/msize.go:13
func roundupsize(size uintptr) uintptr {
    if size <_MaxSmallSize{
        if size <= smallSizeMax-8{
            return uintptr(class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]])
    } else {
        //……
           }
        }
        //……
    }
    const_MaxSmallSize=32768
    const smallSizeMax =1024
    const smallSizeDiv =8

很明显，我们最终将返回这个式子的结果：

class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]]

这是Go源码中有关内存分配的两个slice。class_to_size通过spanClass获取span划分的object大小。而size_to_class8表示通过size获取它的spanClass。关于内存分配span等我前面讲过了，大家自己回头可以看。

var size_to_class8 =[smallSizeMax/smallSizeDiv +1]uint8{0,1,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,18,18,19,19,19,19,20,20,20,20,21,21,21,21,22,22,22,22,23,23,23,23,24,24,24,24,25,25,25,25,26,26,26,26,26,26,26,26,27,27,27,27,27,27,27,27,28,28,28,28,28,28,28,28,29,29,29,29,29,29,29,29,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31}


var class_to_size =[_NumSizeClasses]uint16{0,8,16,32,48,64,80,96,112,128,144,160,176,192,208,224,240,256,288,320,352,384,416,448,480,512,576,640,704,768,896,1024,1152,1280,1408,1536,1792,2048,2304,2688,3072,3200,3456,4096,4864,5376,6144,6528,6784,6912,8192,9472,9728,10240,10880,12288,13568,14336,16384,18432,19072,20480,21760,24576,27264,28672,32768}

我们传进去的size等于40。所以(size+smallSizeDiv-1)/smallSizeDiv=5；获取size_to_class8数组中索引为5的元素为4；获取class_to_size中索引为4的元素为48。

最终，新的slice的容量为 6：

newcap =int(capmem / ptrSize)// 6

所以大家看到了吧，眼见为实，自己亲自去看源码，才会有收获，如果你不看大量的资料去研究，去比对，去探索，那么终究你会被网上的各种资料欺骗，导致最终学到的都是错误的知识和认知。

4 关注公众号

微信公众号：堆栈future

数据库

文章转载自堆栈future，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。