开发者

golang中slice扩容的具体实现

开发者 https://www.devze.com 2025-05-24 10:50 出处:网络 作者: xsh219
目录1. 切片扩容的触发append 函数的实现2. runtime.growslice 函数growslice 函数源码3. 扩容的具体过程4. 扩容的性能考虑5. 扩容策略的总结6. 示例:切片扩容过程总结Go 语言中的切片扩容机制
目录
  • 1. 切片扩容的触发
    • append 函数的实现
  • 2. runtime.growslice 函数
    • growslice 函数源码
  • 3. 扩容的具体过程
    • 4. 扩容的性能考虑
      • 5. 扩容策略的总结
        • 6. 示例:切片扩容过程
          • 总结

            Go 语言中的切片扩容机制是 Go 运行时的一个关键部分,它确保切片在动态增加元素时能够高效地管理内存。这个机制是在 Go 运行时内部实现的,涉及了内存分配、数据拷贝和容量调整。扩容的实现主要体现在 runtime.growslice 函数中。下面我们将深入分析 Go 切片的扩容机制,结合源码来进行详细解答。

            1. 切片扩容的触发

            切片是 Go 中的一种动态数组,它有 长度(len) 和 容量(cap)。当我们向切片添加元素时,切片的长度会增加。如果长度超出了当前的容量,Go 会自动扩容。切片扩容的过程是通过 append 函数来触发的。

            ap编程客栈pend 函数的实现

            append 函数是 Go 内置的函数,用于向切片追加元素。它的实现会首先检查当前切片的容量是否足够容纳新的元素,如果不够,它会调用 runtime.growslice 函数来扩容。

            // append() 源码简化版
            func append(slice []T, elems ...T) []T {
                // 1. 检查当前切片是否有足够的容量
                if len(slice)+len(elems) <= cap(slice) {
                    // 如果容量足够,直接追加元素
                    slice = slice[:len(slice)+len(elems)]
                    copy(slice[len(slice)-len(elems):], elems)
                    return slice
                }
                // 2. 如果容量不足,进行扩容
                return growslice(reflect.TypeOf(slice).Elem(), slice, len(slice)+len(elems))
            }
            
            编程客栈

            2. runtime.growslice 函数

            当切片容量不足时,append 会调用 growslice 函数来扩容。growslice 函数是 Go 运行时内部函数,负责实际的内存分配和切片扩容操作。

            growslice 函数源码

            // growslice 扩容的实现
            func growslice(et *_type, old slice, cap int) slice {
                if cap < old.cap {
                    panic("growslice: cap out of range")
                }
            
                // 如果元素大小为 0,直接返回新的切片
                if et.size == 0 {
                    return slice{unsafe.Pointer(&zerobase), old.len, cap}
                }
            
                // 扩容策略:根据当前容量和预期的新容量来决定新容量
                newcap := old.cap
                doublecap := newcap + newcap
                if cap > doublecap {
                    newcap = cap
                } else {
                    const threshold = 256
                    if old.cap < threshold {
                        newcap = doublecap
                    } else {
                        for 0 < newcap && newcap < cap {
                            newcap += (newcap + 3*threshold) / 4
                        }
                        if newcap <= 0 {
                            newcap = cap
                        }
                    }
                }
            
                // 根据扩容后的容量计算所需的内存空间
                var lenmem, newlenmem, capmem uintptr
                switch {
                case et.size == 1:
                    lenmem = uintptr(old.len)
                    newlenmem = uintptr(cap)
                    capmem = roundupsize(uintptr(newcap))
                    newcap = int(capmem)
                pythoncase et.size == goarch.PtrSize:
                    lenmem = uintptr(old.len) * goarch.PtrSize
                    newlenmem = uintptr(cap) * goarch.PtrSize
                    capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
                    newcap = int(capmem / goarch.PtrSize)
                case isPowerOfTwo(et.size):
                    var shift uintptr
                    if goarch.PtrSize == 8 {
                        shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
                    } else {
                        shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
                    }
                    lenmem = uintptr(old.len) << sjavascripthift
                    newlenmem = uintptr(cap) << shift
                    capmem = roundupsize(uintptr(newcap) << shift)
                    newcap = int(capmem >> shift)
                default:
                    lenmem = uintptr(old.len) * et.size
                    newlenmem = uintptr(cap) * et.size
                    capmem, _ = math.MulUintptr(et.size, uintptr(newcap))
                    capmem = roundupsize(capmem)
                    newcap = int(capmem / et.size)
                }
            
                // 分配新的内存,并拷贝旧的数据
                var p unsafe.Pointer
                if et.ptrdata == 0 {
                    p = mallocgc(capmem, nil, false)
                } else {
                    p = mallocgc(capmem, et, true)
                }
            
                memmove(p, old.array, lenmem)
                return slice{p, old.len, newcap}
            }
            

            3. 扩容的具体过程

            • 检查容量是否足够: growslice 首先会检查请求的扩容是否超过了当前切片的容量。如果新容量大于原容量的两倍,它会直接使用新容量作为目标容量。

            • 根据扩容策略计算新容量:

              • 如果切片的容量小于 256,它会直接翻倍容量(newcap = cap)。

              •  如果切片容量较大,扩容时会采取逐步增加的策略:按原容量的 1.25 倍+192 (也就是3*threshold / 4) 增长,直到满足目标容量。

            • 计算内存所需大小: growslice 会计算新切片所需的内存大小,并分配新的内存空间。对于不同类型的元素(如基本类型、指针类型等),内存分配的方式会有所不同。

            • 内存分配和数据拷贝:

              • 通过 mallocgc 分配新的内存区域,在分配空间的时候因根据标签的大小等级会向上取整,go在扩容的时候宁愿牺牲一部分内部碎片也要保证外部尽可能少的外部碎片,并使用 memmove 将原切片的数据拷贝到新的内存中。

              • 扩容后的切片会更新 指针(指向新的内存)、长度 和 容量,然后返回新的切片。

            4. 扩容的性能考虑

            切片扩容的过程需要进行 内存分配 和 数据拷贝,这会影响性能,尤其是在频繁扩容的场景中。

            • 频繁扩容的开销:每次扩容时,都会重新分配内存并将数据拷贝到新的内存区域,这会带来额外的时间和空间开销。

            • 容量预估:为了避免频繁扩容,最好在创建切片时预估切片需要的容量,尤其是在元素数量已知的情况下。可以使用 make([]T, 0, n) 来预分配一个足够的容量,以减少扩容操作。

            5. 扩容策略的总结

            • 小容量时(比如容量小于 256),切片会按 2 倍扩容。

            • 大容量时,Go 会使用 javascript;1.25 倍扩容 + 192 的策略,确保不会过度浪费内存。

            • 对于 nil 或零容量切片,growslice 会初始化并分配合适的容量。

            6. 示例:切片扩容过程

            下面是一个示例,展示了切片扩容的过程:

            package main
            
            import "fmt"
            
            func main() {
                var slice []int
                for i := 0; i < 10; i++ {
                    slice = append(slice, i)
                    fmt.Printf("Length: %d, Capacity: %d, Slice: %v\n", len(slice), cap(slice), slice)
                }
            }
            

            输出示例:

            Length: 1, Capacity: 1, Slice: [0]

            Length: 2, Capacity: 2, Slice: [0 1]

            Length: 3, Capacity: 4, Slice: [0 1 2]

            Length: 4, Capacity: 4, Slice: [0 1 2 3]

            Length: 5, Capacity: 8, Slice: [0 1 2 3 4]

            Length: 6, Capacity: 8, Slice: [0 1 2 3 4 5]

            Length: 7, Capacity: 8, Slice: [0 1 2 3 4 5 6]

            Length: 8, Capacity: 8, Slice: [0 1 2 3 4 5 6 7]

            Length: 9, Capacity: 16, Slice: [0 1 2 3 4 5 6 7 8]

            Length: 10, Capacity: 16, Slice: [0 1 2 3 4 5 6 7 8 9]

            如上所示,切片的容量在每次添加元素时会根据扩容策略进行增长。初始容量为 1,当容量不足时,扩容后容量翻倍。最终,容量达到 16。

            总结

            Go 的切片扩容机制是通过 append 函数和 growslice 函数实现的。在扩容时,Go 会根据当前切片的容量和预期的容量进行计算,并分配新的内存空间,拷贝原有数据。扩容的策略通常是小容量时翻倍,大容量时逐步增加,保证了内存的高效使用。

            到此这篇关于golang中slice扩容的具体实现的文章就介绍到这了,更多相关golang slice扩容内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)!

            0

            精彩评论

            暂无评论...
            验证码 换一张
            取 消

            关注公众号