Analisis ringkas tentang cara penghirisan bahasa Go dikembangkan

Bagaimanakah penghirisan bahasa Go dikembangkan? Artikel berikut akan memperkenalkan anda kepada mekanisme pengembangan kepingan dalam bahasa Go. Saya harap ia akan membantu anda!

Dalam bahasa Go, terdapat struktur data yang sangat biasa digunakan, iaitu slice.

Kepingan ialah jujukan unsur-unsur yang sama panjangnya daripada jenis yang sama Ia adalah lapisan enkapsulasi berdasarkan jenis tatasusunan. Ia sangat fleksibel dan menyokong pengembangan automatik.

Kepingan ialah jenis rujukan yang mempunyai tiga sifat: Penunjuk, Panjang dan Kapasiti.

Kod sumber asas ditakrifkan seperti berikut:

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

1. Penunjuk: menunjuk ke elemen pertama yang slice boleh mengakses .
2. Panjang: Bilangan unsur dalam kepingan.
3. Kapasiti: Bilangan elemen antara elemen permulaan hirisan dan elemen terakhir tatasusunan asas.

Sebagai contoh, menggunakan make([]byte, 5) untuk mencipta kepingan, ia akan kelihatan seperti ini:

Pengisytiharan dan permulaan

Penggunaan menghiris adalah agak mudah. ​​Ini adalah contoh, lihat sahaja kodnya.

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
}

Masa Pengembangan

Apabila panjang hirisan melebihi kapasitinya, hirisan akan mengembang secara automatik. Ini biasanya berlaku apabila menambah elemen pada kepingan menggunakan fungsi append.

Apabila menskalakan, masa jalan Go memperuntukkan tatasusunan asas baharu dan menyalin elemen daripada kepingan asal ke dalam tatasusunan baharu. Potongan asal kemudiannya akan menunjuk ke tatasusunan baharu, dengan panjang dan kapasitinya dikemas kini.

Perlu diambil perhatian bahawa memandangkan pengembangan akan memperuntukkan tatasusunan baharu dan menyalin elemen, ia mungkin menjejaskan prestasi. Jika anda tahu berapa banyak elemen yang ingin anda tambahkan, anda boleh menggunakan fungsi make untuk pra-peruntukkan hirisan yang cukup besar untuk mengelakkan pengembangan yang kerap.

Mari kita lihat fungsi append, dengan tandatangan berikut:

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

append Parameter fungsi adalah panjang berubah-ubah dan berbilang nilai boleh ditambah , atau sekeping boleh dilampirkan terus. Ia agak mudah untuk digunakan. Mari kita lihat dua contoh masing-masing:

Tambahkan berbilang nilai:

package main

import "fmt"

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

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

Hasil output ialah:

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

Mari kita lihat menambahkan kepingan secara langsung:

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

Hasil keluarannya ialah:

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

Mari lihat contoh pengembangan:

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

Hasil output ialah:

初始状态: 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]

Dalam contoh ini, kami mencipta kepingan dengan panjang 0 dan kapasiti 3. Kami kemudian menggunakan fungsi append untuk menambah elemen 5 pada kepingan.

Apabila kita menambah 4elemen ke-, panjang hirisan melebihi kapasitinya. Pada masa ini, kepingan akan mengembang secara automatik. Kapasiti baharu adalah dua kali ganda kapasiti asal, iaitu 6.

Kami telah melihat fenomena cetek Seterusnya, kami akan pergi jauh ke tahap kod sumber untuk melihat rupa mekanisme pengembangan penghirisan.

Analisis kod sumber

Dalam kod sumber bahasa Go, pengembangan kepingan biasanya dicetuskan apabila melakukan operasi append hirisan. Semasa menjalankan operasi append, jika kapasiti hirisan tidak mencukupi untuk menampung elemen baharu, hirisan perlu dikembangkan Pada masa ini, fungsi growslice akan dipanggil untuk pengembangan.

growslice Fungsi ini ditakrifkan dalam pakej masa jalan bahasa Go dan panggilannya dilaksanakan dalam kod yang disusun. Khususnya, apabila operasi append dilakukan, pengkompil akan menukarnya kepada kod yang serupa dengan yang berikut:

slice = append(slice, elem)

Dalam kod di atas, jika kapasiti kepingan tidak mencukupi untuk menampung elemen baharu, ia akan Memanggil fungsi growslice untuk mengembangkan kapasiti. Jadi panggilan fungsi growslice adalah dilaksanakan oleh pengkompil dalam kod mesin yang dijana, dan bukannya dipanggil secara eksplisit dalam kod sumber.

Strategi pengembangan slice mempunyai dua peringkat, yang berbeza sebelum dan selepas go1.18 Ini dijelaskan dalam nota keluaran go1.18.

Saya akan menggunakan versi go1.17 dan go1.18 untuk menerangkan secara berasingan di bawah. Mula-mula, mari kita lihat sekeping kod ujian untuk merasakan secara intuitif perbezaan pengembangan antara kedua-dua versi.

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

Kod di atas mula-mula mencipta kepingan kosong, dan kemudian terus menambah append elemen baharu padanya dalam gelung.

Kemudian rekodkan perubahan dalam kapasiti Apabila kapasiti berubah, rekodkan kapasiti lama, elemen tambahan dan kapasiti selepas menambah elemen.

Dengan cara ini, anda boleh melihat perubahan kapasiti kepingan lama dan baharu serta mengetahui peraturannya.

Hasil berjalan (versi 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

Hasil berjalan (versi 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

Anda masih boleh melihat perbezaan berdasarkan keputusan di atas Strategi pengembangan khusus akan diterangkan di bawah sambil melihat kod sumber.

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教程

Atas ialah kandungan terperinci Analisis ringkas tentang cara penghirisan bahasa Go dikembangkan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!