go中slice append扩容的一些细节

ivansli 2022/06/14 66℃ 0

1.问题与事件

事件:一个朋友面试某家公司
问题:对容量为4的int切片追加5个元素,最终切片的容量是多少?

针对该问题,朋友回答:16

该问题考察slice扩容:
①在容量小于1024时,在原基础上2倍扩容 ②大于1024时,在原基础上1/4的扩容

面试官回答说:10

让回去自己试一下,看看具体是多少?

事后分析了一下,能确定的是:面试官提出的问题,有4种写法。

2.同一个问题不同写法的不同结果

在4种写法执行之前,你觉得最终的容量cap分别会是多少?

func TestSliceAppend(t *testing.T) {
    SliceAppend0()
    SliceAppend1()
    SliceAppend2()
    SliceAppend3()
}

// slice 长度为0,容量为4,批量追加5个元素
func SliceAppend0() {
    m := make([]int, 0, 4)
    fmt.Println("SliceAppend0 before:", m, len(m), cap(m))
    m = append(m, 1, 2, 3, 4, 5)
    fmt.Println("SliceAppend0 after:", m, len(m), cap(m))
}

// slice 长度为0,容量为4,逐个追加5个元素
func SliceAppend1() {
    m := make([]int, 0, 4)
    fmt.Println("SliceAppend1 before:", m, len(m), cap(m))
    m = append(m, 1)
    m = append(m, 2)
    m = append(m, 3)
    m = append(m, 4)
    m = append(m, 5)
    fmt.Println("SliceAppend1 after:", m, len(m), cap(m))
}

// slice 长度为4,容量为4,批量追加5个元素
func SliceAppend2() {
    m := make([]int, 4, 4)
    fmt.Println("SliceAppend2 before:", m, len(m), cap(m))
    m = append(m, 1, 2, 3, 4, 5)
    fmt.Println("SliceAppend2 after:", m, len(m), cap(m))
}

// slice 长度为4,容量为4,逐个追加5个元素
func SliceAppend3() {
    m := make([]int, 4, 4)
    fmt.Println("SliceAppend3 before:", m, len(m), cap(m))
    m = append(m, 1)
    m = append(m, 2)
    m = append(m, 3)
    m = append(m, 4)
    m = append(m, 5)
    fmt.Println("SliceAppend3 after:", m, len(m), cap(m))
}

代码基于 Go1.18 执行

执行结果如下:

SliceAppend0 before: [] 0 4
SliceAppend0 after: [1 2 3 4 5] 5 8

SliceAppend1 before: [] 0 4
SliceAppend1 after: [1 2 3 4 5] 5 8

SliceAppend2 before: [0 0 0 0] 4 4
SliceAppend2 after: [0 0 0 0 1 2 3 4 5] 9 10

SliceAppend3 before: [0 0 0 0] 4 4
SliceAppend3 after: [0 0 0 0 1 2 3 4 5] 9 16

到这里,想必你也知道了最终的结论。

那么,case by case(面试官的问题:对一个容量为4的int切片追加5个元素)可以看出:
① 提出的问题不严谨,因为没有对问题设置严格的前置条件 (4种写法的哪一种?)
② 同一个问题不同的写法执行结果不同,面试官/候选人各执一词,都觉得自己的没问题(有点盲人摸象的感觉)

3.问题复盘

对于面试官给出的结果 10 (SliceAppend2 的执行结果),为什么是10,而不是16?需要深入研究!

毕竟是面试,面试官说的...都...对...!

复盘步骤:
① 代码 SliceAppend2 转换成汇编

    ......

    PCDATA  $1, $0
    CALL    runtime.growslice(SB) ;; slice 扩容
    LEAQ    5(BX), SI
    MOVQ    AX, BX
    MOVQ    CX, DI
    MOVQ    ""..autotmp_14+72(SP), CX
    JMP     534
    LEAQ    (BX)(CX*8), DX
    MOVQ    $1, (DX)   ;; 追加数字 1
    LEAQ    (BX)(CX*8), DX
    LEAQ    8(DX), DX
    MOVQ    $2, (DX)   ;; 追加数字 2
    LEAQ    (BX)(CX*8), DX
    LEAQ    16(DX), DX
    MOVQ    $3, (DX)   ;; 追加数字 3
    LEAQ    (BX)(CX*8), DX
    LEAQ    24(DX), DX
    MOVQ    $4, (DX)   ;; 追加数字 4
    LEAQ    (BX)(CX*8), DX
    LEAQ    32(DX), DX
    MOVQ    $5, (DX)    ;; 追加数字 5
    ......

可以看到 调用了 runtime.growslice(SB) 对切片进行扩容。此处非常关键关键,正是这里的扩容导致 slice 的 cap 发生变化。

② 追溯 growslice 的 go 源码,计算最终容量大小
runtime.growslice(SB) 方法位于源码:runtime/slice.go中。

这里使用的源码为 go1.18

// growslice handles slice growth during append.
// It is passed the slice element type, the old slice, and the desired new minimum capacity,
// and it returns a new slice with at least that capacity, with the old data
// copied into it.
// The new slice's length is set to the old slice's length,
// NOT to the new requested capacity.
// This is for codegen convenience. The old slice's length is used immediately
// to calculate where to write new values during an append.
// TODO: When the old backend is gone, reconsider this decision.
// The SSA backend might prefer the new length or to return only ptr/cap and save stack space.

// et 为 slice 元素的类型,这里是 int 类型
// old 为旧的 slice
// cap 为容量,此时等于 len(old.cap)+追加元素个数,这里是 9。
// cap为什么是9?后面有相关源码
func growslice(et *_type, old slice, cap int) slice {

  ...

    if cap < old.cap {
        panic(errorString("growslice: cap out of range"))
    }

  // 元素类型大小为0,则特殊处理
    if et.size == 0 {
        // append should not create a slice with nil pointer but non-zero len.
        // We assume that append doesn't need to preserve old.array in this case.
        return slice{unsafe.Pointer(&zerobase), old.len, cap}
    }

  // 切片原来的容量
    newcap := old.cap
  // 对原来的容量*2 得到 doublecap
    doublecap := newcap + newcap

  // cap=old.cap + 追加元素的个数
  //
  // 如果 cap 大于原来2倍旧的容量就是用 cap
  //
  // 所理解的:在容量小于1024时,在原基础上2倍扩容。大于1024时,在原基础上1/4的扩容
  // 也正是源于下面的逻辑
  //
    if cap > doublecap {
        newcap = cap
    } else {
        const threshold = 256
    // 在这里原来1.18之前为小于等于 1024。即:
    // if old.cap < 1024 
    // 
    // 1.18之前 threshold 等于 1024
        if old.cap < threshold {
            newcap = doublecap
        } else {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            for 0 < newcap && newcap < cap {
                // Transition from growing 2x for small slices
                // to growing 1.25x for large slices. This formula
                // gives a smooth-ish transition between the two.
                newcap += (newcap + 3*threshold) / 4
            }
            // Set newcap to the requested cap when
            // the newcap calculation overflowed.
            if newcap <= 0 {
                newcap = cap
            }
        }
    }

  // 走到这里 newcap 等于 9

  // !!!!!!! 注意 !!!!!!!!
  // 走到这里,你是不是认为 已经最终确认了 newcap 的大小?
  // 如果是这样理解的话,就大错特错了
  // !!!!!!! 注意 !!!!!!!!

    var overflow bool
    var lenmem, newlenmem, capmem uintptr
    // Specialize for common values of et.size.
    // For 1 we don't need any division/multiplication.
    // For goarch.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
    // For powers of 2, use a variable shift.
    switch {
    case et.size == 1:
        lenmem = uintptr(old.len)
        newlenmem = uintptr(cap)
        capmem = roundupsize(uintptr(newcap))
        overflow = uintptr(newcap) > maxAlloc
        newcap = int(capmem)

    case et.size == goarch.PtrSize: // slice元素类型大小 等于 指针大小,即:8byte
    // slice元素类型为 指针大小则会对 newcap 进行调整
    //
    // 为什么会调整,还牵扯 go 的内存分配原理
    // go 使用类似于 TCMalloc 的内存分配原理: 会把内存分割为不同 class(level) 的内存块
    // 分配内存时都会去找合适的 class等级 中对应大小的内存,减少内存浪费
    //
    // 旧 slice 的内存大小
        lenmem = uintptr(old.len) * goarch.PtrSize
    // 新的切片应该占用的内存大小 = 元素总个数*指针大小
        newlenmem = uintptr(cap) * goarch.PtrSize

    // newcap 此时等于 9
    //
    // uintptr(newcap) * goarch.PtrSize = 72byte,为新的 slice 应该占用的内存大小
    // roundupsize() 返回 最合适的 class等级 对应的内存大小
    //
    // 这里是核心哟!!! 也最终会影响最终容量 的大小
    // capmem 最终等于 80byte
    // 因为 80byte 为 class7 对应的最接近 72byte 的内存大小
        capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)

    // 新的最终的内存容量 = capmem/指针大小。 即:80/8=10,最终容量等于 10
    //
    // !!!!!!
    // 走到这里 newcap 已经从 9 变为 10
    // !!!!!!
        newcap = int(capmem / goarch.PtrSize)
    case isPowerOfTwo(et.size):
        var shift uintptr
        if goarch.PtrSize == 8 {
            // Mask shift for better code generation.
            shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
        } else {
            shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
        }
        lenmem = uintptr(old.len) << shift
        newlenmem = uintptr(cap) << shift
        capmem = roundupsize(uintptr(newcap) << shift)
        overflow = uintptr(newcap) > (maxAlloc >> shift)
        newcap = int(capmem >> shift)
    default:
        lenmem = uintptr(old.len) * et.size
        newlenmem = uintptr(cap) * et.size
        capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
        capmem = roundupsize(capmem)
        newcap = int(capmem / et.size)
    }

  // 把旧的 slice内容 拷贝到新的slice中
    memmove(p, old.array, lenmem)

  // 返回扩容之后的新 slice,这也就是为什么 append 要接收返回值。因为 slice 已经发生了变化
  // 此时,追加的元素还没有加进来
  // 最终,这里的 newcap 等于 10
    return slice{p, old.len, newcap}
}


