理解 Golang 中 slice 的底层设计

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

Slice 结构体

golang 中的 slice 数据类型,是利用指针指向某个连续片段的数组。
一个 slice 在 golang 中占用24个 bytes

a = make([]int, 0)
unsafe.Sizeof(a)    // 24

var c int
unsafe.Sizeof(c)    // 8, 一个 int 在 golang 中占用 8 个bytes(本机是64位操作系统)

在 runtime 的 slice.go 中,定义了 slice 的 struct

type slice struct {
    array unsafe.Pointer    // 8 bytes
    len   int                // 8 bytes
    cap   int                // 8 bytes
    // 确认了,slice 的大小 24
}
  • array 是指向真实的数组的 ptr
  • len 是指切片已有元素个数
  • cap 是指当前分配的空间

准备调试

简单准备一段程序,看看 golang 是如何初始化一个切片的

package main

import "fmt"

func main() {
    a := make([]int, 0)
    a = append(a, 2, 3, 4)
    fmt.Println(a)
}

Slice 初始化

使用 dlv 调试,反汇编后:

(dlv) disassemble
TEXT main.main(SB) /Users/such/gomodule/runtime/main.go
main.go:5       0x10b70f0       65488b0c2530000000              mov rcx, qword ptr gs:[0x30]
main.go:5       0x10b70f9       488d4424e8                      lea rax, ptr [rsp-0x18]
main.go:5       0x10b70fe       483b4110                        cmp rax, qword ptr [rcx+0x10]
main.go:5       0x10b7102       0f8637010000                    jbe 0x10b723f      main.go:5       0x10b7108*      4881ec98000000                  sub rsp, 0x98
main.go:5       0x10b710f       4889ac2490000000                mov qword ptr [rsp+0x90], rbp
main.go:5       0x10b7117       488dac2490000000                lea rbp, ptr [rsp+0x90]
main.go:6       0x10b711f       488d051a0e0100                  lea rax, ptr [rip+0x10e1a]
main.go:6       0x10b7126       48890424                        mov qword ptr [rsp], rax
main.go:6       0x10b712a       0f57c0                          xorps xmm0, xmm0
main.go:6       0x10b712d       0f11442408                      movups xmmword ptr [rsp+0x8], xmm0
main.go:6       0x10b7132       e8b99af8ff                      ** call $runtime.makeslice **
main.go:6       0x10b7137       488b442418                      mov rax, qword ptr [rsp+0x18]
main.go:6       0x10b713c       4889442460                      mov qword ptr [rsp+0x60], rax
main.go:6       0x10b7141       0f57c0                          xorps xmm0, xmm0
main.go:6       0x10b7144       0f11442468                      movups xmmword ptr [rsp+0x68], xmm0
...

在一堆指令中,看到 call $runtime.makeslice 的调用应该是初始化 slice

func makeslice(et *_type, len, cap int) unsafe.Pointer {
    mem, overflow := math.MulUintptr(et.size, uintptr(cap))
    if overflow || mem > maxAlloc || len < 0 || len > cap {
        // NOTE: Produce a 'len out of range' error instead of a
        // 'cap out of range' error when someone does make([]T, bignumber).
        // 'cap out of range' is true too, but since the cap is only being
        // supplied implicitly, saying len is clearer.
        // See golang.org/issue/4085.
        mem, overflow := math.MulUintptr(et.size, uintptr(len))
        if overflow || mem > maxAlloc || len < 0 {
            panicmakeslicelen()
        }
        panicmakeslicecap()
    }

    return mallocgc(mem, et, true)
}

makeslice 最后返回真正值存储的数组域的内存地址,函数中 uintptr() 是什么呢?

println(uintptr(0), ^uintptr(0))
// 0    18446744073709551615    为什么按位异或后是这个数?

var c int = 1
println(^c, ^uint64(0))
// -2    18446744073709551615

从这几行代码验证,有符号的1,二进制为:0001,异或后:1110,最高位1是负数,表示-2;
uint64二进制:0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
异或后:1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111
因为无符号的,转换成10进制,就是 2 ^ 64 - 1 = 18446744073709551615
。所以,其实^uintptr(0) 就是指当前机器(32位,uint32;64位,uint64)的最大值。
我们可以打印下现在的 a

(dlv) p a
[]int len: 1, cap: 0, [0]

Slice 扩容

=>      main.go:7       0x10b7149       eb00                            jmp 0x10b714b
        main.go:7       0x10b714b       488d0dee0d0100                  lea rcx, ptr [rip+0x10dee]
        main.go:7       0x10b7152       48890c24                        mov qword ptr [rsp], rcx
        main.go:7       0x10b7156       4889442408                      mov qword ptr [rsp+0x8], rax
        main.go:7       0x10b715b       0f57c0                          xorps xmm0, xmm0
        main.go:7       0x10b715e       0f11442410                      movups xmmword ptr [rsp+0x10], xmm0
        main.go:7       0x10b7163       48c744242003000000              mov qword ptr [rsp+0x20], 0x3
        main.go:7       0x10b716c       e84f9bf8ff                      call $runtime.growslice
        main.go:7       0x10b7171       488b442428                      mov rax, qword ptr [rsp+0x28]
        main.go:7       0x10b7176       488b4c2430                      mov rcx, qword ptr [rsp+0x30]
        main.go:7       0x10b717b       488b542438                      mov rdx, qword ptr [rsp+0x38]
        main.go:7       0x10b7180       4883c103                        add rcx, 0x3
        main.go:7       0x10b7184       eb00                            jmp 0x10b7186
        main.go:7       0x10b7186       48c70002000000                  mov qword ptr [rax], 0x2
        main.go:7       0x10b718d       48c7400803000000                mov qword ptr [rax+0x8], 0x3
        main.go:7       0x10b7195       48c7401004000000                mov qword ptr [rax+0x10], 0x4
        main.go:7       0x10b719d       4889442460                      mov qword ptr [rsp+0x60], rax
        main.go:7       0x10b71a2       48894c2468                      mov qword ptr [rsp+0x68], rcx
        main.go:7       0x10b71a7       4889542470                      mov qword 
        ...

