Go 言語のスライシングがどのように拡張されるかについての簡単な分析

Go 言語のスライシングはどのように拡張されますか? Go言語におけるスライスの展開の仕組みについては以下の記事で紹介していますので、ご参考になれば幸いです。

#Go 言語では、スライスという非常に一般的に使用されるデータ構造があります。

スライスは、同じ型の要素を含む可変長シーケンスであり、配列型に基づいたカプセル化の層です。非常に柔軟性があり、自動拡張をサポートしています。

スライスは、Pointer、Length、Capacity の 3 つのプロパティを持つ参照型です。

基礎となるソース コードは次のように定義されます。

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

1. ポインタ: スライスが作成される最初の要素を指します。にアクセスできます。
2. 長さ: スライス内の要素の数。
3. 容量: スライスの開始要素と基礎となる配列の最後の要素の間の要素の数。

たとえば、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 関数パラメータの長さは可変であり、複数の値があります。値を追加できます。スライスを直接追加します。使い方は比較的簡単です。それぞれ 2 つの例を見てみましょう:

複数の値を追加します:

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]

expansion の例を見てみましょう:

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 番目の要素を追加すると、スライスの長さがその容量を超えます。このとき、スライスは自動的に拡張されます。新しい容量は元の容量の 2 倍 (6) です。

ここまでは表面的な現象を見てきましたが、次にソース コード レベルを深く掘り下げて、スライス拡張メカニズムがどのようなものであるかを見ていきます。

ソース コード分析

Go 言語のソース コードでは、通常、スライスの

append 操作を実行するときにスライス展開がトリガーされます。 append 操作中に、スライスの容量が新しい要素を収容するのに十分でない場合は、スライスを拡張する必要があり、このとき、拡張のために growslice 関数が呼び出されます。

growslice この関数は Go 言語のランタイム パッケージで定義され、その呼び出しはコンパイルされたコードに実装されます。具体的には、append 操作が実行されると、コンパイラはそれを次のようなコードに変換します。

slice = append(slice, elem)

上記のコードでは、スライス容量が新しいものを収容するのに十分でない場合、要素で、

growslice 関数が呼び出され、容量が拡張されます。したがって、growslice 関数の呼び出しは、ソース コード内で明示的に 呼び出されるのではなく、生成されたマシン コード内でコンパイラによって 実装されます。

スライス拡張戦略には go1.18 の前後で異なる 2 つの段階があり、これについては go1.18 のリリース ノートで説明されています。

以下では、go1.17 と go1.18 のバージョンを使用して個別に説明します。まず、テスト コードを実行して、2 つのバージョン間の拡張の違いを直感的に感じてみましょう。

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

上記のコードは、まず空のスライスを作成し、ループ

append で新しい要素を継続的に追加します。

次に、容量の変更を記録します。容量が変更されるたびに、以前の容量、追加された要素、および要素を追加した後の容量を記録します。

このようにして、古いスライスと新しいスライスの容量の変化を観察し、ルールを見つけることができます。

実行結果 (

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，直到新容量大于期望容量；

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

推荐学习：Golang教程

以上がGo 言語のスライシングがどのように拡張されるかについての簡単な分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。