切片扩容大法

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_class128 找到第五号元素 为 4,再从 class_to_size 找到 第四号元素 为 48,这就是新切片占用的内存大小,每个int 占用 8 字节,所以最终切片的容量为 6 。所以说切片的扩容有它基本的扩容规则,在规则之后还要考虑内存对齐,这就代表不同数据类型的切片扩容的容量大小是会不一致。
Q:好,那我们进入下一个问题

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!