切片扩容大法

Q: 你先简单介绍一下自己吧 A: 嘛哩嘛哩哄，嘛哩嘛哩哄，嘛哩嘛哩哄 Q: 你说这么多嘛哩嘛哩哄，那你了解数组吗？ A: 数组是具有相同类型且长度固定的数据结构，由于长度不可改变，在实际中使用较少，一般用切片来代替使用。 Q: 你刚刚说到切片，切片和数组有什么相同点和不同点吗？ A: 相同点是他们都是只能储存相同类型的数据结构，切片的底层数据也是基于数组的，不同点是切片是可以改变长度的，能自动扩容。 Q: 嗯，那切片的底层是怎么组成的呢，它的扩容规则你清楚吗？ A: 切片由三部分组成，分别是切片的长度，切片的容量，切片的数据（指向底层数组的指针），至于扩容规则可就难说了。 Q: 难说也是要说的，你搞快点。 A: 切片扩容的基本规则是：当切片 append 的时候（会调用下面的函数），新切片的必须容量大于老切片容量的两倍的，那么新切片的容量就是新切片的必须容量，反之，如果老切片的长度小于 1024，那么新切片的容量就等于老切片的容量的两倍，如果老切片大于等于 1024，则新切片容量等于老切片容量的 1.25 倍，这是切片的预估容量。

// runtime/slice.go
func growslice(et *_type, old slice, cap int) slice {
//et 表示slice的一个元素，old 表示旧的slice cap 表示新切片必须的容量
    ...
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            // Set newcap to the requested cap when
            // the newcap calculation overflowed.
            if newcap <= 0 {
                newcap = cap
            }
        }
    }
    ...
}

根据以上规则，一下切片扩容必须的切片容量为 5 ，5 > 2*2, 所以打印出来应该是 len=5, cap=5

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, 原来容量计算完了后还要考虑到内存的高效利用，进行内存对齐，则会调用这个函数

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 {
            return uintptr(class_to_size[size_to_class128[(size-smallSizeMax+largeSizeDiv-1)/largeSizeDiv]])
        }
    }
    if size+_PageSize < size {
        return size
    }
    return alignUp(size, _PageSize)
}

size 表示新切片需要的内存大小我们传入的 int 类型，每个占用 8 字节 (可以调用 unsafe.Sizeof() 函数查看占用的大小)，一共 5 个所以是 40，size 小于_MaxSmallSize 并且小于 smallSizeMax-8 ，那么使用通用公式 (size+smallSizeDiv-1)/smallSizeDiv 计算得到 5，然后到 size_to_class8 找到第五号元素为 4，再从 class_to_size 找到第四号元素为 48，这就是新切片占用的内存大小，每个 int 占用 8 字节，所以最终切片的容量为 6 。所以说切片的扩容有它基本的扩容规则，在规则之后还要考虑内存对齐，这就代表不同数据类型的切片扩容的容量大小是会不一致。 Q：好，那我们进入下一个问题

原文作者：轻描淡写

原文：https://learnku.com/articles/60644

切片扩容大法

mf67

评论(0)