理解 Golang 中 slice 的底层设计

4,377 阅读8分钟

Slice 结构体

slice 是 golang 中利用指针指向某个连续片段的数组,所以本质上它算是引用类型。 一个 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