偷偷摘套内射激情视频,久久精品99国产国产精,中文字幕无线乱码人妻,中文在线中文a,性爽19p

Go 語(yǔ)言切片是如何擴(kuò)容的?

開(kāi)發(fā) 前端
切片擴(kuò)容通常是在進(jìn)行切片的 append? 操作時(shí)觸發(fā)的。在進(jìn)行 append? 操作時(shí),如果切片容量不足以容納新的元素,就需要對(duì)切片進(jìn)行擴(kuò)容,此時(shí)就會(huì)調(diào)用 growslice 函數(shù)進(jìn)行擴(kuò)容。

在 Go 語(yǔ)言中,有一個(gè)很常用的數(shù)據(jù)結(jié)構(gòu),那就是切片(Slice)。

切片是一個(gè)擁有相同類(lèi)型元素的可變長(zhǎng)度的序列,它是基于數(shù)組類(lèi)型做的一層封裝。它非常靈活,支持自動(dòng)擴(kuò)容。

切片是一種引用類(lèi)型,它有三個(gè)屬性:指針,長(zhǎng)度和容量。

圖片

底層源碼定義如下:

type slice struct {
array unsafe.Pointer
len int
cap int
}

  1. 指針: 指向 slice 可以訪(fǎng)問(wèn)到的第一個(gè)元素。
  2. 長(zhǎng)度: slice 中元素個(gè)數(shù)。
  3. 容量: slice 起始元素到底層數(shù)組最后一個(gè)元素間的元素個(gè)數(shù)。

比如使用 make([]byte, 5) 創(chuàng)建一個(gè)切片,它看起來(lái)是這樣的:

圖片

聲明和初始化

切片的使用還是比較簡(jiǎn)單的,這里舉一個(gè)例子,直接看代碼吧。

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()函數(shù)構(gòu)造切片
fmt.Println(len(nums2), cap(nums2)) // 3 5
}

擴(kuò)容時(shí)機(jī)

當(dāng)切片的長(zhǎng)度超過(guò)其容量時(shí),切片會(huì)自動(dòng)擴(kuò)容。這通常發(fā)生在使用 append 函數(shù)向切片中添加元素時(shí)。

擴(kuò)容時(shí),Go 運(yùn)行時(shí)會(huì)分配一個(gè)新的底層數(shù)組,并將原始切片中的元素復(fù)制到新數(shù)組中。然后,原始切片將指向新數(shù)組,并更新其長(zhǎng)度和容量。

需要注意的是,由于擴(kuò)容會(huì)分配新數(shù)組并復(fù)制元素,因此可能會(huì)影響性能。如果你知道要添加多少元素,可以使用 make 函數(shù)預(yù)先分配足夠大的切片來(lái)避免頻繁擴(kuò)容。

接下來(lái)看看 append 函數(shù),簽名如下:

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

append 函數(shù)參數(shù)長(zhǎng)度可變,可以追加多個(gè)值,還可以直接追加一個(gè)切片。使用起來(lái)比較簡(jiǎn)單,分別看兩個(gè)例子:

追加多個(gè)值:

package main

import "fmt"

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

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

輸出結(jié)果為:

初始切片: [1 2 3]
追加多個(gè)值后的切片: [1 2 3 4 5 6]

再來(lái)看一下直接追加一個(gè)切片:

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("追加另一個(gè)切片后的切片:", s1)
}

輸出結(jié)果為:

初始切片: [1 2 3]
追加另一個(gè)切片后的切片: [1 2 3 4 5 6]

再來(lái)看一個(gè)發(fā)生擴(kuò)容的例子:

package main

import "fmt"

func main() {
s := make([]int, 0, 3) // 創(chuàng)建一個(gè)長(zhǎng)度為0,容量為3的切片
fmt.Printf("初始狀態(tài): 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)
}
}

輸出結(jié)果為:

初始狀態(tài): 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]

在這個(gè)例子中,我們創(chuàng)建了一個(gè)長(zhǎng)度為 0?,容量為 3? 的切片。然后,我們使用 append? 函數(shù)向切片中添加 5 個(gè)元素。