在对 slice 做 append 的时候,其实是调用了 call runtime.growslice,看看做了什么:

func growslice(et *_type, old slice, cap int) slice {
    if cap < old.cap {
        panic(errorString("growslice: cap out of range"))
    }

    if et.size == 0 {
        // append should not create a slice with nil pointer but non-zero len.
        // We assume that append doesn't need to preserve old.array in this case.
        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
    // Specialize for common values of et.size.
    // For 1 we don't need any division/multiplication.
    // For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
    // For powers of 2, use a variable shift.
    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.ptrdata == 0 {
        // 申请内存
        p = mallocgc(capmem, nil, false)
        
        // 清除未使用的地址
        memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
    } else {
        p = mallocgc(capmem, et, true)
        if lenmem > 0 && writeBarrier.enabled {
            bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem)
        }
    }
    // 拷贝大小为 lenmem 个btyes,从old.array到p
    memmove(p, old.array, lenmem)

    return slice{p, old.len, newcap}

具体扩容的策略:

  • 如果要申请的容量(cap)大于 2 倍的原容量(old.cap)或者 原容量 < 1024 ,那么newcap = old.cap + old.cap
  • 否则,计算 newcap += newcap / 4,知道 newcap 不小于要申请的容量,如果溢出,newcap = cap(要申请的容量)

扩容完成后就开始根据 t.size 的大小,重新计算地址,其中新 slice 的 len 为原 slice 的 cap (只有 slice 的 len 超过 cap,才需要扩容)。
接着申请 capmem 大小的内存,从 old.array 拷贝 lenmem 个 bytes (就是原 slice 整个拷贝,lenmem 就是计算的原切片的大小)到 p

a := make([]int, 0)
a = append(a, 1)
println("1 times:", len(a), cap(a))    // 1 times: 1 1

a = append(a, 2, 3)
println("2 times:", len(a), cap(a))    // 2 times: 3 4

a = append(a, 4)
println("3 times:", len(a), cap(a))    // 3 times: 4 4

可以看出:

  1. 如果 append 后的 len 大于 cap 的2倍,即扩大至大于 len 的第一个2的倍数
  2. 如果 append 后的 len 大于 cap 且小于 cap 的两倍,cap扩大至2倍
  3. 如果 append 后的 len 小于 cap,直接追加

Slice污染

使用 slice,也许不知不觉中就会造成一些问题。

a := []int{1, 2, 3, 4, 5}
shadow := a[1:3]
shadow = append(shadow, 100)
fmt.Println(shadow, a)
// [2 3 100] [1 2 3 100 5]

结果很意外,但也是符合逻辑。a 的结构体中 array 是指向数组 [1,2,3,4,5]的内存地址,shadow 是指向其中 [2,3] 的内存地址。在向 shadow 增加后,会直接修改真实的数组,间接影响到指向数组的所有切片。所以可以修改上述代码为:

a := []int{1, 2, 3, 4, 5}
shadow := append([]int{}, a[1:3]...)
shadow = append(shadow, 100)
fmt.Println(shadow, a)
// [2 3 100] [1 2 3 4 5]

如果某个函数的返回值,是上述的这种情况 return a[1:3],还会造成 [1,2,3,4,5] 锁占用的内存无法释放。

黑魔法

知道了 slice 本身是指向真实的数组的指针,在 Golang 中提供了 unsafe 来做指针操作。

a := []int{1, 2, 3, 4, 5}
shadow := a[1:3]
shadowPtr := uintptr(unsafe.Pointer(&shadow[0]))
offset := unsafe.Sizeof(int(0))
fmt.Println(*(*int)(unsafe.Pointer(shadowPtr - offset)))    // 1
fmt.Println(*(*int)(unsafe.Pointer(shadowPtr + 2*offset)))    // 4

shadowPtr 是 a 的第1个下标的位置,一个 int 在64位机器上是8 bytes,向前偏移1个 offset,是 a 的第0个下标 1;向后偏移2个 offset,是 a 的第3个下标 4。

并发安全

slice 是非协程安全的数据类型,如果创建多个 goroutineslice 进行并发读写,会造成丢失。看一段代码

package main

import (
    "fmt"
    "sync"
)

func main () {
    a := make([]int, 0)
    var wg sync.WaitGroup
    for i := 0; i < 10000; i++ {
        wg.Add(1)
        go func(i int) {
            a = append(a, i)
            wg.Done()
        }(i)
    }
    wg.Wait()
    fmt.Println(len(a))
}
// 9403 9876 9985 9491 ...

多次执行,每次得到的结果都不一样,总之一定不会是想要的 10000 个。想要解决这个问题,按照协程安全的编程思想来考虑问题,
可以考虑使用 channel 本身的特性(阻塞)来实现安全的并发读写。

func main() {
    a := make([]int, 0)
    buffer := make(chan int)
    go func() {
        for v := range buffer {
            a = append(a, v)
        }
    }()

    var wg sync.WaitGroup
    for i := 0; i < 10000; i++ {
        wg.Add(1)
        go func(i int) {
            buffer <- i
            wg.Done()
        }(i)
    }
    wg.Wait()
    fmt.Println(len(a))
}
// 10000

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

本文来自:Segmentfault

感谢作者:lambert

查看原文:理解 Golang 中 slice 的底层设计

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

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