乐趣区

关于go:Go-语言切片是如何扩容的

原文链接: Go 语言切片是如何扩容的?

在 Go 语言中,有一个很罕用的数据结构,那就是切片(Slice)。

切片是一个领有雷同类型元素的可变长度的序列,它是基于数组类型做的一层封装。它非常灵活,反对主动扩容。

切片是一种援用类型,它有三个属性:指针 长度 容量

底层源码定义如下:

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}
  1. 指针: 指向 slice 能够拜访到的第一个元素。
  2. 长度: slice 中元素个数。
  3. 容量: slice 起始元素到底层数组最初一个元素间的元素个数。

比方应用 make([]byte, 5) 创立一个切片,它看起来是这样的:

申明和初始化

切片的应用还是比较简单的,这里举一个例子,间接看代码吧。

func main() {var nums []int  // 申明切片
    fmt.Println(len(nums), cap(nums)) // 0 0
    nums = append(nums, 1)   // 初始化
    fmt.Println(len(nums), cap(nums)) // 1 1

    nums1 := []int{1,2,3,4}    // 申明并初始化
    fmt.Println(len(nums1), cap(nums1))    // 4 4

    nums2 := make([]int,3,5)   // 应用 make()函数结构切片
    fmt.Println(len(nums2), cap(nums2))    // 3 5
}

扩容机会

当切片的长度超过其容量时,切片会主动扩容。这通常产生在应用 append 函数向切片中增加元素时。

扩容时,Go 运行时会调配一个新的底层数组,并将原始切片中的元素复制到新数组中。而后,原始切片将指向新数组,并更新其长度和容量。

须要留神的是,因为 扩容会调配新数组并复制元素,因而可能会影响性能。如果你晓得要增加多少元素,能够应用 make 函数事后调配足够大的切片来防止频繁扩容。

接下来看看 append 函数,签名如下:

func Append(slice []int, items ...int) []int

append 函数参数长度可变,能够追加多个值,还能够间接追加一个切片。应用起来比较简单,别离看两个例子:

追加多个值:

package main

import "fmt"

func main() {s := []int{1, 2, 3}
    fmt.Println("初始切片:", s)

    s = append(s, 4, 5, 6)
    fmt.Println("追加多个值后的切片:", s)
}

输入后果为:

初始切片: [1 2 3]
追加多个值后的切片: [1 2 3 4 5 6]

再来看一下间接 追加一个切片:

package main

import "fmt"

func main() {s1 := []int{1, 2, 3}
    fmt.Println("初始切片:", s1)

    s2 := []int{4, 5, 6}
    s1 = append(s1, s2...)
    fmt.Println("追加另一个切片后的切片:", s1)
}

输入后果为:

初始切片: [1 2 3]
追加另一个切片后的切片: [1 2 3 4 5 6]

再来看一个 产生扩容 的例子:

package main

import "fmt"

func main() {s := make([]int, 0, 3) // 创立一个长度为 0,容量为 3 的切片
    fmt.Printf("初始状态: len=%d cap=%d %v\n", len(s), cap(s), s)

    for i := 1; i <= 5; i++ {s = append(s, i) // 向切片中增加元素
        fmt.Printf("增加元素 %d: len=%d cap=%d %v\n", i, len(s), cap(s), s)
    }
}

输入后果为:

初始状态: len=0 cap=3 []
增加元素 1: len=1 cap=3 [1]
增加元素 2: len=2 cap=3 [1 2]
增加元素 3: len=3 cap=3 [1 2 3]
增加元素 4: len=4 cap=6 [1 2 3 4]
增加元素 5: len=5 cap=6 [1 2 3 4 5]

在这个例子中,咱们创立了一个长度为 0,容量为 3 的切片。而后,咱们应用 append 函数向切片中增加 5 个元素。

当咱们增加第 4 个元素时,切片的长度超过了其容量。此时,切片会主动扩容。新的容量是原始容量的两倍,即 6

表面现象曾经看到了,接下来,咱们就深刻到源码层面,看看切片的扩容机制到底是什么样的。

源码剖析

在 Go 语言的源码中,切片扩容通常是在进行切片的 append 操作时触发的。在进行 append 操作时,如果切片容量不足以包容新的元素,就须要对切片进行扩容,此时就会调用 growslice 函数进行扩容。

growslice 函数定义在 Go 语言的 runtime 包中,它的调用是在编译后的代码中实现的。具体来说,当执行 append 操作时,编译器会将其转换为相似上面的代码:

slice = append(slice, elem)

在上述代码中,如果切片容量不足以包容新的元素,则会调用 growslice 函数进行扩容。所以 growslice 函数的调用是 由编译器在生成的机器码中实现的,而不是在源代码中显式调用的

切片扩容策略有两个阶段,go1.18 之前和之后是不同的,这一点在 go1.18 的 release notes 中有阐明。

上面我用 go1.17 和 go1.18 两个版本来离开阐明。先通过一段测试代码,直观感受一下两个版本在扩容上的区别。

package main

import "fmt"

func main() {s := make([]int, 0)

    oldCap := cap(s)

    for i := 0; i < 2048; i++ {s = append(s, i)

        newCap := cap(s)

        if newCap != oldCap {fmt.Printf("[%d -> %4d] cap = %-4d  |  after append %-4d  cap = %-4d\n", 0, i-1, oldCap, i, newCap)
            oldCap = newCap
        }
    }
}

上述代码先创立了一个空的 slice,而后在一个循环里一直往里面 append 新元素。

而后记录容量的变动,每当容量发生变化的时候,记录下老的容量,增加的元素,以及增加完元素之后的容量。

这样就能够察看,新老 slice 的容量变动状况,从而找出法则。

运行后果(1.17 版本):