當(dāng)我們添加第 4? 個(gè)元素時(shí),切片的長(zhǎng)度超過(guò)了其容量。此時(shí),切片會(huì)自動(dòng)擴(kuò)容。新的容量是原始容量的兩倍,即 6。

表面現(xiàn)象已經(jīng)看到了,接下來(lái),我們就深入到源碼層面,看看切片的擴(kuò)容機(jī)制到底是什么樣的。

源碼分析

在 Go 語(yǔ)言的源碼中,切片擴(kuò)容通常是在進(jìn)行切片的 append? 操作時(shí)觸發(fā)的。在進(jìn)行 append? 操作時(shí),如果切片容量不足以容納新的元素,就需要對(duì)切片進(jìn)行擴(kuò)容,此時(shí)就會(huì)調(diào)用 growslice 函數(shù)進(jìn)行擴(kuò)容。

growslice? 函數(shù)定義在 Go 語(yǔ)言的 runtime 包中,它的調(diào)用是在編譯后的代碼中實(shí)現(xiàn)的。具體來(lái)說(shuō),當(dāng)執(zhí)行 append 操作時(shí),編譯器會(huì)將其轉(zhuǎn)換為類(lèi)似下面的代碼:

slice = append(slice, elem)

在上述代碼中,如果切片容量不足以容納新的元素,則會(huì)調(diào)用 growslice? 函數(shù)進(jìn)行擴(kuò)容。所以 growslice 函數(shù)的調(diào)用是由編譯器在生成的機(jī)器碼中實(shí)現(xiàn)的,而不是在源代碼中顯式調(diào)用的。

切片擴(kuò)容策略有兩個(gè)階段,go1.18 之前和之后是不同的,這一點(diǎn)在 go1.18 的 release notes 中有說(shuō)明。

下面我用 go1.17 和 go1.18 兩個(gè)版本來(lái)分開(kāi)說(shuō)明。先通過(guò)一段測(cè)試代碼,直觀感受一下兩個(gè)版本在擴(kuò)容上的區(qū)別。

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

上述代碼先創(chuàng)建了一個(gè)空的 slice,然后在一個(gè)循環(huán)里不斷往里面 append 新元素。

然后記錄容量的變化,每當(dāng)容量發(fā)生變化的時(shí)候,記錄下老的容量,添加的元素,以及添加完元素之后的容量。

這樣就可以觀察,新老 slice 的容量變化情況,從而找出規(guī)律。

運(yùn)行結(jié)果(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

運(yùn)行結(jié)果(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

根據(jù)上面的結(jié)果還是能看到區(qū)別的,具體擴(kuò)容策略下面邊看源碼邊說(shuō)明。

go1.17

擴(kuò)容調(diào)用的是 growslice 函數(shù),我復(fù)制了其中計(jì)算新容量部分的代碼。

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

在分配內(nèi)存空間之前需要先確定新的切片容量,運(yùn)行時(shí)根據(jù)切片的當(dāng)前容量選擇不同的策略進(jìn)行擴(kuò)容:

  1. 如果期望容量大于當(dāng)前容量的兩倍就會(huì)使用期望容量;
  2. 如果當(dāng)前切片的長(zhǎng)度小于 1024 就會(huì)將容量翻倍;
  3. 如果當(dāng)前切片的長(zhǎng)度大于等于 1024 就會(huì)每次增加 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}
}

和之前版本的區(qū)別,主要在擴(kuò)容閾值,以及這行代碼:newcap += (newcap + 3*threshold) / 4。

在分配內(nèi)存空間之前需要先確定新的切片容量,運(yùn)行時(shí)根據(jù)切片的當(dāng)前容量選擇不同的策略進(jìn)行擴(kuò)容:

  1. 如果期望容量大于當(dāng)前容量的兩倍就會(huì)使用期望容量;
  2. 如果當(dāng)前切片的長(zhǎng)度小于閾值(默認(rèn) 256)就會(huì)將容量翻倍;
  3. 如果當(dāng)前切片的長(zhǎng)度大于等于閾值(默認(rèn) 256),就會(huì)每次增加 25% 的容量,基準(zhǔn)是 newcap + 3*threshold,直到新容量大于期望容量;

