Maison > développement back-end > Golang > Une brève analyse de la façon dont le découpage de la langue Go est étendu

Une brève analyse de la façon dont le découpage de la langue Go est étendu

青灯夜游
Libérer: 2023-04-19 19:21:48
avant
921 Les gens l'ont consulté

Comment le découpage linguistique Go s'étend-il ? L'article suivant vous présentera le mécanisme d'expansion des tranches dans le langage Go. J'espère qu'il vous sera utile !

Une brève analyse de la façon dont le découpage de la langue Go est étendu

Dans le langage Go, il existe une structure de données très couramment utilisée, à savoir la tranche.

Une tranche est une séquence de longueur variable avec des éléments du même type. C'est une couche d'encapsulation basée sur le type de tableau. Il est très flexible et prend en charge l'expansion automatique.

Une tranche est un type de référence qui possède trois propriétés : Pointeur, Longueur et Capacité.

Une brève analyse de la façon dont le découpage de la langue Go est étendu

Le code source sous-jacent est défini comme suit :

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}
Copier après la connexion
  1. Pointeur : Pointe vers le premier élément auquel la tranche peut accéder.
  2. Longueur : Le nombre d'éléments dans la tranche.
  3. Capacité : Le nombre d'éléments entre l'élément de départ de la tranche et le dernier élément du tableau sous-jacent.

Par exemple, utilisez make([]byte, 5) pour créer une tranche qui ressemble à ceci : make([]byte, 5) 创建一个切片,它看起来是这样的:

Une brève analyse de la façon dont le découpage de la langue Go est étendu

声明和初始化

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

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
}
Copier après la connexion

扩容时机

当切片的长度超过其容量时,切片会自动扩容。这通常发生在使用 append 函数向切片中添加元素时。

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

需要注意的是,由于扩容会分配新数组并复制元素,因此可能会影响性能。如果你知道要添加多少元素,可以使用 make 函数预先分配足够大的切片来避免频繁扩容。

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

func Append(slice []int, items ...int) []int
Copier après la connexion

append 函数参数长度可变,可以追加多个值,还可以直接追加一个切片。使用起来比较简单,分别看两个例子:

追加多个值:

package main

import "fmt"

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

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

输出结果为:

初始切片: [1 2 3]
追加多个值后的切片: [1 2 3 4 5 6]
Copier après la connexion

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

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)
}
Copier après la connexion

输出结果为:

初始切片: [1 2 3]
追加另一个切片后的切片: [1 2 3 4 5 6]
Copier après la connexion

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

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)
    }
}
Copier après la connexion

输出结果为:

初始状态: 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]
Copier après la connexion

在这个例子中,我们创建了一个长度为 0,容量为 3 的切片。然后,我们使用 append 函数向切片中添加 5 个元素。

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

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

源码分析

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

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

slice = append(slice, elem)
Copier après la connexion

在上述代码中,如果切片容量不足以容纳新的元素,则会调用 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
        }
    }
}
Copier après la connexion

上述代码先创建了一个空的 slice,然后在一个循环里不断往里面 append

Une brève analyse de la façon dont le découpage de la langue Go est étendu

Déclaration et initialisation

L'utilisation du découpage est relativement simple. Voici un exemple. Regardons directement le code.

