欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

golang slice 源码解读

程序员文章站 2022-08-03 15:46:27
本文从源码角度学习 golang slice 的创建、扩容,深拷贝的实现。 内部数据结构 slice 仅有三个字段,其中array 是保存数据的部分,len 字段为长度,cap 为容量。 通过下面代码可以输出空slice 的大小: 创建 创建一个slice,其实就是分配内存。cap, len 的设置 ......

本文从源码角度学习 golang slice 的创建、扩容,深拷贝的实现。

内部数据结构

slice 仅有三个字段,其中array 是保存数据的部分,len 字段为长度,cap 为容量。

type slice struct {
  array unsafe.pointer  // 数据部分
  len   int          // 长度
  cap   int             // 容量
}

通过下面代码可以输出空slice 的大小:

package main

import "fmt"
import "unsafe"

func main() {
  data := make([]int, 0, 3)

  // 24  len:8, cap:8, array:8
  fmt.println(unsafe.sizeof(data))

    // 我们通过指针的方式,拿到数组内部结构的字段值
  ptr := unsafe.pointer(&data)
  opt := (*[3]int)(ptr)

  // addr, 0, 3
  fmt.println(opt[0], opt[1], opt[2])

    data = append(data, 123)

    fmt.println(unsafe.sizeof(data))

    shallowcopy := data[:1]

    ptr1 := unsafe.pointer(&shallowcopy)

    opt1 := (*[3]int)(ptr1)

    fmt.println(opt1[0])
}

创建

创建一个slice,其实就是分配内存。cap, len 的设置在汇编中完成。

golang 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 {
    mem, overflow := math.muluintptr(et.size, uintptr(len))
    if overflow || mem > maxalloc || len < 0 {
      panicmakeslicelen()
    }
    panicmakeslicecap()
  }

  // 分配内存 
  // 小对象从当前p 的cache中空闲数据中分配
  // 大的对象 (size > 32kb) 直接从heap中分配
  // runtime/malloc.go
  return mallocgc(mem, et, true)
}

append

对于不需要内存扩容的slice,直接数据拷贝即可。

golang slice 源码解读

上面的dx 存放的就是array 指针,ax 是数据的偏移. 将 123 存入数组。
而对于容量不够的情况,就需要对slice 进行扩容。这也是slice 比较关心的地方。 (因为对于大slice,grow slice会影响到内存的分配和执行的效率)

func growslice(et *_type, old slice, cap int) slice {
    // 静态分析, 内存扫描
    // ...

  if cap < old.cap {
    panic(errorstring("growslice: cap out of range"))
  }

    // 如果存储的类型空间为0,  比如说 []struct{}, 数据为空,长度不为空
  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 {
            // 如果原有长度小于1024,那新容量是老容量的2倍
      newcap = doublecap
    } else {
            // 按照原有容量的1/4 增加,直到满足新容量的需要
      for 0 < newcap && newcap < cap {
        newcap += newcap / 4
      }
            // 通过校验newcap 大于0检查容量是否溢出。
      if newcap <= 0 {
        newcap = cap
      }
    }
  }

  var overflow bool
  var lenmem, newlenmem, capmem uintptr
    // 为了加速计算(少用除法,乘法)
    // 对于不同的slice元素大小,选择不同的计算方法
    // 获取需要申请的内存大小。

  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)
        // 清空不需要数据拷贝的部分内存
    memclrnoheappointers(add(p, newlenmem), capmem-newlenmem)
  } else {
    // note: can't use rawmem (which avoids zeroing of memory), because then gc can scan uninitialized memory.
    p = mallocgc(capmem, et, true)
    if writebarrier.enabled {   // gc 相关
      // only shade the pointers in old.array since we know the destination slice p
      // only contains nil pointers because it has been cleared during alloc.
      bulkbarrierprewritesrconly(uintptr(p), uintptr(old.array), lenmem)
    }
  }

    // 数据拷贝
  memmove(p, old.array, lenmem)

  return slice{p, old.len, newcap}
}

切片拷贝 (copy)

切片的浅拷贝

    shallowcopy := data[:1]

    ptr1 := unsafe.pointer(&shallowcopy)

    opt1 := (*[3]int)(ptr1)

    fmt.println(opt1[0])

下面是上述代码的汇编代码:

golang slice 源码解读

上面,先将 data 的成员数据拷贝到寄存器,然后从寄存器拷贝到shallowcopy的对象中。(注意到只是拷贝了指针而已, 所以是浅拷贝)

切片的深拷贝

深拷贝也比较简单,只是做了一次内存的深拷贝。

func slicecopy(to, fm slice, width uintptr) int {
  if fm.len == 0 || to.len == 0 {
    return 0
  }

  n := fm.len
  if to.len < n {
    n = to.len
  }

    // 元素大小为0,则直接返回
  if width == 0 {
    return n
  }

    // 竟态分析和内存扫描
    // ...

  size := uintptr(n) * width
    // 直接内存拷贝
  if size == 1 { // common case worth about 2x to do here
    *(*byte)(to.array) = *(*byte)(fm.array) // known to be a byte pointer
  } else {
    memmove(to.array, fm.array, size)
  }
  return n
}

// 字符串slice的拷贝
func slicestringcopy(to []byte, fm string) int {
  if len(fm) == 0 || len(to) == 0 {
    return 0
  }

  n := len(fm)
  if len(to) < n {
    n = len(to)
  }

    // 竟态分析和内存扫描
    // ...

  memmove(unsafe.pointer(&to[0]), stringstructof(&fm).str, uintptr(n))
  return n
}

其他

  1. 汇编的生成方法
go tool compile -n -s slice.go > slice.s
  1. 需要了解unsafe.pointer 的使用

  2. slice.go 位于 runtime/slice.go

  3. 上述代码使用 go1.12.5 版本

  4. 还有一点需要提醒, type 长度为0的对象。比如说 struct{} 类型。(所以,很多使用chan struct{} 做channel 的传递,节省内存)

package main

import "fmt"
import "unsafe"

func main() {
  var data [100000]struct{}
  var data1 [100000]int

  // 0
  fmt.println(unsafe.sizeof(data))
  // 800000
  fmt.println(unsafe.sizeof(data1))
}

golang slice 源码解读