Golang slice 的底层实现

首先我们来看段代码的输出

    s := make([][]int, 4)
    for i := 0; i < 4; i++ {
        s[i] = make([]int, 4)
        s[i][0] = 1
    }

    s0 := s[0]
    s0 = append(s0, 5)
    fmt.Println(s)

输出的结果是

[[1 0 0 0] [1 0 0 0] [1 0 0 0] [1 0 0 0]]

append的值5并没有输出，那么究竟是s0并不等价于s[0]，还是有其他原因呢？
首先，肯定的是在Go中，所有的拷贝都是值拷贝，不存在引用拷贝；
其次，slice由一个指针，两个整型(分别是size和cap)来实现，既然s0包含的指针和s[0]包含的指针相同，为什么append操作并没有达到预期效果呢？

带着这些疑问，我们来看看slice的底层实现。

slice的结构

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

array指向一个数组元素的地址，这个数组可能在makeslice时创建，也可能之前就存在，而slice被"attach"上去，例如 s := a[0:5];

//代码比较简单
func makeslice(et *_type, len, cap int) slice {
   maxElements := maxSliceCap(et.size)
   
   if len < 0 || uintptr(len) > maxElements {
       panic(errorString("makeslice: len out of range"))
   }

   if cap < len || uintptr(cap) > maxElements {
       panic(errorString("makeslice: cap out of range"))
   }
   //分配数组空间
   p := mallocgc(et.size*uintptr(cap), et, true)
   return slice{p, len, cap}
}

e.g.

s := make([]int, 1, 3)
fmt.Printf("%p, %v, len:%d, cap:%d", unsafe.Pointer(&s[0]), s, len(s), cap(s))

输出:

0xc42007c0a0, [0], len:1, cap:3

对于直接"attach"到数组的情形，类似下面这样

a := [10]int{0,1,2,3,4,5,6,7,8,9}

fmt.Printf("%p, %v \n", &a, a)

s1 := a[1:5:7]

fmt.Printf("%p, %v, len:%d, cap:%d, self:%p \n", unsafe.Pointer(&s1[0]), s1, len(s1), cap(s1), unsafe.Pointer(&s1) )

输出:

0xc42006e050, [0 1 2 3 4 5 6 7 8 9] 
0xc42006e058, [1 2 3 4], len:4, cap:6, self:0xc42006c140

根据两个指针的关系，可以看出，slice直接指向了数组中的元素

slice attach1

同理，slice2还可以通过另一个slice1构造，但其属性依赖slice1，并不是slice1底层的数组

s2 := s1[2:]
fmt.Printf("%p, %v, len:%d, cap:%d, self:%p \n", unsafe.Pointer(&s2[0]), s2, len(s2), cap(s2), unsafe.Pointer(&s2) )

输出

0xc42006e068, [3 4], len:2, cap:4, self:0xc42006a140 

slice attach2

修改slice中元素的值，实际上修改的是底层数组元素的值

s2[0] = 100
fmt.Println(a, s1, s2)

输出

[0 1 2 100 4 5 6 7 8 9] [1 2 100 4] [100 4]

扩张

当我们对slice进行append操作时，若len + 追加元素个数 <= cap时，不会发生内存扩张；否则，新的内存被申请，同时旧的数据被拷贝至新内存的前部；

先上代码

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

    if et.size == 0 {
        if cap < old.cap {
            panic(errorString("growslice: cap out of range"))
        }
        
        return slice{unsafe.Pointer(&zerobase), old.len, cap}
    }
    // 计算新的cap，针对不同情况分别处理
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            //2倍
            newcap = doublecap
        } else {
            //每次尝试扩1/4
            for newcap < cap {
                newcap += newcap / 4
            }
        }
    }

    var lenmem, newlenmem, capmem uintptr
    const ptrSize = unsafe.Sizeof((*byte)(nil))
    switch et.size {
    case 1:
        lenmem = uintptr(old.len)
        newlenmem = uintptr(cap)
        capmem = roundupsize(uintptr(newcap))
        newcap = int(capmem)
    case ptrSize:
        lenmem = uintptr(old.len) * ptrSize
        newlenmem = uintptr(cap) * ptrSize
        capmem = roundupsize(uintptr(newcap) * ptrSize)
        newcap = int(capmem / ptrSize)
    default:
        lenmem = uintptr(old.len) * et.size
        newlenmem = uintptr(cap) * et.size
        capmem = roundupsize(uintptr(newcap) * et.size)
        newcap = int(capmem / et.size)
    }
    ......
    var p unsafe.Pointer
    if et.kind&kindNoPointers != 0 {
        //这里有个优化细节，先不zero，因为前部会发生覆盖
        p = mallocgc(capmem, nil, false)
        memmove(p, old.array, lenmem)
        //只对后部zero
        memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
    } else {
        p = mallocgc(capmem, et, true)
        if !writeBarrier.enabled {
            memmove(p, old.array, lenmem)
        } else {
            for i := uintptr(0); i < lenmem; i += et.size {
                typedmemmove(et, add(p, i), add(old.array, i))
            }
        }
    }
    return slice{p, old.len, newcap}
}

当不需要扩容时，append会修改底层数组的值

s2 = append(s2, 1000)
fmt.Printf("%p, %v \n", unsafe.Pointer(&s2[0]), s2)
fmt.Println(a, s1, s2)
fmt.Printf("len(s1)=%d, cap(s1)=%d, len(s2)=%d, cap(s2)=%d", len(s1), cap(s1), len(s2), cap(s2))

输出

[0 1 2 100 4 1000 6 7 8 9] [1 2 100 4] [100 4 1000]
len(s1)=4, cap(s1)=6, len(s2)=3, cap(s2)=4

注意，对s2的append，仅改变了s2的len，并没有改变s1的len
当append过多时，slice底层数组会发生变化

s2 = append(s2, 1000, 1001, 1002)
fmt.Printf("%p, %v \n", unsafe.Pointer(&s2[0]), s2)
fmt.Println(a, s1, s2)
fmt.Printf("len(s1)=%d, cap(s1)=%d, len(s2)=%d, cap(s2)=%d", len(s1), cap(s1), len(s2), cap(s2))

输出

0xc420014280, [100 4 1000 1001 1002] 
[0 1 2 100 4 5 6 7 8 9] [1 2 100 4] [100 4 1000 1001 1002]
len(s1)=4, cap(s1)=6, len(s2)=5, cap(s2)=8

原数组a，切片s1的属性未受影响；但s2底层的数组已发生变化，cap也是之前的2倍。

总结

1、多个slice指向相同的底层数组时，修改其中一个slice，可能会影响其他slice的值；
2、slice作为参数传递时，比数组更为高效，因为slice的结构比较小；
3、slice在扩张时，可能会发生底层数组的变更及内存拷贝；
4、因为slice引用了数组，这可能导致数组空间不会被gc，当数组空间很大，而slice引用内容很少时尤为严重；