[0 ->   -1] cap = 0     |  after append 0     cap = 1   
[0 ->    0] cap = 1     |  after append 1     cap = 2   
[0 ->    1] cap = 2     |  after append 2     cap = 4   
[0 ->    3] cap = 4     |  after append 4     cap = 8   
[0 ->    7] cap = 8     |  after append 8     cap = 16  
[0 ->   15] cap = 16    |  after append 16    cap = 32  
[0 ->   31] cap = 32    |  after append 32    cap = 64  
[0 ->   63] cap = 64    |  after append 64    cap = 128 
[0 ->  127] cap = 128   |  after append 128   cap = 256 
[0 ->  255] cap = 256   |  after append 256   cap = 512 
[0 ->  511] cap = 512   |  after append 512   cap = 1024
[0 -> 1023] cap = 1024  |  after append 1024  cap = 1280
[0 -> 1279] cap = 1280  |  after append 1280  cap = 1696
[0 -> 1695] cap = 1696  |  after append 1696  cap = 2304

运行后果(1.18 版本):

[0 ->   -1] cap = 0     |  after append 0     cap = 1
[0 ->    0] cap = 1     |  after append 1     cap = 2   
[0 ->    1] cap = 2     |  after append 2     cap = 4   
[0 ->    3] cap = 4     |  after append 4     cap = 8   
[0 ->    7] cap = 8     |  after append 8     cap = 16  
[0 ->   15] cap = 16    |  after append 16    cap = 32  
[0 ->   31] cap = 32    |  after append 32    cap = 64  
[0 ->   63] cap = 64    |  after append 64    cap = 128 
[0 ->  127] cap = 128   |  after append 128   cap = 256 
[0 ->  255] cap = 256   |  after append 256   cap = 512 
[0 ->  511] cap = 512   |  after append 512   cap = 848 
[0 ->  847] cap = 848   |  after append 848   cap = 1280
[0 -> 1279] cap = 1280  |  after append 1280  cap = 1792
[0 -> 1791] cap = 1792  |  after append 1792  cap = 2560

依据下面的后果还是能看到区别的,具体扩容策略上面边看源码边阐明。

go1.17

扩容调用的是 growslice 函数,我复制了其中计算新容量局部的代码。

// src/runtime/slice.go

func growslice(et *_type, old slice, cap int) slice {
    // ...

    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {newcap = cap} else {
        if old.cap < 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}
        }
    }

    // ...

    return slice{p, old.len, newcap}
}

在分配内存空间之前须要先确定新的切片容量,运行时依据切片的以后容量抉择不同的策略进行扩容:

  1. 如果冀望容量大于以后容量的两倍就会应用冀望容量;
  2. 如果以后切片的长度小于 1024 就会将容量翻倍;
  3. 如果以后切片的长度大于等于 1024 就会每次减少 25% 的容量,直到新容量大于冀望容量;

go1.18

// src/runtime/slice.go

func growslice(et *_type, old slice, cap int) slice {
    // ...

    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}
        }
    }

    // ...

    return slice{p, old.len, newcap}
}

和之前版本的区别,次要在扩容阈值,以及这行代码:newcap += (newcap + 3*threshold) / 4

在分配内存空间之前须要先确定新的切片容量,运行时依据切片的以后容量抉择不同的策略进行扩容:

  1. 如果冀望容量大于以后容量的两倍就会应用冀望容量;
  2. 如果以后切片的长度小于阈值(默认 256)就会将容量翻倍;
  3. 如果以后切片的长度大于等于阈值(默认 256),就会每次减少 25% 的容量,基准是 newcap + 3*threshold,直到新容量大于冀望容量;

内存对齐

剖析完两个版本的扩容策略之后,再看后面的那段测试代码,就会发现扩容之后的容量并不是严格依照这个策略的。

那是为什么呢?

实际上,growslice 的后半局部还有更进一步的优化(内存对齐等),靠的是 roundupsize 函数,在计算完 newcap 值之后,还会有一个步骤计算最终的容量:

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

这个函数的实现就不在这里深刻了,先挖一个坑,当前再来补上。

总结

切片扩容通常是在进行切片的 append 操作时触发的。在进行 append 操作时,如果切片容量不足以包容新的元素,就须要对切片进行扩容,此时就会调用 growslice 函数进行扩容。

切片扩容分两个阶段,分为 go1.18 之前和之后:

一、go1.18 之前:

  1. 如果冀望容量大于以后容量的两倍就会应用冀望容量;
  2. 如果以后切片的长度小于 1024 就会将容量翻倍;
  3. 如果以后切片的长度大于 1024 就会每次减少 25% 的容量,直到新容量大于冀望容量;

二、go1.18 之后:

  1. 如果冀望容量大于以后容量的两倍就会应用冀望容量;
  2. 如果以后切片的长度小于阈值(默认 256)就会将容量翻倍;
  3. 如果以后切片的长度大于等于阈值(默认 256),就会每次减少 25% 的容量,基准是 newcap + 3*threshold,直到新容量大于冀望容量;

以上就是本文的全部内容,如果感觉还不错的话欢送 点赞 转发 关注,感激反对。


参考文章:

  • https://go.dev/doc/go1.18
  • https://go.dev/blog/slices
  • https://go.dev/blog/slices-intro
  • https://golang.design/go-questions/slice/grow/
  • https://draveness.me/golang/docs/part2-foundation/ch03-datast…

举荐浏览:

  • Go 语言数组和切片的区别
  • Go 语言 new 和 make 关键字的区别
  • [为什么 Go 不反对 []T 转换为 []interface](https://mp.weixin.qq.com/s/cwDEgnicK4jkuNpzulU2bw)
  • 为什么 Go 语言 struct 要应用 tags
退出移动版