// 找到 size 最合适的class等级 对应大小的内存
//
// Returns size of the memory block that mallocgc will allocate if you ask for the size.
func roundupsize(size uintptr) uintptr {
  // _MaxSmallSize = 32768
    if size < _MaxSmallSize {
    // smallSizeMax = 1024
        if size <= smallSizeMax-8 {
      // !!!!size 小于 1024-8, 所以我们的代码走到这里!!!!
      //
      // divRoundUp(size, smallSizeDiv)  这里计算结果是 9
      // size_to_class8[] 返回 size 所在的class 级别
      // var size_to_class8 = [...]uint8{0, 1, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, .... }
      // size_to_class8[9] 等于 7
      //
      // var class_to_size = [...]uint16{0, 8, 16, 24, 32, 48, 64, 80, 96, 112, ...}
      // class_to_size[7] 等于 80 byte
      // 也就是 当前 slice 应该分配 class7级别 大小为 80byte 的内存
      //
      // 源码位置 :runtime/sizeclasses.go
      // class  bytes/obj  bytes/span  objects  tail waste  max waste  min align
      //     1          8        8192     1024           0     87.50%          8
      //     2         16        8192      512           0     43.75%         16
      //     3         24        8192      341           8     29.24%          8
      //     4         32        8192      256           0     21.88%         32
      //     5         48        8192      170          32     31.52%         16
      //     6         64        8192      128           0     23.44%         64
      //     7         80        8192      102          32     19.07%         16
      //     8         96        8192       85          32     15.95%         32
      // ......
            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)
}


// divRoundUp returns ceil(n / a).
func divRoundUp(n, a uintptr) uintptr {
    // a is generally a power of two. This will get inlined and
    // the compiler will optimize the division.
    return (n + a - 1) / a
}

③ 在②中 func growslice(et *_type, old slice, cap int)cap 为什么是9?
在编译器的源码 cmd/compile/internal/walk/assign.go 中可以看到蛛丝马迹。

// expand append(l1, l2...) to
//   init {
//     s := l1
//     n := len(s) + len(l2)
//     // Compare as uint so growslice can panic on overflow.
//     if uint(n) > uint(cap(s)) {
//       s = growslice(s, n)
//     }
//     s = s[:n]
//     memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T))
//   }
//   s
//
// l2 is allowed to be a string.
func appendSlice(n *ir.CallExpr, init *ir.Nodes) ir.Node {
  ......

  // append(l1, l2...) 
    l1 := n.Args[0]
    l2 := n.Args[1]
    l2 = cheapExpr(l2, init)
    n.Args[1] = l2

    var nodes ir.Nodes

    // var s []T
    s := typecheck.Temp(l1.Type())
    nodes.Append(ir.NewAssignStmt(base.Pos, s, l1)) // s = l1

    elemtype := s.Type().Elem()

    // n := len(s) + len(l2)
  // 
  // 注意这里的 nn 就是 len(s) + len(l2)
    nn := typecheck.Temp(types.Types[types.TINT])


    // if uint(n) > uint(cap(s))
    nif := ir.NewIfStmt(base.Pos, nil, nil, nil)
    nuint := typecheck.Conv(nn, types.Types[types.TUINT])
    scapuint := typecheck.Conv(ir.NewUnaryExpr(base.Pos, ir.OCAP, s), types.Types[types.TUINT])
    nif.Cond = ir.NewBinaryExpr(base.Pos, ir.OGT, nuint, scapuint)

    // instantiate growslice(typ *type, []any, int) []any
  //
  // 这里的 growslice 就是  runtime 包中的 growslice
    fn := typecheck.LookupRuntime("growslice")
    fn = typecheck.SubstArgTypes(fn, elemtype, elemtype)

    // s = growslice(T, s, n)
  // T 是 slice 的元素类型
  // s 旧的 slice 切片
  // n 为 len(s) + len(l2)
  // 
  // mkcall1(fn, s.Type(), nif.PtrInit(), reflectdata.TypePtr(elemtype), s, nn)
    nif.Body = []ir.Node{ir.NewAssignStmt(base.Pos, s, mkcall1(fn, s.Type(), nif.PtrInit(), reflectdata.TypePtr(elemtype), s, nn))}
    nodes.Append(nif)

  ...

}

func mkcall1(fn ir.Node, t *types.Type, init *ir.Nodes, args ...ir.Node) *ir.CallExpr {
    // s = growslice(T, s, n)
  // vmkcall(growslice, T, s, n)
  // 
  // 运行时调用 growslice 进行扩容
  return vmkcall(fn, t, init, args)
}

至此,终于知道了 SliceAppend2() 中,slice 最终容量为10的原因。
同理,也可以通过相同的计算得知 其他几种写法得到 cap 数值的原因。

在源码中还有非常多的细节也可能导致结果有偏差,需要具体案例具体分析

4.小结

对于 slice 的扩容,需要知晓以下几个知识点:
1.在向slice追加元素时,如果 cap 不够,会进行扩容
2.不同go版本的扩容逻辑不同 (go1.18与go1.18之前的版本就不一样),会导致 cap 不一样
3.不同的数据类型有不同扩容逻辑,会导致 cap 不一样
4.相同数据类型,追加不同个数元素,会导致 cap 不一样
5.相同数据类型,批量追加 或者 逐个追加 相同个数 元素,会导致 cap 不一样

假设把 容量为4的int切片追加5个元素 改成 容量为40的int切片追加50个元素,你知道结果吗?
估计需要把所有的 class 等级以及对应等级内存块的大小都背诵下来吧,假设能够背诵下来的话!

最后:此生也有涯,此生学无涯!共勉!!!

Golang

评论啦~