逐步学习Go-Slice（切片)还可以多挖一下）

作者： /
内容目录

特性

  1. 扩缩容：只有自动扩容，没有自动缩容
  2. 原地与非原地：切片有原地有非原地操作

自动扩容

Slice只有自动扩容，不会自动缩容，而且自动扩容会根据当前slice的容量来计算不同的扩容系数，具体容量和扩展因子关系如下表：

初始容量（Starting Cap） 扩展因子（Growth Factor）
256 2.0
512 1.63
1024 1.44
2048 1.35
4096 1.30

Go 对Slice这么做的原因是：内存和性能之间的权衡。

  1. Go 设定 256 为一个阈值，这个阈值的设定是基于减少添加元素到最终形成非常大的切片时的总内存的重新分配次数。
  2. 当切片长度小于或等于 256 时，每次添加元素导致切片容量不足时，Go会选择按照2倍增加切片容量，以减少内存重分配的次数。
  3. 当切片长度大于 256 但还小于等于 1024 时，每次容量不足时扩大的容量会小于翻倍，这是为了更加接近实际需求，减少内存的浪费。
  4. 当切片长度超过 1024 时，每次扩容的容量比例更大，这样能尽可能减少因为添加元素导致的大切片内存重分配次数。

原地与非原地操作

什么是原地和非原地？

原地算法（in-place algorithm，也称就地算法）是不需要额外的数据结构就能变换输入数据的算法。不过，分配少量空间给部分辅助变量是被允许的。

不是原地就是非原地，非原地就是要分配额外的内存空间来存储数据。

原地与非原地区别

原地操作和非原地操作的主要区别在于，原地操作在原有的内存空间上进行修改，不需要额外分配内存；而非原地操作由于需要创建新的空间来保存数据，因此会产生额外的内存开销。

slice中的原地与非原地操作

原地操作：

  1. 索引操作
  2. 获取子切片
  3. append操作（当slice容量足够时，也就是不扩容时）

非原地操作：

  1. append操作（当slice容量不足时，进行扩容）
  2. copy操作

原地操作示例

索引操作

以下代码获取切片的某个元素

    s := make([]int, 5)
    s[0] = 1
    s[1] = 2
    s[2] = 3
    s[3] = 4
    s[4] = 5

子切片

子切片就是原来切片的子级。子切片引用原来切片的元素，所以是原址。子切片并没有申请内存空间把元素拷贝到新空间中。


s1 := s[:1]
fmt.Printf("s1 slice addr: %p\n", &s1)
println("s1 addr: ", unsafe.Pointer(&s1[0]))

append操作

append操作在容量足够的情况下是原址操作，比如：我们创建一个slice，容量为5，然后调用append添加第6个元素之前都是原址操作。