內(nèi)存對(duì)齊

分析完兩個(gè)版本的擴(kuò)容策略之后,再看前面的那段測(cè)試代碼,就會(huì)發(fā)現(xiàn)擴(kuò)容之后的容量并不是嚴(yán)格按照這個(gè)策略的。

那是為什么呢?

實(shí)際上,growslice? 的后半部分還有更進(jìn)一步的優(yōu)化(內(nèi)存對(duì)齊等),靠的是 roundupsize? 函數(shù),在計(jì)算完 newcap 值之后,還會(huì)有一個(gè)步驟計(jì)算最終的容量:

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

這個(gè)函數(shù)的實(shí)現(xiàn)就不在這里深入了,先挖一個(gè)坑,以后再來(lái)補(bǔ)上。

總結(jié)

切片擴(kuò)容通常是在進(jìn)行切片的 append? 操作時(shí)觸發(fā)的。在進(jìn)行 append? 操作時(shí),如果切片容量不足以容納新的元素,就需要對(duì)切片進(jìn)行擴(kuò)容,此時(shí)就會(huì)調(diào)用 growslice 函數(shù)進(jìn)行擴(kuò)容。

切片擴(kuò)容分兩個(gè)階段,分為 go1.18 之前和之后:

一、go1.18 之前:

  1. 如果期望容量大于當(dāng)前容量的兩倍就會(huì)使用期望容量;
  2. 如果當(dāng)前切片的長(zhǎng)度小于 1024 就會(huì)將容量翻倍;
  3. 如果當(dāng)前切片的長(zhǎng)度大于 1024 就會(huì)每次增加 25% 的容量,直到新容量大于期望容量;

二、go1.18 之后:

  1. 如果期望容量大于當(dāng)前容量的兩倍就會(huì)使用期望容量;
  2. 如果當(dāng)前切片的長(zhǎng)度小于閾值(默認(rèn) 256)就會(huì)將容量翻倍;
  3. 如果當(dāng)前切片的長(zhǎng)度大于等于閾值(默認(rèn) 256),就會(huì)每次增加 25% 的容量,基準(zhǔn)是 newcap + 3*threshold,直到新容量大于期望容量;

以上就是本文的全部?jī)?nèi)容,如果覺(jué)得還不錯(cuò)的話(huà)歡迎點(diǎn)贊,轉(zhuǎn)發(fā)和關(guān)注,感謝支持。

參考文章:

  • 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-datastructure/golang-array-and-slice/

責(zé)任編輯:武曉燕 來(lái)源: AlwaysBeta
相關(guān)推薦

2023-10-11 06:59:48

Go語(yǔ)言切片

2023-03-29 08:03:53

2018-08-20 08:15:50

編程語(yǔ)言Go語(yǔ)言切片

2021-07-13 06:44:04

Go語(yǔ)言數(shù)組

2022-11-10 07:43:45

2014-11-10 10:52:33

Go語(yǔ)言

2022-04-06 08:19:13

Go語(yǔ)言切片

2021-06-26 07:29:42

RedisHashtable數(shù)據(jù)

2025-04-02 05:23:00

GoChannel數(shù)據(jù)

2020-08-05 12:27:18

Go語(yǔ)言碼農(nóng)

2021-04-09 10:38:59

Go 語(yǔ)言數(shù)組與切片

2022-06-02 13:54:04

Go數(shù)組切片

2021-11-19 11:36:42

語(yǔ)言string字符串

2020-10-23 06:56:00

C語(yǔ)言動(dòng)態(tài)字符串

2024-05-17 08:47:33

數(shù)組切片元素

2023-05-15 08:01:16

Go語(yǔ)言

2023-01-12 08:52:50

GoroutinesGo語(yǔ)言

2022-02-14 08:25:50

Go語(yǔ)言面試

2023-12-27 08:12:04

切片Go語(yǔ)言

2017-12-27 14:52:21

JSGo編程語(yǔ)言
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)