切换语言为:繁体
Golang是如何实现动态数组功能的?Slice切片原理解析

Golang是如何实现动态数组功能的?Slice切片原理解析

  • 爱糖宝
  • 2024-08-04
  • 2083
  • 0
  • 0

当我们需要使用数组,但是又不能提前定义数组大小时,可以使用golang的动态数组结构,slice切片。在 Go 语言的众多特性里,slice 是我们经常用到的数据结构。但您有没有想过,它在背后是怎么工作的呢?接下来,咱们就一起仔仔细细地研究研究 slice 的底层到底是咋回事。比如它的底层数据结构是咋样的,又是怎么和数组配合实现动态数组功能的。把这些弄明白了,咱们写代码不光能更高效,还能躲开不少容易出错的地方。

1 原理

1.1 数据结构

我们每定义一个slice变量,golang底层都会构建一个slice结构的对象。slice结构体由3个成员变量构成:

  • array表示数组指针,数组用于存储数据。

  • len表示切片长度,也就是数组index从0到len-1已存储数据。

  • cap表示切片容量,当切片长度超过最大容量时,需要扩容申请更大长度的数组。

type slice struct {
    array unsafe.Pointer // 数组指针
    len   int // 切片长度
    cap   int // 切片容量
}

Golang是如何实现动态数组功能的?Slice切片原理解析

1.2 切片扩容

当我们往切片中append时,如果新添加数据会导致切片的len>cap,则会触发扩容。申请容量更大的新数组,并将旧数组数据复制到新数组。

当切片扩容时,新申请的数组长度要满足3个需求:

  1. 数组要能承载本次数据append进去,这是基本要求。

  2. 除了1中的基本要求,可以额外多申请一部分空间,防止后续append频繁扩容,引起性能问题。

  3. 额外申请的空间不能过大,防止内存浪费。

为了满足上述的3个要求,golang底层的扩容策略是如果需要的容量比旧容量大很多,则不申请额外的空间;如果需要的容量比旧容量并没有大很多,则可以多申请一些额外的内存空间。具体策略如下:

  1. 如果本次append之后,需要的容量大于旧切片容量*2,则新切片容量等于需要的容量。

  2. 如果旧切片容量<256,则新切片容量为旧切片容量*2。

  3. 否则,以公式newcap += (newcap + 3*threshold) / 4迭代,直到newcap大于需要的容量为止,将newcap作为新切片容量。

// 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.
// 参数cap表示本次append之后需要的切片容量
func growslice(et *_type, old slice, cap int) slice {
    // 扩容策略,决定扩容后切片容量newcap,也就是需要申请的新数组长度。
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        const threshold = 256
        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
            }
        }
    }
    
    // 计算新切片的容量、长度
    var overflow bool
    var lenmem, newlenmem, capmem uintptr
    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)
    
    // 数组内存申请
    var p unsafe.Pointer
    if et.ptrdata == 0 {
        p = mallocgc(capmem, nil, false)
    } else {
        p = mallocgc(capmem, et, true)
    }
    
    // 数据复制
    memmove(p, old.array, lenmem)
    
    // 构建新的切片返回
    return slice{p, old.len, newcap}
}

1.3 for 循环的坑

在for和for range循环中,对于循环迭代变量,它的作用域是整个循环。在循环时,会创建一个变量,每次迭代都会把值赋给同一个地址的变量。如果我们的代码有引用这个变量,可能会出现不符合预期的结果。

比如下面对for循环迭代变量i的使用,会输出不符合预期的结果。

func main() {
    var out []*int
    for i := 0; i < 3; i++ {
        out = append(out, &i)
    }
    fmt.Println("Values:", *out[0], *out[1], *out[2]) // 输出 Values: 3 3 3
    fmt.Println("Addresses:", out[0], out[1], out[2]) // 输出 Addresses: 0x40e020 0x40e020 0x40e020
}

原因是在每次迭代中,我们将变量 i 的地址附加到 out 切片,但由于它是同一个变量,因此我们附加相同的地址,该地址最终包含分配给 i 的最后一个值。解决方案之一是将循环变量复制到新变量中:

for i := 0; i < 3; i++ {
+   i := i // Copy i into a new variable.
    out = append(out, &i)
 }

改正之后输出符合预期的结果:

Values: 0 1 2
Addresses: 0x40e024 0x40e028 0x40e032

又比如下面for range循环,对迭代变量v的使用,也会输出不符合预期的结果。

package main

import "fmt"

type User struct {
    Name string
    Age  int
}

func main() {
    userMap := make(map[string]*User)
    users := []User{
        {Name: "a", Age: 22},
        {Name: "b", Age: 23},
        {Name: "c", Age: 21},
    }

    for _, v := range users {
        userMap[v.Name] = &v
    }

    for name, user := range userMap {
        fmt.Println(name, "=>", user.Age, ",Addresses:", &user) // 输出一下user的地址
    }
}

上面的代码输出不符合预期的结果,三个人的年龄和数据地址变成了相同值:

a => 21 ,Addresses: 0xc000012028
b => 21 ,Addresses: 0xc000012028
c => 21 ,Addresses: 0xc000012028

原因跟for循环一样,在循环时,创建了变量v,后续每次迭代都把值拷贝给变量v,导致循环结束后,拷贝的是最后一个,因此输出的age都是21。解决方案之一也是将循环变量复制到新变量中:

for _, v := range users {
+       temp := v
        userMap[v.Name] = &temp
}

**为了防止循环迭代变量误用导致bug,在Go 1.22中,循环迭代变量的作用域,不再是循环作用域,而是迭代作用域,每次迭代都会申请一个新变量。**Fixing For Loops in Go 1.22

2 实践经验

  1. 切片容量预分配。如果提前能预估切片容量,最好提前在make时就分配好容量,避免后续go底层的再次扩容,在一定程度上能提升代码执行效率。

  2. 注意对slice的循环,看是否需要将循环迭代变量赋值到一个临时变量使用,防止bug。

3 高频面试题

  1. 数组和切片的区别 (基本必问)

  2. 切片的扩容策略是怎样的?

  3. for range 的时候它的地址会发生变化么?for 循环遍历 slice 有什么问题?

  4. 拷贝大切片一定比小切片代价大吗?

对于浅拷贝,比如下面的切片赋值,拷贝大切片和小切片代价一样。原因是浅拷贝a和b共用底层数组,不需要重新申请数组空间,做数组数据迁移,而只需要将a的slice数据结构array、len、cap原样赋值给b的slice。

a:=[]int{1,2}
b:=a

Golang是如何实现动态数组功能的?Slice切片原理解析

对于深拷贝,比如调用copy函数拷贝,拷贝大切片比小切片代价大。原因是深拷贝a和b底层数组不共用,需要重新申请数组空间,并将a中数组元素复制到b,大切片的数据量大,因此数组申请和数据复制的代价也高一些。

a:=[]int{1,2}
b:=make([]int,0)
copy(b,a)

Golang是如何实现动态数组功能的?Slice切片原理解析


0条评论

您的电子邮件等信息不会被公开,以下所有项均必填

OK! You can skip this field.