s := make([]int, 10）
s = append(s, 1, 2, 3, 4, 5)

如何确定自己代码是否是原址？看汇编


 TEXT    main.createSlice(SB), ABIInternal, $32-8
 CMPQ    SP, 16(R14)
 PCDATA  $0, $-2
 JLS     51
 PCDATA  $0, $-1
 PUSHQ   BP
 MOVQ    SP, BP
 SUBQ    $24, SP
 FUNCDATA        $0, 
 FUNCDATA        $1, 
 FUNCDATA        $5, 
 FUNCDATA        $6, 
 PCDATA  $3, $1
 MOVQ    AX, main.cap+40(SP)
 PCDATA  $3, $-1
 MOVQ    AX, BX
 MOVQ    BX, CX
 LEAQ    type:int(SB), AX
 PCDATA  $1, $0
 CALL    runtime.makeslice(SB)
 MOVQ    main.cap+40(SP), BX
 MOVQ    BX, CX
 ADDQ    $24, SP
 POPQ    BP
 RET
 NOP
 PCDATA  $1, $-1
 PCDATA  $0, $-2
 MOVQ    AX, 8(SP)
 CALL    runtime.morestack_noctxt(SB)
 PCDATA  $0, $-1
 MOVQ    8(SP), AX
 JMP     0

非原地操作示例

append操作

你make了一个容量为5的slice，然后再append 5个元素，这会自动扩容。


    s := make([]int, 5)
    s[0] = 1
    s[1] = 2
    s[2] = 3
    s[3] = 4
    s[4] = 5
    s = append(s, 1, 2, 3, 4, 5)
    fmt.Printf("s slice addr: %p\n", &s)

汇编代码：


...
CALL    runtime.makeslice(SB)
...

CALL    runtime.growslice(SB)
...

copy操作

copy操作是深拷贝。


    scopy := make([]int, 10)
    copy(s, scopy)
    println("scopy 1st element addr: ", unsafe.Pointer(&scopy[0]))

slice源码

下面的源码我进行了部分删除，为了更好的聚焦核心内容。

创建makeslice


func makeslice(et *_type, len, cap int) unsafe.Pointer {
    // 根据slice的类型和容量来计算slice总共需要多少个字节的内存
    mem, overflow := math.MulUintptr(et.Size_, uintptr(cap))

    // 分配内存
    // mem为字节长度
    return mallocgc(mem, et, true)
}

自动扩容growslice

首先调用nextslicecap计算出新的容量，然后再使用Switch-case来计算出新容量对应的字节容量，最后申请内存并把老的Slice元素指针复制到新的Slice元素指针。


func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
    oldLen := newLen - num

    // 根据上文中提到的容量大小和扩展因子来计算新的容量
    newcap := nextslicecap(newLen, oldCap)

    switch {
    // 如果是一个字节的类型(byte,bool, int8系列)，那么新的切片元素指针et内存大小=newcap
    case et.Size_ == 1:
        lenmem = uintptr(oldLen)
        newlenmem = uintptr(newLen)
        capmem = roundupsize(uintptr(newcap), noscan)
        overflow = uintptr(newcap) > maxAlloc
        newcap = int(capmem)

    // 如果是类型正好是系统架构的字宽，那么容量需要乘以这个字宽: newcap * et.Size——
    case et.Size_ == goarch.PtrSize:
        lenmem = uintptr(oldLen) * goarch.PtrSize
        newlenmem = uintptr(newLen) * goarch.PtrSize
        capmem = roundupsize(uintptr(newcap)*goarch.PtrSize, noscan)
        overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
        newcap = int(capmem / goarch.PtrSize)

    // 如果类型是2的倍数：2,4,8， 16...，使用位运算来计算内存大小
    case isPowerOfTwo(et.Size_):
        var shift uintptr
        if goarch.PtrSize == 8 {
            // Mask shift for better code generation.
            shift = uintptr(sys.TrailingZeros64(uint64(et.Size_))) & 63
        } else {
            shift = uintptr(sys.TrailingZeros32(uint32(et.Size_))) & 31
        }
        lenmem = uintptr(oldLen) << shift
        newlenmem = uintptr(newLen) << shift
        capmem = roundupsize(uintptr(newcap)<<shift, noscan)
        overflow = uintptr(newcap) > (maxAlloc >> shift)
        newcap = int(capmem >> shift)
        capmem = uintptr(newcap) << shift
    // 其他情况就直接newcap * et.Size_
    default:
        lenmem = uintptr(oldLen) * et.Size_
        newlenmem = uintptr(newLen) * et.Size_
        capmem, overflow = math.MulUintptr(et.Size_, uintptr(newcap))
        capmem = roundupsize(capmem, noscan)
        newcap = int(capmem / et.Size_)
        capmem = uintptr(newcap) * et.Size_
    }

    if overflow || capmem > maxAlloc {
        panic(errorString("growslice: len out of range"))
    }

    var p unsafe.Pointer
    if et.PtrBytes == 0 {
        p = mallocgc(capmem, nil, false)
        // The append() that calls growslice is going to overwrite from oldLen to newLen.
        // Only clear the part that will not be overwritten.
        // The reflect_growslice() that calls growslice will manually clear
        // the region not cleared here.
        memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
    } else {
        // Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
        p = mallocgc(capmem, et, true)
        if lenmem > 0 && writeBarrier.enabled {
            // Only shade the pointers in oldPtr since we know the destination slice p
            // only contains nil pointers because it has been cleared during alloc.
            //
            // It's safe to pass a type to this function as an optimization because
            // from and to only ever refer to memory representing whole values of
            // type et. See the comment on bulkBarrierPreWrite.
            bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(oldPtr), lenmem-et.Size_+et.PtrBytes, et)
        }
    }
    memmove(p, oldPtr, lenmem)

    return slice{p, newLen, newcap}
}

// nextslicecap computes the next appropriate slice length.
func nextslicecap(newLen, oldCap int) int {
    newcap := oldCap
    doublecap := newcap + newcap
    if newLen > doublecap {
        return newLen
    }

    const threshold = 256
    if oldCap < threshold {
        return doublecap
    }
    for {
        // 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) >> 2

        // We need to check `newcap >= newLen` and whether `newcap` overflowed.
        // newLen is guaranteed to be larger than zero, hence
        // when newcap overflows then `uint(newcap) > uint(newLen)`.
        // This allows to check for both with the same comparison.
        if uint(newcap) >= uint(newLen) {
            break
        }
    }

    // Set newcap to the requested cap when
    // the newcap calculation overflowed.
    if newcap <= 0 {
        return newLen
    }
    return newcap
}

可以留心一下

  1. 子切片中的元素是原来切片元素的子集是引用关系，所以有一个子切片就不会释放原来切片的内存，像是内存泄露
  2. 尽量避免切片自动扩容，原因主要是切片耗时并且不会自动缩容
  3. 大切片只有一个很小的子切片，这时候建议copy一个小切片，让切片尽快释放内存
  4. 切片循环引用问题

参考

  1. runtime: make slice growth formula a bit smoother

相关文章

发表评论

您的邮箱地址不会被公开。 必填项已用 * 标注

滚动至顶部