go 基础内容总结三(slice底层分析)

laijh · · 2357 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

切片:可以理解变长数组,也称为动态数组,slice本质上是对一个大数组一段数据的引用
注意:切片是引用传递

slice中比较复杂的就是放入值

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

slice由三部分组成: 指针(指向底层的大数组), len(可用的元素空间), cap(切片的最大容量)

slice的底层实现是一个预分配内存长度为cap的数组,当len超过cap时,底层会重新分配一个块空间,然后将原来的值拷贝过去。

关于扩容原理,我自己测试了很多组append(切片,v1,v2...)与append(切片1,切片2...)的数据,发现和很多博客上说,当小于等于1024时是2倍扩容,大于时是1.25倍扩容有出入,然后就找了关于介绍slice源码中扩容代码的博客。
它的扩容原理:
先分析下源码(源码在runtime包下的slice.go文件中,下面代码是1.12版本的),下面是go的slice实现源码,growslice是append调用的函数

func growslice(et *_type, old slice, cap int) slice {
    if raceenabled {
        callerpc := getcallerpc()
        racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
    }
    if msanenabled {
        msanread(old.array, uintptr(old.len*int(et.size)))
    }

        // 如果新要扩容的容量比原来的容量还要小,这代表要缩容了,那么可以直接报panic了。
    if cap < old.cap {
        panic(errorString("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 {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            if newcap <= 0 {
                newcap = cap
            }
        }
    }

    // 计算新的切片的容量,长度。
    var overflow bool
    var lenmem, newlenmem, capmem uintptr
    switch {
    case et.size == 1:
        lenmem = uintptr(old.len)
        newlenmem = uintptr(cap)
        capmem = roundupsize(uintptr(newcap))
        overflow = uintptr(newcap) > maxAlloc
        newcap = int(capmem)
    case et.size == sys.PtrSize:
        lenmem = uintptr(old.len) * sys.PtrSize
        newlenmem = uintptr(cap) * sys.PtrSize
        capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
        overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
        newcap = int(capmem / sys.PtrSize)
    case isPowerOfTwo(et.size):
        var shift uintptr
        if sys.PtrSize == 8 {
            // Mask shift for better code generation.
            shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
        } else {
            shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
        }
        lenmem = uintptr(old.len) << shift
        newlenmem = uintptr(cap) << shift
        capmem = roundupsize(uintptr(newcap) << shift)
        overflow = uintptr(newcap) > (maxAlloc >> shift)
        newcap = int(capmem >> shift)
    default:
        lenmem = uintptr(old.len) * et.size
        newlenmem = uintptr(cap) * et.size
        capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
        capmem = roundupsize(capmem)
        newcap = int(capmem / et.size)
    }


    // 判断非法的值,保证容量是在增加,并且容量不超过最大容量
    if overflow || capmem > maxAlloc {
        panic(errorString("growslice: cap out of range"))
    }

    var p unsafe.Pointer
    if et.kind&kindNoPointers != 0 {
        // 在老的切片后面继续扩充容量
        p = mallocgc(capmem, nil, false)
        // 先将 P 地址加上新的容量得到新切片容量的地址,然后将新切片容量地址后面的 capmem-newlenmem 个 bytes 这块内存初始化。为之后继续 append() 操作腾出空间。
        memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
    } else {
        // 重新申请新的数组给新切片
        // 重新申请 capmen 这个大的内存地址,并且初始化为0值
        p = mallocgc(capmem, et, true)
        if writeBarrier.enabled {
            bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem)
        }
    }
    // 如果还不能打开写锁,那么只能把 lenmem 大小的 bytes 字节从 old.array 拷贝到 p 的地址处
    memmove(p, old.array, lenmem)
    // 返回最终新切片,容量更新为最新扩容之后的容量
    return slice{p, old.len, newcap}
}

资料参考:
1)Go语言实战笔记(五)| Go 切片
2)Go里面的slice,切片,底层实现
3)深入解析 Go 中 Slice 底层实现
4)Golang slice 源码阅读与分析


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:laijh

查看原文:go 基础内容总结三(slice底层分析)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

2357 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传