Go 語言切片是如何擴容的？

来源:https://www.cnblogs.com/alwaysbeta/archive/2023/04/09/17300635.html
-Advertisement-
Play Games

原文鏈接： Go 語言切片是如何擴容的？ 在 Go 語言中，有一個很常用的數據結構，那就是切片（Slice）。 切片是一個擁有相同類型元素的可變長度的序列，它是基於數組類型做的一層封裝。它非常靈活，支持自動擴容。 切片是一種引用類型，它有三個屬性：指針，長度和容量。 底層源碼定義如下： type s ...


原文鏈接： 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，直到新容量大於期望容量；

以上就是本文的全部內容，如果覺得還不錯的話歡迎點贊，轉發和關註，感謝支持。

參考文章：

推薦閱讀：


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • SpringMVC中使用引入jquery不能載入頁面
    今天在學習springMVC的json數據綁定時，需要使用到jquery發送ajax請求。但是當我通過是<script>標簽引入了jquery.js。 但是當我訪問該jsp的時候就是不顯示頁面的內容 我一直以為時SpringMVC的servelt攔截器攔截了靜態資源，但是我過濾了靜態資源還是不顯示。 ...
  • Java 異常處理：使用和思考
    概念 異常處理的概念起源於早期的編程語言，如 LISP、PL/I 和 CLU。這些編程語言首次引入了異常處理機制，以便在程式執行過程中檢測和處理錯誤情況。異常處理機制隨後在 Ada、Modula-3、C++、Python、Java 等編程語言中得到了廣泛採用和發展。在 Java 中，異常處理是提供一 ...
  • 機械硬碟與固態硬碟的適用場景
    之前一直以為固態硬碟各方面都比機械硬碟性能高，所以首選固態硬碟，直到看了極客時間-深入淺出電腦組成原理中硬碟相關章節的內容，才發現固態硬碟原來是有缺點的，所以這裡來做一個總結。 機械硬碟（HDD） 機械硬碟由以下幾個部分組成： 盤面：盤面（碟片）上有一層磁性塗層，數據就是存儲在這個磁性的塗層上，一 ...
  • 一天吃透電腦網路八股文
    網路分層結構 電腦網路體系大致分為三種，OSI七層模型、TCP/IP四層模型和五層模型。一般面試的時候考察比較多的是五層模型。最全面的Java面試網站 五層模型：應用層、傳輸層、網路層、數據鏈路層、物理層。 應用層：為應用程式提供交互服務。在互聯網中的應用層協議很多，如功能變數名稱系統DNS、HTTP協議 ...
  • 提高代碼質量！詳解在Gradle項目中使用PMD的正確姿勢
    當今的軟體開發需要使用許多不同的工具和技術來確保代碼質量和穩定性。PMD是一個流行的靜態代碼分析工具，可以幫助開發者在編譯代碼之前發現潛在的問題。在本文中，我們將討論如何在Gradle中使用PMD，並介紹一些最佳實踐。 什麼是PMD？ PMD是一個用於Java代碼的靜態代碼分析工具。它可以幫助開發者 ...
  • 完善版手游導航源碼app軟體 APP手機軟體 應用商城下載類網站佈局規整
    demo軟體園每日更新資源,請看到最後就能獲取你想要的: 1.完善版手游導航源碼app軟體 APP手機軟體 應用商城下載類網站佈局規整，利於用戶體驗 瀏覽網站看到一款帶後臺的app軟體手游類源碼，後臺功能強大，界面美觀，適用於app軟體，手機軟體下載，手游類導航網， 其他行業也可以把數據刪掉，添加自 ...
  • Django筆記二十之手動編寫migration文件
    文章目錄一、前言一、方式1：spring 官方創建 springboot項目1、打開線上的 spring initializr2、選擇項目的語言、版本、依賴等3、 解壓源碼包，並使用IDEA打開4、測試介面二、方式2：社區idea安裝Spring插件1、添加插件三、方式3:（麻煩）手動maven 創 ...
  • 推薦演算法在商城系統實踐
    一、簡介 本文博主給大家講解如何在自己開源的電商項目newbee-mall-pro中應用協同過濾演算法來達到給用戶更好的購物體驗效果。 newbee-mall-pro項目地址: 源碼地址：https://github.com/wayn111/newbee-mall-pro 線上地址：http://12 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類