[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
Copier après la connexion

Minutage d'expansion

Lorsque la longueur de la tranche dépasse sa capacité, la tranche s'agrandit automatiquement. Cela se produit généralement lors de l'ajout d'éléments à une tranche à l'aide de la fonction append.

Lors du développement, le runtime Go alloue un nouveau tableau sous-jacent et copie les éléments de la tranche d'origine dans le nouveau tableau. La tranche d'origine pointera alors vers le nouveau tableau, avec sa longueur et sa capacité mises à jour.

Il convient de noter que puisque

l'expansion alloue de nouveaux tableaux et copie des éléments, cela peut affecter les performances

. Si vous savez combien d'éléments vous souhaitez ajouter, vous pouvez utiliser la fonction make pour pré-allouer une tranche suffisamment grande pour éviter une expansion fréquente. 🎜🎜Ensuite, jetons un œil à la fonction append, avec la signature suivante : 🎜
[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
Copier après la connexion
🎜append La longueur des paramètres de la fonction est variable, et plusieurs valeurs peut être ajouté, ou une tranche peut être ajoutée directement. C'est relativement simple à utiliser. Regardons respectivement deux exemples : 🎜🎜🎜Ajouter plusieurs valeurs : 🎜🎜
// 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}
}
Copier après la connexion
Copier après la connexion
🎜Le résultat de sortie est : 🎜
// 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}
}
Copier après la connexion
Copier après la connexion
🎜Regardons-le directement 🎜Ajouter une tranche : 🎜🎜
capmem = roundupsize(uintptr(newcap) * ptrSize)
newcap = int(capmem / ptrSize)
Copier après la connexion
Copier après la connexion
🎜Le résultat de sortie. est : 🎜rrreee🎜 Regardons un exemple d'🎜expansion🎜 : 🎜rrreee🎜Le résultat de sortie est : 🎜rrreee🎜Dans cet exemple, nous avons créé un fichier d'une longueur de 0 et d'une capacité de 3 de tranches. Nous utilisons ensuite la fonction append pour ajouter 5 éléments à la tranche. 🎜🎜Lorsque nous ajoutons l'élément 4, la longueur de la tranche dépasse sa capacité. À ce moment-là, la tranche s’agrandira automatiquement. La nouvelle capacité est le double de la capacité d'origine, qui est 6. 🎜🎜Nous avons vu le phénomène de surface. Ensuite, nous approfondirons le niveau du code source pour voir à quoi ressemble le mécanisme d'expansion du découpage. 🎜

🎜Analyse du code source🎜

🎜Dans le code source du langage Go, l'expansion des tranches est généralement déclenchée lors de l'exécution de l'opération append du tranche. Lors de l'opération append, si la capacité de la tranche n'est pas suffisante pour accueillir de nouveaux éléments, la tranche doit être développée. À ce moment, la fonction growslice sera appelée pour se développer. la capacité. 🎜🎜growslice La fonction est définie dans le package d'exécution du langage Go, et son appel est implémenté dans le code compilé. Plus précisément, lorsque l'opération append est effectuée, le compilateur la convertira en code similaire au suivant : 🎜rrreee🎜Dans le code ci-dessus, si la capacité de la tranche n'est pas suffisante pour accueillir le nouvel élément, elle sera appelée fonction growslice pour l'expansion. Ainsi, l'appel à la fonction growslice est implémenté par le compilateur dans le code machine généré, plutôt que explicitement appelé dans le code source. 🎜🎜La stratégie d'expansion des tranches comporte deux étapes, qui sont différentes avant et après go1.18. Ceci est expliqué dans les notes de version de go1.18. 🎜🎜J'utiliserai les versions go1.17 et go1.18 pour expliquer séparément ci-dessous. Tout d’abord, passons en revue un morceau de code de test pour ressentir intuitivement la différence d’expansion entre les deux versions. 🎜rrreee🎜Le code ci-dessus crée d'abord une tranche vide, puis y ajoute de nouveaux éléments dans une boucle. 🎜🎜Ensuite, enregistrez le changement de capacité. Chaque fois que la capacité change, enregistrez l'ancienne capacité, les éléments ajoutés et la capacité après avoir ajouté les éléments. 🎜🎜De cette façon, vous pouvez observer les changements de capacité des anciennes et des nouvelles tranches et connaître les règles. 🎜🎜Résultats en cours (🎜version 1.17🎜) : 🎜rrreee🎜Résultats en cours (🎜version 1.18🎜) : 🎜rrreee🎜Vous pouvez toujours voir la différence en fonction des résultats ci-dessus. La stratégie d'expansion spécifique est expliquée ci-dessous en regardant la source. code. 🎜

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}
}
Copier après la connexion
Copier après la connexion

在分配内存空间之前需要先确定新的切片容量,运行时根据切片的当前容量选择不同的策略进行扩容:

  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}
}
Copier après la connexion
Copier après la connexion

和之前版本的区别,主要在扩容阈值,以及这行代码: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)
Copier après la connexion
Copier après la connexion

这个函数的实现就不在这里深入了,先挖一个坑,以后再来补上。

总结

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

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

一、go1.18 之前:

  1. 如果期望容量大于当前容量的两倍就会使用期望容量;
  2. 如果当前切片的长度小于 1024 就会将容量翻倍;
  3. 如果当前切片的长度大于 1024 就会每次增加 25% 的容量,直到新容量大于期望容量;

二、go1.18 之后:

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

以上就是本文的全部内容,如果觉得还不错的话欢迎点赞转发关注,感谢支持。

推荐学习:Golang教程

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Étiquettes associées:
source:juejin.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal