golang slice的扩容给你整明白的

简介: golang slice的扩容给你整明白的

感激每一个新的挑战,因为它会锻造你的意志和品格。——佚名


1 切片的数据结构定义



type SliceHeader struct {
    Data uintptr
    Len  int
    Cap  int
}


2 append追加



很多网上资料说这块内容很笼统或者说千篇一律的复制别人的东西,完全没有自己去实践,那我这次我专门讲解追加和扩容,让大家有一个直观的认识。


2.1 append的追加不需要返回


一下源码就展示了append一个slice,但是没有返回值接受的情况


// append(slice, 1, 2, 3)
ptr, len, cap := slice
newlen := len + 3
if newlen > cap {
    ptr, len, cap = growslice(slice, newlen)
    newlen = len + 3
}
*(ptr+len) = 1
*(ptr+len+1) = 2
*(ptr+len+2) = 3
return makeslice(ptr, newlen, cap)


我们会先对切片结构体进行解构获取它的数组指针、大小和容量,如果在追加元素后切片的大小大于容量,那么就会调用 runtime.growslice 对切片进行扩容并将新的元素依次加入切片,注意没有赋值的操作。


2.2 append需要返回值接受


一下源码就展示了append一个slice,但是有返回值接受的情况


// slice = append(slice, 1, 2, 3)
a := &slice
ptr, len, cap := slice
newlen := len + 3
if uint(newlen) > uint(cap) {
   newptr, len, newcap = growslice(slice, newlen)
   vardef(a)
   *a.cap = newcap //赋值cap
   *a.ptr = newptr  //复制底层s数组地址指向新的地址
}
newlen = len + 3
*a.len = newlen //修改len属性
*(ptr+len) = 1
*(ptr+len+1) = 2
*(ptr+len+2) = 3


2.3 小结


是否覆盖原变量的逻辑其实差不多,最大的区别在于最后的结果是不是赋值给原有的变量,如果我们选择覆盖原有的变量,也不需要担心切片的拷贝,因为 Go 语言的编译器已经对这种情况作了优化和处理。


3 growslice扩容



首先看下如下代码:


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


如果按网上各种文章中总结的那样:小于原 slice 长度小于 1024 的时候,容量每次增加 1 倍。大于1024,增加0.25倍。按上例分析,添加元素 4 的时候,容量变为4;添加元素 5 的时候不变;添加元素 6 的时候容量增加 1 倍,变成 8。

那上面代码的运行结果就是:


len=5, cap=8


这是错误的!我们来仔细看看,为什么会这样,因为他们给你展示如下代码:


func growslice(et *_type, old slice, cap int) slice {
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            if newcap <= 0 {
                newcap = cap
            }
        }
    }


但是却忽略了后面还有一块代码:


 capmem = roundupsize(uintptr(newcap)* ptrSize)
    newcap =int(capmem / ptrSize)

这个growslice函数的参数依次是元素的类型,老的slice,新slice最小求的容量。例子中s原来只有2个元素,len和cap都为2,append了三个元素后,长度变为5,容量最小要变成5,即调用growslice函数时,传入的第三个参数应该为5。即cap=5。而一方面,doublecap是原slice容量的2倍,等于4。满足第一个if条件,所以newcap变成了5。

接着调用了roundupsize函数,传入40。(代码中ptrSize是指一个指针的大小,在64位机上是8)


我们再看内存对齐,搬出 roundupsize 函数的代码:


// src/runtime/msize.go:13
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 {
        //……
           }
        }
        //……
    }
    const_MaxSmallSize=32768
    const smallSizeMax =1024
    const smallSizeDiv =8

很明显,我们最终将返回这个式子的结果:


class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]]


这是Go源码中有关内存分配的两个slice。class_to_size通过spanClass获取span划分的object大小。而size_to_class8表示通过size获取它的spanClass。关于内存分配span等我前面讲过了,大家自己回头可以看


var size_to_class8 =[smallSizeMax/smallSizeDiv +1]uint8{0,1,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,18,18,19,19,19,19,20,20,20,20,21,21,21,21,22,22,22,22,23,23,23,23,24,24,24,24,25,25,25,25,26,26,26,26,26,26,26,26,27,27,27,27,27,27,27,27,28,28,28,28,28,28,28,28,29,29,29,29,29,29,29,29,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31}
var class_to_size =[_NumSizeClasses]uint16{0,8,16,32,48,64,80,96,112,128,144,160,176,192,208,224,240,256,288,320,352,384,416,448,480,512,576,640,704,768,896,1024,1152,1280,1408,1536,1792,2048,2304,2688,3072,3200,3456,4096,4864,5376,6144,6528,6784,6912,8192,9472,9728,10240,10880,12288,13568,14336,16384,18432,19072,20480,21760,24576,27264,28672,32768}


我们传进去的size等于40。所以(size+smallSizeDiv-1)/smallSizeDiv=5;获取size_to_class8数组中索引为5的元素为4;获取class_to_size中索引为4的元素为48。

最终,新的slice的容量为 6:


newcap =int(capmem / ptrSize)// 6


所以大家看到了吧,眼见为实,自己亲自去看源码,才会有收获,如果你不看大量的资料去研究,去比对,去探索,那么终究你会被网上的各种资料欺骗,导致最终学到的都是错误的知识和认知。


4 关注公众号



微信公众号:堆栈future

相关文章
|
5月前
|
存储 Go
Golang底层原理剖析之slice类型与扩容机制
Golang底层原理剖析之slice类型与扩容机制
63 0
|
1月前
|
Go
Golang语言之切片(slice)快速入门篇
这篇文章是关于Go语言中切片(slice)的快速入门教程,详细介绍了切片的概念、定义方式、遍历、扩容机制、使用注意事项以及相关练习题。
27 5
|
2月前
|
监控 Serverless Go
Golang 开发函数计算问题之Go 语言中切片扩容时需要拷贝原数组中的数据如何解决
Golang 开发函数计算问题之Go 语言中切片扩容时需要拷贝原数组中的数据如何解决
|
4月前
|
Go 索引
GOLANG SLICE 的底层实现
GOLANG SLICE 的底层实现
|
5月前
|
Go 索引
Golang深入浅出之-切片(Slices)入门:创建、操作与扩容机制
【4月更文挑战第20天】Go语言中的切片是动态数组,提供灵活的操作和自动扩容。本文介绍了切片的创建(通过`make()`、数组创建和切片字面量)、基本操作(索引访问、切片、赋值追加和遍历)以及扩容机制(首次和后续扩容策略)。此外,还强调了切片与底层数组的关系、切片越界问题、`append()`的使用以及理解切片的关键点,帮助提升Go编程效率和代码质量。
101 0
|
12月前
|
存储 大数据 Go
100天精通Golang(基础入门篇)——第11天:深入解析Go语言中的切片(Slice)及常用函数应用
100天精通Golang(基础入门篇)——第11天:深入解析Go语言中的切片(Slice)及常用函数应用
90 0
|
5月前
|
Go
golang随笔之slice+append的陷阱
golang随笔之slice+append的陷阱
39 0
golang踩坑 1.slice传参和for range赋值
golang踩坑 1.slice传参和for range赋值
|
运维 Go
学习golang(5) 初探:go 数组/slice 的基本使用
学习golang(5) 初探:go 数组/slice 的基本使用
117 0
|
1月前
|
Go
Golang语言之管道channel快速入门篇
这篇文章是关于Go语言中管道(channel)的快速入门教程,涵盖了管道的基本使用、有缓冲和无缓冲管道的区别、管道的关闭、遍历、协程和管道的协同工作、单向通道的使用以及select多路复用的详细案例和解释。
55 4
Golang语言之管道channel快速入门篇